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.
'Public' online spaces don't carry speech, rights
(AP) -- Rant all you want in a public park. A police officer generally won't eject you for your remarks alone, however unpopular or provocative.
Grief leads father to create bomb-defusing robot
(AP) -- The knock on Brian Hart's door came at 6 a.m. An Army colonel, a priest and a police officer had come to tell Hart and his wife that their 20-year-old son had been killed when his military vehicle was ambushed in Iraq.
Some psych patients wait days in hospital ERs
(AP) -- When staffers at a Brooklyn hospital spotted a middle-aged woman lying face-down on a waiting room floor last month, it hardly seemed like cause for alarm.
EU, US near deal on pact on protecting privacy
(AP) -- Privacy rights vs. terror fights: The EU and the United States are close to agreeing on how to protect personal and private data while still letting law enforcement officials share information to combat organized crime and terrorism.
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."
South African TB patients rampage
(AP) -- Authorities increased security Friday at a tuberculosis hospital where patients with drug-resistant forms of the disease went on a rampage to protest prison-like conditions.

News discussion:

Technology news