Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
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.
Discipline
Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering
Publication
International Joint Conference on Artificial Intelligence (IJCAI)
First Page
201
Last Page
207
Citation
KUMAR, Akshat and Zilberstein, S..
Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximation. (2009). International Joint Conference on Artificial Intelligence (IJCAI). 201-207.
Available at: https://ink.library.smu.edu.sg/sis_research/2211
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Included in
Artificial Intelligence and Robotics Commons, Business Commons, Operations Research, Systems Engineering and Industrial Engineering Commons