@inproceedings{4716a27278214611a5c70ef1e7fe01d7,
title = "I Always Told My Mom That Order Is Overrated: Unordered HTN Planning is in PSPACE and Models Problems Beyond STRIPS",
abstract = "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.",
author = "Pascal Lauer and Yifan Zhang and Patrik Haslum and Pascal Bercher",
year = "2026",
doi = "10.1609/icaps.v36i1.42825",
language = "English",
isbn = "1-57735-910-0",
volume = "36",
series = "Proceedings of the International Conference on Automated Planning and Scheduling",
publisher = "AAAI Press",
number = "1",
pages = "161--170",
editor = "Amanda Coles and Wheeler Rumi and Sandhya Saisubramanian",
booktitle = "Proceedings of the Thirty-Sixth International Conference on Automated Planning and Scheduling (ICAPS 2026)",
note = "Thirty-Sixth International Conference on Automated Planning and Scheduling, ICAPS 2026 ; Conference date: 27-06-2026 Through 02-07-2026",
}