From: Tal Shaked (tshaked_at_u.washington.edu)
Date: Thu Apr 10 2003 - 22:42:14 PDT
Planning as Heuristic Search: New Results – B. Bonet, H. Geffner
This paper improves upon a heuristic search planner by searching through a
regression space, which speeds up the time for computing the heuristic for a
given state since it is always relative to the start state.
One of the most important points of this paper is that searching backwards
avoids repetitive, costly heuristic calculations. In a forward search each
state must compute a heuristic based on its new start state, and the goal.
In contrast, a backward search will need to compute a heuristic based on a
constant start state, and the current state. Since the heuristic works by
estimating the cost for obtaining each atom from one state to another, in
the regressions space, it is necessary to just compute the costs of each
atom once from the start state, and then apply those results to all states
along the search backwards. This cannot be done in the forward search since
each state is new, and thus the cost for each atom must be recomputed to
reach the same goal state.
Another important point is that the heuristic is not admissible since it can
overestimate. This is because it is better to use an additive cost which is
more informative (but might miss cases when multiple atoms are satisfied by
a single action), rather than a maximum cost which is less accurate in
general. It is also interesting to see how mutual exclusion should be
applied in the regression space (and that it is not a problem in the forward
search).
One confusing part of this paper is that the definition of a regression
space has some points that could have been elaborated on. Although
intuitively it makes sense, clearly it is not as trivial as reversing the
forward search. For example, mutexes are needed, and it might be nice to
give a simple example of why. Also R3 and R4 were initially a little
unclear to me. Another point is that unlike starting from an initial state,
the goal is a set of states, which gives more choices. I also thought that
more could be said about mutexes in GraphPlan and HSPr, since HSPr mutexes
are limited to pairs of atoms, and do not consider actions directly (so it
prunes the search space in a different way).
One concern brought up in the paper a few times is that the heuristic is not
admissible, and furthermore, it tends to get worse for larger state spaces.
Therefore an interesting area to explore is how to make the heuristic both
admissible and more accurate (and computationally efficient). Perhaps
domain-specific axioms can be derived to better estimate the cost. It might
also be nice if there was a way to consider actions in parallel when
searching.
It could also be interesting to see if there is a way to extend this to more
expressive languages, or domains with incomplete information, although then
it may not be clear how to regress.
This archive was generated by hypermail 2.1.6 : Thu Apr 10 2003 - 22:42:20 PDT