Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

7-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.

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

IJCAI-11: Proceedings of the 22nd International Joint Conference on Artificial Intelligence: Barcelona, Spain, 16-22 July

First Page

2140

Last Page

2146

ISBN

9781577355120

Publisher

AAAI Press

City or Country

Menlo Park, CA

Download

Share

COinS