Abstract
Decentralized coordination in multi-agent systems often suffers from high communication overhead and inefficient planning when agents exchange low-level primitive actions. This paper introduces Dec-SGTS, a framework where agents coordinate by sharing "subgoal intentions"—high-level abstract plans. By planning at the subgoal level, Dec-SGTS achieves a 110% improvement in coordination performance and a 45% reduction in communication costs compared to state-of-the-art decentralized methods like Dec-MCTS.
Introduction
In multi-agent systems, such as fleets of delivery robots or warehouse automation swarms, effective coordination is critical to avoid redundant efforts and maximize system-wide efficiency. Traditional approaches are often either centralized, which lack scalability and present single points of failure, or decentralized but inefficient.
The current standard for decentralized planning, Decentralized Monte Carlo Tree Search (Dec-MCTS), requires agents to communicate intentions as sequences of primitive actions (e.g., specific directional moves). This approach faces two primary challenges: significant communication bloat due to the length of low-level action sequences, and a lack of semantic meaning, which hinders teammates' ability to adapt their high-level strategies. Dec-SGTS addresses these issues by enabling agents to communicate via semantically rich subgoals (e.g., "reach the warehouse"), providing a more modular and efficient coordination protocol.
Methodology
The Dec-SGTS framework utilizes a Subgoal-based Protocol (SP) where each agent operates in an asynchronous three-phase loop:
- Local Sub-Goal Tree Search (SGTS): Agents construct a search tree where nodes represent subgoals rather than individual moves. They employ a "Discounted Upper Confidence Bound for Trees" (D-UCT) to balance exploration and exploitation while adapting to the evolving plans of teammates.
- Local Subgoal Intention Update: Instead of selecting a single deterministic path, agents maintain a probability distribution over potential subgoal sequences. This distribution is optimized using a distributed Lagrangian steepest descent method to maximize global utility and minimize inter-agent conflict.
- Global Subgoal Intention Sharing: Agents broadcast their updated probability distributions. Because these distributions represent high-level subgoals, the resulting messages are highly compressed compared to primitive action sequences.
A key feature is demand-driven expansion, where agents use random walks to discover viable neighboring subgoals, only integrating them into the tree once their feasibility is confirmed.
Experimental Evaluation
The researchers evaluated Dec-SGTS using the Courier Dispatching Problem (CDP) in a grid-world simulation based on real-world urban maps. The task involved multiple couriers coordinating to pick up packages scattered across a map featuring various obstacles and bottlenecks like bridges and gates. Dec-SGTS was compared against centralized MCTS, centralized subgoal-based MCTS (S-MCTS), and the standard Dec-MCTS.
Results and Discussion
Dec-SGTS demonstrated significant improvements over existing decentralized baselines. It outperformed Dec-MCTS by 110% in average reward within the same planning budget and reached near-optimal performance in under 10 seconds, whereas competing methods failed to converge even after 20 seconds.
Communication efficiency was another major highlight, with a 45% reduction in costs. By sharing intentions as distributions over subgoals, agents exchanged richer information with fewer bytes. The study also highlighted the importance of "bottleneck" locations (e.g., doors, bridges) as auxiliary subgoals, which significantly accelerated planning speed compared to using only final targets.
Conclusion and Future Work
Dec-SGTS provides a robust and efficient framework for decentralized multi-agent coordination by leveraging the abstraction of subgoals. While highly effective in deterministic environments, future work will focus on extending the protocol to stochastic settings where action outcomes are uncertain. Additionally, the authors aim to explore automated subgoal discovery through deep learning and investigate coalition-based methods to further enhance scalability for massive agent swarms.
Summary updated