Keeping Pace with Criminals: An Extended Study of Designing Patrol Allocation against Adaptive Opportunistic Criminals

Chao Zhang, Shahrzad Gholami, Debarun Kar, Arunesh Sinha, Manish Jain, Ripple Goyal, Milind Tambe

TL;DR

This paper tackles the challenge of designing effective police patrol strategies against opportunistic criminals who adapt their behavior based on patrol presence. They introduce a novel framework that combines learning a dynamic model of criminal behavior with iterative planning, leading to significantly reduced crime rates compared to existing methods.

What Problem Does This Paper Address?

Urban crime is a pervasive issue, and a significant portion of it is opportunistic. Unlike strategic attackers who meticulously plan, opportunistic criminals are agile and adapt their actions based on perceived opportunities, particularly the presence or absence of police patrols. This dynamic and adaptive nature makes it difficult for law enforcement to design effective, static patrol strategies. Traditional methods of manual patrol planning are often time-consuming and ineffective, while purely automated approaches have struggled to accurately model and adapt to the evolving behavior of these criminals, especially when using real-world data. The core problem is how to create a patrol allocation system that can learn from observed criminal activity and dynamically adjust its strategy to stay ahead of adaptive criminals.

Methods

The authors propose a two-pronged approach: learning criminal behavior and then planning patrol strategies based on that learned behavior.

  1. Learning Criminal Behavior:
    • Markov Chain Models (MCM): Initially, they explore Markov chains to model crime as a function of past crime occurrences and defender (police) allocations. This includes models like "crime predicts crime" and how defender allocation influences crime.
  2. Dynamic Bayesian Network (DBN): A more sophisticated approach uses Dynamic Bayesian Networks to model the interaction between criminals and patrol officers. The key innovation here is treating the number of criminals as a hidden state, allowing the model to capture more nuanced dynamics.
  3. Compact DBN (EMC²): To address the computational complexity and overfitting issues of standard DBNs, they introduce a "compact" DBN model. This involves modifications like factoring the crime matrix and marginalizing hidden states, significantly reducing the number of parameters and improving learning speed and accuracy. They use the Expectation-Maximization (EM) algorithm for parameter estimation.
  4. Planning Patrol Strategies:
    • Iterative Learning and Planning: The core idea is to continuously update the criminal behavior model as new data becomes available and then re-plan the patrol strategy. This "online" approach allows the system to adapt to changes in criminal behavior.
  5. Dynamic Opportunistic Game Search (DOGS): A dynamic programming algorithm that finds the optimal patrol strategy for a given horizon by building upon solutions for shorter horizons.
  6. Greedy Search: A faster, though sub-optimal, algorithm that makes decisions one step at a time, optimizing for the immediate expected number of crimes.

Datasets

The primary dataset used for training and evaluation is real-world criminal activity and patrol data from the University of Southern California (USC) Department of Public Safety, spanning three years (2011-2013). This dataset includes crime reports (type, location, time) and patrol schedules. For simulation-based evaluations, they also utilize a criminal behavior model from a previous work on opportunistic criminals.

Key Insights and Ideas

  • Opportunistic Criminals are Key: The paper highlights that understanding and modeling the adaptive nature of opportunistic criminals is crucial for effective patrol design, moving beyond static or purely reactive strategies.
  • Hidden States Matter: Treating the number of criminals as a hidden state in a DBN provides a more powerful way to model their behavior than simply observing crime occurrences.
  • Compact Models for Efficiency: Standard DBNs are computationally prohibitive. The proposed "compact" DBN (EMC²) significantly reduces parameters and improves learning speed, making real-world application feasible.
  • Iterative Learning is Essential: Criminals adapt. Therefore, patrol strategies must also adapt. The iterative learning and planning mechanism is vital for "keeping pace" with evolving criminal behavior.
  • Real-World Data Validation: The use of actual USC crime data lends significant credibility to the proposed methods, demonstrating their practical applicability.

