From: Nan Li (annli_at_cs.washington.edu)
Date: Fri Apr 11 2003 - 11:06:05 PDT
Planning as Heuristic Search: New Results /B. Bonet, H.Geffner
This paper reviews a heuristic search-based planning algorithm, HSP, and
introduces a reformulation of HSP. It also analyze Graphplan in the view
of heuristic search.
One hightlight of the paper is, of course, the analysis of heursitc
function used in the search. The idea is simple. In HSP, the heuristic
function defined on every state is the cost from this state to the goal
state. Since the computation is forward-chainning, the result depends on
the start state, so for every state, a new computation is needed. This is
the bottleneck of the algorithm. The improvement, then, is focus on
possible recomputaton of states' heuristic value. Very impressively, the
authors solve the problem by amending the H function so little: instead of
computing the cost from a state to the goal value, in HSPr, it computes
the cost from the initial state to this state. So the heuristic value of
each atom state can be computed independently, and any state can be
considered as a conjunction of atomic states. Experiment results show that
this improvement does very well.
A very interesting section of this paper is that the authors compare their
work with a famous planning algorithm, Graphplan, and argue that deep
down, Graphplan is also a heuristic-based search algorithm. I think it is
a brilliant thought to provide a different perspective to evaluate
Graphplan, but the claim is not so convincing that the performance of HSPr
and Graphplan should be close.
The paper is well-organized and easy to read. One unclear part, though, is
the experiment results. Since the four algorithm involved run on different
machines, the absolute running time is less valuable. The authors should
have provided a graph to compare the curves. And very important, the
authors should have described the charecteristic of the tested domains, or
tested the algorithms on more domains, since they consider HSP(r) are
general domain planner.
As seen easily, the performance of HSPr might have been improved even more
if the heuristic function is admissble. So it's definitely an open topic
to find an admissible function. The inadmissibility comes from the
computation of conjunctive states. What if, instead of simply adding each
value together, consider the "distance" between these atom states and
remove the common part from the sum. For example, if we know g(p) is
computed from g(r), so is g(q)(this information can be recorded during the
computation w/out extra cost). Then when computing the heuristic value of
state s=p&q, g(s) is equal to g(p)+g(q)-g(r). It is an admissible
function, yet it provides more information than max(g(p), g(q)).
--
This archive was generated by hypermail 2.1.6 : Fri Apr 11 2003 - 11:06:06 PDT