Scalable Multiagent Planning Using Probabilistic Inference

Multiagent planning has seen much progress with the development of formal models such as Dec-POMDPs. However, the complexity of these models-NEXP-Complete even for two agents-has limited scalability. We identify certain mild conditions that are sufficient to make multiagent planning amenable to a scalable approximation w. r. t. the number of agents. This is achieved by constructing a graphical model in which likelihood maximization is equivalent to plan optimization. Using the Expectation-Maximization framework for likelihood maximization, we show that the necessary inference can be decomposed into processes that often involve a small subset of agents, thereby facilitating scalability. We derive a global update rule that combines these local inferences to monotonically increase the overall solution quality. Experiments on a large multiagent planning benchmark confirm the benefits of the new approach in terms of runtime and scalability.

Authors

• Akshat Kumar Singapore Management University
• Shlomo Zilberstein University of Massachusetts Amherst
• Marc Toussaint

Keywords

No keywords are indexed for this paper.