A Deployed Quantal Response-Based Patrol Planning System for the U.S. Coast Guard

被引:46
作者
An, Bo [1 ]
Ordonez, Fernando [1 ,2 ]
Tambe, Milind [1 ]
Shieh, Eric [1 ]
Yang, Rong [1 ]
Baldwin, Craig [3 ]
DiRenzo, Joseph, III [4 ]
Moretti, Kathryn [4 ]
Maule, Ben [5 ]
Meyer, Garrett [6 ]
机构
[1] Univ So Calif, Los Angeles, CA 90089 USA
[2] Univ Chile, Dept Ind Engn, Santiago, RM, Chile
[3] US Coast Guard, New London, CT 06320 USA
[4] US Coast Guard, Portsmouth, VA 23704 USA
[5] US Coast Guard, Los Angeles, CA 90045 USA
[6] US Coast Guard, Seattle, WA 98174 USA
关键词
game theory; security; applications; Stackelberg games; EQUILIBRIA; SECURITY; MODELS;
D O I
10.1287/inte.2013.0700
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we describe the model, theory developed, and deployment of PROTECT, a game-theoretic system that the United States Coast Guard (USCG) uses to schedule patrols in the Port of Boston. The USCG evaluated PROTECT's deployment 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. PROTECT is premised on an attacker-defender Stackelberg game model; however, its development and implementation required both theoretical contributions and detailed evaluations. 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, to make PROTECT efficient enough to solve real-world sized problems. Second, this system does not assume that adversaries are perfectly rational, a typical assumption in previous game-theoretic models for security. Instead, PROTECT relies on a quantal response (QR) model of the adversary's behavior. We believe this is the first real-world deployment of a QR model. Third, we develop specialized solution algorithms that can 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, we present (1) a comparison of human-generated and PROTECT security schedules, and (2) results of an evaluation of PROTECT from an analysis by human mock attackers.
引用
收藏
页码:400 / 420
页数:21
相关论文
共 53 条
[1]  
Agmon N., 2008, P 7 INT JOINT C AUTO, V1, P55
[2]  
Agmon N, 2009, 21ST INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI-09), PROCEEDINGS, P1811
[3]  
An B., 2011, Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI), P587
[4]  
An B, 2011, P AAAI SPRING S HELP, P8
[5]   GUARDS and PROTECT: Next Generation Applications of Security Games [J].
An, Bo ;
Pita, James ;
Shieh, Eric ;
Tambe, Milind ;
Kiekintveld, Chris ;
Marecki, Janusz .
ACM SIGECOM EXCHANGES, 2011, 10 (01) :31-34
[6]  
An Bo, 2012, P 26 AAAI C ART INT, V26, P1241
[7]  
[Anonymous], P 11 INT C AUT AG MU
[8]  
[Anonymous], 2006, INT JOINT C AUT AG M
[9]  
[Anonymous], 1995, Handbook of Global Optimization, DOI DOI 10.1007/978-1-4615-2025-22
[10]  
[Anonymous], 1991, Game Theory