Institutslogo Abteilung Grundlagen der Künstlichen Intelligenz, Institut für Informatik, Universität Freiburg

Principles of AI Planning

Sommersemester 2004

Lecturer: Dr. Jussi Rintanen

[Lecture] [Exercises] [Bibliography]

Time and Location


Monday 14-16, room SR 00-010/14, building 101
Wednesday 14-15, room SR 00-010/14, building 101


Wednesday 15-16, room SR 00-010/14, building 101

Exercise assistant: Michael Brenner


The repeat exam for those students who did not pass the July 28 exam will take place on Wednesday the 13th of October at 2.00pm at lecture hall SR 101-01-013 in building 101 -->.

The examination that took place on Wednesday the 28th of July at 2pm (14:00) in room SR 00-010/14. has been corrected. Scheins may be picked up from the Abteilung KI Sekretariat starting from the 12th of August (assuming that the secretary is not on vacation.)

Students who passed the exam may look up their grade from the following table that depicts the 3rd and 5th digit of the Matrikelnummer followed by the grade. Notice that there are two Matrikelnummers with encoding 17.

If your Matrikelnummer is not on the table you did not pass. We will organize a second exam for those who want to try again. This will most likely be in the end of September or in the beginning of October.

If you want to see your exam paper and find out how the answers were evaluated, visit Dr. Jussi Rintanen on the 30th of August or later.

No Grade


Basic knowledge in AI and propositional logic


The course offers a detailed introduction to the computational techniques that underlie modern planning systems. The following types of planning are presented.

Leading algorithms and implementation techniques are explained in detail.


In addition to attending the lectures, participants of the course are expected to

Lecture Notes

There is no textbook for the course. All the material covered in the lecture will be made available as lecture notes; see the time table below.
You can also download the lecture notes in one file (this also includes the table of contents etc.)

Extra material (not required for the course!) is available on the bibliography page.

Time Table

Day Topics Slides Lecture Notes
April 19 Introduction: What is AI Planning? 1. Introduction
April 21 Reachability; state variables; states; operators (PDF) 2. Preliminaries
April 26 Definition of the planning problem; expressivity; planning by heuristic search (PDF) 3. Deterministic planning
April 28 Distance estimation, PDDL (PDF)
May 3 Regression (definition (simple & general versions), examples) (PDF)
May 5 Regression (correctness) (PDF)
May 10 Planning in the propositional logic (PDF)
May 12 Planning in the propositional logic: parallel plans (PDF)
May 17 Invariants: algorithms, application to regression and satisfiability planning (PDF)
May 19 Matrix multiplication with formulae; BDD-based planning algorithms (PDF) 2. Preliminaries
3. Deterministic planning
May 24 Planning with BDDs (continued); Nondeterminism (PDF) 4. Conditional planning
May 26 Nondeterministic operators (PDF)
June 14 Conditional plans (PDF)
June 16 Algorithms for conditional planning with full observability (PDF)
June 21 Algorithms for conditional planning with full observability; maintenance goals (PDF)
June 23 Probabilistic planning with full observability (PDF) 5. Probabilistic Conditional planning
June 28 Value iteration; Policy iteration (PDF)
June 30 Implementation of value iteration with ADDs (PDF)
July 5 Planning with partial observability; algorithms for unobservable planning (PDF) 4. Conditional planning
July 7 Unobservable planning with QBF (PDF)
July 12 Algorithms for planning with partial observability (PDF)
July 14 Algorithms for planning with partial observability (PDF)
July 19 Algorithms for probabilistic planning with partial observability (POMDPs) (PDF) 5. Probabilistic Conditional planning
July 21 Scheduling (PDF)
Bibliography & Index

Valid HTML 4.01! Valid CSS!, 14. April 2004