From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Thu Apr 10 2003 - 23:19:45 PDT
Planning as Heuristic Search: New Results
Blai Bonet and Hector Geffner
This paper describes incorporates heuristic-guided greedy search and
Graphplan-style mutexes in a competative Heuristic Search Planner.
The (two) most important ideas in the paper, and why:
The authors acknowledge that one of Graphplan's strengths comes from the
fact that its use of mutexes allows it to ignore many useless regions of
the search space, speeding planning. They incorporate a mutex-finding
strategy which is similar in intent, but quite different in
implementation.
HSPr provides an improvement over vanilla Heuristic Search Planners by not
requiring that the heuristic value of a node is recomputed. Instead, the
values of the function at each node are cached, saving up to 85% of the
computation time.
The one or two largest flaws in the paper:
HSPr does not directly compute mutex pairs, but instead uses an approach
to find "most" of them. There is no discussion or summary of what
percentage of mutexes are found, which would be helpful. This also
suggests a class of problems for which HSPr would perform poorly: Simply
create a problem where a large proportion of mutexes are not found by this
algorithm.
The authors admit that memory consumption is a problem with this
algorithm. It is not clear if this problem affects HSPr more that
Graphplan or SATplan or other similar planners, nor do they discuss how
this may be fixed. Also, they don't describe what parts of the algorithm
are responsible for the excess memory usage.
Identify two important, open research questions on the topic,
and why they matter:
HSPr currently uses what amounts to a shortest-path heuristic. The
authors point out that this heuristic is inadmissible, but in most cases
works well. They also propose an admissible heuristic, which is much less
informative. One could spend extra effort finding better, more
informative, admissible heuristics, or perhaps finding ways to combine
multiple, easy-to-compute heuristics into a single, informative and
admissible heuristic. Perhaps this can be done by ignoring most of the
delete-lists, instead of ignoring all of them?
The authors do not directly all mutexes in HSPr, rather, they quickly
produce many of the mutexes in the problem. This is essentially a point
in the space of trade-offs between speed in computing the mutex set, and
how much of the true mutex set is recovered. One could try to find a
better strategy for finding mutexes, either taking a similar amount of
computation time but finding more mutexes, or taking significantly more
time but finding far more mutexes.
This archive was generated by hypermail 2.1.6 : Thu Apr 10 2003 - 23:20:35 PDT