From: MAUSAM (mausam_at_cs.washington.edu)
Date: Fri Apr 04 2003 - 11:33:13 PST
Fast Planning Through Planning Graph Analysis
Avrim Blum and Merrick Furst
The paper proposes a new way to solve classical planning problems using a
planning graph construction and then searching through the graph.
Before this all the planners used to do a complete search in either the
state space (total order planners) or in the plan space (partial order
planners) which were extremely slow. This algorithm combines the aspects
of both total-order and partial order planning and searches in provably
polynomial space, which is faster than the previous methods.
Another valuable contribution of this paper is completeness of the
algorithm i.e. the algorithm outputs failure in case the goals are not
achievable. This feature was absent in most of the previous planners.
The algorithm mostly depends on the fact that pairwise mutual exclusion
relations are quite powerful to model legal actions that can be done at a
step. However, this may not be true for many domains. They only mention
one TSP problem and their solution. However, I feel that there should be
more study of other types of information that could be propagated through
the graph.
Answering Stanley's comment of the unfairness of comparing other Lisp
implementations with Graphplan C implementation, the authors themselves
mention that they are comparing more on the way the algorithm behaves with
size of the input rather than with each other, which seems to me as quite
a fair comparison.
It is unclear from the paper, if the problems that are currently solved by
Graphplan are equivalent in size to the real world domains. If not, still
more heuristics and speed ups would be needed to reach that level.
The other most obvious future work would be relaxing the various
assumptions that classical planning assumes and see if the problems can be
solved taking ideas from the planning graph framework. One may also look
at introducing universally quantified effects in the planning domains.
This archive was generated by hypermail 2.1.6 : Fri Apr 04 2003 - 11:33:14 PST