Integrating Decision Sharing with Prediction in Decentralized Planning for Multi-Agent Coordination under Uncertainty

Minglong Li, Wenjing Yang, Zhongxuan Cai, Shaowu Yang, Ji Wang

Abstract

This paper introduces Dec-MCTS-SP, a decentralized planning algorithm designed to optimize multi-agent coordination under uncertainty while minimizing communication overhead. By combining shared "intentions" for immediate actions with heuristic-based "predictions" for long-term behavior, agents can effectively coordinate without the need for constant, high-bandwidth data exchange. Experimental results in multi-agent information gathering tasks show that Dec-MCTS-SP outperforms standard decentralized Monte Carlo Tree Search (Dec-MCTS) and traditional auction-based methods in both total reward and scalability.

Introduction

In decentralized multi-agent systems, such as robot teams or drone swarms, coordination is typically achieved by agents sharing their planned action sequences. However, real-world communication is often a bottleneck due to latency, instability, or energy constraints. This creates a "communication-coordination trade-off": excessive communication wastes resources, while insufficient communication leads to redundant efforts or conflicts.

The proposed Dec-MCTS-SP framework addresses this by drawing an analogy to human sports, such as soccer. Players do not communicate every intended step; instead, they rely on a shared understanding of the objective and predict their teammates' movements based on the game's state. By replacing expensive communication with intelligent local prediction, agents can maintain high coordination performance with significantly reduced bandwidth.

Methods

The core of Dec-MCTS-SP is a hybrid look-ahead mechanism ($D = D_s + D_p$). Instead of requiring shared data for the entire planning horizon $D$, the algorithm splits the search:

  1. Shared Intentions ($D_s$): Agents communicate their planned actions for the first few steps of the horizon.
  2. Heuristic Prediction ($D_p$): For the remainder of the horizon, agents use computationally cheap heuristics (e.g., "Greedy" or "Iterative Greedy" policies) to predict teammate behavior locally.
The Dec-MCTS-SP framework integrating sharing and prediction between agents.

To handle environmental uncertainty, the algorithm utilizes Factored Belief Vectors to maintain state distributions. A DIY-Bonus is introduced to incentivize agents to complete tasks themselves, preventing over-reliance on potentially inaccurate teammate predictions. Furthermore, the SD-UCT (Sparse and Discounted Upper Confidence Bounds for Trees) algorithm is employed to manage large state spaces by prioritizing recent simulations.

Experimental Evaluation

The approach was evaluated using a simulated Multi-Agent Information Gathering task on the Robot Operating System (ROS). The environment consisted of dynamic graphs (ranging from 36 to 400 nodes) where nodes possessed time-varying "information" rewards and "threat" penalties. Teams of 3 to 16 agents were tasked with maximizing information collection while avoiding threats.

Key Results

Dec-MCTS-SP demonstrated significant improvements over existing baselines:

  • Performance: The algorithm outperformed standard Dec-MCTS by over 5% in total reward and exceeded auction-based methods by more than 60%.
  • Efficiency: Communication costs were drastically reduced compared to standard Dec-MCTS, as the size of the search tree requiring transmission was reduced exponentially through the use of prediction.
  • Scalability: Planning time scaled linearly with the number of agents. In a 400-node map with 16 agents, single-step planning was completed in approximately 12 seconds, making it suitable for real-time applications.
Average reward comparison across different coordination algorithms as the number of agents increases.

Qualitative analysis further revealed that agents using Dec-MCTS-SP spread out more effectively across the map, avoiding the local optima and clustering issues common in less sophisticated coordination strategies.

Conclusion

Dec-MCTS-SP successfully bridges the gap between communication-heavy decentralized planning and purely local heuristics. By integrating prediction into the MCTS framework, it achieves superior coordination with lower resource requirements. Future research will focus on improving heuristic robustness in adversarial environments and exploring more complex, heterogeneous task assignments.

Summary updated

Abstract

The performance of decentralized multi-agent systems tends to benefit from information sharing and its effective utilization. However, too much or unnecessary sharing may hinder the performance due to the delay, instability and additional overhead of communications. Aiming to a satisfiable coordination performance, one would prefer the cost of communications as less as possible. In this paper, we propose an approach for improving the sharing utilization by integrating information sharing with prediction in decentralized planning. We present a novel planning algorithm by combining decision sharing and prediction based on decentralized Monte Carlo Tree Search called Dec-MCTS-SP. Each agent grows a search tree guided by the rewards calculated by the joint actions, which can not only be sampled from the shared probability distributions over action sequences, but also be predicted by a sufficiently-accurate and computationally-cheap heuristics-based method. Besides, several policies including sparse and discounted UCT and DIY-bonus are leveraged for performance improvement. We have implemented Dec-MCTS-SP in the case study on multi-agent information gathering under threat and uncertainty, which is formulated as Decentralized Partially Observable Markov Decision Process (Dec-POMDP). The factored belief vectors are integrated into Dec-MCTS-SP to handle the uncertainty. Comparing with the random, auction-based algorithm and Dec-MCTS, the evaluation shows that Dec-MCTS-SP can reduce communication cost significantly while still achieving a surprisingly higher coordination performance.
BibTeX
@inproceedings{li2019integrating,
  author = {Minglong Li and Wenjing Yang and Zhongxuan Cai and Shaowu Yang and Ji Wang},
  title = {{Integrating Decision Sharing with Prediction in Decentralized Planning for Multi-Agent Coordination under Uncertainty}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/64},
}
Figure