Conference Proceeding Article
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.
Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
International Joint Conference on Artificial Intelligence (IJCAI)
KUMAR, Akshat; Zilberstein, S.; and Toussaint, M..
Scalable Multiagent Planning using Probabilistic Inference. (2011). International Joint Conference on Artificial Intelligence (IJCAI). 2140-2146. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/2204