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

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

Related stories:

Security from chaos
There’s safety (and security) in numbers … especially when those numbers are random. That’s the lesson learned from a DHS-sponsored research project out of the University of Southern California (USC). The research is already helping to beef up security at LAX airport in Los Angeles, and it could soon be used across the country to predict and minimize risk.
MySpace links users to US hurricane emergency alerts
In what is heralded as the seeds of an Internet-age emergency broadcast system, MySpace has teamed with the US Department of Homeland Security (DHS) to spread news on hurricanes through users of the online social network.
Gulf Coast braces, flees as deadly Gustav takes aim at US (Update)
More than a million people fled Louisiana as killer Hurricane Gustav on Sunday roared toward New Orleans, a fragile US coastal city still deeply scarred by the devastating 2005 Katrina storm.
Hackers hacked at infamous DefCon gathering
In the end, it was hackers at DefCon that got hacked. After three days of software cracking duels and hacking seminars, self-described computer ninjas at the infamous gathering in Las Vegas found out Sunday that their online activities were hijacked without them catching on.
Democracies with separation of powers less likely to stop using torture
A system of checks and balances in government is usually regarded as a good thing, except when it comes to the probability that a nation will stop its use of government-sanctioned torture, according to a Florida State University study.
Japan firms step up mobile security after stabbing rampage
Japanese mobile telephone content providers are setting up safeguards to protect young people amid shock after a disgruntled young man used his phone to document his plans for a stabbing rampage.
Wake-up call to business: Tighten up on information security
According to the Department of Trade and Industry there are 4.5 million businesses in the UK of which 99.3% are small to medium sized enterprises (SMEs), employing 0-49 employees. These comprise 58.9% of the total workforce of 24.4 million and account for 51.9% of the £2,600 billion UK turnover. Bruce Hallas, a specialist in information security, said "SMEs are particularly prone to poor or even non-existent information security. As awareness of the importance of information security increases, the SMEs stand to lose competitiveness, potentially losing contracts with existing clients and suffering the financial consequences that are increasingly arising from information security incidents."
Nanotubes could help study retrovirus transmission between human cells
Recent findings by medical researchers indicate that naturally occurring nanotubes may serve as tunnels that protect retroviruses and bacteria in transit from diseased to healthy cells — a fact that may explain why vaccines fare poorly against some invaders.

News discussion:

Technology news