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:
- 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."
- 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.
- 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.
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.
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