The ARMOR software casts the above patrolling/monitoring problem as a Bayesian Stackelberg game, allowing the agent to appropriately weigh the different actions in randomization, as well as uncertainty over adversary types. ARMOR combines three key features:
- It uses the fastest known solver for Bayesian Stackelberg games called DOBSS (Decomposed Optimal Bayesian Stackelberg Solver,
where the dominant mixed strategies enable randomization
- Its mixed-initiative based interface allows users to occasionally adjust or override the automated schedule based on their
local constraints
- It alerts users if mixed-initiative overrides appear to degrade the overall desired randomization
ARMOR has been sucessfully deployed since August 2007 at the Los Angeles International Airport (LAX) to randomize checkpoints on the
roadways entering the airport and canine patrol routes within the airport terminals.
|
The image to the left shows the main screen of the ARMOR interface. In this example, a week's worth of schedules is shown. All three types of constraints are visible:
- Red constraints show times and locations that must not be scheduled
- Green shows the reverse, ,a time and location that must be scheduled
- Yellow regions must have at least one checkpoint scheduled
|
|
The flow chart to the left shows the process of developing a schedule with constrained randomization. Users first input constraints and other aspects of their situation into the frontend interface. Within the backend, external information, such as traffic conditions, is combined with information from the interface to create a game matrix. This matrix is then fed into DOBSS, which produces a probability distribution for airport police actions. A suggested schedule is then produced from the front end's knowledge of the situation combined with the mixed strategy probabilities from the backend. This suggested schedule can be adjusted manually as necessary to produce a finalized schedule.
|
News and Updates on the ARMOR Project
ARMOR's Sucessful Deployment Leads to Work with Federal Air Marshals
ARMOR 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.
Our Work in the News
Currently we are moving forward from our strong start in collaboration with the security forces at the Los Angeles International Airport. The result of our collaboration is the ARMOR program, with two variants for checkpoint and canine scheduling. Visit our news page for more information on our progress.
ARMOR's Success Continues in the Form of New Research
Due to ARMOR's continued success new research has begun regarding dealing with human adversaries who may be boundedly rational or have limited observational capabilities. Find the details of this work in the most recent publication "Effective Solutions for Real-World Stackelberg Games: When Agents Must Deal with Human Uncertainties".
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.
These domains have multiple characteristics which must be carefully addressed:
- The agent or agent-team needs to commit to a security policy while the adversaries may observe and exploit the policy committed to.
- The agent/agent-team potentially faces different types of adversaries and has varying information available about the adversaries
(thus limiting the agents' ability to model its adversaries).
- The adversary may have anywhere from limited to full knowledge of the security policy chosen by the agent/agent-team
- The adversary may be boundedly rational causing him to deviate from what may be rational choices
To address security in such domains, we have developed multiple types of algorithms, to handle cases when the agent has come knowledge of the adversary as well as when it has none.
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
|
|
|
Effective Solutions for Real-World Stackelberg Games: When Agents Must Deal with Human Uncertainties (AAMAS-2009) |
PDF |
Using Game Theory for Los Angeles Airport Security |
PDF |
Bayesian Stackelberg Games and their Application for Security at Los Angeles International Airport (SIGecom Exchanges-2008) |
PDF |
Efficient Algorithms to solve Bayesian Stackelberg Games for Security Applications (AAAI-2008)
|
PDF |
Deployed ARMOR protection: The application of a game-theoretic model for security at the Los Angeles International Airport (AAMAS-2008 Industry track)
|
PDF |
| Playing Games for Security: An Efficient Exact Algorithm for Solving Bayesian Stackelberg Games (AAMAS-2008) |
PDF |
| Robust Solutions in Stackelberg Games: Addressing Boundedly Rational Human Preference Models |
PDF |
| An Efficient Heuristic Approach for Security Against Multiple Adversaries (AAMAS-2007) |
PDF |
| Security in Multiagent Systems by Policy Randomization (AAMAS-2006) |
PDF |
| Keep the Adversary Guessing: Agent Security by Policy Randomization (Thesis Defense) |
PDF |
If you have any questions about the contents of this page please contact James Pita ( jpita@usc.edu )
