A Structural Complexity Analysis of Hierarchical Task Network Planning
This work addresses computational efficiency challenges for AI planning researchers, providing incremental theoretical insights with specific algorithmic improvements.
The paper tackles the complexity of three classical problems in Hierarchical Task Network Planning—plan verification, existence, and reachability—by identifying structural properties that lead to tractability, resulting in new polynomial algorithms for primitive networks and tight lower bounds.
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 lies on identifying structural properties which yield tractability. We obtain new polynomial 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. Finally, we analyze the parameterized complexity of the three problems.