You will be redirected to the page you want to view in  seconds.

Game Theory That Defeats Terrorists

May. 28, 2013 - 03:45AM   |  
By MICHAEL PECK   |   Comments
U.S. Steps Up Security As Precaution After Bin Lad
ARMOR software is used to place checkpoints and dispatch patrols at Los Angeles International Airport. (Getty Images)
  • Filed Under

Listen up, kids: Here’s a math problem to solve. You have 100 airline flights that terrorists might attack. You have 10 air marshals to guard them, which means 17 trillion combinations. Now, determine the optimum schedule to guard the most vulnerable flights. At the same time, randomize the schedule such that patrols don’t become so predictable that terrorists can exploit the routine.

Fortunately, there is a cheat for this very problem. The Department of Homeland Security has a software product called ARMOR, the Assistant for Randomized Monitoring Over Routes, which calculates optimum patrol patterns.

Various versions of ARMOR have been used over the last six years by the Coast Guard to randomize patrols, by the Federal Air Marshal Service to protect the most at-risk flights, and to determine the location of checkpoints and canine patrols at Los Angeles International Airport.

It is currently being evaluated by the Transportation Security Administration and Los Angeles Metro train security, while the U.S. Navy has now expressed interest in using ARMOR for anti-piracy patrols. DHS believes it would also be useful to the U.S. Army and Air Force for tasks such as scheduling surveillance drone flights.

ARMOR is superior to the old way of scheduling patrols, said lead ARMOR researcher Milind Tambe, a computer scientist at the University of Southern California and a researcher at DHS’ National Center for Risk and Economic Analysis of Terrorism Events, or CREATE, at USC.

“Patrols were scheduled either by humans or they rolled dice to choose,” Tambe said.

The heart of ARMOR is game theory, that branch of mathematical/statistical thinking that has much to do with cold logic and very little to do with how real human beings play games. Or more specifically, Stackelberg theory, in which one player moves first and the other players can observe that move before making their own.

The goal is to allocate limited defensive resources in an environment where some targets are more important than others, and where there is an asymmetry of information — namely, in that the defender doesn’t know where and when the attacker will strike, but the attacker can conduct long-term surveillance to discover gaps in the defenses.

(Page 2 of 2)

“Under these circumstances, you can cast the problem as a game, as in game theory. Now you have created a mathematical problem, and the solution tells you how to allocate your forces in an optimal fashion,” Tambe said.

ARMOR-PROTECT, which runs on a guard’s handheld device, creates timetables that list the precise times a patrol must check a target and the routes they must take to get there. So a guard patrolling Los Angeles trains might see a display that says “Station check: Union Station from 10 a.m. to 10:30 a.m.,” followed by instructions to take the Metro Silver and Metro Green lines to Hawthorne/Lennox for a station check from 11:25 to 11:40 a.m. The software will automatically adjust schedules in response to arrests on previous days or for previously missed station checks.

CREATE Director Steve Hora said ARMOR determines the value of a target when creating patrol schedules.

“It takes the value of the target to us into account, it takes the value of the target to the adversary into account, and it takes into account how much travel time you have to spend going from place to place on these routes. For example, in a harbor, if you did a completely randomized search from point to point, you would be spending too much transit time on the water.”

ARMOR has a lot going on under the hood. It must assess time and distance, security tactics (a quick patrol of many targets versus a more thorough patrol of a single target), whether different types of security assets complement or conflict with each other, and potential strategies available to an attacker. When determining the value of a target, it also considers potential economic damage and loss of life.

ARMOR, which cost less than $5 million to design, is small enough to run on handhelds and simple enough that even an ordinary police sergeant can use it. But Tambe emphasizes that creating simplicity is a complex matter, especially when solving problems that have billions or trillions of possible combinations and outcomes.

“This is massive. You cannot even load this into computer memory and run it,” he said.

The solution is to design algorithms that come up with results by analyzing selected data rather than crunching every bit of information. Tambe uses techniques from operations research, large-scale optimization and mixed-integer linear programming.

However, one drawback to game theory (and its offspring such as deterrence theory) is that they are rational actor models. This means they assume an adversary will behave as logically as Mr. Spock. This may (or may not) have been appropriate for decision-making during a nuclear war, but it doesn’t capture the behavior of suicide bombers.

ARMOR addresses this on two levels, Tambe said.

The first is to assume that an attacker has to balance limited resources while trying to maximize damage, so there is an element of predictability. But ARMOR’s algorithms also try to consider “bounded rationality,” where the attacker may have incomplete information about a target or simply makes a mistake.

More In Training & Simulation

Start your day with a roundup of top defense news.

More Headlines



Login to This Week's Digital Edition

Subscribe for Print or Digital delivery today!

Exclusive Events Coverage

In-depth news and multimedia coverage of industry trade shows and conferences.