Exploiting locality of interaction in networked distributed POMDPs

Yoonheui Kim, Ranjit Nair, Pradeep Varakantham, Milind Tambe, Makoto Yokoo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Citations (Scopus)


In many real-world multiagent applications such as distributed 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 optimization (DCOP) captures the locality of interaction but fails to capture planning under uncertainty. In previous work, we presented a model synthesized from distributed POMDPs and DCOPs, called Networked Distributed POMDPs (ND-POMDPs). Also, we presented LID-JESP (locally interacting distributed joint equilibrium-based search for policies: a distributed policy generation algorithm based on DBA (distributed breakout algorithm). In this paper, we present a stochastic variation of the LID-JESP that is based on DSA (distributed stochastic algorithm) that allows neighboring agents to change their policies in the same cycle. Through detailed experiments, we show how this can result in specdups without a large difference in solution quality. We also introduce a technique called hyper-link-based decomposition that allows us to exploit locality of interaction further, resulting in faster run times for both LID-JESP and its stochastic variant without any loss in solution quality.

Original languageEnglish
Title of host publicationDistributed Plan and Schedule Management - Papers from the AAAI Spring Symposium, Technical Report
Number of pages8
Publication statusPublished - 2006
Event2006 AAAI Spring Symposium - Stanford, CA, United States
Duration: Mar 27 2006Mar 29 2006

Publication series

NameAAAI Spring Symposium - Technical Report


Other2006 AAAI Spring Symposium
Country/TerritoryUnited States
CityStanford, CA

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Exploiting locality of interaction in networked distributed POMDPs'. Together they form a unique fingerprint.

Cite this