AI Planning - Overview (2005)
Lecturer: Prof. Dr. Jussi Rintanen
Assistant: Prof. Dr. Marco Ragni
Lectures
Monday 14-16, room SR 01-009/13, building 101Wednesday 14-15, room SR 01-009/13, building 101
Exercises
Wednesday 15-16, room SR 01-009/13, building 101
Prerequisites
Basic knowledge in AI and propositional logic
Contents
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
Participation
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 |