@inbook {1506991,
	title = {ARMOR Software: A game theoretic approach to airport security },
	booktitle = {Protecting Airline Passengers in the Age of Terrorism},
	year = {2009},
	publisher = {Praeger Publishers},
	organization = {Praeger Publishers},
	abstract = {Protecting national infrastructure such as airports, is a challenging task for police and security agencies
around the world; a challenge that is exacerbated by the threat of terrorism. Such protection of these
important locations includes, but is not limited to, tasks such as monitoring all entrances or inbound roads
and checking inbound traffic. However, limited resources imply that it is typically impossible to provide
full security coverage at all times. Furthermore, adversaries can observe security arrangements over time
and exploit any predictable patterns to their advantage. Randomizing schedules for patrolling, checking,
or monitoring is thus an important tool in the police arsenal to avoid the vulnerability that comes with
predictability.
This chapter focuses on a deployed software assistant agent that can aid police or other security agencies
in randomizing their security schedules. We face at least three key challenges in building such a software
assistant. First, the assistant must provide quality guarantees in randomization by appropriately weighing
the costs and benefits of the different options available. For example, if an attack on one part of an
infrastructure will cause economic damage while an attack on another could potentially cost human lives,
we must weigh the two options differently {\textendash} giving higher weight (probability) to guarding the latter.
Second, the assistant must address the uncertainty in information that security forces have about the
adversary. Third, the assistant must enable a mixed-initiative interaction with potential users rather than dictating a schedule; the assistant may be unaware of users{\textquoteright} real-world constraints and hence users must
be able to shape the schedule development.
We have addressed these challenges in a software assistant agent called ARMOR (Assistant for
Randomized Monitoring over Routes). Based on game-theoretic principles, ARMOR combines three key
features to address each of the challenges outlined above. Game theory is a well-established foundational
principle within multi-agent systems to reason about multiple agents each pursuing their own interests
(Fudenberg \& Tirole 1991). We build on these game theoretic foundations to reason about two agents {\textendash}
the police force and their adversary {\textendash} in providing a method of randomization.
In particular, the main contribution of our work is mapping the problem of security scheduling as a
Bayesian Stackelberg game (Conitzer \& Sandholm 2006) and solving it within our software system using
the fastest optimal algorithm for such games (Paruchuri et al. 2008), addressing the first two challenges.
While a Bayesian game allows us to address uncertainty over adversary types, by optimally solving such
Bayesian Stackelberg games (which yield optimal randomized strategies as solutions), ARMOR provides
quality guarantees on the schedules generated. The algorithm used builds on several years of research
regarding multi-agent systems and security (Paruchuri et al. 205; 2006; 2007). ARMOR employs an
algorithm that is a logical culmination of this line of research; in particular, ARMOR relies on an optimal
algorithm called DOBSS (Decomposed Optimal Bayesian Stackelberg Solver) (Paruchuri et al. 2008).
The third challenge is addressed by ARMOR{\textquoteright}s use of a mixed-initiative based interface, where users are
allowed to graphically enter different constraints to shape the schedule generated. ARMOR is thus a
collaborative assistant that iterates over generated schedules rather than a rigid one-shot scheduler.
ARMOR also alerts users in case overrides may potentially deteriorate schedule quality.
ARMOR therefore represents a very promising transition of multi-agent research into a deployed
application. ARMOR has been successfully deployed since August 2007 at the Los Angeles International
Airport (LAX) to assist the Los Angeles World Airport (LAWA) police in randomized scheduling of checkpoints, and since November 2007 for generating randomized patrolling schedules for canine units.
In particular, it assists police in determining where to randomly set up checkpoints and where to randomly
allocate canines to terminals. Indeed, February 2008 marked the successful end of the six month trial
period of ARMOR deployment at LAX. The feedback from police at the end of this six month period is
extremely positive; ARMOR will continue to be deployed at LAX and expand to other police activities at
LAX.},
	author = {J. Pita and M. Jain and C. Western and P. Paruchuri and J. Marecki and M. Tambe and F. Ordonez and Kraus, S.},
	editor = {P. Seidenstat}
}
