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
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.
BibTeX
@inproceedings{ijcai2026_centralizedanddi,
title = {Centralized and Distributed Approaches for Restoring the Weak Controllability of Multi-Agent Interdependent STNUs},
author = {Ajdin Sumic and Gauthier Picard and Roberto Posenato and Thierry Vidal and Carlo Combi and Frédéric Maris},
booktitle = {IJCAI 2026},
year = {2026}
}