---
title: "Centralized and Distributed Approaches for Restoring the Weak Controllability of Multi-Agent Interdependent STNUs"
authors:
  - "Ajdin Sumic"
  - "Gauthier Picard"
  - "Roberto Posenato"
  - "Thierry Vidal"
  - "Carlo Combi"
  - "Frédéric Maris"
doi: "10.24963/ijcai.2026/43"
url: "https://ijcai.org/proceedings/2026/43"
pdf: "https://ijcai.org/proceedings/2026/0043.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "374-382"
track: "Main Track"
keywords:
  - "Agent-based and Multi-agent Systems: Multi-agent planning"
  - "Planning and Scheduling: Distributed and multi-agent planning"
  - "Planning and Scheduling: Planning under uncertainty"
---

# 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

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 374-382. DOI: [10.24963/ijcai.2026/43](https://doi.org/10.24963/ijcai.2026/43)

## 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.