Publications

| Sorted by Date | Classified by Publication Type | Classified by Research Category |

Lossless Clustering of Histories in Decentralized POMDPs

Frans A. Oliehoek, Shimon Whiteson, and Matthijs T. J. Spaan. Lossless Clustering of Histories in Decentralized POMDPs. In Proc. of Int. Conference on Autonomous Agents and Multi Agent Systems, pp. 577–584, May 2009.

Download

pdf [209.6kB]  

Abstract

Decentralized partially observable Markov decision processes (Dec-POMDPs) constitute a generic and expressive framework for multiagent planning under uncertainty. However, planning optimally is difficult because solutions map local observation histories to actions, and the number of such histories grows exponentially in the planning horizon. In this work, we identify a criterion that allows for lossless clustering of observation histories: i.e., we prove that when two histories satisfy the criterion, they have the same optimal value and thus can be treated as one. We show how this result can be exploited in optimal policy search and demonstrate empirically that it can provide a speed-up of multiple orders of magnitude, allowing the optimal solution of significantly larger problems. We also perform an empirical analysis of the generality of our clustering method, which suggests that it may also be useful in other (approximate) Dec-POMDP solution methods.

BibTeX Entry

@InProceedings{Oliehoek09aamas,
  author =       {Frans A. Oliehoek and Shimon Whiteson and Matthijs
                  T. J. Spaan},
  title =        {Lossless Clustering of Histories in Decentralized
                  {POMDP}s},
  booktitle =    {Proc. of Int. Conference on Autonomous Agents
                  and Multi Agent Systems},
  month =        may,
  year =         2009,
  pages =        {577--584}
}

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 bib2html.pl (written by Patrick Riley) on Tue Sep 06, 2011 11:22:28 UTC