http://www.jimdavies.org/summaries/

@Article{ BlumFurst97, author = {Blum Avrim L. and Furst Merrick L.}, title = {Fast Planning Through Planning Graph Analysis}, journal = {Artificial Intelligence}, year = {1997}, number = {90}, pages = {281-300}, note = {}, url = {http://www.cs.cmu.edu/afs/cs.cmu.edu/user/avrim/www/Papers/planning.ps.gz}, }

- General purpose planning.
- Graphplan planning algorithm.
- Encoding of STRIPS-like problem domain in the form of a planning graph.
- Fast problem construction - build planning graphs in polynomial time and size.
- (Sub)goal memoization for speed and termination purposes.
- Graphplan efficiency is mostly invariant to goal order.

Graphplan functions like a total order planner in
that it makes time committments to all actions that must be specified to
reach a solution. Graphplan functions like a partial order planner
in that its plans only make total order committments at the level

underneath which all actions may be parallelized given some initial
conditions. At this high level, Graphplan guarantees that the shortest
existing plan will be found. Much of graphplan's speed comes from mutually
exclusive relationships between nodes such that the planner can reduce
the search space considerably. It does this by realizing that mutually
exclusive nodes can not appear in the same time interval of a plan.
Graphplan does not locate all such relationships in the graph. Also, some
efficiency is gained by the memoization of (sub)goals results for a particular
action at a given timestep. Further efficiency certainly arises from
the fact that graphplan performs no node instantiations during planning
and after the planning graph was constructed.

Graphplan is proven to be sound an complete: any
plan the algorithm finds is a legal plan, and if there exists a legal plan,
then Graphplan will find one. Given a constructed planning graph,
the algorithm performs backward-chaining to search for a plan. Also,
given a problem with no solution, graphplan will eventually detect cyclic
behavior and terminate. The authors compare their algorithm against other
popular planners like Prodigy and UCOP with great success over these other
popular methods.

This paper introduces a relatively new planning paradigm for STRIPS-like domains called Graphplan. The Graphplan approach is novel because it first formulates the planning problem into a graph search problem. The graph is constructed in such a way that many inherent constraints become obvious and explicitly available to reduce the search space. The planning graphs can be constructed in polynomial size and polynomial time. A distinction should be made between state space graphs which can be exponential in size and planning graphs. In the former the solution is a single path while in the latter the solution is more like a network flow. Combines features from total- and partial-order planners -------------------------------------------------------- Graphplan functions like a total order planner in that it makes time commitments to all actions that must be specified to reach a solution. Graphplan functions like a partial order planner in that its plans only make total order commitments at the level underneath which all actions may be parallelized given some initial conditions. Several actions may be specified to occur at the same time step so long as they do not interfere with each other. More precisely the Planning Graph is a directed leveled graph (i.e. the nodes can be partitioned into disjoint sets L1, L2, ..., Ln such that the edges only connect nodes in adjacent levels.) with two kinds of nodes and three kinds of edges. The levels alternate between proposition levels and action levels. No-op actions are allowed so that propositions can be propagated from level to level even if they are not a direct result of an operator in the previous level. The edges can be * precondition edges * add-edges * delete-edges Exclusion Relations among Planning Graph nodes ----------------------------------------------- Graphplan notices and records mutual exclusion relations by propagating them through the planning graph. Description of the algorithm ---------------------------- Starting with a Planning graph that only has a single level containing the initial conditions, Graphplan runs in stages. In stage i the algorithm takes the planning graph from stage i-1 extends it one time step and then searches the new graph for a solution( valid plan of length i). * Extending Planning Graphs -new action level for each operator and each way of instantiating preconditions of that operator to propositions in the previous level, insert an action node. The above step is performed only if no two of the preconditions are labeled as mutually exclusive. Also insert the no-op actions and add all precondition edges. Check the action nodes for exclusivity and create an "actions-that_I_am_exclusive-of" list for each action. -new proposition level look at the ADD effects of the actions in the previous layer and place them in the next level as propositions. Mark two propositions as exclusive if all ways of generating the first are exclusive of all ways of generating the second. *Searching for a Plan Given a constructed planning graph, the algorithm performs backward-chaining to search for a plan. Unlike other planners it works level by level in order to best utilize the mutual exclusion constraints. Graphplan is proven to be sound an complete: any plan the algorithm finds is a legal plan, and if there exists a legal plan, then Graphplan will find one. Also because it tries to establish the goals in a breadth first manner it is relatively insensitive to the goal ordering. Given a problem with no solution, graphplan can go into a cycle, but some modifications are made to the algorithm to prevent that. Conclusions: ------------ The main contribution is that Graphplan casts the planning problem into a graph search problem. Thus standard graph algorithms can readily be applied. Much of graphplan's speed comes from mutually exclusive relationships between nodes such that the planner can reduce the search space considerably. It does this by realizing that mutually exclusive nodes can not appear in the same time interval of a plan. Graphplan does not locate all such relationships in the graph. Also, some efficiency is gained by the memoization of (sub)goals results for a particular action at a given timestep. Further efficiency certainly arises from the fact that graphplan performs no node instantiations during planning and after the planning graph was constructed. Limitations: ------------ The main limitation is that it works only for STRIPS-like domains. I.e. actions cannon create new objects and the effect of performing an action should be statically determined. A second limitation is that in order to perform well Graphplan requires that either the pairwise mutual exclusion relations capture important constraints of the problem or else the ability to perform parallel actions significantly reduces the depth of the graph. Finally, because Graphplan guarantees that the shortest existing plan will be found it may make its task more difficult. Sometimes non optimal solutions are easier to find. Experiments ----------- The authors compare their algorithm against other popular planners like Prodigy and UCPOP with great success over these other popular methods. The comparison is made on several standard planning domains. Author's notes: --------------- A simple example might help to understand how the graph is constructed. Example: Initial propositions: P,Q Operators: op1: pre P op2: pre Q add R add R delete Q ************* * * - - op1 -----\ * / \ * P - - no-op ---P R * / * / * Q - - op2 ----- * \ * - - no-op --------Q propo- actions propo- sitions time 1 sitions time 1 time2 Where ** is a delete edge.

Back to the Cognitive Science Summaries homepage

Cognitive Science Summaries Webmaster: JimDavies (jim@jimdavies.org)

Last modified: Thu Apr 15 11:07:19 EDT 1999