Publication - A Compact Mathematical Formulation For Problems With Structured Agent Interactions

Authors: Mostafa, Hala; Lesser, Victor
Title: A Compact Mathematical Formulation For Problems With Structured Agent Interactions
Abstract: The general problem of calculating policies in decentralized POMDPs is known to be NEXP-complete. One way of dealing with this prohibitive complexity is identifying a subclass of the general problem that is more tractable to solve, but still of practical interest. One such sub-class consists of problems exhibiting structured transition and reward interactions among agents, and is modeled using Event-Driven Interactions with Complex Rewards (EDI-CR). In this paper, we propose a Mixed Integer Linear Program formulation of EDI-CR instances. The key insight we use is that from one agent perspective, most action sequences of another agent have the same effect, thereby allowing us to treat them similarly and use fewer variables in the formulation. Experimental results show that our formulation is more compact, and leads to faster solution times, than formulations ignoring the structure of interactions.
Keywords: Coordination, Distributed MDP, MDP, Multi-Agent Systems, Uncertainty
Publication: Proceedings of the Multi-Agent Sequential Decision Making Workshop, International Conference on Autonomous Agents and Multi-agent Systems, pp. 55 - 62
Location: Taiwan
Date: 2011
Sources: PDF: /Documents/mostafamsdm11.pdf
Reference: Mostafa, Hala; Lesser, Victor. A Compact Mathematical Formulation For Problems With Structured Agent Interactions. Proceedings of the Multi-Agent Sequential Decision Making Workshop, International Conference on Autonomous Agents and Multi-agent Systems, pp. 55-62. 2011.
bibtex: 
@inproceedings{Mostafa-506,
  author    = "Hala Mostafa and Victor Lesser",
  title     = "{A Compact Mathematical Formulation For Problems
               With Structured Agent Interactions}",
  booktitle = "Proceedings of the Multi-Agent Sequential Decision
               Making Workshop, International Conference on
               Autonomous Agents and Multi-agent Systems",
  pages     = "55-62",
  year      = "2011",
  address   = "Taiwan",
  url       = "http://mas.cs.umass.edu/paper/506",
}