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
Résumé : La relaxation ignorant les {\it delete lists} est très importante pour la planification efficace, que ce soit pour la planification optimale ou approximative. Hoffmann (2005) a observé que l'heuristique {\it optimal relaxation heuristic}, $h^+$, a des très fortes propriétés dans beaucoup de benchmarks de la planification, notamment concernant l'absence complète de minima locaux. Ces propriétés ont été démontrées à la main, ce qui soulève la question s'il est possible de les démontrer automatiquement, par analyse de domaines. Alors que Hoffmann, en essayant d'y répondre, n'a obtenu que des résultats décevants -- le temps d'exécution de son analyse est exponentielle, et en plus l'analyse ne réussit que dans deux benchmarks extrêmement simples -- notre investigation ici répond a cette question affirmativement. On découvre des liens entre la structure des graphes causaux et la topologie de $h^+$. En conséquence, on construit une analyse avec temps d'exécution polynomial, implémenté dans un logiciel que l'on appelle TorchLight. Parmi les 12 domaines pour lesquels Hoffmann a démontré l'absence de minima locaux, TorchLight a une garantie de succès forte dans 8. Dans nos expériences, l'analyse de TorchLight a une performance forte dans 2 domaines en plus, parmi ces domaines, et aussi dans 4 domaines dans lesquels des minima locaux existent, mais sont rares. On montre que, de cette façon, TorchLight peut distinguer les domaines ``faciles'' de Hoffmann des domaines ``difficiles''. En résumant les causes des échecs de l'analyse, TorchLight produit aussi un diagnostic, indiquant des aspects du domaine qui pourraient provoquer des minima locaux.
Type de document :
Rapport
[Research Report] RR-7505, INRIA. 2011, pp.1--74
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00552255
Contributeur : Joerg Hoffmann <>
Soumis le : mardi 18 janvier 2011 - 14:33:23
Dernière modification le : jeudi 11 janvier 2018 - 06:19:51
Document(s) archivé(s) le : samedi 3 décembre 2016 - 03:46:26

Fichier

RR-7505.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00552255, version 2

Collections

Citation

Joerg Hoffmann. Where Ignoring Delete Lists Works, Part II: Causal Graphs. [Research Report] RR-7505, INRIA. 2011, pp.1--74. 〈inria-00552255v2〉

Partager

Métriques

Consultations de la notice

214

Téléchargements de fichiers

299