TitleTight bounds for HTN planning
Publication TypeConference Proceedings
Year of Conference2015
AuthorsAlford, R, Bercher, P, Aha, DW
Conference Name2015 International Conference on Automated Planning and Scheduling
Date PublishedJune 2015
Conference LocationJerusalem, Isreal

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.

NRL Publication Release Number: