Publication - Solving Transition Independent Decentralized Markov Decision Processes

Authors: Becker, Raphen; Zilberstein, Shlomo; Lesser, Victor; Goldman, Claudia V
Title: Solving Transition Independent Decentralized Markov Decision Processes
Abstract: Formal treatment of collaborative multi-agent systems has been lagging behind the rapid progress with sequential decision making by individual agents. Recent work on decentralized Markov decision processes (MDPs) has contributed to closing this gap, but the computational complexity of the model remains a serious obstacle. To overcome this complexity barrier, we identify a general class of transition independent decentralized MDPs that is widely applicable. The class consists of independent collaborating agents that are tied together through a global reward function that depends on all of their histories. We present a novel algorithm for solving this class of problems and examine its properties, both as an optimal algorithm and as an anytime algorithm. The result is the first effective technique to solve optimally a large class of decentralized MDPs. This lays the foundation for further work in this area on both exact and approximate algorithms.
Keywords: Agent Control, Distributed MDP, Multi-Agent Systems
Publication: Journal of Artificial Intelligence Research, Vol: 22, pp. 423 - 455
Publisher: Morgan Kaufmann Publishers
Date: December 2004
Sources: PDF: http://mas.cs.umass.edu/~raphen/Papers/JAIR-04/becker_JAIR-04.pdf
PDF: /Documents/raphen/JAIR-04/becker_JAIR-04.pdf
Reference: Becker, Raphen; Zilberstein, Shlomo; Lesser, Victor; Goldman, Claudia V. Solving Transition Independent Decentralized Markov Decision Processes. Journal of Artificial Intelligence Research, Volume 22, Morgan Kaufmann Publishers, pp. 423-455. December 2004.
bibtex: 
@article{Becker-368,
  author    = "Raphen Becker and Shlomo Zilberstein and Victor
               Lesser and Claudia V Goldman",
  title     = "{Solving Transition Independent Decentralized
               Markov Decision Processes}",
  journal   = "Journal of Artificial Intelligence Research",
  volume    = "22",
  publisher = "Morgan Kaufmann Publishers",
  pages     = "423-455",
  month     = "December",
  year      = "2004",
  url       = "http://mas.cs.umass.edu/paper/368",
}