A Structural Complexity Analysis of Hierarchical Task Network Planning
Cornelius Brand, Robert Ganian, Fionn Mc Inerney, Simon Wietheger
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 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.
BibTeX
@inproceedings{ijcai2025_astructuralcompl,
title = {A Structural Complexity Analysis of Hierarchical Task Network Planning},
author = {Cornelius Brand and Robert Ganian and Fionn Mc Inerney and Simon Wietheger},
booktitle = {IJCAI 2025},
year = {2025}
}