From: Krzysztof Gajos (kgajos_at_cs.washington.edu)
Date: Fri Apr 04 2003 - 11:36:12 PST
Fast Planning Through Planning Graph Analysis
by Blum and Furst
This paper presents a fast planning algorithm for STRIPS domains that
uses an intermediate Plan Graph representation to increase its
efficiency.
Graphplan is a novel planning algorithm for STRIPS domains that builds
parial order plans in two stages. First, it creates a Plan Graph -- a
graph that provides a solution to a relaxed planning problem where
actions are allowed to clobber one another. This structure is further
annotated with edges indicating sets of pairwise exclusive actions and
states. Once the Plan Graph is completed, the second stage of the
algorithm is to perform a backward search through the graph to find a
valid partially ordered plan.
A couple of different mechanisms are also provided to quickly detect
situations where no valid plan exists.
Empirical and theoretical results are provided strongly supporting the
claim of superior performance of the algorithm as well as its
correctness.
Interesting further work (perhaps already done) might include adapting
Graphplan to less constrained domains such as resource-bound planning,
etc.
This archive was generated by hypermail 2.1.6 : Fri Apr 04 2003 - 11:36:20 PST