Conference Proceeding Article
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.
Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
International Joint Conference on Artificial Intelligence (IJCAI)
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. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/2211