ICAPS'08 Tutorial Program

The tutorials will be presented on Sunday and Monday September 14 and 15 (exact schedule to be decided.) The duration of each tutorial will be 4 hours including a coffee break.

ICAPS-TUT1: Abstraction Heuristics for Planning: PDBs and Beyond

Patrik Haslum, Malte Helmert (handout)

Pattern databases (PDBs) were a breakthrough in the automatic construction of admissible heuristics for single-agent search problems. However, PDBs are also an instance of a more general class of heuristics based on computing and storing solutions to an abstraction of the search problem. Both PDBs and other abstraction heuristics have been applied to classical planning, and are probably the currently most effective approach to cost-optimal planning.

This tutorial will describe abstraction-based heuristics in general, and PDBs and their application to planning in particular. It is intended for researchers in planning interested in heuristics, but - we hope - may also be of interest to researchers familiar with PDBs in heuristic search and interested in the particular challenges of applying them to domain-independent planning.

Contents:

ICAPS-TUT2: First-Order Planning Techniques

Scott Sanner, Kristian Kersting (handout)

First-order classical (and probabilistic) planning techniques allow problems stated in (P)STRIPS or (P)PDDL to be solved independently of a particular set of domain objects (e.g., a logistics problem could be solved irrespective of the actual number of trucks, cities, and packages). The key to such approaches is to translate a (P)STRIPS or (P)PDDL problem description to a fully first-order representation and then to generalize standard solution approaches to manipulate an abstracted logical description of the problem in a way that minimally partitions the state and action space. In this tutorial, we provide an introduction to first-order planning techniques for both classical and probabilistic problems and survey recent specialized solution approaches and extensions to this framework.

Audience: Classical, probabilistic and decision-theoretic planning communities

Outline & Goals:

ICAPS-TUT3: Constraint Processing for Planning and Scheduling

Roman Barták (handout)

Constraint satisfaction emerged from AI research and nowadays it contributes to many areas like planning, scheduling, and assignment problems, circuit design, network management and configuration, interactive graphics, molecular biology etc. The tutorial explains major constraint satisfaction algorithms with emphasis put on using constraints in planning and scheduling.

The goal of the tutorial is to explain mainstream constraint satisfaction techniques used in current constraint solvers and to show how these techniques are exploited when solving planning and scheduling problems. The tutorial is divided into two main parts. In the first part the constraint satisfaction technology is explained in general - the mainstream search and inference algorithms are presented. The second part is specialised to planning and scheduling problems. The constraint models of these problems will be described together with several inference and search techniques developed for these models.

The tutorial is targeted to a broad planning and scheduling community, in particular to those who are not familiar with details of constraint satisfaction technology and want to exploit this technology in solving planning and scheduling problems. The audience will take away a basic understanding of how constraints work with more details on problem modelling and special constraint solving techniques for P&S problems (global constraints and search strategies). No prior knowledge of Constraint Programming is required.

ICAPS-TUT4: External-Memory Graph Search

Stefan Edelkamp, Eric Hansen, Shahid Jabbar, Rong Zhou (handout)

Graph-search algorithms such as A* and its variants play an important role in AI planning and problem-solving, as well as in other areas of computer science. Traditionally, their scalability is limited by the amount of RAM available to store generated nodes for use in duplicate detection. However, recent work shows that their scalability can be dramatically improved by using external memory, such as disk, in addition to RAM, although this requires very different search strategies to overcome the six orders-of-magnitude difference in random-access speed between RAM and disk.

This tutorial provides an overview of external-memory graph search strategies and techniques, and discusses how to integrate them in algorithms for planning, scheduling, model checking, and other search problems with very large state spaces. The tutorial is directed at AI researchers interested in graph-search algorithms and their applications. The only prerequisite is familiarity with A* graph search.

Outline:

Tutorial Chair

CFP

Call for Tutorial Proposals