From: Sumit Sanghai (sanghai_at_cs.washington.edu)
Date: Fri Apr 04 2003 - 12:01:37 PST
Fast Planning Through Planning Graph Analysis
--- Avrim Blum and Merrick Furst
Summary :
The paper presents a new algorithm to solve planning problems through the
construction of a plan graph and doing backward chaining on it.
Ideas:
In my opininon, two of the most important ideas presented are the concept
of a planning graph and the mutex relationships between action pairs and
propositions pairs. The graph represents the possible actions and
propositions at each level which can hold. In addition, there is a
ploynomial algorithm which computes this graph alongwith the mutex
relationships (which can be thought of as representing the constraints of
the system). In addition, the algorithm uses parallelization of plans,
uses backward chaining, finds the minimal action set which produces the
goals at each level, is independent of goal ordering, guarantees
termination and is sound and complete.
Flaws:
Although this is due to the lack of any other significant ideas,
theauthors mention that the algorithm performs badly if the mutex
relationships are only minimal and do not capture the constraints.
The problem of computing mutex relationships is mentioned to be NP-hard
but still the fact that once a pair of prositions are not mutually
exclusive at a level, they cannot be mutex at any further lvele seems to
be annoying. Also, there is a tradeoff between producing a larger set of
goals to be satisfied at the previous level and choosing the minimal
action set. It is not clear which direction should be taken depending upon
the graph.
Future Work :
There is a scope for a lot of future work such as improving the way in
which mutex relationships are generated, learning to apply the results
of doing analysis on one graph in similar situations, douing two-way
searches, and using other algorithm such as max-flow.
This archive was generated by hypermail 2.1.6 : Fri Apr 04 2003 - 12:01:38 PST