Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximation

Akshat Kumar and Shlomo Zilberstein. Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximation. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI), 201-207, Pasadena, California, 2009.

Abstract

Planning under uncertainty for multiple agents has grown rapidly with the development of formal models such as multi-agent MDPs and decentralized MDPs. But despite their richness, the applicability of these models remains limited due to their computational complexity. We present the class of event-detecting multi-agent MDPs (eMMDPs), designed to detect multiple mobile targets by a team of sensor agents. We show that eMMDPs are NP-Hard and present a scalable 2-approximation algorithm for solving them using matroid theory and constraint optimization. The complexity of the algorithm is linear in the state-space and number of agents, quadratic in the horizon, and exponential only in a small parameter that depends on the interaction among the agents. Despite the worst-case approximation ratio of 2, experimental results show that the algorithm produces near-optimal policies for a range of test problems.

Bibtex entry:

@inproceedings{KZijcai09,
  author	= {Akshat Kumar and Shlomo Zilberstein},
  title		= {Event-Detecting Multi-Agent {MDP}s: Complexity and Constant-Factor
                   Approximation},
  booktitle     = {Proceedings of the Twenty-First International Joint Conference on
                   Artificial Intelligence},
  year		= {2009},
  pages		= {201-207},
  address       = {Pasadena, California},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/KZijcai09.html}
}

shlomo@cs.umass.edu