Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation
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.
Cite
Text
Zhang and Bercher. "Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation." International Joint Conference on Artificial Intelligence, 2025. doi:10.24963/IJCAI.2025/967Markdown
[Zhang and Bercher. "Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation." International Joint Conference on Artificial Intelligence, 2025.](https://mlanthology.org/ijcai/2025/zhang2025ijcai-computational/) doi:10.24963/IJCAI.2025/967BibTeX
@inproceedings{zhang2025ijcai-computational,
title = {{Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation}},
author = {Zhang, Yifan and Bercher, Pascal},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2025},
pages = {8696-8704},
doi = {10.24963/IJCAI.2025/967},
url = {https://mlanthology.org/ijcai/2025/zhang2025ijcai-computational/}
}