Foundations of Artificial Intelligence (FAI) Group
divider line

Spezialized Lecture: AI 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, Tuesdays 12:15 -- 13:45, and Wednesdays 16:15 -- 17:45. Some slots are used for tutorials on paper exercises (see calendar below). Once every week, there will be office hours for the programming exercises.

The lectures will take place in Building E1 3, HS002. The tutorials and programming workshops will take place either in that same room, or at the FAI offices (Building E1 1, room 3.06). Exact details will be announced in our Moodle system.

The lectures will be given by Dr. Alvaro Torralba and Dr. Cosmina Croitoru. The exercises will be organized by Dr. Cosmina Croitoru, 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 "AI Planning (Winter 2018/2019)"; when prompted, enter key "UDS-PLAN-18".

In case you wonder: Yes, the course is very similar to last winter's Automatic Planning course. We have renamed the course to AI Planning now to make the link to AI more explicit.

Abstract. AI 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 contains many research results from the last decade, close to the current research frontier in planning.

Prerequisites. Ideally, participating students should have successfully completed an introductory course in Artificial Intelligence. However, the course is self-contained and any student with a solid basis in Computer Science -- algorithms, data structures, programming, propositional logic, NP-hardness -- should in principle be able to follow. Prior knowledge about search (the A* algorithm etc) is an advantage. Students who have already passed Automatic Planning in previous years are not allowed to attend the course.

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; the dependencies with other options; and the deadline for submitting your solution if you choose to implement the option. The latter deadlines are also listed in the calendar at the bottom of this page.

The tutorial sessions will be classical tutorials discussing the solutions to the already solved paper exercises.

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, or import some benchmarks in the editor.

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 final grade will be determined based on a combination of your performance in the programming exercises and exam. 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.6*N + 0.4*min(M,110)). 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 110 points in case you got more than 110 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 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 Tue 16.10 1 on 1;4 on 1
Last change: Mon, 22 Oct 2018
2 Planning Formalisms Wed 17.10 1 on 1;4 on 1
Last change: Fri, 16 Nov 2018
1 on 1;4 on 1
Last change: Fri, 16 Nov 2018
3 PDDL Tue 23.10 1 on 1;4 on 1
Last change: Thu, 18 Oct 2018
1 on 1;4 on 1
Last change: Tue, 23 Oct 2018
4 Applications Tue 23.10 1 on 1;4 on 1
Last change: Tue, 23 Oct 2018
1 on 1;4 on 1
Last change: Tue, 23 Oct 2018
5 Causal Graphs Wed 24.10 1 on 1;4 on 1
Last change: Wed, 24 Oct 2018
1 on 1;4 on 1
Last change: Wed, 24 Oct 2018
6 Progression and Regression Wed 24.10;Tue 30.10 1 on 1;4 on 1
Last change: Tue, 23 Oct 2018
1 on 1;4 on 1
Last change: Wed, 31 Oct 2018
7 Heuristic Search Tue 30.10;Wed 31.10 1 on 1;4 on 1
Last change: Mon, 29 Oct 2018
1 on 1;4 on 1
Last change: Wed, 31 Oct 2018
8 Critical Path Heuristics Wed 31.10 1 on 1;4 on 1
Last change: Mon, 29 Oct 2018
1 on 1;4 on 1
Last change: Wed, 31 Oct 2018
9 Delete Relaxation Heuristics Tue 06.11;Wed 07.11 1 on 1;4 on 1
Last change: Mon, 05 Nov 2018
1 on 1;4 on 1
Last change: Wed, 07 Nov 2018
10 Partial Delete Relaxation Tue 13.11;Tue 20.11 1 on 1;4 on 1
Last change: Mon, 12 Nov 2018
1 on 1;4 on 1
Last change: Thu, 22 Nov 2018
11 Abstractions Tue 20.11;Wed 21.11 1 on 1;4 on 1
Last change: Mon, 19 Nov 2018
1 on 1;4 on 1
Last change: Thu, 22 Nov 2018
12 Pattern Database Heuristics Wed 21.11;Tue 27.11 1 on 1;4 on 1
Last change: Fri, 23 Nov 2018
1 on 1;4 on 1
Last change: Mon, 3 Dec 2018
13 Merge-and-Shrink Heuristics Tue 04.12 1 on 1;4 on 1
Last change: Fri, 23 Nov 2018
1 on 1;4 on 1
Last change: Fri, 7 Dec 2018
14 Landmarks Wed 05.12;Tue 11.12 1 on 1;4 on 1
Last change: Fri, 23 Nov 2018
15 Combining Heuristic Functions Tue 11.12;Wed 12.12
16 LP Heuristics Tue 18.12
17 Comparing Heuristic Functions Tue 08.01
18 Partial-Order Reduction Wed 09.01
19 Dominance Pruning Tue 15.01
20 Symmetry Reduction Tue 22.01
21 Planning Systems and the IPC Wed 22.01
22 --- Tue 29.01
23 Exam Preparation Wed 06.02

