Structural Patterns Beyond Forks: Extending the Complexity Boundaries of Classical Planning - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

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

Résumé

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.
Fichier principal
Vignette du fichier
AAAI2012_Katz_Keyder.pdf (242 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00765037 , version 1 (14-12-2012)

Identifiants

  • HAL Id : hal-00765037 , version 1

Citer

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. ⟨hal-00765037⟩
71 Consultations
75 Téléchargements

Partager

Gmail Facebook X LinkedIn More