Game theory AI research moves from Ph.D. thesis to experimental police tool

October 1, 2007

Security officials at Los Angeles Airport are experimenting with a system developed by USC Viterbi School of Engineering computer scientists to make their operations harder for the bad guys to predict and defeat.

Milind Tambe, a specialist in artificial intelligence, led a team of USC researchers in applying game theory insights to systematically make it extremely difficult for observers to find any patterns or regularities in LAX vehicle security routines.

The result is a software package with a computer interface showing a blank schedule, with a button labeled "randomize." Pressing the button produces a set of times and places for security forces to be, a schedule that produces the same level overall coverage as conventional scheduling but does so unpredictably.

"To interrupt or deter a terrorist plot in the surveillance phase is the safest and most efficient manner to protect the airport," said James Butts, director of law enforcement for Los Angeles airports, including LAX, Van Nuys, Palmdale and Ontario. "This program and technology directly addresses thwarting potential terrorists at the earliest stages of planning."

The initial impetus for the system came from Erroll Southers, a former FBI special agent who serves as an associate director for the Department of Homeland Security-funded Center for Risk and Economic Analysis of Terrorism Events (CREATE). Southers said he "looked at the checkpoint situation at the airport," and decided it was vulnerable. "That's how we came up with the project."

But the solution was not simple or obvious: it involved basic research in computer science application to game theory. The USC system, called ARMOR, answers a challenge posed in a 2007 doctoral thesis by Tambe student Praveen Paruchuri that is the mathematical heart of the new system, the bulit-in strategic advantage enjoyed by terrorists. "For security, " Paruchuri wrote, "the police have to commit to a policy, while their adversaries may observe and exploit the policy committed to."

Complicating matters, the police face different types of adversaries, with different threats or aims; smugglers and terrorists— and the strategy has to cope with all the threats in optimal fashion. And the police force itself isn't a simple, singular "decision" (to raise prices, for example) but the activities of a host of individual agents working in a large area, trying to counter an unknown number of opposition agents.

The thesis, "Keeping the Adversary Guessing: Agent Security by Policy Randomization," builds on a mathematical business strategy developed for commercial situations in which one company in a competitive situation because of its size and prominence has to essentially 'play first," known formally by the formidable title of a "Bayesian-Stackelberg game."

Paruchuri then used artificial intelligent agent techniques, in which computer programs are set up to play individual, cooperative roles in problem solving and, making simplifying assumptions, was able to create the best algorithm yet for solving this class of problems, for making the right first move an algorithm that was computable. Sarit Kraus, a professor of computer science at Bar-Ilan University in Ramat Gan, Israel, contributed input to Paruchari's work, and USC assistant professor of systems engineering Fernando Ordoñez was instrumental in helping Praveen formulate the Bayesian Stackelberg game as an optimization problem, so it could be solved efficiently.

Using his insights, Tambe, Ordoñez and a team of graduate students -- Janusz Marecki, James Pita, Christopher Portway and Jonathan Pearce -- were able to create ARMOR, working with funding from CREATE.

In April, the work was presented at LAX by Praveen "to a room full of police officers, and it was very deeply appreciated," Tambe continued.

"We then had a few meetings, visited with LAX and saw checkpoints in operation. Based on the inputs they have provided we refined our system, and then did some initial program demonstrations to them in July; in August, we suggested that we start implementing our outputs, and they did."

Tambe emphasized that his team tailored the basic system directly to the needs of LAX police, based upon their inputs. "I am overwhelmed by the goodwill and spirit of collaboration of LAX police," he said. "I am really glad that they are willing to take on new technology."

"I liked the concept," said Butts, "I approved of us being part of it. This randomization technique allows us to maximize the impact of our deployment."

CREATE's Southers emphasized that the office of Mayor Antonio Villaraigosa took a direct interest in cooperation between the city and airport and CREATE in finding security solutions.

ARMOR can take the entire system, including resources available (officers, K9 units work and break hours) and create a completely randomized schedule that will cover as completely as a conventional one, but will baffle efforts to predict it.

Paruchuri is the second of Tambe's 2007 Ph.D. students to have his work used in homeland security applications. Nathan Schurr's PhD work was the basis of a simulation system to use as training tool for fire department emergency responders.

Source: University of Southern California