Embedded Files
We present a scalable tree search planning algorithm for large multi-agent sequential decision problems that require dynamic collaboration. Teams of agents need to coordinate decisions in many domains, but naive approaches fail due to the exponential growth of the joint action space with the number of agents. We circumvent this complexity through an anytime approach that allows us to trade computation for approximation quality and also dynamically coordinate actions. Our algorithm comprises three elements: online planning with Monte Carlo Tree Search (MCTS), factored representations of local agent interactions with coordination graphs, and the iterative Max-Plus method for joint action selection. We evaluate our approach on the benchmark SysAdmin domain with static coordination graphs and achieve comparable performance with much lower computation cost than our MCTS baselines. We also introduce a multi-drone delivery domain with dynamic, i.e., state-dependent coordination graphs, and demonstrate how our approach scales to large problems on this domain that are intractable for other MCTS methods.
Accepted at AAMAS-2021.
Update 3: Extended version published at JAIR as Scalable Online Planning for Multi-Agent MDPs.
Update 2: Best Paper Award at AAMAS 2021!
Update 1: Finalist for best paper award at AAMAS-2021.
Domains
Domains
Main Results
Main Results
On Multi-Agent SysAdmin, proposed algorithm FV-MCTS-Max-Plus scales better than baseline MCTS variants
On Multi-UAV Delivery (Dynamic Coordination Graphs), proposed algorithm FV-MCTS-Max-Plus vastly outperforms and scales better than baselines
Page updated
Report abuse