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.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-00765037
Contributor : Olivier Buffet <>
Submitted on : Friday, December 14, 2012 - 9:36:16 AM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Document(s) archivé(s) le : Sunday, December 18, 2016 - 1:11:39 AM

File

AAAI2012_Katz_Keyder.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-00765037⟩

Share

Metrics

Record views

199

Files downloads

134