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.
Type de document :
Communication dans un congrès
21st International Conference on Automated Planning and Scheduling, Jun 2011, Freiburg, Germany. 2011
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00578653
Contributeur : Joerg Hoffmann <>
Soumis le : lundi 21 mars 2011 - 18:05:44
Dernière modification le : jeudi 11 janvier 2018 - 06:19:51
Document(s) archivé(s) le : mercredi 22 juin 2011 - 10:03:26

Fichier

total.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00578653, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

131

Téléchargements de fichiers

143