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

摘要

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.