The aim of this project was to address how to optimally patrol an airport or shopping mall to minimize the risk of a terrorist attack, how to patrol a border to guard against infiltration, or how to optimally search for an improvised explosive device (IED) or lost hiker. A major challenge of modeling such problems is that intelligent adversaries may have the capability to view current search or patrolling policies and exploit their weaknesses. This project aimed for an improved understanding of the strategic nature of search and patrolling problems, so that better policies can be employed to improve public safety and security. It also addressed the need to understand how search and patrolling policies may be constrained by the topology of the environment.  This research modeled search and patrolling problems on a network in continuous time and space, rather than the approach taken by most previous work of applying finite methods to a discretized search space.

The first part of the project considered the problem of finding a patrol of a network that minimizes the probability of a successful attack or infiltration by an intelligent adversary. A crucial assumption we made we that the length of time required to execute that attack/infiltration is a parameter known to the patroller. Using the framework of game theory, we found optimal randomized patrolling strategies for any type of network, as long as the attack time is relatively short. We strengthened our results for tree networks (that is, those without cycles), and were able to find optimal patrols for any length of attack time.

The second part of the project considered the problem of finding time-minimal searches for a target hidden on a network according to either a known or unknown probability distribution. In the case of a known probability distribution, the problem is equivalent to that of a postal worker who wishes to deliver letters to some locations on a network in such a way as to minimize the average time of delivery (the deliveryman problem).  We focused on addressing this problem for tree networks, and investigated when the optimal search could be characterized as depth-first, meaning that whenever the searcher always chooses an unexplored direction whenever she has a choice. We found necessary criteria for the existence of an optimal depth-first search, and were able to correct an error in the literature about the optimal location of a depot for the deliveryman problem.

In the case of an unknown distribution for the target, we used the framework of game theory to look for optimal searches under the assumption the target is being hidden by an adversary. We use the paradigm of expanding search, which assumes that the time taken to retrace one’s steps is negligible compared to the time taken to explore new territory. This is appropriate if the time required to search is much larger than the time required to move over ground that has already been explored, for example in the search for an IED. We found optimal, and in some cases, near optimal search strategies for this game. We also considered an extension in which there is some probability that the searcher does not find the target even when looking in the right place. In the simple case of a finite number of possible hiding location where these "overlook probabilities” are all the same, we found an optimal search strategy. In general, optimal strategies in games are randomized, but we were able to find optimal deterministic strategies in some cases.

This project has generated five peer reviewed journal publications. The results of the research have been disseminated all over the world in conferences and seminar series in such locations as London, Porto and Sicily. This award has supported the participation of a talented graduate student, and the PI has integrated results of the research into graduate level courses in game theory.

Last Modified: 01/05/2024
Modified by: Thomas Lidbetter