Details

Lecturer(s)

Jörg Hoffmann

Definition

The lecture covers the known methods for Automatic Planning, a sub-field of Artificial Intelligence. The task, which is also relevant in other fields such as Model-Checking, is to automatically solve the ``reachability problem'' in declaratively specified transition systems. Given a set of transition rules, an initial state, and a (non-temporal) goal formula, the reachability problem asks for the existence of a transition sequence that transforms the initial state into a state that satisfies the goal formula. Solving this problem is hard even for very restrictive classes of transition rules and goal formulas. The focus of the lecture lies on the techniques that have most successfully been used to solve the problem efficiently, in Automatic Planning.

Schedule:
Lectures: Wed, 12:00-13:20
Tutorials: Wed, 13:30-14:00
Start Date: October 3rd, 2007

Content:

• Basic Languages for planning, and associated complexity
• Automaticaly generated heuristic functions; local search topology
• Encodings into SAT; clause learning

Evaluation:
The slides will be made available online every Tuesday afternoon preceding the lecture. Students are expected to print the slides and take notes on the slides during the lecture.

A worksheet will be given every week and students are expected to work it out for the next week. Worksheets will be collected and graded. An exam will be given at the end of the semester.

The final grade is assigned as follows: 50% Exercises and 50% Exam

Lecture Slides:

Organization (2x2 for printing)

1. Introduction (2x2 for printing)
2. Planning Formalisms (2x2 for printing)
3. State Space Search Algorithms (2x2 for printing)
4. The "Pattern Database" Relaxation (2x2 for printing)
5. The "k-Subsets" Relaxation (2x2 for printing)
6. The "Monotonicity" Relaxation (2x2 for printing)
7. Planning Systems, and the IPC (2x2 for printing)
8. Local Search Topology (2x2 for printing)
9. SAT and DPLL (2x2 for printing)
10. Planning as Satisfiability (2x2 for printing)
11. Clause Learning (2x2 for printing)

Exercise Sheets:

1. Introduction -- no exercises
2. Planning Formalisms (the Fast-Forward planner is available from here)
3. State Space Search Algorithms
4. The "Pattern Database" Relaxation
5. The "k-Subsets" Relaxation (1st part)
6. The "k-Subsets" Relaxation (2nd part)
7. The "Monotonicity" Relaxation (1st part)
   
8. The "Monotonicity" Relaxation (2nd part)
9. Local Search Topology (1st part)
10. Local Search Topology (2nd part)