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

• Main Authors: KUMAR, Akshat, Zilberstein, S.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2009
• Subjects: Artificial Intelligence and Robotics; Business; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/2211; https://ink.library.smu.edu.sg/context/sis_research/article/3211/viewcontent/Event_Detecting_Multi_Agent_MDPs__Complexity_and_Constant_Factor_Approximation.pdf
• Institution: Singapore Management University

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.