Foundations of Artificial Intelligence (FAI) Group
divider line


Spezialized Lecture: Automatic Planning


Organization. The course consists of oral lectures accompanied by programming exercises. Successful participation in the course yields 9 ECTS.

The course has two weekly slots of 90 minutes each, Mondays 10:15 -- 11:45, and Tuesdays 10:15 -- 11:45. Some Tuesdays slots are used for tutorials on paper exercises (see calendar below). There is a programming workshop on Thursday 03.11.16, 14:15--15:45. On every Thursday after that (10.11.16 and so forth) we offer office hours 14:15 -- 15:45 to provide help for the programming exercises.

The lectures take place in Building E1 3, HS003. The tutorials and office hours take place in Building E1 1, room 3.06.

The lectures will be given by Prof. Dr. Joerg Hoffmann and Dr. Alvaro Torralba. The exercises will be organized by Dr. Alvaro Torralba, Maximilian Fickert, Daniel Gnad, and Marcel Steinmetz. All lectures and tutorials will be held in English.

The lecture slides will be made available for download here, i.e., on this web page. By contrast, all exercises material and all interaction -- registration, announcements, technical discussions -- will be available and run through our Moodle pages. Apart from the lecture slide publication, this web page here will remain fixed throughout the course. (For the curious amongst you: the lecture slides will be made available here, as opposed to the Moodle pages, so that people from outside Saarland university can access them as well.)

On our Moodle pages, you can login with your CS department account that you also use to login e.g. to the cloud, GOGS, or possibly other Moodle pages (i.e. your official s9xyabcd username with the new password you got from the CS department). If you have trouble with the login, contact Daniel Gnad). Go to "Automatic Planning (Winter 2016/2017)"; when prompted, enter key "UDS-PLAN-16".

In case you wonder: Yes, the course is very similar (although not identical) to last winter's Automatic Planning course.


Abstract. Automatic Planning is one of the fundamental sub-areas of Artificial Intelligence, concerned with algorithms that can generate strategies of action for arbitrary autonomous agents in arbitrary environments. The course will address so-called classical planning, where the actions and environment are assumed to be deterministic; this is a central area in planning, and has been the source of many influential ideas. It is also successfully applied in practice, as we will exemplify in the course. We will examine the technical core of the current research on solving this kind of problem. We will consider four different paradigms for automatically generating heuristic functions (lower bound solution cost estimators): critical paths, ignoring delete lists, abstractions, landmarks. Apart from understanding these techniques themselves, we will learn how to analyze, combine, and compare such estimators. We will furthermore consider optimality-preserving pruning techniques based on partial-order reduction, symmetries, and dominance pruning. The course consists mostly of research results from the last decade, and is very close to the current research frontier in planning.


Prerequisites. Participants should have successfully completed an introductory course in Artificial Intelligence, and should be familiar specifically with the basics of search (the A* algorithm etc) as well as the basics of logics (propositional formulas etc).


Exercises and ECTS. The course will be accompanied by two kinds of exercises, paper exercises and programming exercises. Each of the two kinds of exercises will be counted separately; each will have a seprate series of exercise sheets. To qualify for the exam, you need to obtain at least 50 points in each, paper exercises and programming exercises. (If you want to participate in future editions of this course, then you need to qualify anew; see also below.)

The paper exercises will involve applying the introduced concepts and algorithms to examples, and leading simple proofs. The paper exercise sheets will be handed out and submitted roughly in a biweekly cycle, i.e., in 2-week intervals. The submission deadline will be stated on each sheet.

The programming exercises will involve implementing some of the techniques discussed, starting from a code base (essentially the Fast Downward planning system, FD, implemented in C++) we will provide. In other words, you will build your own planning system as part of the course! We'll run a competition amongst these systems at the end of term. In light of the work involved in programming, we allow groups of 3 students working together. To further motivate the programming work, good performance in the programming can help you in getting a good exam grade (see below).

Furthermore, in the programming exercises, you will be given the choice of which techniques to implement: Instead of fixed programming tasks on regular sheets, you will obtain a list of programming options up front. Each "option" here is one technique from the course, along with: the number of points obtained by implementing that technique; the time point in the course at which the technique will be explained; and the dependencies with other options.

The tutorial sessions will be classical tutorial discussing the solutions to the already solved paper exercises. For the programming exercises, there will be a programming workshop, introducing the students to the FD code base, on Thursday 03.11.16, 14:15--15:45, in Building E1 1 room 3.06. Later on, the programming exercises will be supported through office hours, i.e., by individual support for the student teams, offered every Thursday at 14:15 -- 15:45 in Building E1 1 room 3.06.

