Structural patterns heuristics via fork decomposition
Michael Katz, Carmel Domshlak · 2008
We consider a generalization of the PDB homomorphism ab-stractions to what is called “structural patterns”. The ba-sic 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 di-mensionality. 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 ab-stractions provide state-of-the-art worst-case informativeness guarantees on several standard domains.