IJCAI'05 Planning Tutorial by Jussi Rintanen

Planning: Techniques for efficient state-space traversal (IJCAI'05 Tutorial)

Tutorial at the International Joint Conference on Artificial Intelligence

July 30, 2005. Edinburgh, Scotland.

Dr. Jussi Rintanen (Albert-Ludwigs-Universität Freiburg)

Summary

During the last ten years a number of algorithmic breakthroughs have lifted the efficiency of domain-independent planning to the level required in many challenging applications. The tutorial presents the most important approaches to state space traversal as applied in algorithms for classical/deterministic planning and in implementations of algorithms for more general forms of planning, including planning as satisfiability, planning by heuristic state-space search, and logic-based data structures such as binary decision diagrams.

The presentation is based on general and uniform concepts that allow the description of the most central notions in many approaches to planning concisely, and allows seeing the essential differences and similarities between different approaches. Unlike in most of the current research papers which use STRIPS operators, the presentation is based on an expressive language similar to ADL and PDDL used by many recent planner implementations.

Motivation

Planning is a fundamental problem in the behavior of intelligent beings, and is therefore of importance in solving many types of computational problems arising when constructing intelligent agents. The focus of the tutorial is in the algorithmic basis of different forms of state-space traversal which are needed in a wide range of AI planning problems stretching from the simplest forms of deterministic/classical planning to conditional planning and more general forms of multi-agent planning and game-theoretic planning.

To balance the presentation and place the techniques in a wider context, the tutorial also discusses techniques developed outside the AI planning community, and points out connections to computational problems closely related to those addressed by planning, including reachability and model-checking problems in computer aided verification as well as controller synthesis problems.

Target audience

The target audience is the following two groups of IJCAI'05 participants.

AI researchers interested in the state-of-the-art in planning techniques.
The tutorial is intended for the general AI community audience and only assumes basic knowledge in AI and the propositional logic.
Because of the wide applicability of basic planning techniques, applications potentially benefiting from planning technology span a wide range of subfields of AI, and the tutorial provides a basis for assessing the suitability of different planning techniques for specific applications.
Graduate students and researchers working in AI planning.
The approach in presenting the material is new and therefore also of interest to people already working in AI planning. We present the material in a unifying way that makes it easy to see connections between different strands of earlier work and to place earlier results in the big picture.

Contents outline

Introduction
1. A historical timeline
2. Main approaches to state-space traversal
3. Related computational problems
Planning by state-space search
1. Forward and backward search
  1. Progression
  2. Representation of state sets as propositional formulae, regression
  3. Finding plans by heuristic search
2. Reachability: distance heuristics, invariants
  1. Notions of distance in transition graphs
  2. Approximations of distance
  3. Heuristics based on approximate distances and relaxed plans
  4. Computation of invariants
Planning by propositional satisfiability
1. Satisfiability testing
2. Representation of transition relations as propositional formulae
3. Search for plans of length n
4. Parallel plans
Planning by symbolic representations
1. Representations of transition relations as propositional formulae
2. Computation of relational products as formula manipulation
3. Symbolic breadth-first search
4. Specialized representations: binary decision diagrams
Extensions to nondeterministic transitions systems
1. Regression for nondeterministic operators
2. Representation of nondeterministic transition relations as propositional formulae
Conclusions

Course material

Handout (PDF) (J. Rintanen. State-space traversal techniques for planning, Albert-Ludwigs-Universität-Freiburg, Institut für Informatik, Technical Report 220, 76 pages, 2005.)
Tutorial presentation (PDF)
Tutorial presentation (PDF, 8 slides per page)

Literature

Earlier overviews of planning

Subbarao Kambhampati, Recent advances in AI planning: a unifying view, Tutorial at the Sixteenth International Joint Conference on Artificial Intelligence, 1999.

Daniel S. Weld, Recent advances in AI planning, AI Magazine 20(2), 1999,

Planning as satisfiability

Henry Kautz and Bart Selman, Pushing the envelope: planning, propositional logic, and stochastic search, Proceedings of the Thirteenth National Conference on Artificial Intelligence, 1996.

Michael Ernst, Todd Millstein, Daniel S. Weld, Automatic SAT-compilation of planning problems, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI'97), pages 1169-1177, 1997.

Jussi Rintanen, Keijo Heljanko and Ilkka Niemelä, Planning as satisfiability: parallel plans and algorithms for plan search, Artificial Intelligence, 170(12-13), pages 1031-1080, 2006.

Symbolic state-space traversal (BDDs)

J.R. Burch, E.M. Clarke, D.E. Long, K.L. McMillan, D.L. Dill, Symbolic model-checking for sequential circuit verification, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993.

Randall E. Bryant, Symbolic Boolean manipulation with Ordered Binary Decision Diagrams, ACM Computing Surveys, 1992.

R. I. Bahar, E. Frohm, C. Gaona, G. Hachtel, E. Macii, A. Pardo and F. Somenzi, Algebraic decision diagrams and their applications, Proceedings of the International Conference on Computer Aided Design, 1993.

Heuristic state-space search

Blai Bonet and Héctor Geffner, Planning as heuristic search, Artificial Intelligence 129, 2001.