Key Results

  • Crime Reduction: The proposed approach, when applied to the USC dataset, projects a significant reduction in the crime rate, approximately ~50%, compared to the actual strategy deployed by the police department.
  • Improved Accuracy: The EMC² algorithm (compact DBN) consistently outperforms traditional Markov Chain models and the standard EM algorithm in terms of prediction accuracy for crime numbers.
  • Faster Learning: The EMC² algorithm is significantly faster than the standard EM algorithm, especially as the number of patrol areas increases.
  • Online Planning Effectiveness: The iterative online planning mechanism (both DOGS and Greedy) significantly outperforms a static, pure planning approach, especially when criminal behavior is dynamic.
  • Software Deployment: A web-based software for recommending patrol strategies, incorporating the learning and planning algorithms, is currently deployed at USC.

Limitations and Future Work

  • Model Simplifications: The current model assumes homogeneous criminals and does not explicitly model criminal payoffs or bounded rationality. Future work could explore more sophisticated criminal models.
  • Data Granularity: The current analysis primarily focuses on the number of crimes per area per shift, abstracting away from crime types. Future work could incorporate more detailed crime patterns (e.g., influenced by time of day, day of week, season, or specific events like football games).
  • Sensitivity Analysis: The authors suggest performing sensitivity analysis on how the dataset is divided (e.g., by season) to understand the robustness of their findings.
  • Integration: The planned integration of the learning and planning algorithms into the deployed USC software is a key next step.

Summary updated

Abstract

Game theoretic approaches have recently been used to model the deterrence effect of patrol officers’ assignments on opportunistic crimes in urban areas. One major challenge in this domain is modeling the behavior of opportunistic criminals. Compared to strategic attackers (such as terrorists) who execute a well-laid out plan, opportunistic criminals are less strategic in planning attacks and more flexible in executing well-laid plans based on their knowledge of patrol officers’ assignments. In this paper, we aim to design an optimal police patrolling strategy against opportunistic criminals in urban areas. Our approach is comprised by two major parts: learning a model of the opportunistic criminal (and how he or she responds to patrols) and then planning optimal patrols against this learned model. The planning part, by using information about how criminals responds to patrols, takes into account the strategic game interaction between the police and criminals. In more detail, first, we propose two categories of models for modeling opportunistic crimes. The first category of models learns the relationship between defender strategy and crime distribution as a Markov chain. The second category of models represents the interaction of criminals and patrol officers as a Dynamic Bayesian Network (DBN) with the number of criminals as the unobserved hidden states. To this end, we: (i) apply standard algorithms, such as Expectation Maximization (EM), to learn the parameters of the DBN; (ii) modify the DBN representation that allows for a compact representation of the model, resulting in better learning accuracy and the increased speed of learning of the EM algorithm when used for the modified DBN. These modifications exploit the structure of the problem and use independence assumptions to factorize the large joint probability distributions. Next, we propose an iterative learning and planning mechanism that periodically updates the adversary model. We demonstrate the efficiency of our learning algorithms by applying them to a real dataset of criminal activity obtained from the police department of the University of Southern California (USC) situated in Los Angeles, CA, USA. We project a significant reduction in crime rate using our planning strategy as compared to the actual strategy deployed by the police department. We also demonstrate the improvement in crime prevention in simulation when we use our iterative planning and learning mechanism when compared to just learning once and planning. Finally, we introduce a web-based software for recommending patrol strategies, which is currently deployed at USC. In the near future, our learning and planning algorithm is planned to be integrated with this software. This work was done in collaboration with the police department of USC.
BibTeX
@inproceedings{zhang2016keeping,
  author = {Chao Zhang and Shahrzad Gholami and Debarun Kar and Arunesh Sinha and Manish Jain and Ripple Goyal and Milind Tambe},
  title = {{Keeping Pace with Criminals: An Extended Study of Designing Patrol Allocation against Adaptive Opportunistic Criminals}},
  booktitle = {Games},
  year = {2016},
  url = {https://openreview.net/forum?id=1bbqATzLP9},
}
Figure