Publications

Adversarial patrolling games

Vorobeychik, Yevgeniy V.; An, Bo; Tambe, Milind

Defender-Attacker Stackelberg games are the foundations of tools deployed for computing optimal patrolling strategies in adversarial domains such as the United states Federal Air Marshals Service and the United States Coast Guard, among others. In Stackelberg game models of these systems the attacker knows only the probability that each target is covered by the defender, but is oblivious to the detailed timing of the coverage schedule. In many real-world situations, however, the attacker can observe the current location of the defender and can exploit this knowledge to reason about the defender's future moves. We study Stackelberg security games in which the defender sequentially moves between targets, with moves constrained by an exogenously specified graph, while the attacker can observe the defender's current location and his (stochastic) policy concerning future moves. We offer five contributions: (1) We model this adversarial patrolling game (APG) as a stochastic game with special structure and present several alternative formulations that leverage the general nonlinear programming (NLP) approach for computing equilibria in zero-sum stochastic games. We show that our formulations yield significantly better solutions than previous approaches. (2) We extend the NLP formulation for APG allow for attacks that may take multiple time steps to unfold. (3) We provide an approximate MILP formulation that uses discrete defender move probabilities. (4) We experimentally demonstrate the efficacy of an NLP-based approach, and systematically study the impact of network topology 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. Copyright © 2012, Association for the Advancement of Artificial Intelligence. All rights reserved.