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.ICAPSTUT1: 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 singleagent 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 costoptimal planning.This tutorial will describe abstractionbased 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 domainindependent planning.
Contents:
 Abstraction and abstractionbased 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/searchbased heuristics) get?
 Towards more flexible (and better!) abstraction heuristics.
ICAPSTUT2: FirstOrder Planning Techniques
Scott Sanner, Kristian Kersting (handout)
Firstorder 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 firstorder 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 firstorder planning techniques for both classical and probabilistic problems and survey recent specialized solution approaches and extensions to this framework.
Audience: Classical, probabilistic and decisiontheoretic planning communities
Outline & Goals:
 Motivation for firstorder planning

Firstorder classical planning
 Translation of STRIPS and PDDL to firstorder action theory
 Regression and constrained forwardsearch solutions

Probabilistic and decisiontheoretic extensions
 Firstorder Markov decision processes
 Symbolic dynamic programming

Specialized solution techniques
 Firstorder decision diagrams (FODDs)
 Constraint logic programming (ReBel)
 Approximate linear programming (FOALP)

If time, briefly introduce extensions
 Metric extensions
 Factored firstorder probabilistic extensions
ICAPSTUT3: 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.
ICAPSTUT4: ExternalMemory Graph Search
Stefan Edelkamp, Eric Hansen, Shahid Jabbar, Rong Zhou (handout)
Graphsearch algorithms such as A* and its variants play an important role in AI planning and problemsolving, 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 ordersofmagnitude difference in randomaccess speed between RAM and disk.
This tutorial provides an overview of externalmemory 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 graphsearch algorithms and their applications. The only prerequisite is familiarity with A* graph search.
Outline:
 Review of basic graphsearch techniques, especially techniques for limitedmemory graph search, including frontier search.
 Introduction to externalmemory algorithms and I/O complexity analysis.
 Strategies for duplicatedetection in externalmemory graph search, including delayed, hashbased, and structured duplicate detection, and integration of these strategies in externalmemory versions of breadthfirst search, breadthfirst heuristic search, and frontier A*.
 Overview of applications of externalmemory graph search, including domainindependent action planning.
 Advanced topics, including externalmemory patterndatabase heuristics and integration of parallelism with externalmemory graph search.
Tutorial Chair
 Blai Bonet, Universidad Simon Bolivar, Venezuela