Tight bounds for HTN planning with task insertion

Abstract

Hierarchical Task Network (HTN) planning with Task Insertion (TIHTN planning) is a formalism that hybridizes classical planning with HTN plan-ning by allowing the insertion of operators from outside the method hierarchy. This additional capa-bility has some practical benefits, such as allowing more flexibility for design choices of HTN models: the task hierarchy may be specified only partially, since “missing required tasks ” may be inserted dur-ing planning rather than prior planning by means of the (predefined) HTN methods. While task insertion in a hierarchical planning set-ting has already been applied in practice, its theo-retical properties have not been studied in detail, yet – only EXPSPACE membership is known so far. We lower that bound proving NEXPTIME-completeness and further prove tight complexity bounds along two axes: whether variables are al-lowed in method and action schemas, and whether methods must be totally ordered. We also intro-duce a new planning technique called acyclic pro-gression, which we use to define provably efficient TIHTN planning algorithms. 1