Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation. Zhang, Y. & Bercher, P. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI 2025), 2025. IJCAI. ![Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper abstract bibtex 3 downloads 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 based on 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.
@InProceedings{Zhang2025AckermannRefined,
author = {Yifan Zhang and Pascal Bercher},
booktitle = {Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI 2025)},
title = {Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation},
year = {2025},
publisher = {IJCAI},
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 based on 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.},
keywords = {conference,DECRA},
url_Paper = {https://bercher.net/publications/2025/Zhang2025AckermannRefined.pdf}
}
Downloads: 3
{"_id":"wAqRGerLopa29W4SF","bibbaseid":"zhang-bercher-computationalcomplexityofplanningforrecursiveprimitivetasknetworksselectiveactionnullificationwithstatepreservation-2025","author_short":["Zhang, Y.","Bercher, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Yifan"],"propositions":[],"lastnames":["Zhang"],"suffixes":[]},{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]}],"booktitle":"Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI 2025)","title":"Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation","year":"2025","publisher":"IJCAI","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 based on 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.","keywords":"conference,DECRA","url_paper":"https://bercher.net/publications/2025/Zhang2025AckermannRefined.pdf","bibtex":"@InProceedings{Zhang2025AckermannRefined,\n author = {Yifan Zhang and Pascal Bercher},\n booktitle = {Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI 2025)},\n title = {Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation},\n year = {2025},\n publisher = {IJCAI},\n 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 based on 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.},\n keywords = {conference,DECRA},\n url_Paper = {https://bercher.net/publications/2025/Zhang2025AckermannRefined.pdf}\n}\n\n","author_short":["Zhang, Y.","Bercher, P."],"key":"Zhang2025AckermannRefined","id":"Zhang2025AckermannRefined","bibbaseid":"zhang-bercher-computationalcomplexityofplanningforrecursiveprimitivetasknetworksselectiveactionnullificationwithstatepreservation-2025","role":"author","urls":{" paper":"https://bercher.net/publications/2025/Zhang2025AckermannRefined.pdf"},"keyword":["conference","DECRA"],"metadata":{"authorlinks":{}},"downloads":3},"bibtype":"inproceedings","biburl":"https://bercher.net/bibtex/bibliography.bib","dataSources":["bPpsmYWjffAy6QHP5"],"keywords":["conference","decra"],"search_terms":["computational","complexity","planning","recursive","primitive","task","networks","selective","action","nullification","state","preservation","zhang","bercher"],"title":"Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation","year":2025,"downloads":6}