Structural Patterns Beyond Forks: Extending the Complexity Boundaries of Classical Planning

Michael Katz 1 Emil Keyder 1
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : Tractability analysis in terms of the causal graphs of planning problems has emerged as an important area of research in recent years, leading to new methods for the derivation of domain-independent heuristics (Katz and Domshlak 2010). Here we continue this work, extending our knowledge of the frontier between tractable and NP-complete fragments. We close some gaps left in previous work, and introduce novel causal graph fragments that we call the hourglass and semi-fork, for which under certain additional assumptions optimal planning is in P. We show that relaxing any one of the restrictions required for this tractability leads to NP-complete problems. Our results are of both theoretical and practical interest, as these fragments can be used in existing frameworks to derive new abstraction heuristics. Before they can be used, however, a number of practical issues must be addressed. We discuss these issues and propose some solutions.
Type de document :
Communication dans un congrès
Twenty-Sixth Conference on Artificial Intelligence (AAAI), Jul 2012, Toronto, Canada. 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00765037
Contributeur : Olivier Buffet <>
Soumis le : vendredi 14 décembre 2012 - 09:36:16
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : dimanche 18 décembre 2016 - 01:11:39

Fichier

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

Identifiants

  • HAL Id : hal-00765037, version 1

Collections

Citation

Michael Katz, Emil Keyder. Structural Patterns Beyond Forks: Extending the Complexity Boundaries of Classical Planning. Twenty-Sixth Conference on Artificial Intelligence (AAAI), Jul 2012, Toronto, Canada. 2012. 〈hal-00765037〉

Partager

Métriques

Consultations de la notice

158

Téléchargements de fichiers

103