Rotecting national infrastructure such as airports, historical

P
rotecting national infrastructure such as airports, historical
landmarks, or a location of political or economic importance 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 important locations includes tasks such as
monitoring all entrances or inbound roads and checking
inbound traffic. However, limited resources imply that it is typ-
ically impossible to provide full security cover age at all times.
Furthermore, adversaries can observe se curity arrangements
over time and exploit any predictable patterns to their advan-
tage. Randomizing schedules for pa trolling, checking, or moni-
toring is thus an important tool in the police arsenal to avoid
the vulnerability that comes with predictability. Even beyond
protecting infrastructure, ran domized patrolling is important in
tasks ranging from secu rity on university campuses to normal
police beats to border or maritime security (Billante 2003,
Paruchuri et al. 2007, Ruan et al. 2005). 
This article 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 chal lenges in
building such a software assistant. First, the as sistant must pro-
vide quality guarantees in randomization by appropriately
weighing the costs and benefits of the different options avail-
able. For example, if an attack on one part of an infrastructure
will cause economic damage while an at tack on another could
potentially cost human lives, we must weigh the two options
differently—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 en able a mixed-initiative interaction
with potential users rather than dictate a schedule; the assistant
may be unaware of users’ real-world constraints, and hence
users must be able to shape the schedule development. 
We have addressed these challenges in a software assis tant
Articles
SPRING 2009 43
Copyright © 2009, Association for the Advancement of Artificial Intelligence. All rights reserved. ISSN 0738-4602