Exploiting locality of interaction in networked distributed POMDPs: An empirical evaluation

摘要

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 works, Nair et al. presented a model synthesized from distributed POMDPs and DCOPs, called Networked Distributed POMDPs (ND-POMDPs). Also, they presented LID-JESP, a locally interacting distributed joint equilibrium-based search for policies: a distributed policy generation algorithm based on DBA (distributed breakout algorithm). In this thesis, I introduce two of its variants. The first variant, SLID-JESP is based on DSA (distributed stochastic algorithm) that allows neighboring agents to change their policies in the same cycle. I 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. Finally, I present a thorough experimental analysis of LID-JESP and its variants against benchmark algorithms that do not exploit locality of interaction. Furthermore, towards improving quality of the solutions, I provide a heuristic to select a better initial policy.