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", } |