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 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.
Cite
Text
Brand et al. "A Structural Complexity Analysis of Hierarchical Task Network Planning." International Joint Conference on Artificial Intelligence, 2025. doi:10.24963/IJCAI.2025/489Markdown
[Brand et al. "A Structural Complexity Analysis of Hierarchical Task Network Planning." International Joint Conference on Artificial Intelligence, 2025.](https://mlanthology.org/ijcai/2025/brand2025ijcai-structural/) doi:10.24963/IJCAI.2025/489BibTeX
@inproceedings{brand2025ijcai-structural,
title = {{A Structural Complexity Analysis of Hierarchical Task Network Planning}},
author = {Brand, Cornelius and Ganian, Robert and Inerney, Fionn Mc and Wietheger, Simon},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2025},
pages = {4391-4400},
doi = {10.24963/IJCAI.2025/489},
url = {https://mlanthology.org/ijcai/2025/brand2025ijcai-structural/}
}