Strategic Coordination of Human Patrollers and Mobile Sensors With Signaling for Security Games

Authors

  • Haifeng Xu University of Southern California
  • Kai Wang University of Southern California
  • Phebe Vayanos University of Southern California
  • Milind Tambe University of Southern California

Keywords:

Security Games, Sensors, Signaling, Deception

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' 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 zero-sum cases and serves as a useful heuristic for general-sum SEGs. Our experiments demonstrate the significant benefit of utilizing mobile sensors.

Downloads

Published

2018-04-25

How to Cite

Xu, H., Wang, K., Vayanos, P., & Tambe, M. (2018). Strategic Coordination of Human Patrollers and Mobile Sensors With Signaling for Security Games. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11447

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms