Foundations of Artificial Intelligence (FAI) Group
divider line


Spezialized Lecture: Automatic Planning


Organization. The course consists of oral lectures, 3*45 minutes per week (on average, see next), as well as exercises that will be supervised in tutorial groups (45 minutes/week on average).

The course has two weekly slots of 90 minutes each, Mondays 10:15 -- 11:45, and Tuesdays 10:15 -- 11:45. Every second week, the Tuesday slot is used for the tutorial. All lectures and tutorials take place in HS003, Building E1 3.

The lectures will be given by Prof. Dr. Joerg Hoffmann. The tutorials will be given by Dr. Peter Kissmann and Michal Krajnansky.. All lectures and tutorials will be held in English.

If you already used our Moodle pages as part of the AI'13 Core Course, then your account is still valid. Otherwise, go to "Create new account" (you must use a valid email address ending with ".uni-saarland.de"; if you have no such email address, contact Peter Kissmann). Go to "Automatic Planning (Winter 2013/2014)"; when prompted, enter key "UDS-PLAN-13".

In case you wonder: Yes, the course is very similar to last winter's Automatic Planning course; however, it is not identical. Some new recent material will be included, other parts will be shortened to make space.


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, consisting of 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. 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. We intend to accompany the course by programming exercises, that involve implementing (simple versions of) some of the techniques discussed, starting from a baseline 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. We expect this to be interesting and fun for the students, and in light of the work involved in programming we'll allow groups of 3 and give 9 ECTS.

If, however, a large majority of students prefers paper exercises, then we will go with that and give 6 ECTS only. The decision about which exercises to run will be taken based on a vote near the beginning of the term.


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. Precisely, each of the exercises and the exam will yield a maximum of 100 points. 50 points from the exercises are needed for admission to the exam. The final overall points will be determined from either the exam points alone, or from the average of exercise and exam points (0.5*exercises+0.5*exam), whichever one is better. At least 50 overall points are needed to pass the course.


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.


Course Overview and Slides.

Date Chapter(s) / Tutorials
Mon, 14.10.13 About this Course
Tue, 15.10.13 Planning Formalisms
Mon, 21.10.13 PDDL; Applications
Tue, 22.10.13 Causal Graphs; Progression and Regression
Mon, 28.10.13 Progression and Regression; Heuristic Search
Tue, 29.10.13 Heuristic Search; Critical Path Heuristics
Mon, 04.11.13 Delete Relaxation Heuristics
Tue, 05.11.13 Tutorial 1 (PDDL Modeling)
Mon, 11.11.13 Delete Relaxation Heuristics
Tue, 12.11.13 Search Space Surface Analysis
Mon, 18.11.13 Search Space Surface Analysis
Tue, 19.11.13 Tutorial 2 (Simple Heuristics)
Mon, 25.11.13 Beyond the Delete Relaxation
Tue, 26.11.13 Abstractions
Mon, 02.12.13 Abstractions; Pattern Database Heuristics
Tue, 03.12.13 Tutorial 3 (Critical Path Heuristics)
Mon, 09.12.13 Pattern Database Heuristics
Tue, 10.12.13 Merge-and-Shrink Heuristics
Mon, 16.12.13 Christmas Surprise Lecture
Tue, 17.12.13 Tutorial 4 (Delete Relaxation Heuristics)
CHRISTMAS BREAK
Mon, 06.01.14 Landmark Heuristics
Tue, 07.01.14 Landmarks Heuristics; Combining Heuristic Functions
Mon, 13.01.14 Combining Heuristic Functions
Tue, 14.01.14 Tutorial 5 (Pattern Databases)
Mon, 20.01.14 Comparing the Power of Heuristic Functions
Tue, 21.01.14 Planning Systems and the IPC
Mon, 27.01.14 Exam Preparation
Tue, 28.01.14 Tutorial 6 (Competition)
Mon, 03.02.14 Written Exam