Scalable Anytime Planning for Multi-Agent MDPs (Extended Abstract)

Shushman Choudhury, Jayesh K. Gupta, Mykel J. KochenderferIJCAI 2022 · DOI

Abstract

Planning in Multi-Agent Markov Decision Processes (MMDPs) is notoriously difficult due to the exponential growth of the joint action space. While Factored-Value Monte Carlo Tree Search (FV-MCTS) addresses this by using Coordination Graphs (CGs), existing implementations rely on Variable Elimination (Var-El), which lacks "anytime" properties and scales poorly. We introduce FV-MCTS-MP, which replaces Var-El with the iterative Max-Plus message-passing algorithm. Our approach restores the anytime nature of MCTS and enables efficient planning in systems with dozens of agents and dynamic, state-dependent coordination requirements.

Introduction

The "curse of dimensionality" is a primary hurdle in multi-agent systems. With $N$ agents and $K$ actions each, the joint action space $K^N$ overwhelms standard planning algorithms. Coordination Graphs (CGs) mitigate this by factoring global rewards into local interactions. However, the state-of-the-art FV-MCTS with Variable Elimination (Var-El) is computationally prohibitive for dense or dynamic graphs and cannot provide intermediate solutions if interrupted, conflicting with the anytime nature of MCTS.

Methodology: FV-MCTS-MP

We propose Factored-Value MCTS with Max-Plus (FV-MCTS-MP). The framework integrates three core innovations:

  1. Max-Plus Message Passing: We replace the exact Var-El with Max-Plus, an iterative algorithm where agents negotiate joint actions via scalar messages. This makes the coordination step interruptible and "anytime."
  2. Factored UCB Exploration: To maintain effective exploration, Upper Confidence Bound (UCB) bonuses are integrated directly into Max-Plus messages using Node and Edge exploration strategies.
  3. Dynamic Coordination: Our method supports state-dependent coordination graphs, allowing agents to coordinate only when necessary (e.g., proximity-based interaction), which is crucial for real-world scalability.

Experimental Results

The algorithm was evaluated on the SysAdmin benchmark (static graphs) and a new Multi-Drone Delivery domain (dynamic graphs).

Speed and Scalability

FV-MCTS-MP significantly reduces computational overhead. On a 32-agent SysAdmin Ring topology, our method was more than twice as fast as the Var-El variant (16 seconds vs. 35 seconds per action), demonstrating superior scaling properties as the number of agents increases.

Average time for action across different agent counts.

Performance

Despite using an approximate coordination method, FV-MCTS-MP matches or exceeds the performance of exact methods while remaining tractable at scales where others fail. In the Multi-Drone domain, standard MCTS and Var-El variants became intractable due to memory constraints, whereas FV-MCTS-MP successfully scaled to 32 agents.

Discounted return comparison. Note that NaiveMCTS becomes intractable as agent counts increase.

Conclusion

By restoring the anytime property to factored planning, FV-MCTS-MP enables scalable coordination in complex multi-agent environments. Future work will explore more theoretically grounded exploration strategies and optimizations for low-bandwidth communication environments.

Summary updated

BibTeX
@inproceedings{choudhury2022scalable,
  author = {Shushman Choudhury and Jayesh K. Gupta and Mykel J. Kochenderfer},
  title = {{Scalable Anytime Planning for Multi-Agent MDPs (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/735},
}
Figure