Coordinated Multiagent Patrolling With State-Dependent Cost Rates: Asymptotically Optimal Policies for Large-Scale Systems

• 成果类型: Article
• 署名作者: Fu, Jing; Wang, Zengfu; Chen, Jie
• 署名单位: Royal Melbourne Institute of Technology (RMIT); Northwestern Polytechnical University; Northwestern Polytechnical University; City University of Hong Kong
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2024.3517326
• 发表日期: 2025
• 页码: 3800-3815
• 关键词: costs; Stochastic processes; trajectory; sensors; HISTORY; monitoring; indexes; uncertainty; Thermal sensors; STANDARDS; Asymptotic Optimality; multi-agent patrolling; restless bandit

摘要

We study a large-scale patrol problem with state-dependent costs and multiagent coordination. We consider heterogeneous agents, rather general reward functions, and the capabilities of tracking agents' trajectories. We model the problem as a discrete-time Markov decision process consisting of parallel stochastic processes. The problem exhibits an excessively large state space, which increases exponentially in the number of agents and the size of patrol region. By randomizing all the action variables, we relax and decompose the problem into multiple subproblems, each of which can be solved independently and lead to scalable heuristics applicable to the original problem. Unlike the past studies assuming relatively simple structures of the underlying stochastic process, here, tracking the patrol trajectories involves stronger dependencies between the stochastic processes, leading to entirely different state and action spaces and transition kernels, rendering the existing methods inapplicable or impractical. Furthermore, we prove that the performance deviation between the proposed policies and optimality diminishes exponentially in the problem size.