Where Ignoring Delete Lists Works, Part II: Causal Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

Where Ignoring Delete Lists Works, Part II: Causal Graphs

Joerg Hoffmann
  • Fonction : Auteur
  • PersonId : 864556

Résumé

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.
Fichier principal
Vignette du fichier
total.pdf (331.85 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00578653 , version 1 (21-03-2011)

Identifiants

  • HAL Id : inria-00578653 , version 1

Citer

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⟩
62 Consultations
138 Téléchargements

Partager

Gmail Facebook X LinkedIn More