---
title: "Scalable Multiagent Planning Using Probabilistic Inference"
authors:
  - "Akshat Kumar"
  - "Shlomo Zilberstein"
  - "Marc Toussaint"
doi: "10.5591/978-1-57735-516-8/IJCAI11-357"
url: "https://ijcai.org/proceedings/2011/357"
pdf: "https://ijcai.org/proceedings/2011/0357.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "2140-2145"
track: ""
keywords:
---

# Scalable Multiagent Planning Using Probabilistic Inference

Akshat Kumar, Shlomo Zilberstein, Marc Toussaint

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 2140-2145. DOI: [10.5591/978-1-57735-516-8/IJCAI11-357](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-357)

## Abstract

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.