---
title: "Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximations"
authors:
  - "Akshat Kumar"
  - "Shlomo Zilberstein"
doi: ""
url: "https://ijcai.org/proceedings/2009/43"
pdf: "https://ijcai.org/proceedings/2009/0043.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "201-206"
track: ""
keywords:
---

# Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximations

Akshat Kumar, Shlomo Zilberstein

*Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence*, pages 201-206.

## Abstract

Planning under uncertainty for multiple agents has flourished with the development of formal models such as multi-agent MDPs and decentralized MDPs. Despite their richness, 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. Its complexity 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 nearoptimal policies for a range of test problems.Akshat Kumar, Shlomo Zilberstein