Rotecting national infrastructure such as airports, historical

agent called ARMOR (assistant for randomized
mon itoring 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 multiagent sys tems to reason
about multiple agents, each pursuing its own inter-
ests (Fudenberg and Tirole 1991). We build on
these game-theoretic foundations to reason about
two agents—the police force and its adversary—in
providing a method of randomization. In particu-
lar, the main contri bution of our article is mapping
the problem of security scheduling as a Bayesian
Stackelberg game (Conitzer and Sandholm 2006)
and solving it through the fastest optimal al go-
rithm for such games (Paruchuri et al. 2008),
address ing the first two challenges. The algorithm
used builds on several years of research regarding
multiagent systems and security (Paruchuri et al.
2005, 2006, 2007). In particular, ARMOR relies on
an optimal algorithm called DOBSS (de composed
optimal Bayesian Stackelberg solver) (Paruchuri et
al. 2008). 
While a Bayesian game allows us to address
uncertainty over adversary types, by optimally
solving such Bayesian Stackelberg games (which
yield optimal randomized strate gies as solutions),
ARMOR provides quality guarantees on the sched-
ules generated. These quality guarantees obviously
do not imply that ARMOR provides perfect securi-
ty; in stead, ARMOR guarantees optimality in the
utilization of fixed security resources (number of
police or canine units) assuming the rewards are
accurately modeled. In other words, given a
specific number of security resources and ar eas to
protect, ARMOR creates a schedule that random-
izes over the possible deployment of those
resources in a fashion that optimizes the expected
reward obtained in protecting LAX. 
The third challenge is addressed by ARMOR’s use
of a mixed-initiative-based interface, where users
are allowed to graphically enter different con-
straints to shape the schedule generated. ARMOR is
thus a collaborative assistant that it erates over gen-
erated schedules rather than a rigid one-shot
scheduler. ARMOR also alerts users in case over-
rides may potentially deteriorate schedule quality. 
ARMOR thus represents a very promising transi-
tion of multiagent research into a deployed appli-
cation. ARMOR has been successfully deployed
since August 2007 at the Los Angeles Internation-
al Airport (LAX) to assist the Los An geles World
Airport (LAWA) police in randomized schedul ing
of checkpoints and since November 2007 for gen-
erating randomized patrolling schedules for canine
units. In particu lar, it assists police in determining
where to randomly set up checkpoints and where
to randomly allocate canines to ter minals. 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 pe riod was extremely positive; ARMOR
will continue to be deployed at LAX and expand to
other police activities at LAX. 
Security Domain Description 
We will now describe the specific challenges in the
security problems faced by the LAWA police. LAX
1
is the fifth bus iest airport in the United States and
the largest destination airport in the United States,
serving 60–70 million passen gers per year (Stevens
et al. 2006). LAX is unfortunately also suspected to
be a prime terrorist target on the West Coast of the
United States, with multiple arrests of plotters
attempting to attack LAX (Stevens et al. 2006). To
protect LAX, LAWA police have designed a securi-
ty sys tem that utilizes multiple rings of protection.
As is evident to anyone traveling through an air-
port, these rings include such things as vehicular
checkpoints, police units patrolling the roads to
the terminals and inside the terminals (with dogs),
and security screening and bag checks for passen-
gers. There are unfortunately not enough resources
(police offi cers) to monitor every single event at
the airport; given its size and the number of pas-
sengers served, such a level of screen ing would
require considerably more personnel and cause
greater delays to travelers. Thus, assuming that all
check points and terminals are not being moni-
tored at all times, setting up available checkpoints,
canine units, or other pa trols on deterministic
schedules allows adversaries to learn the schedules
and plot an attack that avoids the police check-
points and patrols, which makes deterministic
schedules in effective. 
Randomization offers a solution here. In partic-
ular, from among all the security measures to
which randomization could be applied, LAWA
police have so far posed two cru cial problems to
us. First, given that there are many roads leading
into LAX, they want to know where and when
they should set up check points to check cars driv-
ing into LAX. For example, figure 1 shows a vehic-
ular checkpoint set up on a road inbound towards
LAX. Police officers examine cars that drive by,
and if any car appears suspicious, they do a more
detailed inspec 
tion of that car. LAWA police
wished to obtain a randomized schedule for such
checkpoints for a particular time frame. For exam-
ple, if we are to set up two checkpoints, and the
timeframe of interest is 8 
AM
to 11 
AM
, then a can-
didate schedule may suggest to the police that on
Monday, check points should be placed on route 1
and route 2, whereas on Tuesday during the same
time slot, they should be on route 1 and 3, and so
on. Second, LAWA police wished to obtain an
assignment of canines to patrol routes through the

tải về 0.64 Mb.

Chia sẻ với bạn bè của bạn: