Home

Description

This course is about the theory and realisation of so-called intelligent agents, pieces of software that display some degree of autonomy, realised by incorporating `high-level cognitive / mental attitudes' into both modelling and implementation of this kind of software. As such, the subject of intelligent agents is at the cross-roads of the fields of artificial intelligence and mainstream computer science, in particular software engineering. These mental attitudes comprise 'informational' and 'motivational' ones and are often of the so-called BDI kind, dealing with 'beliefs', 'desires' and 'intentions' of agents. The agent concept calls for an integration of several topics in artificial intelligence, such as knowledge representation and reasoning (in particular reasoning about action and change) and planning.
Agent technology, as the field is generally called, has a great potential of applications, ranging from intelligent personal assistants to e-commerce and robotics (where in the latter case often the term 'cognitive robotics' is used).
In the course we will devote much time to the philosophical and theoretical (mostly logical) foundations of the area of intelligent agents, and then go on with describing ways of realising them by special architectures and so-called agent-oriented programming languages in which one can program the 'mental states' of agents. This course presents the introductory theory for the agent-directed courses in the Master programme and gives a background for courses such as MAS and MAP.

Docent / Lecturer

Prof. dr John-Jules Meyer

Literature

Downloadable at the moment:
Agent technology (John-Jules Meyer, Agent Technology, in: Encyclopedia of Computer Science and Engineering, Vol. 1 (B.W. Wah, ed.), Wiley, Hoboken, NJ, 2009, pp.42-49.
Modal Logics for Intelligent Agents (John-Jules Meyer)
BDI Logics (Meyer, Broersen & Herzig)
Intelligent Agents by Michael Wooldridge
Levesque, H.; Pirri, F.; and Reiter, R. 1998. Foundations for the Situation Calculus (only background, no direct material for exam)
3APL paper in JAAMAS (material upto and including section 6.4)
Cohen & Levesque (P.R. Cohen & H.J. Levesque, Intention Is Choice with Commitment, Artificial Intelligence 42, 1990, pp. 213-261.)
Rao & Georgeff (A.S. Rao & M.P. Georgeff, Modeling Rational Agents within a BDI-Architecture, in Proc. KR'91, Morgan Kaufmann, 1991, pp. 473-484.)
KARO 1 (W. van der Hoek, B. van Linder & J.-J. Ch. Meyer, An Integrated Modal Approach to Rational Agents, Report UU-CS-1997-06, UU, 1997; also in: M. Wooldridge & A. Rao (eds.), Foundations of Rational Agents, Applied Logic Series 14, Kluwer, Dordrecht, 1998, pp. 133-168) and KARO 2 (J.-J.Ch. Meyer, W. van der Hoek & B. van Linder, A Logical Approach to the Dynamics of Commitments, CKI Preprint Series No 14, 1999, also in: AI Journal 113, 1999, pp. 1-40) are the basic papers on KARO
Agent-0 (Y. Shoham, Agent-Oriented Programming, Artificial Intelligence 60 (1), 1993, pp. 51-92) (only background, no direct material for exam).

Slides

Slides are downloadable. However, some caution is in order: due to fonts used on my machine printing errors may occur (e.g. deleted or wrong symbols). Unfortunately this is unavoidable. So, always check your prints.
Introduction
HU.example
Philosophy
Modal logic
Modal logic II
Cohen&Levesque Errata:: p 251, Thm 7.2, 3rd line: "INTEND2" -> "INTEND1"; pagina 236, prop 4.2, first part of first clause "p \/ q". should read "p /\ q".
TemporalLogic
CTL, BDI(R&G)
Rao&Georgeff'sBDI(ctd)
KARO (Slides on informational attitudes are not examination material)
SitCalc, Frameproblem, STRIPS (STRIPS IS NOT EXAMINATION MATERIAL)
Regression (Thielscher) (Examination material: upto and including slide 23!!!)
Architectures
AOP, 3APL
3APL(semantics) Erratum: p 14, def 9: in conclusion of transition rule: "\pi" should read "\pi \eta"
example AGENT0 program
example 3APL program

Homework

Regularly homework will be given to enable you to practise with the material and prepare yourself for the examination. This home work will be discussed (partially) during the werkcolleges. It does not give you direct credits for the examination. It is only for necessary practice.

1. Think about the realisability of Asimov's laws of robotics. How difficult are they? What kind of AI techniques are necessary to be able to implement them?
2.(a) Show the validity of the basic property on slide 67, i.e. show that it holds in any world in any Kripke model.
(b) Prove the correspondences of slide 70 in the following sense: show that Kripke models that satisfy the respective conditions on the accessibility relation R make the corresponding modal formula true in any world.
3. Prove Prop 3.15, 3.16, 3.21, 3.22, 3.23, 3.26, 3.28 of Cohen & Levesque formally, using the definiition of the semantics.
4. Prove Prop. 3.8, 3.9, 3.11, 3.13, 4.5 (as precisely as possible). Challenge: does Theorem 7.2 hold for any actions a and e?
5. Prove Prop. 3.8 and 3.9 of Cohen & Levesque again, but now in the framework of (P)LTL (this is much simpler!).
6. Check whether the following formulas are valid in CTL*:
(a) A psi -> E psi (b) E box psi -> A diam psi (c) A diam psi -> E box psi
7. Construct BDI-models Rao & Georgeff-style for the following formulas:
(a) GOAL(optional \Box p)
(b) optional \Diamond inevitable \Box GOAL p
(c) inevitable \Box optional \Diamond GOAL p & ¬(optional \Diamond inevitable \Box GOAL p)
8. (a) Prove the validity of GOAL(alpha) -> BEL(alpha) for alpha = optional(psi) under the B-G condition (see slides).
(b) Prove Theorems 1 and 2 in the article of Rao & Georgeff.
9. Show that in dynamic logic (and so also in KARO) the following holds:
(a) |= [alpha1 ; alpha2] phi <-> [alpha1]([alpha2] phi )
(b) for deterministic alpha: |= <alpha>(phi & psi) <-> ( <alpha>phi & <alpha>psi). Also show that this does not hold for general alpha (that may thus be non-deterministic)!
10. Regarding KARO logic:
(a) Show |= A(alpha1 ; alpha2) <-> A(alpha1) & [alpha1] A(alpha2) under the condition for function C on slide 146.
(b) Show for deterministic, non-failing actions alpha1 and alpha2 the validity of:
Can( alpha1 ; alpha2 , phi ) <-> Can ( alpha1 , PracPoss ( alpha2 , phi ))
(Hint: first show that now it holds also that: A( alpha1; alpha2 ) <-> (A alpha1 & <alpha1> A alpha2).)
(c) Show: |= phi -> psi does NOT imply |= Goal(phi) -> Goal(psi)
(d) Prove the first 3 validities on slide 166 (using the semantics on slide 165).
(e) Compare the logics of Cohen & Levesque, Rao & Georgeff and KARO. What are similarities and differences?
11. Exercises situation calculus and STRIPS planning (downloadable Word document)
12. (a) Prove the Theorem on slide 18 of Thielscher.
(b) Exercise about regression in situation calculus (downloadable Word document)
13. (a) Compare deliberative and reactive agent architectures: what situations call for which architecture?
(b) Discuss the problems occurring when realising a layered hybrid agent architecture, and how to solve these.
(c) Discuss (dis)advantages of horizontally versus vertically layered hybrid agent architectures.
14. Consider the following exercise:
exercise about 3apl (downloadable Word document)

Sample elaborations of homework

Here you can find a couple of elaborated exercises to show how this should be done: 3.15c 8a 10d 12b

Tentamen

There will be a written examination which is ' limited open book' , i.e. only clean (non-annotated) versions of the study material (slides, copies of articles) may be used. HOWEVER THE ELABORATION OF THE HOMEWORK EXERCISES AS PROVIDED AT THE INSTRUCTION HOURS IS NOT ALLOWED!!! A sample exam can be found here .

Extra material

For persons who (think they) do not have sufficient background in (modal) logic (as e.g. been treated in courses like Logic for AI), I recommend to study the first two chapters of the book Meyer & van der Hoek, Epistemic Logic for AI and Computer Science . (This also contains exercises with answers.) By now there is a paperback version of this book, but it should also be available in the library.

File last modified at

Datum	Wijziging

OCTOBER 23, 2012