Publication - Offline Planning for Communication by Exploiting Structured Interactions in Decentralized MDPs

Authors: Mostafa, Hala; Lesser, Victor
Title: Offline Planning for Communication by Exploiting Structured Interactions in Decentralized MDPs
Abstract: Variants of the decentralized MDP model focus on problems exhibiting some special structure that makes them easier to solve in practice. Our work is concerned with two main issues. First, we propose a new model, Event-Driven Interaction with Complex Rewards, that addresses problems having structured transition and reward dependence. Our model captures a wider range of problems than existing structured models. In spite of its generality, the model still offers structure that can be leveraged by heuristics and solution algorithms. This is facilitated by explicitly representing interactions as first-class entities. We formulate and solve instances of our model as bilinear programs. Second, we look at making offline planning for communication tractable. To this end, we propose heuristics that limit problem size by making communication available only at a few strategically chosen points based on an analysis that exploits problem structure in the proposed model. Experimental results demonstrate a reduction in problem size and solution time using restricted communication, with little or no decrease in solution quality. Our heuristics therefore allow us to solve problems that would otherwise be intractable.
Keywords: Coordination, Distributed MDP, Multi-Agent Systems, Planning, Uncertainty
Publication: UMass Computer Science Technical Report 2009-020
Date: May 2009
Sources: PDF: http://mas.cs.umass.edu/~hmostafa/publications/TR2009.pdf
Reference: Mostafa, Hala; Lesser, Victor. Offline Planning for Communication by Exploiting Structured Interactions in Decentralized MDPs. UMass Computer Science Technical Report 2009-020. May 2009.
bibtex: 
@techreport{Mostafa-472,
  author    = "Hala Mostafa and Victor Lesser",
  title     = "{Offline Planning for Communication by Exploiting
               Structured Interactions in Decentralized MDPs}",
  month     = "May",
  year      = "2009",
  url       = "http://mas.cs.umass.edu/paper/472",
}