From: Alexander Yates (ayates_at_cs.washington.edu)
Date: Fri Apr 04 2003 - 12:46:14 PST
Review of "Fast Planning Through Planning Graph Analysis" by Avrim Blum and
Merrick Furst.
This paper describes a way to break the planning problem into two stages,
one that builds a graph representation of the problem and another that
searches the graph for a subgraph that connects the initial conditions to
the goal conditions without violating certain constraints. The graphical
representation and the dissection of the problem into two subproblems lead
to good empirical performance and a variety of innovative techniques that
appear intuitive in light of the new graphical representation.
I think the two most important ideas in the paper are the idea of the
Planning Graph as a representation for the planning problem and the use of
mutual exclusion constraints. The use of planning graphs led to the idea of
finding and propagating mutual exclusion constraints because those
constraints fit intuitively in the graph as edges between nodes. So the use
of planning graphs was important not just for dividing the planning problem
into subproblems, but also for inspiration in coming up with helpful
constraints on the search phase. The mutual exclusion constraints are
important for the speedup they provide in the search phase, with only a
small hit to performance in the construction of the planning graph. Another
important idea was the flexibility to allow parallel actions in the plan,
thus potentially making successful plans much shorter and easier to find.
This idea appeared earlier in partial-order planners, though.
I was a little disappointed by the experimental results section because I
didn't think the comparisons were fair enough to warrant making any
conclusions. As the paper says, GraphPlan was implemented in a faster
language than the other planners, and since all of the curves in their plots
looked roughly exponential, it is conceivable that the entire difference in
performance was just due to some constants resulting from different
languages (except on the Fixit problem). The paper reported other measure
of performance, like the number of actions and goal sets considered, but
they did not or could not report comparable statistics for the other
planners, so they did not mean very much to me.
The authors suggested a number of open research directions that sounded
interesting and important to me, including learning for speedup and symmetry
detection. One that they didn't mention was the use of 3-ary or 4-ary or
higher-ary mutual exclusion constraints to capture more of the domain
constraints in the graph construction phase. These higher-ary constraints
do not fit very naturally into a graph representation, since edges are
inherently binary, but it's possible to "propositionalize" the graph and
include higher arity relations. It might be interesting to see if the use
of these higher arity constraints manage to provide any speedup for
difficult problems.
Alex Yates
This archive was generated by hypermail 2.1.6 : Fri Apr 04 2003 - 12:46:28 PST