From: Tal Shaked (tshaked_at_u.washington.edu)
Date: Fri Apr 04 2003 - 09:28:37 PST
“Fast Planning Through Planning Graph Analysis”, Blum, Furst
This paper discusses how to build a planning graph that is then used to
efficiently find plans in STRIPS-like domains. The idea is to construct a
leveled graph alternating between possible propositions and actions that
give a compact (and approximate) representation of achievable goals at
depths of potential plans. Then a search over this graph is likely to
produce a plan more quickly than other techniques.
One of the most important ideas presented is that a planning graph is
relatively easy and quick to construct and that the efficient-to-compute
mutual exclusion links between actions and propositions often encompass many
of the important constraints in the problem which will likely severely limit
the search space. Basically the planning problem is converted to a CSP that
is generally easier to solve.
Another important point is that the planning graph can be used as a
heuristic in the following ways (it takes polynomial time to compute in the
length of the problem description). It is admissible in that it gives a
minimum length for a plan that includes concurrent actions. It also easily
shows when a goal is unattainable.
Perhaps more time could have been devoted to considering the cases in which
GraphPlan does not perform well. As mentioned, when individual actions can
only meet individual goals, then the plan must be at least the length of the
number of goals, and searching through this space can be inefficient. This
was a little unclear, as well as their solution (and how exactly it is used
or scaled to other problems). Somewhat related is that it would be
interesting to get some analysis of the results for graphs 6, 7, 8, and
specifically why GraphPlan seems to grow exponentially in 8, and why it did
not perform significantly better than POCL (what aspects of the domain made
these the cases).
I’m not sure of all the further research done in this area since. A couple
examples are extending GraphPlan to include conditional effects (in the
optional reading), and showing how to apply GraphPlan to temporal planning
domains. More generally, it is interesting to see how to apply the
techniques mentioned to other planning problems that may include incomplete
information, uncertainty, and actions that create objects (the example in
the paper is digging a hole of arbitrary depth), which may lead to an
infinite number of actions (or over continuous arguments). Another possible
area is that some problems will be too big for GraphPlan to solve as
described, so perhaps more sophisticated heuristics can be developed or
extended from the ideas mentioned (i.e. how to view planning graphs as a
relaxed problem).
This archive was generated by hypermail 2.1.6 : Fri Apr 04 2003 - 09:28:40 PST