Rotecting national infrastructure such as airports, historical

humans have difficulty randomizing. Instead,
mathemati cal randomization that appropriately
weighs the costs and benefits of different actions
and randomizes accordingly leads to improved
results. Security officials were hence extremely
enthusiastic in their reception of our research and
eager to apply it to their domain. In addition, these
officials have indicated that obtaining schedules
automat ically reduces their burden of having to
construct such schedules manually taking all the
relevant factors into ac count. 
Importance of 
Manual Schedule Overrides
While AR MOR incorporates all the knowledge that
we could obtain from LAWA police and provides the
best output possi ble, it may not be aware of dynam-
ic developments on the ground. For example, police
officers may have very spe 
cific intelligence for
requiring a checkpoint on a particu lar inbound road.
Hence, it was crucial to allow LAWA police officers
(in rare instances when it is necessary) to manually
selectively override the schedule provided. 
Importance of Providing Police Officers
with Operational Flexibility
When initially generating schedules for ca nine
patrols, the system created a very detailed sched-
ule, micromanaging the patrols. This did not get as
positive a reception from the officers. Instead, an
abstract sched ule that afforded the officers some
flexibility to respond to dynamic situations on the
ground was better received. 
Experimental Results 
Our experimental results explore the run-time effi-
ciency of DOBSS and evaluate the solution quality
and implementa tion of the ARMOR system. 
Run-Time Analysis 
It has been shown in Paruchuri et al. (2008) that
DOBSS sig nificantly outperforms its competitors,
which include MIP-Nash (Sandholm, Gilpin, and
Conitzer 2005) and multiple LPs (Conitzer and
Sandholm 2006) in an experimental do main that
involves a security agent patrolling a world con sist-
ing of m houses, 1 … m and a robber trying to rob
these houses. These results show that even for a
world as small as three houses, MIP-Nash and mul-
tiple LPs are unable to con verge on a solution with-
in the allowed time of 30 minutes when there are 8
or more adversary types. DOBSS, how ever, is able to
achieve a solution in less than 10 seconds for up to
14 adversary types. Also, as the number of houses
increases up to five, Paruchuri and colleagues find
that MIP-Nash and multiple LPs are unable to con-
verge on a solution within 30 minutes for even low
numbers of adversary types (Paruchuri et al. 2008). 
Our run-time analysis adds to the above results,
focusing specifically on the current security
domain for which this work has been applied. For
this reason we compare the run-time results of
DOBSS versus multiple LPs, described pre viously,
given the specific domain used for canine deploy-
ment at LAX. MIP-Nash (Sandholm, Gilpin, and
Conitzer 2005) has not been included in this
analysis of run times as it only provides the best
Bayes-Nash equilibrium as opposed to the optimal
mixed strategies provided by the multiple-LPs
method and the DOBSS method. The aim of this
analysis is to show that DOBSS is indeed the most
suitable procedure for application to real domains
such as the LAX canine and checkpoint allocation.
To that end, we used the data from a full week of
canine deployment to analyze the time nec essary
to generate a schedule given the DOBSS method
and the multiple-LPs method. For completeness we
show the results given one to four adversary types
where four adver 
sary types is the minimum
amount LAWA has set forth as necessary. 
In figure 8 we summarize the run-time results for
our Bayesian games using DOBSS and multiple LPs.
We tested our results on the Bayesian games pro-
vided from the canine domain with number of
adversary types varying between one to four. Each
game between LAWA and one adversary type is
modeled as a normal form game. Thus, there are
four normal form games designed for the game
between LAWA and the various adversary types for
the base case. The size of each of these normal
form games is (784, 8), corresponding to 784
strategies for LAWA and 8 for the adversary. We
then used the seven generated instances, taken
from an arbitrary week of canine deployment, of
this base case to obtain averaged results. 
The x-axis in figure 8 shows the number of fol-
lower types the leader faces starting, and the y-axis
of the graph shows the run time in seconds. All the
experiments that were not concluded in 20 min-
utes (1,200 seconds) were cut off. From the graph
we summarize that DOBSS outperforms the multi-
ple-LPs method by a significant margin given our
real canine domain. In the graph, while multiple
LPs could solve the problem only for up to two
adversary types, DOBSS could solve for all four
adversary types within 80 seconds. 
Hence we see that the DOBSS method is faster
than the multiple-LPs method. Consequently, we
conclude that DOBSS is the algorithm of choice for
Bayesian Stackelberg games (Paruchuri et al. 2008),
especially given the partic ular games created by
real security domains such as the ca nine patrolling
problem presented in this article. 
Evaluation of ARMOR 
We now evaluate the solution quality obtained
when DOBSS is applied to the LAX security

tải về 0.64 Mb.

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