Michael Katz, Carmel Domshlak
We describe a procedure that takes a classical planning task, 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 known to us abstraction-based heuristics such as PDBs, constrained PDBs, merge-and-shrink abstractions, fork-decomposition structural patterns, and structural patterns based on tractable constraint optimization.
Subjects: 1.11 Planning; 15.7 Search
Submitted: Jun 27, 2008