The performance of decision makers in many practical settings can be improved significantly by using new computational tools for coordination, prediction and planning. We are developing such tools for situations involving multiple decision makers operating over an extended period of time in either collaborative or adversarial domains. To address this challenge, we employ two formal models. A Decentralized Partially Observable Markov Decision Process (DEC-POMDP) is designed for collaborative systems in which all the decision makers share the same objective or utility function. A Partially Observable Stochastic Game (POSG) is a proper extension of a DEC-POMDP that is designed for competitive systems in which decision makers have separate, possibly conflicting, objectives. We have recently produced important new results regarding these two models. We have published the first complexity analysis of DEC-POMDPs and identified a taxonomy of sub-classes whose complexity ranges between polynomial and NEXP-hard. We are developing new exact dynamic programming algorithm for solving DEC-POMDPs and POSGs as well as a range of approximation schemes. We are also working on effective decision-theoretic techniques to model and exploit bounded rationality and opponent models in decentralized settings.

Related Publications

• Solving POMDPs Using Quadratically Constrained Linear Programs.
  C. Amato, D.S. Bernstein, and S. Zilberstein. Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, 2418-2424, Hyderabad, India, 2007. [abs] [pdf]

• Memory-Bounded Dynamic Programming for DEC-POMDPs.
  S. Seuken and S. Zilberstein. Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, 2009-2015, Hyderabad, India, 2007. [abs] [pdf]

• Learning to Communicate in a Decentralized Environment.
  C. V. Goldman, M. Allen, and S. Zilberstein. Autonomous Agents and Multi-Agent Systems, 2007. [abs] [pdf]

• Optimal Fixed-Size Controllers for Decentralized POMDPs.
  C. Amato, D.S. Bernstein, and S. Zilberstein. AAMAS 2006 Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains, Hakodate, Japan, May, 2006. [abs] [pdf]

• Analyzing Myopic Approaches for Multi-Agent Communication.
  R. Becker, V. Lesser, and S. Zilberstein. Proceedings of Intelligent Agent Technology, Compiègne, France, 2005. (Best Paper Award) [abs] [pdf]

• Bounded Policy Iteration for Decentralized POMDPs.
  D.S. Bernstein, E.A. Hansen, and S. Zilberstein. Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, 2005. [abs] [pdf]

• MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs.
  D. Szer, F. Charpillet, and S. Zilberstein. Proceedings of the Twenty First Conference on Uncertainty in Artificial Intelligence, Edinburgh, Scotland, 2005. [abs] [pdf]