Exploiting Locality of Interaction in Factored Dec-POMDPs

Frans A. Oliehoek, Matthijs T. J. Spaan, Shimon Whiteson, and Nikos Vlassis. Exploiting Locality of Interaction in Factored Dec-POMDPs. In Proc. of Int. Conference on Autonomous Agents and Multi Agent Systems, pp. 517–524, 2008.


pdf [2.1MB]  


Decentralized partially observable Markov decision processes (Dec-POMDPs) constitute an expressive framework for multiagent planning under uncertainty, but solving them is provably intractable. We demonstrate how their scalability can be improved by exploiting locality of interaction between agents in a factored representation. Factored Dec-POMDP representations have been proposed before, but only for Dec-POMDPs whose transition and observation models are fully independent. Such strong assumptions simplify the planning problem, but result in models with limited applicability. By contrast, we consider general factored Dec-POMDPs for which we analyze the model dependencies over space (locality of interaction) and time (horizon of the problem). We also present a formulation of decomposable value functions. Together, our results allow us to exploit the problem structure as well as heuristics in a single framework that is based on collaborative graphical Bayesian games (CGBGs). A preliminary experiment shows a speedup of two orders of magnitude.

BibTeX Entry

  author =       {Frans A. Oliehoek and Matthijs T. J. Spaan and
                  Shimon Whiteson and Nikos Vlassis},
  title =        {Exploiting Locality of Interaction in Factored
  booktitle =    {Proc. of Int. Conference on Autonomous Agents
                  and Multi Agent Systems},
  year =         2008,
  pages =        {517--524}

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Generated by (written by Patrick Riley) on Tue Sep 06, 2011 11:22:28 UTC