Dec-SGTS: Decentralized Sub-Goal Tree Search for Multi-Agent Coordination

Minglong Li, Zhongxuan Cai, Wenjing Yang, Lixia Wu, Yinghui Xu, Ji Wang

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:

  1. 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.
  2. 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.
  3. 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.
The Dec-SGTS framework overview, illustrating the local tree search, intention update, and sharing phases.

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.

Performance comparison showing average reward and communication cost across different planning budgets.

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

Abstract

Multi-agent coordination tends to benefit from efficient communication, where cooperation often happens based on exchanging information about what the agents intend to do, i.e. intention sharing. It becomes a key problem to model the intention by some proper abstraction. Currently, it is either too coarse such as final goals or too fined as primitive steps, which is inefficient due to the lack of modularity and semantics. In this paper, we design a novel multi-agent coordination protocol based on subgoal intentions, defined as the probability distribution over feasible subgoal sequences. The subgoal intentions encode macro-action behaviors with modularity so as to facilitate joint decision making at higher abstraction. Built over the proposed protocol, we present Dec-SGTS (Decentralized Sub-Goal Tree Search) to solve decentralized online multi-agent planning hierarchically and efficiently. Each agent runs Dec-SGTS asynchronously by iteratively performing three phases including local sub-goal tree search, local subgoal intention update and global subgoal intention sharing. We conduct the experiments on courier dispatching problem, and the results show that Dec-SGTS achieves much better reward while enjoying a significant reduction of planning time and communication cost compared with Dec-MCTS (Decentralized Monte Carlo Tree Search).
BibTeX
@inproceedings{li2021dec,
  author = {Minglong Li and Zhongxuan Cai and Wenjing Yang and Lixia Wu and Yinghui Xu and Ji Wang},
  title = {{Dec-SGTS: Decentralized Sub-Goal Tree Search for Multi-Agent Coordination}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17345},
}
Figure