|
|
|
|
|
|
|
|
|
|
|
|
|
Alumni:
MotivationSecurity at major locations of economic or political importance is a key concern around the world, particularly given the threat of terrorism. 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 an attack avoiding existing patrols. Hence, randomized patrolling or monitoring is important, but randomization must provide distinct weights to different actions based on their complex costs and benefits. Security ChallengeLos Angeles International Airport has posed the following two key challenges to our team:
These challenges bring with them some other important security challenges:
ARMOR: Assistant for Randomized Monitoring Over Routes
The ARMOR software casts the above patrolling/monitoring problem as a Bayesian Stackelberg
game, allowing the ARMOR program to appropriately weigh the different actions in
randomization taking into account different target weights, as well as the fact
that the adversary will conduct surveillance, and the that there is uncertainty
over adversary types. According to Dr Milind Tambe, a tenured Professor at USC and
the prime developer of ARMOR, the program was based on the fastest known solver
for Bayesian Stackelberg games at that time called DOBSS (Decomposed Optimal Bayesian
Stackelberg Solver), where the dominant mixed strategies enables the weighted randomization
mentioned above. (Since the deployment of ARMOR, the USC CREATE team led by Dr.
Tambe has continued to scale up their algorithms beyond DOBSS so the algorithms
can handle much larger domains such as those presented by the US Coast Guard as
well as address more of the uncertainties presented in such domains.)
Download Problem SetNews on the ARMOR ProjectRecent Updates
ARMOR's Sucessful Deployment Leads to Work with Federal Air MarshalsARMOR has now been successfully deployed at Los Angeles International Airport (LAX) since August 2007 to schedule canine patrols and police checkpoints. Based on the successful deployment at LAX the United States Federal Airmarshals have recently commissioned TEAMCORE to work on a similar project for randomization of Federal Air Marshals on flights. See the full details here: ARMOR Federal Air Marshals 
Pictured here are the attendees of the original six month debriefing celebration for the six month trial period at LAX. ARMOR has since then been officially handed over to the LAX Police. General Advances in Security Domains
Security, commonly defined as the ability to deal with intentional threats from
other agents, is a major challenge for agents or agent-teams deployed in adversarial
domains. Such adversarial scenarios arise in a wide variety of situations that are
becoming increasingly important. Some example cases are agents patrolling to provide
perimeter security around critical infrastruture or performing routine security
checks.
In the case where the agent has no model of its adversaries, our key idea is to randomize agent's policies to minimize the information gained by adversaries. To that end, we developed algorithms for policy randomization for both the Markov Decision Processes (MDPs) and the Decentralized-Partially Observable MDPs (Dec POMPDPs). Since arbitrary randomization can violate quality constraints (for example, the resource usage should be below a certain threshold or key areas must be patrolled with a certain frequency), our algorithms guarantee quality constraints on the randomized policies generated. For efficiency, we provide a novel linear program for randomized policy generation in MDPs, and then build on this program for a heuristic solution for Dec-POMDPs. In the other case, when the agent has a partial model of the adversaries, we model the security domain as a Bayesian Stackelberg game, where the agent's model of the adversary includes a probability distribution over possible adversary types. While the optimal policy selection for a Bayesian Stackelberg game is known to be NP-hard, our solution approach based on an efficient Mixed Integer Linear Program (MILP) provides significant speed-ups over existing approaches while obtaining the optimal solution. The resulting policy randomizes the agent's possible strategies, while taking into account the probability distribution over adversary types. This is the approach used in the ARMOR program. We have also developed a new algorithm similar to the one used in the ARMOR program that accounts for adversaries who may be boundedly rational or have limited observational capabilities. This algorithm makes certain assupmtions on the observational capabilities of the adversary as well as their rationality and finds an optimal solution to the Bayesian Stackelberg games given these assumptions. We have already begun to show that under certain conditions this new algorithm can better predict the actions of human adversaries. Relevant Papers and Presentations
This project funded by the USC Homeland Security Center (CREATE).If you have any questions about the contents of this page please contact James Pita (jpita@usc.edu)
|
