@conference {1504349,
	title = {Adversarial Patrolling Games },
	booktitle = {AAAI Spring Symposium on Security, Sustainability and Health},
	year = {2012},
	abstract = {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{\textquoteright}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{\textquoteright}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.},
	author = {Vorobeychik, Yevgeniy and An, Bo and Tambe, Milind}
}
