  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 a 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 optimal planning. We then
introduce a concrete setting of 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. This study
testifies for the accuracy of the fork decomposition heuristics, yet our
empirical evaluation also stresses the tradeoff between their accuracy and the
runtime complexity of computing them. 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. By contrast, while fork-decomposition heuristics can be calculated in
polynomial time, computing them 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.
