Message-Passing Algorithms for Large Structured Decentralized POMDPs

Decentralized POMDPs provide a rigorous framework for multi-agent decision-theoretic planning. However, their high complexity has limited scalability. In this work, we present a promising new class of algorithms based on probabilistic inference for infinite-horizon ND-POMDPs-a restricted Dec-POMDP model. We first transform the policy optimization problem to that of likelihood maximization in a mixture of dynamic Bayes nets (DBNs). We then develop the Expectation-Maximization (EM) algorithm for maximizing the likelihood in this representation. The EM algorithm for ND-POMDPs lends itself naturally to a simple messagepassing paradigm guided by the agent interaction graph. It is thus highly scalable w. r. t. the number of agents, can be easily parallelized, and produces good quality solutions.

Authors

• Akshat Kumar Singapore Management University
• Shlomo Zilberstein University of Massachusetts Amherst

Keywords

• Agent Reasoning: Planning (single and multiagent)