Please don’t remove this alert box from this page.
This alert box is placed on all the pages of this website. Although visible in edit mode, it is hidden by custom code.
ARMOR-Project
Motivation
The Coast Guard Atlantic Area’s mission includes maritime security of our coasts, ports, and inland waterways, a mission that faces increased risks given threats such as terrorism and drug trafficking. Atlantic Area performs this mission at the Operational Level of the Coast Guard, looking at mission assessment across five districts encompassing the vast majority of economically significant ports in the United States.
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 actions avoiding existing patrols. Despite extensive outreach and coordination with other federal agencies, along with state, local authorities and industry there is simply not enough assets to maintain a 24/7 presence. This lack of assets extends to all 361 ports in the United States. Randomization of patrols and surveillance can be of help, but randomization must not mean haphazard operations. Randomization must still provide some quality-guaranteed security and very importantly, it must maximize deterrence.
Model
Port Resilience Operational / Tactical Enforcement to Combat Terrorism (PROTECT)
Model for the United States Coast Guard (ARMOR-PROTECT)
In use by the US Coast Guard since 2011
Given a particular port and the variety of critical infrastructure that an adversary (i.e., terrorist) may attack within the port, the US Coast Guard (USCG) conducts patrols to protect this infrastructure; however, while the adversary has the opportunity to observe patrol patterns, limited security resources imply that USCG patrols cannot be at every location 24/7. To assist the USCG in allocating its patrolling resources, PROTECT uses an attacker-defender Stackelberg game framework, with USCG as the defender against terrorist adversaries that conduct surveillance before potentially launching an attack. PROTECT’s solution is to typically provide a mixed strategy, i.e. randomized patrol patterns taking into account the importance of different targets, and the adversary’s surveillance and anticipated reaction to USCG patrols. The patrols generated by PROTECT for the USCG incorporate multiple defender patrol boats along with scheduling various defender activities to be performed at the different critical infrastructure.
Another problem that USCG faces is the protection of ferries, including the Staten Island Ferry in New York, from potential terrorist attacks from water. We developed a game-theoretic system for scheduling escort boat patrols to protect ferries, and this has been deployed at the Staten Island Ferry since 2013. The key research challenge is the fact that the ferries are continuous moving in a continuous domain, and the attacker could attack in any moment in time. This type of moving targets domain leads to game-theoretic models with continuous strategy spaces, which presents computational challenges. Our theoretical work showed that while it is safe to discretize the defender’s strategy space, discretizing the attacker’s strategy space would result in loss of utility. We developed a novel algorithm that uses a compact representation for the defender’s mixed strategy space while able to exactly model the attacker’s continuous strategy space. The implemented algorithm, running on a laptop, is able to generate daily schedules for escort boats with guaranteed expected utility values.
Features videos
Awards
2012 Daniel H. Wagner Prize
The PROTECT project won the 2012 Daniel H. Wagner Prize for Excellence in Operations Research Practice at the annual Institute for Operations Research and the Management Science (INFORMS) Analytics Conference in San Antonio. The Wagner prize emphasizes the quality and coherence of analysis used in practical problems. The prize is named for the late Dr. Wagner who strove to apply mathematics to practical problems, supported by clear and intelligible writing. The prize reflects those principles by emphasizing good writing, strong analytical content and verifiable practice successes. His company, Wagner Associates, Inc., conducted leading-edge mathematical work in naval tactics, including anti-submarine warfare, detection theory and search planning. Many of the mathematical and operations research applications he developed for the U.S. Navy and Coast Guard are still used today.
Part of Prof. Tambe’s acceptance speech at the Wagner prize
This research started over three years ago with our meetings with members of the US Coast Guard and the challenges that they described awaited us in applying computational game theory to one of their critical mission areas. More specifically, our goal was to use game theory to assist the US Coast Guard in maximizing the effectiveness, efficiency and optimization of the Ports, Waterways, and Coastal Security patrols. Game theory could help allocate limited security resources, while ensuring that the patrols were unpredictable.
Three years later, after all the hard work of a large team of individuals, the ARMOR-PROTECT system is now deployed in the ports of Boston, New York and Los Angeles; and it is now undergoing Validation, Verification and Accreditation by a team from the US Coast Guard Headquarters and the Coast Guard Research and Development center for potential nationwide deployment. This outcome would not have been possible without the tremendous support we received from the US Coast Guard crews. Indeed, this is a result of true teamwork among university researchers and the US Coast Guard. The Coast Guard is now exploring ways to use Game Theory in other major mission applications.
2013 Meritorious Team Commendation from Commandant of the US Coast Guard
2013 Meritorious Team Commendation from Commandant of the US Coast Guard for creating “an innovative approach to optimize patrol schedules and actions for the Coast Guard Ports, Waterways and Coast Security missions” while serving the Coast Guard Port Resilience for Operational/Tactical Enforcement to Combat Terrorism (PROTECT) Team.
Videos of the Coast Guard using PROTECT
Pictures
Abstracts
Abstract from the “PROTECT: A Deployed Game Theoretic System to Protect the Ports of the United States” paper
While three deployed applications of game theory for security have recently been reported at AAMAS, we as a community remain in the early stages of these deployments; there is a continuing need to understand the core principles for innovative security applications of game theory. Towards that end, this paper presents PROTECT, a game-theoretic system deployed by the United States Coast Guard (USCG) in the port of Boston for scheduling their patrols. USCG has termed the deployment of PROTECT in Boston a success, and efforts are underway to test it in the port of New York, with the potential for nationwide deployment.
PROTECT is premised on an attacker-defender Stackelberg game model and offers five key innovations. First, this system is a departure from the assumption of perfect adversary rationality noted in previous work, relying instead 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 the QR model. Second, to improve PROTECT’s efficiency, we generate a compact representation of the defender’s strategy space, exploiting equivalence and dominance. Third, we show how to practically model a real maritime patrolling problem as a Stackelberg game. Fourth, our experimental results illustrate that PROTECT’s QR model more robustly handles real-world uncertainties than a perfect rationality model. Finally, in evaluating PROTECT, this paper for the first time provides real-world data: (i) comparison of human-generated vs PROTECT security schedules, and (ii) results from an Adversarial Perspective Team’s (human mock attackers) analysis.
Abstract from the “Optimal Patrol Strategy for Protecting Moving Targets with Multiple Mobile Resources” paper
Previous work on Stackelberg Security Games for scheduling security resources has mostly assumed that the targets are stationary relative to the defender and the attacker, leading to discrete game models with finite numbers of pure strategies. This paper in contrast focuses on protecting mobile targets that lead to a continuous set of strategies for the players. The problem is motivated by several real-world domains including protecting ferries with escorts and protecting refugee supply lines. Our contributions include: (i) a new game model for multiple mobile defender resources and moving targets with a discretized strategy space for the defender and a continuous strategy space for the attacker; (ii) an efficient linearprogram-based solution that uses a compact representation for the defender’s mixed strategy, while accurately modeling the attacker’s continuous strategy using a novel sub-interval analysis method; (iii) a heuristic method of equilibrium refinement for improved robustness and (iv) detailed experimental analysis in the ferry protection domain.
Support
People
TEAMCORE Members
Alumni
- Bo An, Assitant Professor
- Nanyang Technological University, Singapore
- Albert Jiang
- Rong Yang
- Andrew Deeds
Associated US Coast Guard groups
- Atlantic Area
- Pacific Area
- District One
- District Eleven
- Research and Development Center
- Sector Boston
- Sector New York
- Sector Los Angeles Long Beach
- Station Boston
- Station New York
- Station Los Angeles Long Beach
PUBLICATIONS
Bo An, Eric Shieh, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer, PROTECT – A Deployed Game Theoretic System for Strategic Security Allocation for the United States Coast Guard, AI Magazine 2013
Bo An, Fernando Ordonez, Milind Tambe, Eric Shieh, Rong Yang, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer, A Deployed Quantal Response Based Patrol Planning System for the US Coast Guard, Interfaces 2013
Fei Fang, Albert Xin Jiang, Milind Tambe, Optimal Patrol Strategy for Protecting Moving Targets with Multiple Mobile Resources, International Conference on Autonomous Agents and Multiagent Systems (AAMAS)
Fei Fang, Albert Xin Jiang, Milind Tambe, Designing Optimal Patrol Strategy for Protecting Moving Targets with Multiple Mobile Resources, International Workshop on Optimisation in Multi-Agent Systems (OPTMAS)
Eric Shieh, Manish Jain, Albert Xin Jiang, Milind Tambe, Efficiently Solving Joint Activity Based Security Games, International Joint Conference on Artificial Intelligence (IJCAI)
Eric Shieh, Manish Jain, Albert Xin Jiang, Milind Tambe, Efficiently Solving Time-Dependent Joint Activities in Security Games, Workshop on Optimization in Multi |oai:code-citation|
Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer, PROTECT: An Application of Computational Game Theory for the Security of the Ports of the United States, Conference on Artificial Intelligence (AAAI) Spotlight Track
Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer, Kathryn Moretti, PROTECT in the Ports of Boston, New York and Beyond: Experiences in Deploying Stackelberg Security Games with Quantal Response, Book Publisher: Springer
Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer, PROTECT: A Deployed Game Theoretic System to Protect the Ports of the United States, International Conference on Autonomous Agents and Multiagent Systems (Best paper, Innovative Application track)
Rong Yang, Fernando Ordonez, Milind Tambe, Computing Optimal Strategy against Quantal Response in Security Games, International Conference on Autonomous Agents and Multiagent Systems (AAMAS)
Manish Jain, Bo An, Milind Tambe, An Overview of Recent Application Trends at the AAMAS conference: Security, Sustainability and Safety, AI Magazine, 33(3):14-28
Bo An, James Pita, Eric Shieh, Milind Tambe, Christopher Kiekintveld, Janusz Marecki, GUARDS and PROTECT: Next Generation Applications of Security Games, ACM SIGecom Exchanges, Vol. 10, No. 1
Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer, Kathryn Moretti, PROTECT in the Ports of Boston, New York and Beyond: Experiences in Deploying Stackelberg Security Games with Quantal Response, Book Publisher: Springer
News
PROTECT in News
How The US Coast Guard Uses Game Theory To Protect New York City [PHOTOS]
The Security Benefits of Unpredictability
Acquisition Update: U.S. Coast Guard Awarded the Daniel H. Wagner Prize for Excellence in Operations Research Practice
LISTEN: CREATE Director Steve Hora Interviewed about ARMOR-PROTECT Rollout
USC Engineered Anti-Terrorism System Deployed at Ports of Los Angeles and Long Beach
Ports of Long Beach, Los Angeles using USC software to beef up security
A Safe Harbor – A Software Program Created by USC Viterbi Computer Scientist Milind Tambe Protects U.S. Ports from Terrorists
USC-Developed Software Protects Ports from Terrorism
Ports of Long Beach, Los Angeles using USC software to beef up security
At USC, the first U.S. Department of Homeland Security-funded Center of Excellence fights terrorism with game theory, computer algorithms and weapons of social science
US Coast Guard, USC Win INFORMS Wagner Prize for Protecting America’s Ports, Waters from Terror Attack
Daniel H. Wagner Prize Awarded to USC Teamcore
CREATE’s ARMOR-PROTECT Featured in Coast Guard Outlook Magazine
The Port Resiliency for Operational/Tactical Enforcement to Combat Terrorism Model
CREATE Helps the US Coast Guard Randomize
Port of Boston Not Playing Games with Its Security
USC Engineering Anti-Terrorism System Begins Tests in Boston Harbor
Become a Harvard Teamcore partner through community projects, funding, volunteering, or research collaboration.
Get Involved