Centralized and Distributed Approaches for Restoring the Weak Controllability of Multi-Agent Interdependent STNUs

Sumic, Ajdin; Picard, Gauthier; Posenato, Roberto; Vidal, Thierry; Combi, Carlo; Maris, Frédéric

doi:10.24963/ijcai.2026/43

Centralized and Distributed Approaches for Restoring the Weak Controllability of Multi-Agent Interdependent STNUs

Ajdin Sumic, Gauthier Picard, Roberto Posenato, Thierry Vidal, Carlo Combi, Frédéric Maris

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 374-382.

https://doi.org/10.24963/ijcai.2026/43

Keywords

Agent-based and Multi-agent Systems: Multi-agent planning
Planning and Scheduling: Distributed and multi-agent planning
Planning and Scheduling: Planning under uncertainty

Abstract

Temporal planning and scheduling often rely on constraint models to reason about activity durations. Simple Temporal Networks with Uncertainty (STNUs) address cases where some contingent durations are outside the control of the executing agent. The Multiple Interdependent STNU (MISTNU) model extends this setting to multi-agent systems by representing shared activities whose duration is decided by one agent and imposed on others. While controllability properties for MISTNUs have been defined, existing repair methods rely on a centralized SMT-based brute-force approach. This paper introduces a linear-constraint characterization of all negative cycles responsible for uncontrollability. Based on this formulation, we propose both a more efficient centralized linear-programming repair method and a distributed constraint reasoning approach that treats inconsistent cycles as inter-agent constraints. We experimentally compare several Distributed Constraint Optimization Problem (DCOP) solvers against the centralized baseline in terms of efficiency and repair quality.

Ajdin Sumic, Gauthier Picard, Roberto Posenato, Thierry Vidal, Carlo Combi, and Frédéric Maris. 2026. Centralized and Distributed Approaches for Restoring the Weak Controllability of Multi-Agent Interdependent STNUs. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 374–382. https://doi.org/10.24963/ijcai.2026/43

@inproceedings{ijcai2026p43,
  title     = {Centralized and Distributed Approaches for Restoring the Weak Controllability of Multi-Agent Interdependent STNUs},
  author    = {Sumic, Ajdin and Picard, Gauthier and Posenato, Roberto and Vidal, Thierry and Combi, Carlo and Maris, Frédéric},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {374--382},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/43},
  url       = {https://doi.org/10.24963/ijcai.2026/43},
}

TY  - CPAPER
TI  - Centralized and Distributed Approaches for Restoring the Weak Controllability of Multi-Agent Interdependent STNUs
AU  - Sumic, Ajdin
AU  - Picard, Gauthier
AU  - Posenato, Roberto
AU  - Vidal, Thierry
AU  - Combi, Carlo
AU  - Maris, Frédéric
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 374
EP  - 382
DO  - 10.24963/ijcai.2026/43
UR  - https://doi.org/10.24963/ijcai.2026/43
ER  -