Proceedings

Efficient Planning for Factored Infinite-Horizon DEC-POMDPs

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 325-330.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-064

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

Decentralized partially observable Markov decision processes (DEC-POMDPs) are used to plan policies for multiple agents that must maximize a joint reward function but do not communicate with each other. The agents act under uncertainty about each other and the environment. This planning task arises in optimization of wireless networks, and other scenarios where communication between agents is restricted by costs or physical limits. DEC-POMDPs are a promising solution, but optimizing policies quickly becomes computationally intractable when problem size grows. Factored DEC-POMDPs allow large problems to be described in compact form, but have the same worst case complexity as non-factored DEC-POMDPs. We propose an efficient optimization algorithm for large factored infinite-horizon DEC-POMDPs. We formulate expectation-maximization based optimization into a new form, where complexity can be kept tractable by factored approximations. Our method performs well, and it can solve problems with more agents and larger state spaces than state of the art DEC-POMDP methods. We give results for factored infinite-horizon DEC-POMDP problems with up to 10 agents.

  1. [Allen and Zilberstein, 2009] M. Allen and S. Zilberstein. Complexity of decentralized control: Special cases. In Advances in Neural Information Processing Systems 22, pages 19-27, 2009.
  2. [Amato et al., 2007] C. Amato, D. Bernstein, and S. Zilber- stein. Optimizing Memory-Bounded Controllers for De- centralized POMDPs. In Proc. of 23rd UAI, pages 1-8. AUAI Press, 2007.
  3. [Bernstein et al., 2005] D.S. Bernstein, E.A. Hansen, and S. Zilberstein. Bounded policy iteration for decentralized POMDPs. In Proc. of 19th IJCAI, pages 1287-1292. IJCAI
  4. Mor- gan Kaufmann, 2005.
  5. [Boyen and Koller, 1998] X. Boyen and D. Koller. Tractable Inference for Complex Stochastic Processes. In Proc. of 14th UAI, volume 98, pages 33-42.
  6. Morgan Kaufmann, 1998.
  7. [Boyen and Koller, 1999] X. Boyen and D. Koller. Exploit- ing the architecture of dynamic systems. In Proc. of 16th Nat. Conf. on AI, pages 313-320. The AAAI Press, 1999.
  8. [Kumar and Zilberstein, 2010a] A. Kumar and S. Zilber- stein. Anytime Planning for Decentralized POMDPs using Expectation Maximization. In Proc. of 26th UAI, 2010.
  9. [Kumar and Zilberstein, 2010b] A. Kumar and S. Zilber- stein. Point-Based Backup for Decentralized POMDPs: Complexity and New Algorithms. In Proc. of 9th AAMAS, pages 1315-1322. IFAAMAS, 2010.
  10. [Murphy, 2002] Kevin Murphy. Dynamic Bayesian Net- works: Representation, Inference and Learning. PhD the- sis, University of California, Berkeley, 2002.
  11. [Oliehoek et al., 2008] F.A. Oliehoek, M.T.J. Spaan, S. Whiteson, and N. Vlassis. Exploiting locality of interaction in factored DEC-POMDPs. In Proc. of 7th AAMAS, volume 1, pages 517-524. IFAAMAS, 2008.
  12. [Oliehoek, 2010] Frans A. Oliehoek. Value-Based Planning for Teams of Agents in Stochastic Partially Observable En- vironments. PhD thesis, Informatics Institute, University of Amsterdam, February 2010.
  13. [Pajarinen et al., 2010] J. Pajarinen, J. Peltonen, A. Hot- tinen, and M. Uusitalo. Efficient Planning in Large POMDPs through Policy Graph Based Factorized Approx- imations. In Proc. of ECMLPKDD 2010, volume 6323, pages 1-16. Springer, 2010.
  14. [Szer and Charpillet, 2005] D. Szer and F. Charpillet. An op- timal best-first search algorithm for solving infinite hori- zon DEC-POMDPs. Proc. of 16th ECML, pages 389-399, 2005.
  15. [Toussaint et al., 2006] M. Toussaint, S. Harmeling, and A. Storkey. Probabilistic inference for solving (PO)MDPs. Technical report, University of Edinburgh, 2006.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards