ICAPS'08 Tutorial ProgramThe 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.
- Abstraction and abstraction-based heuristics.
- Projections and PDBs: Abstractions with some nice properties.
- Constrained projections: Abstractions with even nicer properties.
- Pattern selection: That difficult detail.
- PDB compression, symbolic representation, etc.
- The Limits: How good can PDBs (and other abstraction-/search-based heuristics) get?
- Towards more flexible (and better!) abstraction heuristics.
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:
- Motivation for first-order planning
First-order classical planning
- Translation of STRIPS and PDDL to first-order action theory
- Regression and constrained forward-search solutions
Probabilistic and decision-theoretic extensions
- First-order Markov decision processes
- Symbolic dynamic programming
Specialized solution techniques
- First-order decision diagrams (FODDs)
- Constraint logic programming (ReBel)
- Approximate linear programming (FOALP)
If time, briefly introduce extensions
- Metric extensions
- Factored first-order probabilistic extensions
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.
- Review of basic graph-search techniques, especially techniques for limited-memory graph search, including frontier search.
- Introduction to external-memory algorithms and I/O complexity analysis.
- Strategies for duplicate-detection in external-memory graph search, including delayed, hash-based, and structured duplicate detection, and integration of these strategies in external-memory versions of breadth-first search, breadth-first heuristic search, and frontier A*.
- Overview of applications of external-memory graph search, including domain-independent action planning.
- Advanced topics, including external-memory pattern-database heuristics and integration of parallelism with external-memory graph search.
- Blai Bonet, Universidad Simon Bolivar, Venezuela