Skip to Main content Skip to Navigation
Conference papers

Where Ignoring Delete Lists Works, Part II: Causal Graphs

Joerg Hoffmann 1 
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work (Hoffmann JAIR'05), it was observed that the optimal relaxation 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 automatically by domain analysis techniques. In contrast to earlier disappointing results (Hoffmann JAIR'05) -- 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 local 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Joerg Hoffmann Connect in order to contact the contributor
Submitted on : Monday, March 21, 2011 - 6:05:44 PM
Last modification on : Saturday, June 25, 2022 - 7:45:22 PM
Long-term archiving on: : Wednesday, June 22, 2011 - 10:03:26 AM


Files produced by the author(s)


  • HAL Id : inria-00578653, version 1



Joerg Hoffmann. Where Ignoring Delete Lists Works, Part II: Causal Graphs. 21st International Conference on Automated Planning and Scheduling, Jun 2011, Freiburg, Germany. ⟨inria-00578653⟩



Record views


Files downloads