  We study a large-scale patrol problem with state-dependent costs and
multi-agent coordination.We consider heterogeneous agents, rather general
reward functions, and the capabilities of tracking agents' trajectories.Given
the complexity and uncertainty of the practical situations for patrolling, we
model the problem as a discrete-time Markov decision process (MDP) that
consists of a large number of parallel stochastic processes.We aim to minimize
the cumulative patrolling cost over a finite time horizon.The problem exhibits
an excessively large size of state space, which increases exponentially in the
number of agents and the size of geographical region for patrolling.To reach
practical solutions, we relax the dependencies between these parallel
stochastic processes by randomizing all the state and action variables.In this
context, the entire problem can be decomposed into a number of sub-problems,
each of which has a much smaller state space and can be solved independently.
The solutions of these sub-problems can lead to efficient heuristics.Unlike the
past systems assuming relatively simple structure of the underlying stochastic
process, here, tracking the patrol trajectories involves strong dependencies
between the stochastic processes, leading to entirely different state and
action spaces, transition kernels, and behaviours of processes,rendering the
existing methods inapplicable or impractical.Further more, we prove that the
performance deviation between the proposed policies and the possible optimal
solution diminishes exponentially in the problem size, which also establishes
the fact that the policies converge asymptotically at an exponential rate.
