Optimization Under Epistemic Uncertainty Using Prediction
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
Schutte. "Optimization Under Epistemic Uncertainty Using Prediction." International Joint Conference on Artificial Intelligence, 2024. doi:10.24963/ijcai.2024/967Markdown
[Schutte. "Optimization Under Epistemic Uncertainty Using Prediction." International Joint Conference on Artificial Intelligence, 2024.](https://mlanthology.org/ijcai/2024/schutte2024ijcai-optimization/) doi:10.24963/ijcai.2024/967BibTeX
@inproceedings{schutte2024ijcai-optimization,
title = {{Optimization Under Epistemic Uncertainty Using Prediction}},
author = {Schutte, Noah},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2024},
pages = {8504-8505},
doi = {10.24963/ijcai.2024/967},
url = {https://mlanthology.org/ijcai/2024/schutte2024ijcai-optimization/}
}