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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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