Technical Report No. 220 - Abstract

Jussi Rintanen
State-Space Traversal Techniques for Planning

This report is an overview of state-space traversal techniques used in planning in artificial intelligence. These techniques directly underlie the algorithms for classical (deterministic) planning, and they can also be used in implementing algorithms for more general forms of planning with nondeterministic actions and sensing. The overview first defines the transition system model used in most works of AI planning as well as succinct representations of transition systems in terms of state variables and operators. Then planning by heuristic state-space search is described. Search proceeds either forwards or backwards. Heuristic search algorithms are guided by heuristics that estimate the distances between states. The second approach to state-space traversal is based on testing the satisfiability of propositional formulae. A problem instance and an integer is mapped to a formula that is satisfiable if and only if a plan of the given length exists. The third approach also uses propositional formulae, but considers them as a data structure for representing transition relations and sets of states. Logical operations like conjunction and disjunction respectively correspond to set-theoretic operations of intersection and union. Implementations of this approach typically use binary decision diagrams for representing the formulae.