Scalable Multiagent Planning using Probabilistic Inference

• Main Authors: KUMAR, Akshat, ZILBERSTEIN, Shlomo, TOUSSAINT, Marc
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2011
• Subjects: Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/2204; https://ink.library.smu.edu.sg/context/sis_research/article/3204/viewcontent/Scalable_Multiagent_Planning_using_Probabilistic_Inference.pdf
• Institution: Singapore Management University

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.