Scalable Multiagent Planning Using Probabilistic Inference

Akshat Kumar, Shlomo Zilberstein, and Marc Toussaint. Scalable Multiagent Planning Using Probabilistic Inference. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI), 2140-2146, Barcelona, Spain, 2011.

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.

Bibtex entry:

@inproceedings{KZTijcai11,
  author	= {Akshat Kumar and Shlomo Zilberstein and Marc Toussaint},
  title		= {Scalable Multiagent Planning Using Probabilistic Inference},
  booktitle     = {Proceedings of the Twenty-Second International Joint Conference on
                   Artificial Intelligence},
  year		= {2011},
  pages		= {2140-2146},
  address       = {Barcelona, Spain},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/KZTijcai11.html}
}

shlomo@cs.umass.edu