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

Yifan Zhang; Pascal Bercher

IJCAI 20250 citations

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.

BibTeX

@inproceedings{ijcai2025_computationalcom,
  title = {Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation},
  author = {Yifan Zhang and Pascal Bercher},
  booktitle = {IJCAI 2025},
  year = {2025}
}