Scalable Randomized Patrolling for Securing Rapid Transit Networks

Pradeep Varakantham, Hoong Chuin Lau, Zhi YuanIAAI 2013 · DOI

TL;DR

This paper introduces RaPtoR, a novel algorithm for scheduling randomized patrols in large-scale mass rapid transit (MRT) networks. By combining game theory with practical constraints, RaPtoR generates efficient patrol plans that adapt to potential criminal activity, offering a scalable solution for enhancing public safety in complex urban environments.

What Problem Does This Paper Address?

Mass Rapid Transit (MRT) systems are vital for urban mobility, but their sheer size and constant usage make them attractive targets for criminals. Traditional security approaches struggle to cover all stations effectively due to resource limitations. Existing research has explored game theory, particularly Stackelberg games, to model these adversarial scenarios, where a defender (patrols) plans against an attacker (criminals). However, these methods often falter when dealing with the massive scale of real-world MRT networks, which involve numerous stations, complex transfer possibilities, and dynamic passenger flow. This paper tackles the challenge of creating scalable, randomized patrol schedules for these extensive networks, ensuring optimal coverage while minimizing patrol travel time and accounting for practical constraints like team breaks.

Methods

The core of the paper's contribution lies in its two-phase approach, RaPtoR:

  • Phase 1: Computing SSE Coverage: This phase formulates the problem as a Stackelberg game. It uses an Integer Linear Program (ILP) to compute "coverage vectors" for each decision epoch (time interval). These vectors represent the probability of a station being covered by a patrol. The goal is to find a Strong Stackelberg Equilibrium (SSE), which guarantees optimal randomized strategies for the defender against an intelligent adversary. This phase is designed to be scalable and handles the complexities of MRT networks.
  • Phase 2: Computing Execution Plans: This phase translates the probabilistic coverage from Phase 1 into concrete patrol schedules. It uses a dynamic programming algorithm to "stitch" together coverage samples from adjacent decision epochs. The key innovation here is a mixed-integer optimization model that minimizes the maximum travel distance for any patrol team, ensuring that patrols spend more time securing stations and less time traveling. This phase also incorporates practical constraints like team breaks and the requirement that a patrol team cannot visit the same station twice within a shift.

Datasets

The authors evaluate their approach using real-world data from the Singapore MRT system. This dataset includes:

  • A map of 108 stations spread across seven lines, with 11 transfer stations.
  • Passenger usage statistics for each station over a 19-hour period each day, reflecting the dynamic risk profile of different locations at different times.

This real-world data allows for a realistic assessment of the algorithm's scalability and effectiveness in a complex, large-scale operational environment.

Key Insights and Ideas

  • Randomization is Key: The paper strongly advocates for randomized patrol strategies. This is crucial because deterministic patrols can be predicted and exploited by intelligent adversaries. SSE provides a robust framework for achieving this optimal randomization.
  • Scalability through Two-Phase Approach: The separation into coverage computation (Phase 1) and execution plan generation (Phase 2) is critical for scalability. Phase 1 determines the probabilities, and Phase 2 uses these probabilities to generate practical routes, allowing the system to handle large networks where a single, monolithic optimization would be intractable.
  • Balancing Coverage and Travel Time: A significant insight is the need to explicitly optimize for minimizing travel distance in Phase 2. This directly translates to more efficient resource utilization and better station coverage, a practical concern for any security operation.
  • Handling Real-World Constraints: The paper's success hinges on its ability to incorporate realistic constraints like patrol team breaks and non-revisiting rules within a shift, moving beyond purely theoretical models.

Key Results

  • Scalability Demonstrated: The RaPtoR algorithm shows impressive scalability. For the Singapore MRT network (78 stations, 35 resources, 8-12 hour horizons), Phase 1 and Phase 2 computations complete in under 4 seconds. Even with larger networks (up to 180 stations), the total runtime for both phases remains under 10 seconds.
  • Efficient Travel Times: The generated patrol plans result in average travel times between adjacent targets of less than 15 minutes, a practical and desirable outcome.
  • Coverage Improvement: Even with a limited number of samples (100), the coverage obtained for targets increases with more patrol resources, indicating the algorithm's effectiveness.
  • Robustness to Attack Assumptions: The algorithm's performance is shown to be largely independent of specific assumptions about when attacks might occur.

Limitations and Future Work

  • Breaks and Non-Adjacent Constraints: While the paper discusses accounting for breaks, the detailed implementation and its impact on optimality are presented as an area for further work. Specifically, ensuring breaks are not adjacent and managing the complexity of these constraints in Phase 2 requires further refinement.
  • Optimality with Constraints: The paper acknowledges that Phase 2 is not guaranteed to be optimal when complex constraints spanning non-adjacent epochs (like break scheduling) are present. However, it still provides better plans as resources increase.
  • Decision Support System: The authors have developed a patrol scheduler as a decision support system, hinting at future deployment and refinement based on real-world operational feedback.
  • Further Experimental Validation: While initial experiments are promising, more extensive testing with varying attack scenarios and network configurations would be beneficial.

Summary updated

BibTeX
@inproceedings{varakantham2013scalable,
  author = {Pradeep Varakantham and Hoong Chuin Lau and Zhi Yuan},
  title = {{Scalable Randomized Patrolling for Securing Rapid Transit Networks}},
  booktitle = {IAAI},
  year = {2013},
  doi = {10.1609/aaai.v27i2.19002},
}
Figure