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.