EUVIMEDEUVIMED entdecken
Crossref

Complexity Results for Fixing Classical Models Using LTL to Express Which Solutions Are (Un)Desired

Huanghua Sheng, Pascal Bercher

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

DOI: 10.1609/icaps.v36i1.42838 ↗

Kurz gefasst

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

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Model repair is the task of modifying a given planning model so that it satisfies a set of validity constraints. Prior frameworks encode constraints as finite sets of desired and undesired plans, which cannot capture properties of infinite sets of plans or patterns shared by all (non)solutions, thereby limiting their usefulness. We propose a unified formalism that subsumes prior approaches by incorporating validity constraints specified in Linear Temporal Logic over process traces (LTLp), thereby capturing temporal and structural properties of plans. We further present a comprehensive complexity analysis that begins with a highly restricted fragment of LTLp and progressively lifts restrictions, tracking how increasing expressivity impacts the complexity of model repair. This yields a complexity landscape ranging from NP through Sigma_2^p up to PSPACE. We also highlight connections between our framework and some well-studied problems, including planning with temporally extended goals (TEGs), model repair using desired and undesired plans, the model reconciliation explanation (MRE) problem, and counterfactual scenarios for automated planning.

Zitieren

APA

Sheng, H., & Bercher, P. (2026). Complexity Results for Fixing Classical Models Using LTL to Express Which Solutions Are (Un)Desired. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 284-293. https://doi.org/10.1609/icaps.v36i1.42838

Vancouver

Sheng H, Bercher P. Complexity Results for Fixing Classical Models Using LTL to Express Which Solutions Are (Un)Desired. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):284-293. doi:10.1609/icaps.v36i1.42838

BibTeX
@article{Sheng2026,
  author = {Sheng, Huanghua and Bercher, Pascal},
  title = {Complexity Results for Fixing Classical Models Using LTL to Express Which Solutions Are (Un)Desired},
  journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2026},
  volume = {36},
  number = {1},
  pages = {284--293},
  doi = {10.1609/icaps.v36i1.42838}
}
Kostenlos starten →