Optimal admissible composition of abstraction heuristics

AbstractAdditive ensembles of admissible heuristics constitute the most general form of exploiting the individual strengths of numerous admissible heuristics in optimal planning. However, the same set of heuristics can be additively composed in infinitely many ways and the quality of the resulting heuristic estimate depends directly on the choice of the composition. Focusing on abstraction heuristics, we describe a procedure that takes a deterministic planning problem, a forward-search state, and a set of abstraction-based 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) and merge-and-shrink, and implicit abstractions such as fork-decomposition and abstractions based on tractable constraint optimization over tree-shaped constraint networks