Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport

ABSTRACT

Security at major locations of economic or political importance is a key concern around the world, particularly given the threat of terrorism. Limited security resources prevent full security coverage at all times, which allows adversaries to observe and exploit patterns in selective patrolling or monitoring, e.g. they can plan an attack avoiding existing patrols. Hence, randomized patrolling or monitoring is important, but randomization must provide distinct weights to different actions based on their complex costs and benefits. To this end, this paper describes a promising transition of the latest in multi-agent algorithms -- in fact, an algorithm that represents a culmination of research presented at AAMAS - into a deployed application. In particular, it describes a software assistant agent called ARMOR (Assistant for Randomized Monitoring over Routes) that casts this patrolling/monitoring problem as a Bayesian Stackelberg game, allowing the agent to appropriately weigh the different actions in randomization, as well as uncertainty over adversary types. ARMOR combines three key features: (i) It uses the fastest known solver for Bayesian Stackelberg games called DOBSS, where the dominant mixed strategies enable randomization; (ii) Its mixed-initiative based interface allows users to occasionally adjust or override the automated schedule based on their local constraints; (iii) It alerts the users if mixed-initiative overrides appear to degrade the overall desired randomization. ARMOR has been successfully deployed since August 2007 at the Los Angeles International Airport (LAX) to randomize checkpoints on the roadways entering the airport and canine patrol routes within the airport terminals. This paper examines the information, design choices, challenges, and evaluation that went into designing ARMOR.

REFERENCES

• 1: General Description: Just the Facts. http://www.lawa.org/lax/justTheFact.cfm, 2007.
• 2: N. Billante. The Beat Goes On: Policing for Crime Prevention. http://www.cis.org.au/IssueAnalysis/ia38/ia38.htm, 2003.
• 3: Gerald Brown , Matthew Carlyle , Javier Salmerón , Kevin Wood, Defending Critical Infrastructure, Interfaces, v.36 n.6, p.530-544, November 2006 [doi>10.1287/inte.1060.0252]
• 4: Vincent Conitzer , Tuomas Sandholm, Computing the optimal strategy to commit to, Proceedings of the 7th ACM conference on Electronic commerce, p.82-90, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134717]
• 5: D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
• 6: J. C. Harsanyi and R. Selten. A Generalized Nash Solution for Two-person Bargaining Games With Incomplete Information. Management Science, 18(5):80--106, 1972.
• 7: R. C. Larson. A Hypercube Queuing Model for Facility Location and Redistricting in Urban Emergency Services. Computer and OR, 1(1):67--95, 1974.
• 8: A. Murr. The Element of Surprise. Newsweek National News, http://www.msnbc.msn.com/id/21035785/site/newsweek/page/0/, 28 September 2007.
• 9: Praveen Paruchuri , Jonathan P. Pearce , Janusz Marecki , Milind Tambe , Fernando Ordonez , Sarit Kraus, Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 10: Praveen Paruchuri , Jonathan P. Pearce , Milind Tambe , Fernando Ordonez , Sarit Kraus, An efficient heuristic approach for security against multiple adversaries, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329344]
• 11: Praveen Paruchuri , Milind Tambe , Fernando Ordóñez , Sarit Kraus, Security in multiagent systems by policy randomization, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160681]
• 12: Praveen Paruchuri , Milind Tambe , Fernando Ordóñez , Sarit Kraus, Security in multiagent systems by policy randomization, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160681]
• 13: S. Ruan, C. Meirina, F. Yu, K. R. Pattipati, and R. L. Popp. Patrolling in a Stochastic Environment. In 10th Intl. Command and Control Research and Tech. Symp., 2005.
• 14: D. Stevens and et. al. Implementing Security Improvement Options at Los Angeles International Airport. http://www.rand.org/pubs/documented_briefings/2006/RAND_DB499-1.pdf, 2006.
• 15: W. A. Wagenaar. Generation of Random Sequences by Human Subjects: A Critical Survey of Literature. 1972.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents

General Terms:
Design, Security, Theory

Keywords:
Bayesian and Stackelberg games, game theory, security of agent systems