Publication - Decentralized Markov Decision Processes with Event-Driven Interactions

Authors: Becker, Raphen; Lesser, Victor; Zilberstein, Shlomo
Title: Decentralized Markov Decision Processes with Event-Driven Interactions
Abstract: Decentralized MDPs provide a powerful formal framework for planning in multi-agent systems, but the complexity of the model limits its usefulness. We study in this paper a class of DEC-MDPs that restricts the interactions between the agents to a structured, event-driven dependency. These dependencies can model locking a shared resource or temporal enabling constraints, both of which arise frequently in practice. The complexity of this class of problems is shown to be no harder than exponential in the number of states and doubly exponential in the number of dependencies. Since the number of dependencies is much smaller than the number of states for many problems, this is significantly better than the doubly exponential (in the state space) complexity of DEC-MDPs. We also demonstrate how an algorithm we previously developed can be used to solve problems in this class both optimally and approximately. Experimental work indicates that this solution technique is significantly faster than a naive policy search approach.
Keywords: Coordination, Distributed MDP, TAEMS
Publication: The Third International Joint Conference on Autonomous Agents and Multi Agent Systems, Vol: 1, pp. 302 - 309
Location: NYC
Publisher: IEEE Computer Society
Date: 2004
Sources: PDF: /Documents/p302.pdf
Reference: Becker, Raphen; Lesser, Victor; Zilberstein, Shlomo. Decentralized Markov Decision Processes with Event-Driven Interactions. The Third International Joint Conference on Autonomous Agents and Multi Agent Systems, Volume 1, IEEE Computer Society, pp. 302-309. 2004.
bibtex: 
@inproceedings{Becker-364,
  author    = "Raphen Becker and Victor Lesser and Shlomo
               Zilberstein",
  title     = "{Decentralized Markov Decision Processes with
               Event-Driven Interactions}",
  booktitle = "The Third International Joint Conference on
               Autonomous Agents and Multi Agent Systems",
  volume    = "1",
  publisher = "IEEE Computer Society",
  pages     = "302-309",
  year      = "2004",
  address   = "NYC",
  url       = "http://mas.cs.umass.edu/paper/364",
}