AI Planning - Overview (2004)
Lecturer: Prof. Dr. Jussi Rintanen
Exercises: Michael Brenner
Time and Location
Lectures
Monday 14-16, room SR 00-010/14, building 101
Wednesday 14-15, room SR 00-010/14, building 101
Exercises
Wednesday 15-16, room SR 00-010/14, building 101
Exam
Wednesday, July 28th, 14-16, room SR 00-010/014, 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.)
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 |