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)
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.
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.
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.
- 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, 8 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,
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.