From: Christophe Bisciglia (chrisrb_at_cs.washington.edu)
Date: Fri Apr 11 2003 - 10:51:14 PDT
B. Bonet and H. Geffner Planning as Search: New Results ECP
This paper shows how a new look at heuristic state space search can
compete with other planners in the STRIPS domain by automatically
generating the heuristic from the state space.
The most important idea in the paper was reversing the direction of the
search. By using a regression search, the algorithm spends much less time
exploring irrelevant actions. In addition to this, HSPr uses a different
mutex definition, and generates it quickly by composing an approximation
of the largest mutex set. Although this is admittedly incomplete, the
paper claimed it caught most mutex relationships, and allowed many nodes
to be pruned.
The other main idea of the paper was how the heuristic was computed. In
HSP, 85% of the time was spent computing the heuristic. In HSPr, the
heuristic is computed once to estimate the cost to the initial state from
the goal, all subsequent heuristic values are defined in terms of this
initial value. This savings in computation, combined with regression
search allows HSPr to explore far more nodes than HSP, and in general come
discover better plans.
The largest flaw in the paper was the experimental results. The feeling
I.m left with is it.s obvious that HSPr (and HSP for that matter)
outperform other planners in the 2 domains tested. but what others. This
makes me wonder if there is something fundamentally different about HSPr
that harms its performance in the more general sense. And if there isn.t
such a difference, why weren.t more domains discussed. The other thing
that didn.t sit well with me were (as others have mentioned) that
GraphPlan is a form of heuristic search. Although some argument was made,
it was far from fully convincing. I feel if they weren.t going to
completely support their claim, it should have been left out.
In my mind, it was clear that the largest open question presented by this
paper was whether or not an admissible heuristic could be found that was
as informative as the one currently in use. If this were possible, it
would open the door to using optimal heuristic search algorithms such as
A* or IDA*.
This archive was generated by hypermail 2.1.6 : Fri Apr 11 2003 - 10:51:15 PDT