Computational Complexity of Repair Problems on Simple Temporal Networks with Uncertainty

Junkang Li, Frédéric Maris, Ajdin Sumic, Thierry Vidal, Bruno Zanuttini
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:3546-3555, 2026.

Abstract

Simple Temporal Networks with Uncertainty (STNUs) are a well-established formalism for reasoning about temporal plans involving uncontrollable durations, known as contingent links. This model enables checking the controllability of plans under different assumptions about when uncertainties are revealed (Weak, Dynamic, and Strong Controllability). Recent work has also introduced methods to repair uncontrollable STNUs by adjusting contingent bounds, which is relevant e.g., in multi-agent systems, or resource-aware settings where some external flexibility can be negotiated. Nevertheless, there remains a lack of formal understanding regarding the computational complexity of such repair problems. This paper fills that gap by formally defining the problems and assessing the complexity of a number of them. In particular, we show that for a number of settings, repair is no harder than controllability.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-li26a, title = {Computational Complexity of Repair Problems on Simple Temporal Networks with Uncertainty}, author = {Li, Junkang and Maris, Fr\'{e}d\'{e}ric and Sumic, Ajdin and Vidal, Thierry and Zanuttini, Bruno}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {3546--3555}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/li26a/li26a.pdf}, url = {https://proceedings.mlr.press/v337/li26a.html}, abstract = {Simple Temporal Networks with Uncertainty (STNUs) are a well-established formalism for reasoning about temporal plans involving uncontrollable durations, known as contingent links. This model enables checking the controllability of plans under different assumptions about when uncertainties are revealed (Weak, Dynamic, and Strong Controllability). Recent work has also introduced methods to repair uncontrollable STNUs by adjusting contingent bounds, which is relevant e.g., in multi-agent systems, or resource-aware settings where some external flexibility can be negotiated. Nevertheless, there remains a lack of formal understanding regarding the computational complexity of such repair problems. This paper fills that gap by formally defining the problems and assessing the complexity of a number of them. In particular, we show that for a number of settings, repair is no harder than controllability.} }
Endnote
%0 Conference Paper %T Computational Complexity of Repair Problems on Simple Temporal Networks with Uncertainty %A Junkang Li %A Frédéric Maris %A Ajdin Sumic %A Thierry Vidal %A Bruno Zanuttini %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-li26a %I PMLR %P 3546--3555 %U https://proceedings.mlr.press/v337/li26a.html %V 337 %X Simple Temporal Networks with Uncertainty (STNUs) are a well-established formalism for reasoning about temporal plans involving uncontrollable durations, known as contingent links. This model enables checking the controllability of plans under different assumptions about when uncertainties are revealed (Weak, Dynamic, and Strong Controllability). Recent work has also introduced methods to repair uncontrollable STNUs by adjusting contingent bounds, which is relevant e.g., in multi-agent systems, or resource-aware settings where some external flexibility can be negotiated. Nevertheless, there remains a lack of formal understanding regarding the computational complexity of such repair problems. This paper fills that gap by formally defining the problems and assessing the complexity of a number of them. In particular, we show that for a number of settings, repair is no harder than controllability.
APA
Li, J., Maris, F., Sumic, A., Vidal, T. & Zanuttini, B.. (2026). Computational Complexity of Repair Problems on Simple Temporal Networks with Uncertainty. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:3546-3555 Available from https://proceedings.mlr.press/v337/li26a.html.

Related Material