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

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.