AAAI'06 Planning Tutorial by Jussi Rintanen
Planning: Techniques for efficient state-space traversal (AAAI'06 Tutorial)
July 16, 2006. Boston, Massachusetts
Dr. Jussi Rintanen (National ICT Australia, Canberra Research Laboratory)
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.
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.
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.
- A historical timeline
- Main approaches to state-space traversal
- Related computational problems
- Planning by state-space search
- Forward and backward search
- Representation of state sets as propositional formulae, regression
- Finding plans by heuristic search
- Reachability: distance heuristics, invariants
- Notions of distance in transition graphs
- Approximations of distance
- Heuristics based on approximate distances and relaxed plans
- Computation of invariants
- Planning by propositional satisfiability
- Satisfiability testing
- Representation of transition relations as propositional formulae
- Search for plans of length n
- Parallel plans
- Planning by symbolic representations
- Representations of transition relations as propositional formulae
- Computation of relational products as formula manipulation
- Symbolic breadth-first search
- Specialized representations: binary decision diagrams
- Extensions to nondeterministic transitions systems
- Regression for nondeterministic operators
- Representation of nondeterministic transition relations as propositional formulae
- 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)
Earlier overviews of planning
Recent advances in AI planning: a unifying view,
Tutorial at the Sixteenth International Joint Conference on Artificial
Daniel S. Weld,
Recent advances in AI planning,
AI Magazine 20(2), 1999,
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,
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,
Heuristic state-space search
Blai Bonet and Héctor Geffner,
Planning as heuristic search,
Artificial Intelligence 129, 2001.
- Leading research groups in AI planning: