Networked Distributed POMDPs: DCOP-Inspired Distributed POMDPs
Ranjit Nair, Pradeep Varakantham, Milind Tambe, and Makoto Yokoo

Abstract

In many real-world multiagent applications such as distrib- uted sensor nets, a network of agents is formed based on each agent s limited interactions with a small number of neighbors. While distributed POMDPs capture the real-world uncertainty in multiagent domains, they fail to exploit such locality of interaction. Distributed constraint opti- mization (DCOP) captures the locality of interaction but fails to capture planning under uncertainty. This paper present a new model synthesized from distributed POMDPs and DCOPs, called Networked Distributed POMDPs (ND-POMDPs). Exploiting network structure enables us to present two novel algorithms for ND-POMDPs: a distributed policy gen- eration algorithm that performs local search and a systematic policy search that is guaranteed to reach the global optimal.