A Structural Complexity Analysis of Hierarchical Task Network Planning

Abstract

We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network planning: the verification of a provided plan, whether an executable plan exists, and whether a given state can be reached. Our focus is to identify structural properties yielding tractability. We obtain new polynomial-time algorithms for all three problems on a natural class of primitive networks, along with corresponding lower bounds. We also obtain an algorithmic meta-theorem for lifting polynomial-time solvability from primitive to general task networks, and prove that its preconditions are tight. Lastly, we analyze the parameterized complexity of the three problems.