ARMOR-PROTECT
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
Overview of PROTECT by Capt. Tom Vitullo, Chief of Response, 1st Coast Guard District
PROTECT has been currently deployed in the ports of Boston, New York and Los Angeles.
US Coast guard Testimony at House Committee on Transportation and Infrastructure, Subcommittee on Coast Guard and Maritime Transportation mentions our research on game theory for security
AWARDS
2012 Daniel H. Wagner Prize
INFORMS Edelman Competition, 2013
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
USCG Wagner Prize presentation - San Antonio
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.
2012 Wagner Prize Presentations
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.
The paper, "PROTECT: A Deployed Game Theoretic System to Protect the Ports of the United States", won the Best Innovative Application Paper Award at AAMAS 2012
Commander, First Coast Guard District’s Operational Excellence Award, 2011
PROTECT Team on US Coast Guard (USCG) Cutter Morgenthau while visiting USCG Station Los Angeles Long Beach
USCG Cutter Morgenthau from above
Professor Milind Tambe before going up on the
H-65 "Dolphin" helicopter
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
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.
| Title | Author | Published At | Year |
|---|---|---|---|
| PROTECT – A Deployed Game Theoretic System for Strategic Security Allocation for the United States Coast Guard | Bo An, Eric Shieh, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer | AI Magazine 2013 | 2013 |
| A Deployed Quantal Response Based Patrol Planning System for the US Coast Guard | Bo An, Fernando Ordonez, Milind Tambe, Eric Shieh, Rong Yang, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer | Interfaces 2013 | 2013 |
| Optimal Patrol Strategy for Protecting Moving Targets with Multiple Mobile Resources | Fei Fang, Albert Xin Jiang, Milind Tambe | International Conference on Autonomous Agents and Multiagent Systems (AAMAS) | 2013 |
| Designing Optimal Patrol Strategy for Protecting Moving Targets with Multiple Mobile Resources | Fei Fang, Albert Xin Jiang, Milind Tambe | International Workshop on Optimisation in Multi-Agent Systems (OPTMAS) | 2013 |
| Efficiently Solving Joint Activity Based Security Games | Eric Shieh, Manish Jain, Albert Xin Jiang, Milind Tambe | International Joint Conference on Artificial Intelligence (IJCAI) | 2013 |
| Efficiently Solving Time-Dependent Joint Activities in Security Games | Eric Shieh, Manish Jain, Albert Xin Jiang, Milind Tambe | Workshop on Optimization in Multiagent Systems (OPTMAS) at AAMAS | 2013 |
| PROTECT: An Application of Computational Game Theory for the Security of the Ports of the United States | Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer | Conference on Artificial Intelligence (AAAI) Spotlight Track | 2012 |
| PROTECT in the Ports of Boston, New York and Beyond: Experiences in Deploying Stackelberg Security Games with Quantal Response | Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer, Kathryn Moretti | Book Publisher: Springer | 2012 |
| PROTECT: A Deployed Game Theoretic System to Protect the Ports of the United States | Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer | International Conference on Autonomous Agents and Multiagent Systems (Best paper, Innovative Application track) | 2012 |
| Computing Optimal Strategy against Quantal Response in Security Games | Rong Yang, Fernando Ordonez, Milind Tambe | International Conference on Autonomous Agents and Multiagent Systems (AAMAS) | 2012 |
| An Overview of Recent Application Trends at the AAMAS conference: Security, Sustainability and Safety | Manish Jain, Bo An, Milind Tambe | AI Magazine, 33(3):14-28 | 2012 |
| GUARDS and PROTECT: Next Generation Applications of Security Games | Bo An, James Pita, Eric Shieh, Milind Tambe, Christopher Kiekintveld, Janusz Marecki | ACM SIGecom Exchanges, Vol. 10, No. 1 | 2011 |
| PROTECT in the Ports of Boston, New York and Beyond: Experiences in Deploying Stackelberg Security Games with Quantal Response | Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer, Kathryn Moretti | Book Publisher: Springer | 2012 |
PROTECT in News
How The US Coast Guard Uses Game Theory To Protect New York City [PHOTOS]
* Business Insider
* May 29, 2013
Within the data seized from Osama bin Laden's Abbottabad compound was the al Qaeda plan to blow up oil tankers in U.S. waters to create an “extreme economic crisis.”
Protecting tankers at home is part of what the USCG does, and faced with a fixed amount of resources and a growing threat, it got innovative.
To continue reading the full article, please click here.
The Security Benefits of Unpredictability
* The Business magazine for Security Technology
* Apr 22, 2013
To continue reading the full article, please click here.
Acquisition Update: U.S. Coast Guard Awarded the Daniel H. Wagner Prize for Excellence in Operations Research Practice
* USCG: Acquisition Directorate News
* Apr 10, 2013
A team of 10 researchers from the Coast Guard Research and Development Center, University of Southern California, and University of Chile were recognized April 8, 2013, as the recipients of the 2013 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 Coast Guard Research and Development Center and its partners’ prize-winning project was titled “A Deployed QuantalResponse-Based Patrol Planning System for the U.S. Coast Guard.” The Wagner prize emphasizes the quality and coherence of analysis used in practical problems.To continue reading the full article, please click here.
LISTEN: CREATE Director Steve Hora Interviewed about ARMOR-PROTECT Rollout
* CREATE News
* Mar 06, 2013
Last month, CREATE's ARMOR-PROTECT was deployed at the ports of Los Angeles and Long Beach. CREATE director, Steve Hora was interviewed on Openline to explain the origins of the academic research project-turned-technology and how it is being used to make a real world impact.
Developed by USC computer scientist and CREATE researcher Milind Tambe, the Port Resilience Operational/Tactical Enforcement to Combat Terrorism system (ARMOR-PROTECT) uses complex algorithms to randomize U.S. Coast Guard boat patrol schedules to stymie would-be terrorists and increase security.To continue reading the full article, please click here.
USC Engineered Anti-Terrorism System Deployed at Ports of Los Angeles and Long Beach
* The Maritime Executive News
* Feb 28, 2013
Funded by the National Center for Risk and Economic Analysis of Terrorist Events (CREATE) through a contract from the USCG Research and Development Center and created by USC computer scientist and CREATE researcher, Milind Tambe, the Port Resilience Operational / Tactical Enforcement to Combat Terrorism system (ARMOR-PROTECT) uses complex algorithms to randomize U.S. Coast Guard boat patrol schedules to stymie would-be terrorists and increase security. ARMOR-PROTECT extends to the maritime domain the Assistant for Randomized Monitoring Over Routes (ARMOR) software that was successfully deployed at LAX to schedule vehicle checkpoints and canine patrols.To continue reading the full article, please click here.
Ports of Long Beach, Los Angeles using USC software to beef up security
* Contra Costa Times News
* Feb 27, 2013
Officials at the U.S. Coast Guard are now using USC-designed anti-terrorism software to maximize security patrols at the nation's busiest seaports, the university announced Wednesday.
Earlier this month, the ports of Long Beach and Los Angeles implemented ARMOR-PROTECT, a program that uses a series of mathematical equations to randomize security patrols while giving maximum protection to high-level targets such as bridges, terminals and piers.To continue reading the full article, please click here.
A Safe Harbor - A Software Program Created by USC Viterbi Computer Scientist Milind Tambe Protects U.S. Ports from Terrorists
* Viterbi News
* Feb 27, 2013
Scene: Dining alone at a popular bistro at the end of a pier, a nondescript man takes in the glorious Southern California sunshine, the comings and goings of ships, and ocean views that stretch forever. He spends this and other days sipping white wine, sampling hors d’oeuvres and writing on his iPad.
The young man, appearances notwithstanding, is anything but a typical 30-something with time on his hands. Instead, he is an American member of a terrorist organization, casing the area to identify potential vulnerabilities in the port’s security network. His mission: to wreak as much havoc as possible.To continue reading the full article, please click here.
USC-Developed Software Protects Ports from Terrorism
* Annenberg TV News
* Feb 27, 2013
A USC-designed computer software system has been installed at the ports of Los Angeles and Long Beach protect the area's harbors against terrorism attacks, the university announced today.
The anti-terrorism system, called Port Resilience Operational/Tactical Enforcement to Combat Terrorism system (ARMOR-PROTECT), was created by USC computer scientist Milind Tambe. Tambe said development of the software relied on multiple USC graduate and post-doctoral students.To continue reading the full article, please click here.
Ports of Long Beach, Los Angeles using USC software to beef up security
* Press-Telegram News
* Feb 27, 2013
Officials at the U.S. Coast Guard are now using USC-designed anti-terrorism software to maximize security patrols at the nation's busiest seaports, the university announced Wednesday.
Earlier this month, the ports of Long Beach and Los Angeles implemented ARMOR-PROTECT, a program that uses a series of mathematical equations to randomize security patrols while giving maximum protection to high-level targets such as bridges, terminals and piers.To continue reading the full article, please click here.
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
* USC Trojan Family News
* Dec 15, 2012
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.To continue reading the full article, please click here.
US Coast Guard, USC Win INFORMS Wagner Prize for Protecting America’s Ports, Waters from Terror Attack
* Informs News
* Nov 21, 2012
HANOVER, MD, November 21, 2012 – The Institute for Operations Research and the Management Sciences (INFORMS®) today announced the award of the Daniel H. Wagner Prize by CPMS, the association’s Practice Section, to the U.S. Coast Guard and its research partner, the University of Southern California’s Viterbi School of Engineering. The winners used analytics and operations research to ramp up protection of America’s ports and waterways from unpredictable terrorist attack.To continue reading the full article, please click here.
Daniel H. Wagner Prize Awarded to USC Teamcore
* Viterbi News
* Oct 30, 2012
The Daniel H. Wagner Prize, which is awarded annually at the INFORMS Conference, recognized the joint team of USC/US Coast Guard researchers for their work on the PROTECT system. This program has been deployed by the US Coast Guard in Boston and New York, to provide intelligent (game-theoretic) randomization of Coast Guard patrols to protect important targets at the ports. Part of the CREATE research effort (National Center for Risk and Economic Analysis of Terrorism Events), the winning paper is entitled “A Deployed Quantal Response Based Patrol Planning System for the US Coast Guard,” by Milind Tambe, Fernando Ordóñez, Bo An, Eric Shieh, Rong Yang (USC) and Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer (US Coast Guard). Members of the team include Milind Tambe, a Helen N. and Emmett H. Jones Professor in Engineering in the Computer Science & Industrial and Systems Engineering Departments and Fernando Ordóñez, a research faculty member in the Daniel J. Epstein Department of Industrial and Systems Engineering.To continue reading the full article, please click here.
CREATE's ARMOR-PROTECT Featured in Coast Guard Outlook Magazine
* Coast Guard Outlook Magazine
* Aug 7, 2012
To learn more about ARMOR-PROTECT and the strong partnership between CREATE and the U.S. Coast Guard, view article on page 28, entitled "The Port Resiliency for Operational/Tactical Enforcement to Combat Terrorism Model." To continue reading the full article, please click here.
The Port Resiliency for Operational/Tactical Enforcement to Combat Terrorism Model
* DefenseMediaNetwork
* July 10, 2012
The 1960s TV comedy Hogan’s Heroes featured a group of Allied World War II prisoners of war (POWs) who were housed in a camp run by a bunch of bumbling jailers. The POWs were able to strike against Germany from the camp due in large part to the predictable routine of the guards’ patrols. Led by “Sgt. Shultz” (played by actor John Banner), the guards followed the same routine every day and night. In simplest terms, the POWs knew that every day at 10 a.m. the guard patrolling the southern part of the camp would be turning at the watch tower. They used this information to send patrols out of the camp with great success. The success of the POWs was primarily due to their jailers’ tactics, techniques, and procedures being so predictable that they could be easily exploited.To continue reading the full article, please click here.
CREATE Helps the US Coast Guard Randomize
* CREATE News
* Aug 1, 2011
CREATE's ARMOR research team, led by Dr. Milind Tambe, was presented the Commander, First Coast Guard District's Operational Excellence Award for their work on the PROTECT project being carried out at Boston Harbor.
Rear Admiral Daniel Neptun presented the award to Drs. Milind Tambe and Isaac Maya, along with commendations to United States Coast Guard (USCG) personnel, for the scheduling software developed to intelligently randomize boat patrols of critical infrastructure around Boston Harbor.To continue reading the full article, please click here.
Port of Boston Not Playing Games with Its Security
* By Laura Williams
* Apr 25, 2011
Studying robot interactions is not typically a career path that leads to a central role in infrastructure security – after all, the Department of Homeland Security doesn’t trust just anyone with vital information about the nation’s critical structures.
Unlikely though it was, it was exactly that research interest that led Milind Tambe, a computer science professor at the University of Southern California, to a project helping the U.S. Coast Guard create a complex patrol schedule that the Port of Boston has been piloting for the past month.
In 2002, Tambe and a student began working on a game-theory algorithm to optimize interactions between robots, and their result turned out to be that randomized interactions worked most effectively. At a 2004 conference, though, this finding received a chilly reception.
“We were so fascinated by the randomization process itself that we didn’t want to give it up,” Tambe said, and so they continued their exploration.To continue reading the full article, please click here.
USC Engineering Anti-Terrorism System Begins Tests in Boston Harbor
Coast Guard testing a computer application designed for airports that makes security activity impossible for observers to predict
April 12, 2011 —
It began with Viterbi School work on randomizing airport security police patrol routines at Los Angeles International Airport while still maintaining the same level of protection. The example spread across the nation, and is now methodically and unpredictably at work in the waters off Massachusetts.
The new PROTECT system schedules the operations of Coast Guard response vessels in a way that make it impossible for observers to predict their activities, while still maintaining the same degree of surveillance.
After months of study, PROTECT (Port Resilience Operational / Tactical Enforcement to Combat Terrorism) began a two-month trial around Boston Harbor April 4, 2011.
To continue reading the full article, please click here.