Structural-Pattern Databases

Abstract

Explicit abstraction heuristics, notably pattern-database and merge-and-shrink heuristics, are employed by some state-of-the-art optimal heuristic-search planners. The major limitation of these abstraction heuristics is that the size of the abstract space has to be bounded by a (large) constant. Targeting this issue, Katz and Domshlak (2008b) introduced structural, and in particular fork-decomposition, abstractions, in which the planning task is abstracted by an instance of a tractable fragment of optimal planning. At first view, however, the lunch was not free. Some of the power of the explicit abstraction heuristics comes from pre-computing the heuristic function offline, and then determine h(s) for each evaluated state s by a very fast lookup in a "database." In contrast, fork-decomposition offer a poly-time, yet far from being fast, computation.

In this contribution, we show that the time-per-node complexity bottleneck of the fork-decomposition heuristics can be successfully overcome. Specifically, we show that an equivalent of the explicit abstractions' notion of "database" exists for the fork-decomposition abstractions as well, and this despite of their exponential-size abstract spaces. Experimentally, we show that heuristic search with such "databased" fork-decomposition heuristics favorably competes with the state-of-the-art of optimal planning.