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 · 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.
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}
}
EUVIMED