From: Parag (parag_at_cs.washington.edu)
Date: Fri Apr 04 2003 - 13:07:18 PST
Paper Title: Fast Planning Through Planning Graph Analysis
Authors: Avrim L. Blum and Merrick L. Furst
The paper introuduces a new planning paradigm which uses
an intermediate structure Planning Graph for exploiting the
constraints inherent in the problem for fast planning in STRIPS
like domains.
The paper introduces a novel algorithm for fast planning in STRIPS like
domains. The algorithm inherits some of the interesting ideas
from the standard total order and partial order planners. But it also
significanly differs from them in the sense that it constructs
a planning graph to exploit the inherent constraints in the problem
thereby reducing the search space by a significant amount. More specifically,
the algorithm identifies the mutual exclusion relation among the nodes
of the graph, thereby helping to reduce the search for a plan drastically
in many cases. Also, it is proved that the size of the planning graph itself
is polynomial in the size of the problem description and the number of time
steps thereby making the algorithm quite attractive for fast planning.
Second important feature is the completeness of the algorithm. In the cases,
where there exists no valid plan, the algorithm is guaranteed to stop
and detect failure to construct a plan thereby avoiding infinite search.
One of the limitations of the paper, in my opinion, is a lack for formal framework
for precisely identifying the kind of problems where the algorithm is guaranteed to
perform efficiently and others where it is not. The authors mention that for the
algorithm to perform well, it requires that either the pairwise mutual exclusion
relations capture the inherent constraints or there is significant scope for parallel
search. They also give mention a case - TSP, where none of these hold. What I would
have expected here is some kind of formal categorization of such problems for which
the technique does not perform that well.
An interesting direction for future research would be examine how one could
use these ideas to fast planning in domains less restrictive than STRIPS
for example domains where the effects of the actions can not be determined
statically.
This archive was generated by hypermail 2.1.6 : Fri Apr 04 2003 - 13:07:19 PST