From: MAUSAM (mausam_at_cs.washington.edu)
Date: Fri Apr 11 2003 - 04:31:22 PDT
Planning as Heuristic Search: New Results
Blai Bonet and Hector Geffner
This paper improves on the drawbacks of HSP - the heuristic search planner
by using goal regression.
The earlier version of the planner, HSP, took considerably longer time
than many other planners because heuristic computation was bottleneck. The
authors tried to remedy the situation by using similar heuristics, however
searching in the backward direction from the goals. The new planner,
called HSPr, uses similar heuristic computation as HSP. However since its
a backward search, the start state for heuristic computation is always the
final goal state and thus a lot of computation time is saved.
Another important idea in the paper is the observed similarity between
various features of graphplan and HSPr. Planning graph is related to
calculating heuristic and that is in forward direction similar to HSPr.
Similarly search in both planners is backward etc.
Another interesting idea is the computation of mutexes to speedup the
whole process in the state space.
The section on hill climbing search using some cost function with a
parameter W is something that is not explained well at all. They use W to
be 5 which seems quite unreasonable for me and they don't provide any
reasons either.
One major flaw that seems standard in the various papers that we have read
is the absence of any intuitive or analytical reasoning about the
strengths of the planner in various domains. The authors have done
experiments showing speedups however, they don't question where their
planner would perform better and where not.
Some of the future works are creating better heuristics midway between sum
and max (as mentioned in the paper). I don't know if this would work but
can we use planning graph to compute heuristics and do regression search
as in HSP (as for Graphplan more time is utilized in search and for HSPr
more time goes in heuristic computation). Of course we would have to take
care of different action models (parallel and sequential) somehow.
The authors need to do an explicit state enumeration in the process. I
wonder if symbolic techniques like ADDs will provide some speedup.
This archive was generated by hypermail 2.1.6 : Fri Apr 11 2003 - 04:31:23 PDT