A Deployed Quantal Response Based Patrol Planning System for the US Coast Guard


B. An, E. Shieh, R. Yang, M. Tambe, C. Baldwin, J. DiRenzo, B. Maule, and G. Meyer. 2013. “A Deployed Quantal Response Based Patrol Planning System for the US Coast Guard .” In Interfaces, 43, 5, Pp. 400-420.


In this paper we describe the model, theory developed and deployment of PROTECT, a game-theoretic system in use by the United States Coast Guard (USCG) in the Port of Boston for scheduling patrols. The USCG evaluated the deployment of PROTECT in the Port of Boston as a success and is currently evaluating the system in the Port of New York, with the potential for nationwide deployment. The PROTECT system is premised on an attacker-defender Stackelberg game model but its development and implementation required both theoretical contributions and detailed evaluations. In this paper we describe the work required in the deployment which we group into five key innovations. First, we propose a compact representation of the defender’s strategy space, by exploiting equivalence and dominance, that makes PROTECT efficient enough to solve real world sized problems. Second, this system does not assume that adversaries are perfectly rational, a regular assumption in previous game theoretic models for security. Instead, PROTECT relies on a quantal response (QR) model of the adversary’s behavior — to the best of our knowledge, this is the first real-world deployment of a QR model. Third, we develop specialized solution algorithms that are able to solve this problem for real-world instances and give theoretical guarantees. Fourth, our experimental results illustrate that PROTECT’s QR model handles real-world uncertainties more robustly than a perfect rationality model. Finally, this paper presents real-world evaluation of PROTECT by: (i) a comparison of human-generated vs PROTECT security schedules, and (ii) results from an Adversarial Perspective Team’s (human mock attackers) analysis.
See also: 2013