Tight Bounds for HTN Planning. Alford, R., Bercher, P., & Aha, D. In Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), pages 7–15, 2015. AAAI Press.
Tight Bounds for HTN Planning [pdf]Paper  Tight Bounds for HTN Planning [link]Video of presentation  doi  abstract   bibtex   15 downloads  
Although HTN planning is in general undecidable, there are many syntactically identifiable sub-classes of HTN problems that can be decided. For these sub-classes, the decision procedures provide upper complexity bounds. Lower bounds were often not investigated in more detail, however. We generalize a propositional HTN formalization to one that is based upon a function-free first-order logic and provide tight upper and lower complexity results along three axes: whether variables are allowed in operator and method schemas, whether the initial task and methods must be totally ordered, and where recursion is allowed (arbitrary recursion, tail-recursion, and acyclic problems). Our findings have practical implications, both for the reuse of classical planning techniques for HTN planning, and for the design of efficient HTN algorithms
Downloads: 15
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021