Where Ignoring Delete Lists Works, Part II: Causal Graphs

The ignoring delete lists relaxation is of paramount impor-tance for both satisficing and optimal planning. In earlier work (Hoffmann 2005), it was observed that the optimal re-laxation heuristic h+ has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automat-ically by domain analysis techniques. In contrast to earlier disappointing results (Hoffmann 2005) – the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains – we herein answer this question in the affirmative. We establish connections between causal graph structure and h+ topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of lo-cal minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish “easy ” domains from “hard ” ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima