University of Southern California

Assistant for Randomized Monitoring Over Routes ARMOR

The ARMOR project is focused on developing methods for creating randomized plans and processes for monitoring, inspection, patrolling, and security in general --- so that even if an attacker observes the plans, he/she cannot predict its progression --- thus providing risk reduction while guaranteeing a certain level of protection quality.

Security 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.

We have developed two different approaches depending on what is known about the adversary. If there is no information about the adversary we use a Markov Decision Process (MDP) to represent patrols and identify randomized solutions that minimize the information available to the adversary. When there is partial information about the adversary we decide on efficient patrols following novel game-theoretic methods, which require solving a Bayesian Stackelberg game.

The ARMOR system focuses on the game-theoretic method of providing such randomization of plans and processes. Casting the problem as a Bayesian Stackelberg game, it obtains randomized strategies for security agents; one of the fundamental advances in ARMOR then is to provide the fastest algorithms known-to-date to solve such games. ARMOR's strength is its marriage of strong theoretical game-theoretic foundations with practical applications, and the virtuous cycle of theory and practice to benefit from each other.

The ARMOR software has been deployed successfully at the Los Angeles International Airport since August 2007 to determine where and when to place checkpoints, and where and when to deploy canine units. In addition, since May 2008, we have been working in adapting this system to randomize the scheduling of Federal Air Marshals to commercial flights. This deployment in real applications has led to significant interest from the media and other potential users/customers, and substantial research.

For more information about the project, contact the lead researcher at: tambe@usc.edu