Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Olivier Buffet Connect in order to contact the contributor
Submitted on : Friday, December 14, 2012 - 9:36:16 AM
Last modification on : Wednesday, February 2, 2022 - 5:00:56 PM
Long-term archiving on: : Sunday, December 18, 2016 - 1:11:39 AM


Files produced by the author(s)


  • HAL Id : hal-00765037, version 1



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⟩



Record views


Files downloads