Course Overview. The following table provides the provisional timing for the course. ATTENTION: Items displayed in red and blue deviate from the regular lecture days/times.

Date Lecturer Chapter(s) / Tutorials Exercise Deadlines
Tue 16.10 Torralba About this course
Wed 17.10 Torralba Planning Formalisms
Tue 23.10 Torralba PDDL; Applications
Wed 24.10 Torralba Causal Graphs; Progression and Regression
Tue 30.10 Torralba Progression and Regression; Heuristic Search Mon 29.10 Deadline: login, groups
Wed 31.10 Torralba Heuristic Search; Critical Path Heuristics Paper Exercise Handout: Sheet 1
Tue 06.11 Torralba Delete Relaxation Heuristics Mon 05.11. Deadline: goal counting
Wed 07.11 Torralba Delete Relaxation Heuristics Deadline: Paper Exercise Sheet 1
Tue 13.11 Torralba Partial Delete Relaxation
Wed 14.11 Croitoru Tutorial 1 Paper Exercise Handout: Sheet 2
Tue 20.11 Torralba Partial Delete Relaxation; Abstractions
Wed 21.11 Torralba Abstractions ; Pattern Database Heuristics Deadline: Paper Exercise Sheet 2
Tue 27.11 Croitoru Pattern Database Heuristics Mon 26.11. Deadline: hmax, hadd
Wed 28.11 Croitoru Tutorial 2
Tue 04.12 Croitoru Merge-and-Shrink Heuristics
Wed 05.12 Croitoru Landmarks Paper Exercise Handout: Sheet 3
Tue 11.12 Torralba Landmarks;Combining Heuristic Functions Mon 10.12. Deadline: h2, hFF
Wed 12.12 Torralba Combining Heuristic Functions Deadline: Paper Exercise Sheet 3
Tue 18.12 Torralba LP Heuristics
Wed 19.12 Torralba, Croitoru Tutorial 3; Christmas Surprise Lecture Paper Exercise Handout: Sheet 4
Christmas Break
Tue 08.01 Torralba Comparing Heuristic Functions Mon 07.01. Deadline: PDBs, MS, RB, EHC
Wed 09.01 Torralba Partial-Order Reduction Deadline: Paper Exercise Sheet 4
Tue 15.01 Torralba Dominance Pruning Mon 14.01. Deadline: LM, HA
Wed 16.01 Croitoru Tutorial 4 Paper Exercise Handout: Sheet 5
Tue 22.01 Torralba Symmetry Reduction Mon 21.01. Deadline: LP Heuristics
Wed 22.01 Torralba Planning Systems and the IPC Deadline: Paper Exercise Sheet 5
Tue 29.01 --- --- Mon 28.01. Deadline: POR, Dominance, LMcut
Wed 30.01 Croitoru Tutorial 5 Thu 31.01. Deadline: Competition
Tue 05.02 Torralba, Croitoru, Gnad, Steinmetz, Fickert Students' Planning Systems Competition
Wed 06.02 Torralba Exam Preparation
Mon 11.02 14:00 – 17:00 Exam