EUVIMEDEUVIMED entdecken
Crossref

Relaxing Is Hard: Complexity Results for Lifted Partial Order Causal Link Planning

Harrison Oates, Pascal Bercher

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

DOI: 10.1609/icaps.v36i1.42828 ↗

Kurz gefasst

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

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We investigate Partial Order Causal Link (POCL) planning in the lifted setting, where plan steps are represented as parameterised action schemas. While delete relaxation has been shown to reduce the complexity of plan existence in the ground POCL setting, operating on lifted representations may at times be necessary to avoid the prohibitive cost of grounding. This motivates a separate complexity analysis for the lifted case. We formalise delete-relaxation via filter functions that selectively suppress delete effects, yielding differently strong relaxation semantics, with and without respect for pre-existing delete effects and causal links of the input plan. We prove that plan existence is EXPTIME--complete for most variants, even when the input plan is totally ordered. Further, we prove results ranging from NP--completeness to PSPACE--completeness for fixed-schema plan existence, with a tractable case when planning is done from scratch.

Zitieren

APA

Oates, H., & Bercher, P. (2026). Relaxing Is Hard: Complexity Results for Lifted Partial Order Causal Link Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 191-199. https://doi.org/10.1609/icaps.v36i1.42828

Vancouver

Oates H, Bercher P. Relaxing Is Hard: Complexity Results for Lifted Partial Order Causal Link Planning. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):191-199. doi:10.1609/icaps.v36i1.42828

BibTeX
@article{Oates2026,
  author = {Oates, Harrison and Bercher, Pascal},
  title = {Relaxing Is Hard: Complexity Results for Lifted Partial Order Causal Link Planning},
  journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2026},
  volume = {36},
  number = {1},
  pages = {191--199},
  doi = {10.1609/icaps.v36i1.42828}
}
Kostenlos starten →