From: Alexander Yates (ayates_at_cs.washington.edu)
Date: Thu Apr 10 2003 - 23:13:27 PDT
Review of "Planning as Heuristic Search: New Results", by Blai Bonet and
Hector Geffner.
This paper tries to revive the paradigm of heuristic search for planning by
describing a method for automatically extracting heuristics from STRIPS
planning problem descriptions and giving a fast algorithm for planning using
these heuristics.
The main contribution of this paper, in combination with the results on HSP,
is to show that heuristic search can compete with some of the best planners
that use other methods. In support of this result it describes a
new-and-improved HSPr that uses a greedy-best-first search in the reverse
direction, non-temporal mutexes for pruning the search space, and a more
efficient heuristic calculation for the regression search that enables
faster node generation during the search. The others also cast Graphplan as
a particular kind of heuristic search as further evidence that heuristic
search is a viable option for planning. The efficient heuristic calculation
is another key innovation in this paper, since the heuristic calculation
made node generation in HSP several orders of magnitude slower than other
planners. While the others don't give explicit numbers anywhere about how
much faster the node generation is in HSPr, they say that its fast enough to
use a systematic (which I took to mean complete) algorithm, instead of
hill-climbing. The trick to the faster heuristic calculation was that the
regression search allowed them to calculate the estimated cost of getting
from the initial state to any proposition, independent of the current search
state. These costs can be computed once, and then the cost of any search
node can be computed very rapidly from them.
I found the experimental results for HSPr unconvincing, mainly because they
showed HSPr greatly outperforming Blackbox on a series of problems where HSP
also mostly outperformed Blackbox, and as the table a few pages before that
showed, Blackbox outperformed HSP in the AIPS competition. Taking these two
tables together, I would say that the authors had only given evidence that
HSPr was effective in one kind of domain.
One obvious aspect of Graphplan and Blackbox that HSP(r) does not have is
the ability to find parallel plans. I would expect that allowing parallel
plans would not only have the potential to speed up search by decreasing the
depth of search, it might also make the "max" heuristic (which is
admissible, as opposed to their "sum" heuristic) more informative because
the search would have the ability to collapse independent subgoals into
simultaneous actions.
Another thing that this paper made me curious about was the effectiveness of
other search algorithms. It would be interesting to see an experimental
comparison of algorithms like A*, IDA*, BFS, and HSPr on a broad range of
problems in order to understand whether the idea of greedy BFS really is a
good idea or not, and if it is, it would be interesting to see an analysis
of why it outperforms A*.
Alex Yates
This archive was generated by hypermail 2.1.6 : Thu Apr 10 2003 - 23:13:44 PDT