@conference {1500419,
	title = {Strategic Coordination of Human Patrollers and Mobile Sensors with Signaling for Security Games },
	booktitle = {AAAI conference on Artificial Intelligence (AAAI-18)},
	year = {2018},
	abstract = {Traditional security games concern the optimal randomized
allocation of human patrollers, who can directly catch attackers or interdict attacks. Motivated by the emerging application of utilizing mobile sensors (e.g., UAVs) for patrolling,
in this paper we propose the novel Sensor-Empowered security Game (SEG) model which captures the joint allocation
of human patrollers and mobile sensors. Sensors differ from
patrollers in that they cannot directly interdict attacks, but
they can notify nearby patrollers (if any). Moreover, SEGs
incorporate mobile sensors{\textquoteright} natural functionality of strategic
signaling. On the technical side, we first prove that solving
SEGs is NP-hard even in zero-sum cases. We then develop
a scalable algorithm SEGer based on the branch-and-price
framework with two key novelties: (1) a novel MILP formulation for the slave; (2) an efficient relaxation of the problem
for pruning. To further accelerate SEGer, we design a faster
combinatorial algorithm for the slave problem, which is provably a constant-approximation to the slave problem in zerosum cases and serves as a useful heuristic for general-sum
SEGs. Our experiments demonstrate the significant benefit of
utilizing mobile sensors.},
	author = {Haifeng Xu and Kai Wang and Vayanos, Phebe and Tambe, Milind}
}
