---
title: "Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation"
authors:
  - "Yifan Zhang"
  - "Pascal Bercher"
doi: "10.24963/ijcai.2025/967"
url: "https://ijcai.org/proceedings/2025/967"
pdf: "https://ijcai.org/proceedings/2025/0967.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "8696-8704"
track: "Main Track"
keywords:
  - "Planning and Scheduling: PS: Theoretical foundations of planning"
  - "Planning and Scheduling: PS: Hierarchical planning"
---

# Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation

Yifan Zhang, Pascal Bercher

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

## Abstract

This paper investigates fundamental aspects of Hierarchical Task Network (HTN) planning by systematically exploring recursive arrangements of primitive task networks. Working within a general framework that aligns with recently identified ACKERMANN-complete HTN problems, we map the computational complexity across various recursive configurations, revealing a rich complexity landscape. Through a novel proof technique that we call selective action nullification with state preservation, we demonstrate that even a highly restricted class of regular HTN problems remains PSPACE-complete, establishing a profound connection to classical planning. We hope these findings contribute to a deeper and broader understanding of the theoretical foundations of HTN planning.