Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximations
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
@inproceedings{ijcai2009p43,
title = {Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximations},
author = {Kumar, Akshat and Zilberstein, Shlomo},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {201--206},
year = {2009},
url = {https://ijcai.org/proceedings/2009/43},
}
TY - CPAPER TI - Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximations AU - Kumar, Akshat AU - Zilberstein, Shlomo T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 201 EP - 206 UR - https://ijcai.org/proceedings/2009/43 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
