# Patrol Security Game: Defending Against Adversary with Freedom in Attack Timing, Location, and Duration

arXiv: https://arxiv.org/abs/2410.15600 · HTML: https://mlsanity.com/paper/2410.15600/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 92 references that are in the map.
- First posted on arXiv 21 Oct 2024.

## Builds on (most cited first, 19 of 19)

- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [Deep Reinforcement Learning for Autonomous Internet of Things: Model, Applications and Challenges](https://mlsanity.com/paper/1907.09059/) (2019)
- [Delay-Aware Model-Based Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/2005.05440/) (2020)
- [A Dynamic Games Approach to Proactive Defense Strategies against Advanced Persistent Threats in Cyber-Physical Systems](https://mlsanity.com/paper/1906.09687/) (2019)
- [Multi-Robot Adversarial Patrolling: Facing a Full-Knowledge Opponent](https://mlsanity.com/paper/1401.3903/) (2014)
- [Adversarial patrolling with spatially uncertain alarm signals](https://mlsanity.com/paper/1506.02850/) (2015)
- [Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency](https://mlsanity.com/paper/2005.02530/) (2020)
- [Finding Diverse Trees, Paths, and More](https://mlsanity.com/paper/2009.03687/) (2020)
- [A Robust Stackelberg Game for Cyber-Security Investment in Networked Control Systems](https://mlsanity.com/paper/2103.16611/) (2021)
- [Markov Chains with Maximum Return Time Entropy for Robotic Surveillance](https://mlsanity.com/paper/1803.07705/) (2018)
- [Obtaining Approximately Optimal and Diverse Solutions via Dispersion](https://mlsanity.com/paper/2202.10028/) (2022)
- [On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem](https://mlsanity.com/paper/2203.07280/) (2022)
- [Stochastic Strategies for Robotic Surveillance as Stackelberg Games](https://mlsanity.com/paper/2011.07604/) (2020)
- [The Effect of Behavioral Probability Weighting in a Simultaneous Multi-Target Attacker-Defender Game](https://mlsanity.com/paper/2103.03392/) (2021)
- [Multi-defender Security Games with Schedules](https://mlsanity.com/paper/2311.16392/) (2023)

## Abstract (arXiv)

We explored the Patrol Security Game (PSG), a robotic patrolling problem modeled as an extensive-form Stackelberg game, where the attacker determines the timing, location, and duration of their attack. Our objective is to devise a patrolling schedule with an infinite time horizon that minimizes the attacker's payoff. We demonstrated that PSG can be transformed into a combinatorial minimax problem with a closed-form objective function. By constraining the defender's strategy to a time-homogeneous first-order Markov chain (i.e., the patroller's next move depends solely on their current location), we proved that the optimal solution in cases of zero penalty involves either minimizing the expected hitting time or return time, depending on the attacker model, and that these solutions can be computed efficiently. Additionally, we observed that increasing the randomness in the patrol schedule reduces the attacker's expected payoff in high-penalty cases. However, the minimax problem becomes non-convex in other scenarios. To address this, we formulated a bi-criteria optimization problem incorporating two objectives: expected maximum reward and entropy. We proposed three graph-based algorithms and one deep reinforcement learning model, designed to efficiently balance the trade-off between these two objectives. Notably, the third algorithm can identify the optimal deterministic patrol schedule, though its runtime grows exponentially with the number of patrol spots. Experimental results validate the effectiveness and scalability of our solutions, demonstrating that our approaches outperform state-of-the-art baselines on both synthetic and real-world crime datasets.