PropPlan: background

Adapted from the Plan Compilation Homepage

Traditional AI planners have typically done very little compilation of a planning problem. Recently, several techniques for compiling planning problems have been developed and applied with great success. GraphPlan, the first compiling planner stimulated renewed activity in planning. PropPlan was inspired by GraphPlan, but is an essentially different algorithm, BlackBox and SatPlan compile a planning problem into a propositional theory, any model of which is a valid plan. They then use general-purpose sat solvers to solve the planning problem. HSP automatically generates a heuristic function to bias search using general-purpose search algorithms. STAN, derived from GraphPlan, uses type inferencing methods to further prune the search space. In Planning as Model Checking (PMC), BDD-based model checking techniques are used to compactly represent and efficiently search a finite state automaton compiled from a domain description.

PropPlan belongs to this family. Like GraphPlan, it builds a layered datastructure encoding information about the set of states reachable after some number of action steps. GraphPlan uses an approximate representation of the set of reachable states. PropPlan uses BDDs to represent exactly the sets of reachable states. Like Blackbox and PMC, PropPlan compiles a planning problem to a propositional representation. But, unlike these two, PropPlan does not introduce propositional variables to represent actions.

Related Work

Other researchers have realised that BDDs can be applied to planning, most notably Cimatti, Giunchiglia, Giunchiglia and Traverso, in their Planning as Model-Checking (PMC) approach. PropPlan differs from this approach as noted above. Furthermore, in PropPlan, (generalized) strips operators are represented directly by efficient operations on BDDs in n state variables, rather than, as is traditional in model checking, as abstract transition relations requiring 2n variables. PropPlan is directly comparable with PMC, and it will be instructive to compare the sizes of the BDD representations used by the two systems.

• Alessandro Cimatti, Enrico Giunchiglia, Fausto Giunchiglia, and Paolo Traverso, Planning via Model Checking: A Decision Procedure for AR.
  May 1997. In Proc. of the Fourth European Conference on Planning -- ECP '97, Toulouse, France, 24/25/26 September 1997.
• A. Cimatti, M. Roveri, P. Traverso, Automatic OBDD-based Generation of Universal Plans in Non-Deterministic Domains.
  January 1998. In Proceedings of the Fifteenth National Conference on Artificial Intelligence July 26-30, 1998, Madison, Wisconsin