EUVIMEDEUVIMED entdecken
Crossref

Computing Planning Width: How Hard Is It, Really?

Jiajia Song, Seeun William Umboh, Malte Helmert, Nir Lipovetzky, Sebastian Sardiña

Proceedings of the International Conference on Automated Planning and Scheduling · 08.06.2026 · 36 (1) · 304-312

DOI: 10.1609/icaps.v36i1.42840 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.06.2026. Verfasst von Jiajia Song und 4 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The width of a classical planning instance, among other metrics, indicates the computational difficulty of solving the instance. However, no result exists on the complexity of computing the width itself. In this paper, we address this open problem by considering two versions: non-parameterised and parameterised. In the non-parameterised version, a positive integer is given as an input along a classical planning instance, and it is PSPACE-complete to decide if this number is an upper bound of the instance's width. In the parameterised version, it is coNP-complete to decide if the width is no greater than the fixed parameter. These tight results resolve the long standing question of how hard it is to compute the width of planning instances, and call for further research on width approximations, generalisation of width computation over multiple instances and islands of tractability.

Zitieren

APA

Song, J., Umboh, S. W., Helmert, M., Lipovetzky, N., & Sardiña, S. (2026). Computing Planning Width: How Hard Is It, Really?. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 304-312. https://doi.org/10.1609/icaps.v36i1.42840

Vancouver

Song J, Umboh SW, Helmert M, Lipovetzky N, Sardiña S. Computing Planning Width: How Hard Is It, Really?. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):304-312. doi:10.1609/icaps.v36i1.42840

BibTeX
@article{Song2026,
  author = {Song, Jiajia and Umboh, Seeun William and Helmert, Malte and Lipovetzky, Nir and Sardiña, Sebastian},
  title = {Computing Planning Width: How Hard Is It, Really?},
  journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2026},
  volume = {36},
  number = {1},
  pages = {304--312},
  doi = {10.1609/icaps.v36i1.42840}
}
Kostenlos starten →