AI Planning - Overview (2005)

Lecturer: PD Dr. Jussi Rintanen

Assistant: PD Dr. Marco Ragni


Monday 14-16, room SR 01-009/13, building 101
Wednesday 14-15, room SR 01-009/13, building 101


Wednesday 15-16, room SR 01-009/13, 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.)

(Please report errors and inaccuracies in the lecture notes! Points collected by finding errors in the lecture notes count as exercise points!!)

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

Time Table

Day Lecture Handout Lecture notes
April 11 Introduction 8on1 Introduction
April 13 Basic framework: transition systems 8on1 Preliminaries
April 18 Deterministic planning: forward and backward search 8on1 Deterministic planning
April 20 Deterministic planning: continued, regression
April 25 Deterministic planning: planning by heuristic search 8on1
April 27 Deterministic planning: continued, distance heuristics
May 2 Deterministic planning: planning by satisfiability testing 8on1
May 4 Deterministic planning: continued, parallel plans
May 9 Deterministic planning: invariants 8on1
May 11 Deterministic planning: invariants
May 16 Pentecost
May 18 Pentecost
May 23 Deterministic planning: properties 8on1
May 25 Nondeterministic planning: motivation 8on1 Nondeterministic planning
May 30 Nondeterministic planning: algorithms for fully observable problems 8on1
June 1 Nondeterministic planning: implementation with binary decision diagrams
June 6 Nondeterministic planning: looping plans 8on1
June 8 Nondeterministic planning: maintenance problems
June 13 Probabilistic planning: problem definition 8on1 Probabilistic planning
June 15 Nondeterministic planning: algorithms
June 20 Nondeterministic planning: partial observability 8on1 Nondeterministic planning
June 22 Nondeterministic planning: algorithms for unobservable problems
June 27 Nondeterministic planning: QBF, planning with QBF
June 29 Nondeterministic planning: partial observability 8on1
July 4 Nondeterministic planning: partial observability
July 6 Nondeterministic planning: algorithms
July 11 Scheduling: planning vs. scheduling 8on1
July 13 Scheduling: algorithms