I Always Told My Mom That Order Is Overrated: Unordered HTN Planning Is in PSPACE and Models Problems Beyond STRIPS
Proceedings of the International Conference on Automated Planning and Scheduling · 08.06.2026 · 36 (1) · 161-170
DOI: 10.1609/icaps.v36i1.42825 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.06.2026. Verfasst von Pascal Lauer und 3 weiteren Autor:innen.
Abstract (Originalsprache)
Hierarchical Task Network planning is (in)famous for offering great modeling power but making plan existence undecidable. To lift the computational barrier, it is common to enforce orders between all tasks, which allows for an EXPTIME computation. We show that the opposite extreme, using no ordering constraints, reduces complexity further to PSPACE. This unites benefits of STRIPS and HTN planning in a single formalism: It matches the complexity of STRIPS planning while provably giving modelers more expressive power. We observe the same benefit for more, partially new, planning formalisms along the way to the main result. This motivates that these formalisms have similar merit on their own.
Zitieren
APA
Lauer, P., Zhang, Y., Haslum, P., & Bercher, P. (2026). I Always Told My Mom That Order Is Overrated: Unordered HTN Planning Is in PSPACE and Models Problems Beyond STRIPS. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 161-170. https://doi.org/10.1609/icaps.v36i1.42825
Vancouver
Lauer P, Zhang Y, Haslum P, Bercher P. I Always Told My Mom That Order Is Overrated: Unordered HTN Planning Is in PSPACE and Models Problems Beyond STRIPS. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):161-170. doi:10.1609/icaps.v36i1.42825
BibTeX
@article{Lauer2026,
author = {Lauer, Pascal and Zhang, Yifan and Haslum, Patrik and Bercher, Pascal},
title = {I Always Told My Mom That Order Is Overrated: Unordered HTN Planning Is in PSPACE and Models Problems Beyond STRIPS},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2026},
volume = {36},
number = {1},
pages = {161--170},
doi = {10.1609/icaps.v36i1.42825}
}
EUVIMED