Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+

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, 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 -- 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 :
Article dans une revue
Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2011, 41, pp.155--229. 〈10.1613/jair.3276〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00598248
Contributeur : Joerg Hoffmann <>
Soumis le : dimanche 5 juin 2011 - 21:59:11
Dernière modification le : jeudi 11 janvier 2018 - 06:19:51
Document(s) archivé(s) le : vendredi 9 novembre 2012 - 14:20:11

Fichier

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

Identifiants

Collections

Citation

Joerg Hoffmann. Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+. Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2011, 41, pp.155--229. 〈10.1613/jair.3276〉. 〈inria-00598248〉

Partager

Métriques

Consultations de la notice

139

Téléchargements de fichiers

149