@conference {1502897,
	title = {Computing Solutions in Infinite-Horizon Discounted Adversarial Patrolling Game },
	booktitle = {International Conference on Automated Planning and Scheduling (ICAPS)},
	year = {2014},
	abstract = {Stackelberg games form the core of a number of tools deployed for computing optimal patrolling strategies in adversarial domains, such as the US Federal Air Marshall Service
and the US Coast Guard. In traditional Stackelberg security
game models 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 show that this general modeling framework can be captured using adversarial
patrolling games (APGs) in which the defender sequentially
moves between targets, with moves constrained by a graph,
while the attacker can observe the defender{\textquoteright}s current location
and his (stochastic) policy concerning future moves. We offer a very general model of infinite-horizon discounted adversarial patrolling games. Our first contribution is to show that
defender policies that condition only on the previous defense
move (i.e., Markov stationary policies) can be arbitrarily suboptimal for general APGs. We then offer a mixed-integer nonlinear programming (MINLP) formulation for computing optimal randomized policies for the defender that can condition on history of bounded, but arbitrary, length, as well as
a mixed-integer linear programming (MILP) formulation to
approximate these, with provable quality guarantees. Additionally, we present a non-linear programming (NLP) formulation for solving zero-sum APGs. We show experimentally
that MILP significantly outperforms the MINLP formulation,
and is, in turn, significantly outperformed by the NLP specialized to zero-sum games.},
	author = {Y. Vorobeychik and B. An and M. Tambe and S. Singh}
}
