AAAI'06 Planning Tutorial by Jussi Rintanen

Planning: Techniques for efficient state-space traversal (AAAI'06 Tutorial)

Tutorial at the National Conference on Artificial Intelligence

July 16, 2006. Boston, Massachusetts

Dr. Jussi Rintanen (National ICT Australia, Canberra Research Laboratory)

Summary

During the last decade a number of breakthroughs have lifted the efficiency of domain-independent planning to a level required in many challenging applications. This tutorial presents the most important approaches to state space traversal used in planning, including techniques based on propositional satisfiability testing, heuristic state-space search, and logic-based data structures like binary decision diagrams. The main applications of these techniques in classical planning and in more complex forms of planning, including planning with uncertainty and incomplete information, are explained.

Rintanen's presentation is based on general and uniform concepts that allow the description of the most central notions in planning concisely, and makes the essential differences and similarities between the different approaches more apparent. Unlike in most research papers, which use restricted STRIPS operators, the presentation uses an expressive language similar to ADL/PDDL that is used by many recent planner implementations. As a prerequisite to attending the tutorial, only basic knowledge of the classical propositional logic and search algorithms is assumed.

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.

Target audience

The target audience is the following two groups of AAAI'06 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, 4 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,

Jussi Rintanen, course on AI planning, Albert-Ludwigs-Universität Freiburg, 2005. [Includes detailed material on many important topics]

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.

Other resources

Leading research groups in AI planning: