06-02562 Planning

Manfred Kerber 10 credits in Semester 2

Recommended Books

Title Author(s) Publisher Comments
Automated Planning -- Theory & Practice Malik Ghallab, Dana Nau, Paolo Traverso Elsevier, 2004 Detailed Information
Artificial Intelligence - A Modern Approach Stuart Russell & Peter Norvig Prentice Hall 1995 Further Reading
Artificial Intelligence, 2nd Edition Elaine Rich & Kevin Knight McGraw-Hill 1994 Further Reading
Artificial Intelligence, Third edition Patrick Henry Winston Addison-Wesley 1992 Further Reading

Detailed Syllabus and Relevant Links

The lectures take place Fridays 13:00 - 15:00 in Lecture Room B, Watson Building.

The following lectures are currently planned, modifications are possible: (Slides and Exercises are available in gzipped PostScript files, spare copies can be found in the School's library, these should be taken first in order not to waste printer resources.)

gzipped PostScript slides.ps.gz exercises.ps.gz topics.ps.gz eval.ps.gz
pdf slides.pdf exercises.pdf topics.pdf eval.pdf
txt (no pictures) slides.txt exercises.txt topics.txt eval.txt

A link to the allocated talks can be found locally here.

The module has two components. In the first, the basic knowledge about planning is presented in a mixture of conventional lectures and exercise classes (together 2 hours per week throughout that part of the module). In the second, each student gives a presentation of a research paper.


The module will be assessed to 80% by a 2-hour unseen examination in May (on the material of the first component) and to 20% on the basis of the preparation and the presentation of a seminar. Presence of all participants is obligatory for this part of the module.

Week Lectures
1 Basic notions of planning (Goals, Blocks world, Deductive Planning) Frame Problem, frame axioms (tractability), planning as search (breadth-first search, depth-first search, heuristic search),
Slides: html, txt, gzipped PostScript, pdf
2 Planning with STRIPS, Representation, Search, Limits (interaction of partial goals, unsolvable problems),
Slides: html, txt, gzipped PostScript, pdf
3 MEASG (Planning for simultaneous goals Solution to the so-called Sussman anomaly), Planning as Satisfiability,
Slides: html, txt, gzipped PostScript, pdf
4 Non-Linear Planning (basic idea and notions, classification and solution of conflicts, critics), Linear vs. non-linear planning,
Slides: html, txt, gzipped PostScript, pdf
5 Graphplan,
Slides: html, txt, gzipped PostScript, pdf
6 Hierarchical Planning (Planning with abstraction of situations, Planning with abstraction of operators),
Slides: html, txt, gzipped PostScript, pdf
7 Hierarchical Task Networks,
Slides: html, txt, gzipped PostScript, pdf
8 Increasing the Flexibility in Planning, Conditional Planning, Constraints,
Slides: html, txt, gzipped PostScript, pdf
9 Reactivity vs Deliberation, Distributed Planning, Multi-agent planning,
Slides: html, txt, gzipped PostScript, pdf
10 Student presentations
11 Student presentations

Richard Dearden has been so kind to make the slides of his talk on Planning with Uncertainty in Continuous Domains in the Departmental Seminar of 1 October 2004 available here in the formats pdf and ppt.

You can find some Pop11 programs on general search and STRIPS in the following table. Furthermore there are two examples with OTTER input to demonstrate the idea of the situation calculus.

Topic Program Fragment
General Search (without loopcheck)search.p
General Search (with loopcheck)search-w-loopcheck.p
Problem description of the kitchen problemkitchen.p
Otter Example (without frame axioms)otter1.in otter1.out
Otter Example (with frame axioms)otter2.in otter2.out

You can find past exam papers as follows

gzipped PostScript Exam98.ps.gz Exam00.ps.gz Exam03.ps.gz Exam04.ps.gz
pdf Exam98.pdf Exam00.pdf Exam03.pdf Exam04.pdf

Maintained by: Manfred Kerber, School of Computer Science, The University of Birmingham
Last update: 12.11.2004