A tip: To get started on the planning modeling language PDDL, a good idea may be to have a look at this archive with example files.


Exam and final grade. There will be a written exam at the end of the course. The final grade will be determined based on the performance in that exam, and the performance in the exercises.

For admission to the exam, you need to get at least 50 points from each of the paper and programming exercises.

The exam grade will be determined based on a combination of your performance in the programming exercises and the paper exercises. Precisely, let N be your number of points in the exam itself, and M be your number of points in the programming exercises. To pass the exam, N>=50 is required. Your grade will be determined from max(N, 0.5*N + 0.5*min(M,100)). In other words, your grade results from either your exam performance, or from the average over exam and programming exercises (the latter being reduced to 100 points in case you got more than 100 points in those exercises).

Depending on the outcome of the 1st exam, there may be a 2nd exam in the first half of April. If so, then, in compliance with the new study regulations each of the two exams will count as a separate attempt to pass the course. In particular, the grading rule for each exam (separately) will be as just explained.

ATTENTION! The re-exam is your only chance to improve your grade.


Course Material. Due to the recency of the material covered, there exists no text book for this course. There are two kinds of slides, pre-handouts and post-handouts. Pre-handouts do not contain the answers to questions asked during the lecture sessions, and do not contain the details for examples worked during the lecture sessions. The post-handouts do contain all this, and correct any bugs. The pre-handouts are made available one day before the lecture sessions on each chapter, the post-handouts are made available directly after the lecture sessions on a chapter are finished.

The following table provides the links to the hand-outs as the course progresses:

Chapter Title Dates Pre-Handouts Post-Handouts
1 About this Course Mon, 24.10.16 (None) 1 on 1, 4 on 1
Last change: Thu, 2.2.17
2 Planning Formalisms Tue, 25.10.16 1 on 1, 4 on 1
Last change: Tue, 25.10.16
1 on 1, 4 on 1
Last change: Mon, 12.12.16
3 PDDL Mon, 31.10.16 1 on 1, 4 on 1
Last change: Mon, 24.10.16
1 on 1, 4 on 1
Last change: Mon, 12.12.16
4 Applications Mon, 31.10.16 1 on 1, 4 on 1
Last change: Mon, 24.10.16
1 on 1, 4 on 1
Last change: Wed, 02.11.16
5 Causal Graphs Wed, 02.11.16 1 on 1, 4 on 1
Last change: Mon, 13.02.17
1 on 1, 4 on 1
Last change: Mon, 13.02.17
6 Progression and Regression Wed, 02.11.16; Mon, 07.11.16 1 on 1, 4 on 1
Last change: Mon, 07.11.16
1 on 1, 4 on 1
Last change: Mon, 07.11.16
7 Heuristic Search Mon, 07.11.16; Tue, 08.11.16 1 on 1, 4 on 1
Last change: Tue, 08.11.16
1 on 1, 4 on 1
Last change: Tue, 08.11.16
8 Critical Path Heuristics Tue, 08.11.16 1 on 1, 4 on 1
Last change: Tue, 08.11.16
1 on 1, 4 on 1
Last change: Mon, 12.12.16
9 Delete Relaxation Heuristics Mon, 14.11.16; Mon, 21.11.16 1 on 1, 4 on 1
Last change: Mon, 21.11.16
1 on 1, 4 on 1
Last change: Mon, 21.11.16
10 Partial Delete Relaxation Tue, 22.11.16; Mon, 28.11.16 1 on 1, 4 on 1
Last change: Mon, 13.02.17
1 on 1, 4 on 1
Last change: Mon, 13.02.17
11 Abstractions Mon, 28.11.16; Mon, 05.12.16 1 on 1, 4 on 1
Last change: Tue, 25.10.16
1 on 1, 4 on 1
Last change: Mon, 05.12.16
12 Pattern Database Heuristics Mon, 05.12.16; Tue, 06.12.16 1 on 1, 4 on 1
Last change: Fri, 02.12.16
1 on 1, 4 on 1
Last change: Tue, 06.12.16
13 Merge-and-Shrink Heuristics Mon, 12.12.16 1 on 1, 4 on 1
Last change: Mon, 13.02.17
1 on 1, 4 on 1
Last change: Mon, Mon, 13.02.17
14 Partial-Order Reduction Tue, 13.12.16 1 on 1, 4 on 1
Last change: Tue, 06.12.16
1 on 1, 4 on 1
Last change: Tue, 13.12.16
15 Dominance Pruning Mon, 19.12.16 1 on 1, 4 on 1
Last change: Wed, 21.12.16
1 on 1, 4 on 1
Last change: Wed, 21.12.16
XX Christmas Surprise Lecture Tue, 20.12.16 (None) 1 on 1, 4 on 1
Last change: Tue, 20.12.16
16 Landmark Heuristics Mon, 09.01.17; Tue, 10.01.17 1 on 1, 4 on 1
Last change: Tue, 10.01.17
1 on 1, 4 on 1
Last change: Tue, 10.01.17
17 Combining Heuristic Functions Tue, 10.01.17; Mon, 16.01.17 1 on 1, 4 on 1
Last change: Mon, 13.02.17
1 on 1, 4 on 1
Last change: Mon, 13.02.17
18 Comparing Heuristic Functions Wed, 01.02.17 1 on 1, 4 on 1
Last change: Wed, 01.02.17
1 on 1, 4 on 1
Last change: Wed, 01.02.17
19 Symmetry Reduction Mon, 23.01.17 1 on 1, 4 on 1
Last change: Fri, 20.01.17
1 on 1, 4 on 1
Last change: Thu, 26.1.17
20 Search Space Surface Analysis Mon, 20.11.17; Tue, 31.01.17 1 on 1, 4 on 1
Last change: Mon, 13.02.17
1 on 1, 4 on 1
Last change: Mon, 13.02.17
21 Planning Systems and the IPC Mon, 06.02.17 (None) 1 on 1, 4 on 1
Last change: Mon, 06.02.17
22 Exam Preparation Mon, 13.02.17 1 on 1, 4 on 1
Last change: Mon, 13.02.17
1 on 1, 4 on 1
Last change: Mon, 13.02.17


