Scalable Multiagent Planning Using Probabilistic Inference

Kumar, Akshat; Zilberstein, Shlomo; Toussaint, Marc

doi:10.5591/978-1-57735-516-8/IJCAI11-357

Scalable Multiagent Planning Using Probabilistic Inference

Akshat Kumar, Shlomo Zilberstein, Marc Toussaint

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2140-2145.

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.

Akshat Kumar, Shlomo Zilberstein, and Marc Toussaint. 2011. Scalable Multiagent Planning Using Probabilistic Inference. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2140–2145. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-357

@inproceedings{ijcai2011p357,
  title     = {Scalable Multiagent Planning Using Probabilistic Inference},
  author    = {Kumar, Akshat and Zilberstein, Shlomo and Toussaint, Marc},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2140--2145},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-357},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-357},
}

TY  - CPAPER
TI  - Scalable Multiagent Planning Using Probabilistic Inference
AU  - Kumar, Akshat
AU  - Zilberstein, Shlomo
AU  - Toussaint, Marc
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2140
EP  - 2145
DO  - 10.5591/978-1-57735-516-8/IJCAI11-357
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-357
ER  -