From: Christophe Bisciglia (chrisrb_at_cs.washington.edu)
Date: Fri Apr 04 2003 - 12:21:00 PST
Blum/Furst, Fast Planning through Graph Analysis
This paper descripes an efficient means of finding plans in STRIPS domains
by using a plan graph.
Using mutual mutual exclusion relationships to speed up search. GraphPlan
is prevented from searching through an impoosile are of the search space
by flagging nodes (either action or proposition) as mutually exclusive
from one another (either by inference of competing needs), and not using
them to produce the next level of the graph. It is mentioned in the paper
that this process is not perfect, as corectly labeling all nodes could be
as hard as finding a plan. Nevertheless, a large potion of such nodes are
found, hence greatly reducing the search space. The way that these mutex
relationships manage to greatly reduce the search space comes form how the
plan graph is built. The graph is built level by level. Without
considering the mutex relationships, there are many possible actions that
can come from any given set of propositions; this would cause the graph to
grow exponentially, however, GraphPlan prevent this by notice that two
propositions for a given action may be mutually exclusive, and not adding
that action.
Another intersting idea is how the algorithm uses backward chaining to
find the minimal set of actions to produce any goal. This continues until
either a valid plan is found, or the pre-conditions are mutually
exclusive, in which case it goes forward and tries a different path.
What strikes me as a potnetial problem with this paper is its reliance on
detection of mutex relationships, combined with the statement to the
effect of "GraphPlan *usually* does a *pretty good* job of detecting
*most* such relationships." I'm no expert on this, but it seems to me from
what I've read that in those cases that GraphPlan does a particualarly bad
job of detecting realtionships, GraphPlan would perform just as bad as a
state space search.
I would be very curious to discuss how you could take the ideas from
GraphPlan and apply the to problems outside the STRIPS domain, or with not
discrete actions.
This archive was generated by hypermail 2.1.6 : Fri Apr 04 2003 - 12:21:00 PST