Tight Bounds for HTN Planning


  • Ron Alford U.S. Naval Research Laboratory
  • Pascal Bercher Ulm University
  • David Aha U.S. Naval Research Laboratory




HTN Planning, Complexity, Theory


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.




How to Cite

Alford, R., Bercher, P., & Aha, D. (2015). Tight Bounds for HTN Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 25(1), 7-15. https://doi.org/10.1609/icaps.v25i1.13721