Lossless clustering of histories in decentralized POMDPs

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.

REFERENCES

• 1: C. Amato, D. S. Bernstein, and S. Zilberstein. Optimal fixed-size controllers for decentralized POMDPs. In Multi-Agent Sequential Decision Making in Uncertain Domains (AAMAS Workshop), May 2006.
• 2: C. Amato, D. S. Bernstein, and S. Zilberstein. Optimizing memory-bounded controllers for decentralized POMDPs. In Proc. of Uncertainty in Artificial Intelligence, July 2007.
• 3: R. Aras, A. Dutech, and F. Charpillet. Mixed integer linear programming for exact finite-horizon planning in decentralized POMDPs. In Int. Conf. on Automated Planning and Scheduling, 2007.
• 4: Daniel S. Bernstein , Robert Givan , Neil Immerman , Shlomo Zilberstein, The Complexity of Decentralized Control of Markov Decision Processes, Mathematics of Operations Research, v.27 n.4, p.819-840, November 2002 [doi>10.1287/moor.27.4.819.297]
• 5: A. Boularias and B. Chaib-draa. Exact dynamic programming for decentralized POMDPs with lossless policy compression. In Int. Conf. on Automated Planning and Scheduling, 2008.
• 6: Alan Carlin , Shlomo Zilberstein, Value-based observation compression for DEC-POMDPs, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 7: Rosemary Emery-Montemerlo , Geoff Gordon , Jeff Schneider , Sebastian Thrun, Approximate Solutions for Partially Observable Stochastic Games with Common Payoffs, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.136-143, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.67]
• 8: R. Emery-Montemerlo, G. Gordon, J. Schneider, and S. Thrun. Game theoretic control for robot teams. In IEEE Int. Conf. on Robotics and Automation, 2005.
• 9: C. V. Goldman and S. Zilberstein. Decentralized control of cooperative systems: Categorization and complexity analysis. Journal of Artificial Intelligence Research, 22, 2004.
• 10: Eric A. Hansen , Daniel S. Bernstein , Shlomo Zilberstein, Dynamic programming for partially observable stochastic games, Proceedings of the 19th national conference on Artifical intelligence, p.709-715, July 25-29, 2004, San Jose, California
• 11: R. Nair, M. Tambe, M. Yokoo, D. V. Pynadath, and S. Marsella. Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings. In IJCAI, 2003.
• 12: F. A. Oliehoek, M. T. J. Spaan, and N. Vlassis. Optimal and approximate Q-value functions for decentralized POMDPs. Journal of Artificial Intelligence Research, 32, 2008.
• 13: M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, July 1994.
• 14: David V. Pynadath , Milind Tambe, Multiagent teamwork: analyzing the optimality and complexity of key theories and models, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544946]
• 15: S. Seuken and S. Zilberstein. Improved memory-bounded dynamic programming for decentralized POMDPs. In Proc. of Uncertainty in Artificial Intelligence, July 2007.
• 16: Matthijs T. J. Spaan , Francisco S. Melo, Interaction-driven Markov games for decentralized multiagent planning under uncertainty, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 17: D. Szer, F. Charpillet, and S. Zilberstein. MAA*: A heuristic search algorithm for solving decentralized POMDPs. In Proc. of Uncertainty in Artificial Intelligence, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
cooperative multiagent systems, decentralized POMDPs, planning under uncertainty