AI Planning - Overview (2004)

Lecturer: Prof. Dr. Jussi Rintanen

Exercises: Michael Brenner

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


Wednesday, July 28th, 14-16, room SR 00-010/014, building 101.


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.

  • Classical planning (deterministic, full information)
  • Conditional planning (nondeterministic, full/partial observability)
  • Probabilistic conditional planning (nondeterministic, full/partial observability)

Leading algorithms and implementation techniques are explained in detail.

  • Representations of planning in propositional logic and its extensions
  • Planning as satisfiability testing, planning with binary decision diagrams and their extensions
  • Search algorithms, heuristic search, heuristics for planning


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

  • submit weekly exercises and
  • pass an exam at the end of the semester (for ACS students and students who want to obtain a "Schein", which is worth six credit points.)

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