Prerequisites	Introduction to Foundations of Computer Science
Lecturer	Mehrnoosh Sadrzadeh
Degrees	Schedule B2 — Computer Science Schedule B2 — Mathematics and Computer Science Schedule B — MSc in Advanced Computer Science MSc by Research
Term	Hilary Term 2009  (16 lectures)

Overview

The course is addressed to both MSc students (in Mathematics, CS and MFoCS) and third year undergarduate students (in any of the following fields: Maths, CS, Maths and Comp, MMath, and Maths and Philosophy), with an interest in Logic, AI and the dynamics of information in multi-agent systems. It explores and compares various logical approaches to information flows based on the use of modal logics, on formal languages for the specification of knowledge-related features of a system, and on the use of Kripke models (or transition systems), as abstract models for information systems. A range of important mathematical techniques (such as completeness and decidability proofs, definability and expressivity results etc.) and concepts (bisimulation, canonical models, filtration etc.) are introduced and explained. The course presents applications of these notions to the analysis of information update and communication, and of the role of beliefs and belief-changing actions, in the overall dynamics of any "society" of intelligent agents (e.g. the Internet, the market, communicating networks of robots, cryptographic communication between unreliable or adversary agents over un-secure channels etc.). Implementation of these applications are studied by presenting a range of practical theories of agency in Computer Science and focusing on one of them: the Belief-Desire-Intension (BDI) model that uses modal logic to implement rational agents.

Learning outcomes

At the end of the course students are expected to:

• Analyze and model interactive scenarios of multi-agent information systems and reason about them using the formal logics (epistemic, dynamic, temporal).
• Work with theoretical aspects of Kripke models of action and information, such as correspondence theory, isomorphism, and bisimulation.
• Model check dynamic properties of information on the presented Kripke models.
• Deduce dynamic properties of information, using the presented proof system.
• Implement rational agents as program specifications, using the dynamic model of information

Synopsis

Part 1: Multi-modal logics for multi-agent systems(6 lectures)
(1 lecture) Examples of dynamic scenarios of multi-agent systems. The Muddy Children Puzzle. The Coordinated Attack. The Simultaneous Byzantine Agreement. The Surprise Examination Paradox. Games of imperfect information. Cryptographic protocols. Knowledge, belief, common knowledge, distributed knowledge. Evolving knowledge. Belief-changing actions. Rational agents on our personal computers and on the internet.
(3 lectures) Syntax and Semantics of multi-modal logics: Epistemic Logic, Temporal Logic, Dynamic Logic (PDL). Kripke models.
(2 lectures) Validity and Correctness. Correspondence Theory. Isomorphism, Bisimulation and characteristic formulae.

Part 2: Dynamic logics of knowledge for information flow in multi-agent systems(6 lectures)
(2 lectures) Syntax and Semantics of logics of action and knowledge: Temporal Epistemic Logic, Dynamic Epistemic Logic, the logic of public and private announcements. Operations on epistemic programs, epistemic update.
(2 lectures) A Hilbert-Style proof system for Dynamic Epistemic Logic.
(2 lectures) Applications of Dynamic Epistemic Logic to the analysis of information solutions to: epistemic puzzles such as the Muddy Children Puzzle, communication strategies,and cryptographic attacks.

Part 3: Implementing multi-agent systems via modal logic(4 lectures)
(2 lectures) Main theories of agency in Computer Science: Rational (intelligent), Deductive, Reactive, Hybrid, and Cooperative agents
(2 lectures) The Belief-Desire-Intension (BDI) model of rational agents.

 

Reading list

There will be a full set of pdf  slides and  hand outs from the following:

Part 1: Multi-modal logics for multi-agent systems.

• Chapters 1,2,3 of: R. Fagin, J, Halpern, Y. Moses, M. Vardi. Reasoning about Knowledge, MIT Press, 1995.
• Chapter 5 of D. Harel, D. Kozen, J. Tiuryn. Dynamic Logic, The MIT Press, 2000.
• Cahpters 1 to 5 of P. Blackburn, M. de Rijke, Y. Venema. Modal logic, Cambridge University Press, 2001.

Part 2: Dynamic logics of knowledge for information flow in multi-agent systems

• Chapters 4,5,6 of H. van Ditmarsch, W. van der Hoek, B. Kooi. Dynamic Epistemic Logic, Springer, 2007. (The first sections of this book can be used as a concise reference for Part 1.)

Part 3: Implementing multi-agent systems via modal logic

• M. Wooldridge. An Introduction to Multi-agent Systems, John Wiley & Sons, 2002. (slides of a course based on this book are available from http://www.csc.liv.ac.uk/~mjw/pubs/imas/distrib/)

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.