Ph.D Student | Michael Katz |
---|---|

Subject | Implicit Abstraction Heuristics for Cost-Optimal Planning |

Department | Department of Industrial Engineering and Management |

Supervisor | Full Professor Domshlak Carmel |

Full Thesis text |

State-space search with explicit
abstraction heuristics is at the state of the art of cost-optimal planning. These
heuristics are inherently limited nonetheless, because the size of the abstract
space must be bounded by some, even if very large, constant. Targeting this
shortcoming, we introduce the notion of *(additive) implicit abstractions*,
in which the planning task is abstracted by instances of tractable fragments of
cost-optimal planning. We then introduce a concrete setting for this framework,
called *fork-decomposition*, that is based on two novel fragments of
tractable cost-optimal planning. The induced admissible heuristics are then
studied formally and empirically. While our empirical evaluation demonstrates
the accuracy of the fork decomposition heuristics, the runtime complexity of
computing them poses an obvious tradeoff. Indeed, some of the power of the
explicit abstraction heuristics comes from precomputing the heuristic function
offline and then determining h(s) for each evaluated state s by a very fast
lookup in a ``database.'' But implicit abstraction heuristics are, at first
glance, a different story: while their calculation time is polynomial, it is
far from being fast. To address this problem, we show that the time-per-node complexity
bottleneck of the fork-decomposition heuristics can be successfully overcome.
We demonstrate that an equivalent of the explicit abstraction notion of a
``database'' exists for the fork-decomposition abstractions as well, despite
their exponential-size abstract spaces. We then verify empirically that
heuristic search with the ``databased" fork-decomposition heuristics
favorably competes with the state of the art of cost-optimal planning.

Of course, as planning is known to be
NP-hard even for extremely conservative planning formalisms, no heuristic
should be expected to work well in all planning tasks. Thus, addditive
ensembles of admissible heuristics are used in cost-optimal planning to exploit
the individual strengths of numerous admissible heuristics. The same set of
heuristics can, however, be composed in infinitely many ways, with the choice
of composition directly determining the quality of the resulting heuristic
estimate. Continuing our focus on abstraction heuristics, we describe a
procedure that takes a deterministic planning problem, a forward-search state, and
a set of admissible heuristics, and derives an *optimal* additive
composition of these heuristics with respect to the given state. Most
importantly, we show that this procedure is *polynomial-time *for
arbitrary sets of all abstraction heuristics with which we are acquainted, including
explicit abstractions such as pattern databases (regular or constrained) or
merge-and-shrink, and implicit abstractions such as fork-decomposition or
abstractions based on tractable constraint optimization over tree-shaped
constraint networks.