Abstract
In multiagent systems, coordinating activities across independent entities requires balancing global consistency with local flexibility and privacy. This paper introduces a novel distributed algorithm for decoupling Multiagent Simple Temporal Networks (MaSTNs). By framing the decoupling task as a distributed convex optimization problem and employing a modified Dual Consensus Alternating Direction Method of Multipliers (DC-ADMM), the proposed method achieves near-optimal scheduling flexibility. Crucially, the approach ensures that agents only exchange minimal dual variables, preserving the privacy of internal constraints while guaranteeing convergence to a global optimum.
Introduction
Managing complex multiagent systems—such as construction sites with various subcontractors or fleets of autonomous delivery robots—often relies on Simple Temporal Networks (STNs) to maintain synchronization. However, traditional centralized or tightly coupled approaches suffer from two primary weaknesses: brittleness and lack of privacy. If communication fails or a single agent's local constraints shift, the entire system can become inconsistent. Furthermore, independent agents are often reluctant to share their full internal schedules or business constraints with competitors or partners.
Temporal decoupling addresses these issues by partitioning shared constraints into independent local bounds. Once decoupled, an agent can adjust activities within their "private" window without further coordination. This research presents a distributed method that is both mathematically optimal and privacy-preserving, moving beyond previous heuristic-based or centralized solutions.
Methodology
The authors frame MaSTN decoupling as a distributed convex optimization problem aimed at maximizing "social welfare," defined as the sum of local flexibility measures.
Distributed Optimization via DC-ADMM
The core of the approach is an adaptation of Dual Consensus ADMM (DC-ADMM). This framework allows agents to solve local optimization problems in parallel and reach a consensus on decoupling points through iterative "gossip" with immediate neighbors. To minimize communication overhead, the algorithm was modified so that agents only communicate Lagrange dual variables associated with the specific constraints they share, rather than full state vectors.
Privacy and Optimality
Because the objective function is concave and the constraints are affine, the distributed approach is guaranteed to converge to the global optimum. Privacy is maintained because the exchanged dual variables do not reveal the underlying local constraints of the participating agents. Furthermore, the framework is objective-agnostic; as long as the local flexibility metric is concave, agents can even use different internal measures tailored to their specific business needs.
Evaluation and Results
The algorithm was evaluated using the BDH Problem Instances, encompassing 50 MaSTN instances for group sizes ranging from 2 to 20 agents. Each agent managed 10 tasks, with inter-agent constraints scaling linearly with the number of agents.
Performance Metrics
The distributed algorithm demonstrated exceptional accuracy and scalability. When compared against a centralized gold-standard solver (IPOPT), the distributed solutions were within 0.0016% to 0.0005% of the true optimum.
As shown in the results table, the algorithm converges efficiently, requiring approximately 660 iterations for a 20-agent problem. The maximum violation of any temporal constraint remained under 0.1 "time ticks," a negligible margin for most real-world applications. While the reported times were recorded on a single 4-core machine, the authors anticipate significantly lower wall-clock times in true distributed environments where each agent has dedicated computational resources.
Conclusion
This work provides a robust, distributed framework for decoupling multiagent schedules with optimality guarantees. By leveraging DC-ADMM, the system achieves high flexibility and maintains agent privacy. Future work will focus on improving scalability by incorporating techniques like Partial Path Consistency (PPC) to reduce model size and exploring dynamic decoupling to handle real-time constraint changes during execution.
Summary updated