Adversarial Patrolling Games

Defender-Attacker Stackelberg games are the foundations of toolsdeployed for computing optimal patrolling strategies in adversarialdomains such as the United states Federal Air Marshals Service and the UnitedStates Coast Guard, among others.In Stackelberg game models of these systems the attacker knows only theprobability that each target is covered by the defender, but isoblivious to the detailed timing of the coverage schedule.In many real-world situations, however, the attacker can observe thecurrent location of the defender and can exploit this knowledge toreason about the defender's future moves.We study Stackelberg security games in which the defender sequentiallymoves between targets, with moves constrained by an exogenouslyspecified graph, while the attacker can observe the defender's currentlocation and his (stochastic) policy concerning future moves. We offerfive contributions: (1) We model this adversarial patrolling game (APG) as a stochastic game with special structure and presentseveral alternative formulations that leverage the general non-linearprogramming (NLP) approach for computing equilibria in zero-sumstochastic games. We show that our formulations yield significantlybetter solutions than previous approaches. (2) We extend theNLP formulation for APG allow for attacks that may take multiple timesteps to unfold.(3) We provide anapproximate MILP formulation that uses discrete defender moveprobabilities. (4) We experimentally demonstrate the efficacy of anNLP-based approach, and systematically study the impact of networktopology on the results.(5) We extend our model to allow the defender to construct the graph constraining his moves, at some cost, and offer novel algorithms for this setting, finding that a MILP approximation is much more effective than the exact NLP in this setting.