טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentMichael Katz
SubjectImplicit Abstraction Heuristics for Cost-Optimal Planning
DepartmentDepartment of Industrial Engineering and Management
Supervisor Full Professor Domshlak Carmel
Full Thesis textFull thesis text - English Version


Abstract

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.