@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},
}
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.