A Structural Complexity Analysis of Hierarchical Task Network Planning

Brand, Cornelius; Ganian, Robert; Mc Inerney, Fionn; Wietheger, Simon

doi:10.24963/ijcai.2025/489

A Structural Complexity Analysis of Hierarchical Task Network Planning

Cornelius Brand, Robert Ganian, Fionn Mc Inerney, Simon Wietheger

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 4391-4400.

https://doi.org/10.24963/ijcai.2025/489

Keywords

Planning and Scheduling: PS: Hierarchical planning
Planning and Scheduling: PS: Theoretical foundations of planning
Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning

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.

Cornelius Brand, Robert Ganian, Fionn Mc Inerney, and Simon Wietheger. 2025. A Structural Complexity Analysis of Hierarchical Task Network Planning. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 4391–4400. https://doi.org/10.24963/ijcai.2025/489

@inproceedings{ijcai2025p489,
  title     = {A Structural Complexity Analysis of Hierarchical Task Network Planning},
  author    = {Brand, Cornelius and Ganian, Robert and Mc Inerney, Fionn and Wietheger, Simon},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {4391--4400},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/489},
  url       = {https://doi.org/10.24963/ijcai.2025/489},
}

TY  - CPAPER
TI  - A Structural Complexity Analysis of Hierarchical Task Network Planning
AU  - Brand, Cornelius
AU  - Ganian, Robert
AU  - Mc Inerney, Fionn
AU  - Wietheger, Simon
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 4391
EP  - 4400
DO  - 10.24963/ijcai.2025/489
UR  - https://doi.org/10.24963/ijcai.2025/489
ER  -