Where Ignoring Delete Lists Works, Part II: Causal Graphs
Résumé
The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. Hoffmann (2005) 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. Hoffmann's proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to Hoffmann's disappointing results -- his 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 Hoffmann proved the absence of local minima, 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. We show that, in this way, TorchLight can distinguish Hoffmann's ``easy'' domains from the ``hard'' ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...