Structural Patterns Heuristics via Fork Decomposition

Michael Katz, Carmel Domshlak

We consider a generalization of the PDB homomorphism abstractions to what is called "structural patterns". The basic idea is in abstracting the problem in hand into provably tractable fragments of optimal planning, alleviating by that the constraint of PDBs to use projections of only low dimensionality. We introduce a general framework for additive structural patterns based on decomposing the problem along its causal graph, suggest a concrete non-parametric instance of this framework called fork-decomposition, and formally show that the admissible heuristics induced by the latter abstractions provide state-of-the-art worst-case informativeness guarantees on several standard domains.

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.