Proceedings

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

Yifan Zhang, Pascal Bercher

Download BibTeX Cite

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

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

Keywords

  • Planning and Scheduling: PS: Theoretical foundations of planning
  • Planning and Scheduling: PS: Hierarchical planning

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.

Yifan Zhang, and Pascal Bercher. 2025. Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 8696–8704. https://doi.org/10.24963/ijcai.2025/967
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards