From: Daniel Hasselrot (danielh_at_cs.washington.edu)
Date: Fri Apr 11 2003 - 10:57:19 PDT
Title:
Planning as Heuristic Search: New Results
Author:
Blai Bonet and Héctor Geffner
One-line summary:
Speeding up planning by heuristic search planning by searching backward
from the goal states to the initial state.
Important ideas:
In an ordinary heuristic search planner the heuristic depends on the state
s, and needs to be recomputed at every new state. By searching backwards
from the goal states, over the regression space, the heuristic only needs
to be calculated once for each atom and can be used to estimate the
heuristic at any state. This speeds up the search.
When searching over the regression space states, which cannot reach the
initial state s0 and thus not lead to a solution, are often encountered.
To avoid these states a set of mutually exclusive relations (mutexes) are
kept. These are relations between two atoms where no reachable state will
contain them both. To find the set mutexes the paper starts with a set of
probable mutexes and removes the ones who doesn't meet the mutex
conditions. Using mutexes enables pruning many of the nodes in the search
tree and speeds up the search.
Biggest flaws:
The paper is lacking examples.
Open research questions:
Finding a better heuristic that’s informative and admissible. This would
lead to faster searches and the possibility to use an optimal search
algorithm as for example IDA*.
Apply the HSPr on other modeling languages so that more complex planning
problems can be solved.
This archive was generated by hypermail 2.1.6 : Fri Apr 11 2003 - 10:57:20 PDT