Course Overview.

Date Lecturer Chapter(s) / Tutorials
Mon, 24.10.16 Hoffmann About this Course
Tue, 25.10.16 Hoffmann Planning Formalisms
Mon, 31.10.16 Torralba PDDL; Applications
Tue, 01.11.16 Public Holiday
Wed, 02.11.16, 12:15--13:45, HS002 Hoffmann Causal Graphs; Progression and Regression
Thu, 03.11.16, 14:15--15:45, Building E1 1 room 3.06 Programming Workshop: Introduction to the FD Code Base
Mon, 07.11.16 Hoffmann Progression and Regression; Heuristic Search
Tue, 08.11.16 Hoffmann Heuristic Search; Critical Path Heuristics
Mon, 14.11.16 Hoffmann Delete Relaxation Heuristics
Tue, 15.11.16 Tutorial 1
Mon, 21.11.16 Hoffmann Delete Relaxation Heuristics
Tue, 22.11.16 Hoffmann Partial Delete Relaxation
Mon, 28.11.16 Hoffmann; Torralba Partial Delete Relaxation; Abstractions
Tue, 29.11.16 Tutorial 2
Mon, 05.12.16 Torralba Abstractions; Pattern Database Heuristics
Tue, 06.12.16 Torralba Pattern Database Heuristics
Mon, 12.12.16 Hoffmann Merge-and-Shrink Heuristics
Tue, 13.12.16 Hoffmann Partial-Order Reduction
Mon, 19.12.16 Torralba Dominance Pruning
Tue, 20.12.16 Tutorial 3
Tue, 20.12.16, 11:30--13:00, Building E1 1 room 3.06 Christmas Surprise Lecture (includes PIZZA lunch)
CHRISTMAS BREAK
Mon, 09.01.17 Hoffmann Landmark Heuristics
Tue, 10.01.17 Hoffmann; Torralba Landmark Heuristics; Combining Heuristic Functions
Mon, 16.01.17 Torralba Combining Heuristic Functions
Tue, 17.01.17 Torralba Comparing Heuristic Functions
Mon, 23.01.17 Torralba Symmetry Reduction
Tue, 24.01.17 Tutorial 4
Mon, 30.01.17 Hoffmann Search Space Surface Analysis
Tue, 31.01.17 Hoffmann Search Space Surface Analysis
Mon, 06.02.17 Hoffmann Planning Systems and the IPC
Tue, 07.02.17 Tutorial 5
Mon, 13.02.17 Hoffmann Exam Preparation
Tue, 14.02.17 Students' Planning Systems Competition
Thu, 02.03.17, 9:00--11:30, E1 3 HS003 Exam
Mon, 06.03.17, 10:00--12:00 Room 3.06, Building E1 1 Exam Inspection
Tue, 11.04.17, 14:00--16:30, E1 3 HS003 Re-Exam
Thu, 13.04.17, 14:00--16:00 Room 3.06, Building E1 1 Re-Exam Inspection