Foundations of Artificial Intelligence (FAI) Group
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 14:15 -- 15:45. Every second week, the Tuesday slot is used for the tutorial. All lectures and tutorials take place in HS003, Building E1 3. (One exceptional lecture slot will be on Friday, December 19; see course overview below).
The lectures will be given by Prof. Dr. Joerg Hoffmann. The tutorials will be given by Alvaro Torralba, Dr. Peter Kissmann, and Daniel Gnad. 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.)
In case you wonder: Yes, the course is very similar 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, 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. The course will be accompanied by programming exercises, that involve implementing (simple versions of) some of the techniques discussed, starting from a baseline (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. 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.
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.
Tentative Course Overview.
|Date||Chapter(s) / Tutorials|
|Mon, 20.10.14||About this Course|
|Tue, 21.10.14||Planning Formalisms|
|Mon, 27.10.14||PDDL; Applications|
|Tue, 28.10.14||Causal Graphs; Progression and Regression|
|Mon, 03.11.14||Progression and Regression; Heuristic Search|
|Tue, 04.11.14||Heuristic Search; Critical Path Heuristics|
|Mon, 10.11.14||Delete Relaxation Heuristics|
|Tue, 11.11.14||Tutorial 1 (PDDL Modeling)|
|Mon, 17.11.14||Delete Relaxation Heuristics|
|Tue, 18.11.14||Search Space Surface Analysis|
|Mon, 24.11.14||Search Space Surface Analysis|
|Tue, 25.11.14||Tutorial 2 (Simple Heuristics)|
|Mon, 01.12.14||Partial Delete Relaxation|
|Mon, 08.12.14||Abstractions; Pattern Database Heuristics|
|Tue, 09.12.14||Tutorial 3 (Critical Path Heuristics)|
|Mon, 15.12.14||Pattern Database Heuristics|
|Tue, 16.12.14||Merge-and-Shrink Heuristics|
|Fri, 19.12.14, 12:15--13:45||Christmas Surprise Lecture|
|Mon, 12.01.15||Landmark Heuristics|
|Tue, 13.01.15||Tutorial 4 (Delete Relaxation Heuristics)|
|Mon, 19.01.15||Landmark Heuristics; Combining Heuristic Functions|
|Tue, 20.01.15||Combining Heuristic Functions|
|Mon, 26.01.15||Comparing Heuristic Functions|
|Tue, 27.01.15||Planning Systems and the IPC|
|Mon, 02.02.15||Exam Preparation|
|Tue, 03.02.15||Tutorial 5 (Competition)|
|Mon, 09.02.15, 10:00--12:30, HS001||Written Exam|