From: Krzysztof Gajos (kgajos_at_cs.washington.edu)
Date: Fri Apr 11 2003 - 09:26:21 PDT
Planning as Heuristic Search: New Results
by B. Bonet and H. Geffner
This paper presents a second generation of a planner based on
heuristic search.
This paper opens by presenting the first incarnation of the heuristic
search planner (HSP)and summarizing its relative strengths and
weaknesses compared to the other state of the art planners such as
Graphplan and Satplan. HSP was found to produce valid plans for a
larger set of problems than any of its competitors but often took more
time to find the plans and returned suboptimal (though still good)
plans.
The main insight of HSP was that with a good enough heuristic, search
through the state was plausible because a large portion of the space
could be quickly pruned out. The drawback of the approach was that a
new heuristic had to be computed at every step in the search process.
HSPr, the improvement over HSP described in this paper, solves the
problem by conducting the search backwards from the goal -- this
allows it to compute the heuristic only once per each node thus
significantly speeding up the search.
Like Graphplan, HSPr begins the process by detecting possible mutex
relationships among nodes in order to pre-prune the search space
before starting the search.
Finally, probably one of the most important decisions in the design of
HSPr was to use a non-admissible but very informative heuristic to
guide the search. The heuristic ocassionally overestimates when
multiple goals can be achieved with the same action. However the
authors preferred it to a maximum (rather than summation) based
heuristic because of its prunning power. A great challenge for the
heuristic search approach to planning would be to find an informative
admissible heuristic which is also fast to compute.
As usual, it would be very interesting to see if this approach could
be extended to more complex planning problems. The main challenge
would be to find easy to solve relaxed versions of the problem whose
solutions would constitute an informative guiding heuristic for the
search process.
This archive was generated by hypermail 2.1.6 : Fri Apr 11 2003 - 09:26:22 PDT