Optimal Additive Composition of Abstraction-based Admissible Heuristics

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.