D-CIS Publication Database

Publication

Type of publication:Inproceedings
Entered by:AVI
TitleLossless Clustering of Histories in Decentralized POMDPs
Bibtex cite IDOliehoek09AAMAS
Booktitle Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009)
Year published 2009
Month May
Pages 577-584
Location 1015 May 2009, Budapest, Hungary
URL http://staff.science.uva.nl/~faolieho/docs/Oliehoek09AAMAS.pdf
Keywords Planning under uncertainty,cooperative multiagent systems
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.
Authors
Oliehoek, Frans
Whiteson, Shimon
Spaan, Matthijs T. J.
Topics
=SEE CLASSIFICATION DIFFERENCE FROM OTHERS=
BibTeXBibTeX
RISRIS
Attachments
 
Total mark: 5