Scalable Multiagent Planning Using Probabilistic Inference
Akshat Kumar, Shlomo Zilberstein and Marc Toussaint
Multiagent planning has seen much progress with the development of formal models such as decentralized MDPs and 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. Inference processes in an Expectation-Maximization (EM) framework can be decomposed, often involving a small subset of agents and thereby facilitating scalability. We derive a global update rule using the EM algorithm 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.