TY - JOUR AU - Alford, Ron AU - Bercher, Pascal AU - Aha, David PY - 2015/04/08 Y2 - 2024/03/28 TI - Tight Bounds for HTN Planning JF - Proceedings of the International Conference on Automated Planning and Scheduling JA - ICAPS VL - 25 IS - 1 SE - Technical Papers DO - 10.1609/icaps.v25i1.13721 UR - https://ojs.aaai.org/index.php/ICAPS/article/view/13721 SP - 7-15 AB - <p> 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. </p> ER -