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

Principles of AI Planning

Wintersemester 2002/2003

Lecturer: Dr. Jussi Rintanen, Exercises: Malte Helmert & Dr. Rintanen

[Lecture] [Exercises] [Bibliography] [Evaluation]

Time and Location

Lectures

Monday 13-15, room SR 00-006, building 051
Wednesday 13-14, room HS 00-006, building 082

Exercises

Wednesday 14-15, room HS 00-006, building 082

Exam

Time: Wednesday, Februrary 12th, 13:15-15:00
Location: Room SR 01-018, building 101
Duration: 105 min

Prerequisites

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)
Hierarchical planning
Conditional planning (nondeterministic, full/partial observability)
Probabilistic conditional planning (nondeterministic, full/partial observability)
Interleaving planning and execution

Recent algorithms and implementation techniques are explained in detail.

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

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.

This is compulsory for ACS students and all other 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 complete lecture notes.

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

Time Table

Day	Topics	Slides	Lecture Notes
October 14th	Introduction: What is AI Planning?	full size (PDF) 4-on-1 (PS)	1. Introduction
October 16th	Background: transition systems, state variables, operators	full size (PDF) 4-on-1 (PS)	2. Background
October 16th	PDDL: The planning domain definition language	full size (PDF) 4-on-1 (PS)	2. Background
October 21st	Progression, regression, plan search	full size (PDF) 4-on-1 (PS)	3. Deterministic planning
October 23rd	Deterministic planning as heuristic search	full size (PDF) 4-on-1 (PS)
October 28th	Distance estimation, symmetry reduction	full size (PDF) 4-on-1 (PS)
October 30th	Invariants, improved distance estimation	full size (PDF) 4-on-1 (PS)
November 4th	Planning in propositional logic: satisfiability planning	full size (PDF) 4-on-1 (PS)
November 6th	Planning in propositional logic: planning with BDDs	full size (PDF) 4-on-1 (PS)
November 11th	Computational complexity of deterministic planning	full size (PDF) 4-on-1 (PS)
November 13th	Nondeterminism and conditional planning	full size (PDF) 4-on-1 (PS)	4. Conditional planning
November 18th	Conditional planning, planning with full observability	full size (PDF) 4-on-1 (PS)
November 20th	Conditional planning, full observability, looping plans	full size (PDF) 4-on-1 (PS)
November 25th	Complexity of conditional planning with full observability	full size (PDF) 4-on-1 (PS)
November 27th	Planning with restrictions on observability	full size (PDF) 4-on-1 (PS)
December 2nd	Planning without observability	full size (PDF) 4-on-1 (PS)
December 4th	Complexity of conditional planning without observability	full size (PDF) 4-on-1 (PS)
December 9th	Planning with partial observability	full size (PDF) 4-on-1 (PS)
December 11th	Complexity of conditional planning with partial observability	full size (PDF) 4-on-1 (PS)
December 16th	Planning in AI robotics	full size (PDF) 4-on-1 (PS)	-
December 18th	Planning in AI robotics II, robocup	full size (PDF) 4-on-1 (PS)	-
January 8th	Probabilistic planning	full size (PDF) 4-on-1 (PS)	5. Probabilistic planning
January 13th	Algorithms for probabilistic planning with full observability	full size (PDF) 4-on-1 (PS)
January 15th	ADDs, implementation of value iteration with ADDs	full size (PDF) 4-on-1 (PS)
January 20th	Reinforcement learning, planning with partial observability	full size (PDF) 4-on-1 (PS)
January 22th	Planning with partial observability: value iteration	full size (PDF) 4-on-1 (PS)
January 27th	Adversarial planning	full size (PDF) 4-on-1 (PS)	-
January 29th	Adversarial planning	full size (PDF) 4-on-1 (PS)	-
February 3rd	Summary	full size (PDF) 4-on-1 (PS)	-
February 5th	Scheduling	full size (PDF) 4-on-1 (PS)	-
February 10th	Scheduling; open research problems in planning	full size (PDF) 4-on-1 (PS)	-

helmert@informatik.uni-freiburg.de, 4. Februar 2003