EUVIMEDEUVIMED entdecken
Crossref

I Always Told My Mom That Order Is Overrated: Unordered HTN Planning Is in PSPACE and Models Problems Beyond STRIPS

Pascal Lauer, Yifan Zhang, Patrik Haslum, Pascal Bercher

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →