---
title: "A Structural Complexity Analysis of Hierarchical Task Network Planning"
authors:
  - "Cornelius Brand"
  - "Robert Ganian"
  - "Fionn Mc Inerney"
  - "Simon Wietheger"
doi: "10.24963/ijcai.2025/489"
url: "https://ijcai.org/proceedings/2025/489"
pdf: "https://ijcai.org/proceedings/2025/0489.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "4391-4400"
track: "Main Track"
keywords:
  - "Planning and Scheduling: PS: Hierarchical planning"
  - "Planning and Scheduling: PS: Theoretical foundations of planning"
  - "Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning"
---

# A Structural Complexity Analysis of Hierarchical Task Network Planning

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

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 4391-4400. DOI: [10.24963/ijcai.2025/489](https://doi.org/10.24963/ijcai.2025/489)

## 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.