Learning to Send Reinforcements: Coordinating Multi-Agent Dynamic Police Patrol Dispatching and Rescheduling via Reinforcement Learning

Waldy Joe, Hoong Chuin LauIJCAI 2023 · DOI

Introduction

In urban policing, patrol teams must balance two conflicting responsibilities: proactive deterrence through visible patrol and reactive response to emergency calls. When a dynamic incident occurs, dispatching a team creates a coverage gap in the original patrol schedule. This challenge, termed the Multi-Agent Dynamic Police Patrol Dispatching and Rescheduling Problem (MADPRP), is complicated by the need for inter-sector coordination and the computational difficulty of optimizing joint actions across many agents in real-time.

Researchers have developed a Multi-Agent Reinforcement Learning (MARL) framework that enables police sectors to coordinate reinforcements dynamically. By jointly learning dispatching and rescheduling policies, the system ensures rapid incident response without compromising overall patrol coverage.

Methodology: MAVFA-BR-H

The proposed framework, MAVFA-BR-H, integrates deep reinforcement learning with optimization heuristics through three core components:

  1. Multi-Agent Value Function Approximation (MAVFA): To manage scalability, the joint value function is factorized into individual sector-level value functions. Under the Individual Global Max (IGM) assumption, a global mixing network ensures that local optimizations contribute to a global optimum.
  2. Iterative Best Response (BR): A decentralized heuristic where agents take turns proposing responses to the global schedule. This prevents the "simultaneous action" trap, where uncoordinated agents might redundantly respond to the same incident or leave areas uncovered.
  3. Ejection Chain Heuristic (H): A "check-and-repair" algorithm that re-optimizes patrol routes when a team is dispatched, minimizing the impact on proactive patrol presence.
Architecture of the Multi-Agent Value Function Approximation (MAVFA) showing the mixing network used to coordinate local value functions.

Unlike traditional two-stage models that decide a dispatch first and then fix the schedule later, MAVFA-BR-H learns to do both jointly. This allows the agent to anticipate the long-term scheduling consequences of immediate dispatch decisions by evaluating the post-decision state.

Experimental Setup

The model was evaluated using a simulation based on the North-Central region of a real-world city-state, encompassing 3 police sectors and 62 patrol areas. Due to data sensitivity, synthetic data modeled on public sources was used to simulate incident frequencies and travel times. Each sector featured distinct operational characteristics, such as varying team-to-area ratios and incident densities, to test the model's robustness across diverse spatial distributions.

Key Results and Insights

The MAVFA-BR-H model demonstrated superior performance across multiple metrics compared to non-coordinated and myopic baselines.

Performance comparison of MAVFA-BR-H against baseline models, highlighting improvements in overall (O) and worst-case (W) success rates.

Coordination and Fairness

A key finding is that coordination significantly improves "fairness" across sectors. The success rate for the most resource-stressed sector (the "worst-agent") increased from 44.0% in the uncoordinated MAVFA-H model to 52.4% with MAVFA-BR-H. This synergy allows sectors to support one another during peak demand periods, effectively sharing the burden of high incident rates.

Operational Efficiency

Despite its complexity, the system remains viable for real-time use. Decisions are computed in approximately 24 seconds on average. While the value function approximation itself is nearly instantaneous, the majority of the computation time is spent on the iterative rescheduling heuristic, which ensures high-quality patrol coverage is maintained.

Structured Communication

The authors noted that explicit Iterative Best Response was more effective than implicit communication via neural networks. In high-stakes environments like policing, structured turn-taking in decision-making prevents the chaos associated with simultaneous, uncoordinated actions.

Conclusion and Future Work

While MAVFA-BR-H sets a new benchmark for dynamic dispatching, it remains dependent on the quality of the underlying Ejection Chain heuristic. Future research may explore more advanced neural architectures, such as Graph Neural Networks, to better capture urban spatial dependencies. Additionally, relaxing the IGM assumption could help address extreme edge cases of resource scarcity where sector goals might conflict.

Summary updated

BibTeX
@inproceedings{joe2023learning,
  author = {Waldy Joe and Hoong Chuin Lau},
  title = {{Learning to Send Reinforcements: Coordinating Multi-Agent Dynamic Police Patrol Dispatching and Rescheduling via Reinforcement Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/18},
}

Loading related content...

Figure