Continuous Search and Patrolling on Networks

Abstract

This award will contribute to securing the national defense by modeling and solving search and patrolling problems on networks. The project will 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 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 award supports 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 will also address the need to understand how search and patrolling policies may be constrained by the topology of the environment. This award will support the participation of a talented graduate student in this research, and the PI will integrate the results of the research into a graduate level course in game theory.

This research models 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 project will consider the problems of finding (i) a patrol of a network that minimizes the probability of a successful attack or infiltration by an intelligent adversary and (ii) a time-minimal search for a target hidden on a network according to either a known or unknown probability distribution. A game theoretic framework will be used to deal with adversaries and unknown probability distributions, whilst a "one-sided" approach will be used in the case of known probability distributions. The research will exploit graph theoretical properties of networks to produce optimal or near-optimal policies based on an understanding of the structure of the networks, rather than using black box algorithms.

Project participants

Faculty: Thomas Lidbetter

PhD students: Thuy (Christy) Bui

Publications

• Bui, T., Lidbetter, T. and Lin, K. (2023) Searching with overlook probabilities: multiple targets and optimal pure strategies, European Journal of Operations Research (in press, draft here)

• Bui, T. and Lidbetter, T. (2022) Optimal patrolling strategies for trees and complete networks, European Journal of Operational Research, 311(2):769-776 (draft here)

• Alpern, S., Lidbetter, T and Papadaki, K. (2022) Continuous patrolling games, Operations Research, 70(6):3076-3089 (draft here)

• Angelopoulos, S. and Lidbetter, T. (2020) Competitive search in a network, European Journal of Operational Research, 286(2):781-790 (draft here)

• Alpern, S. and Lidbetter, T. (2020) Search and delivery man problems: when are depth-first paths optimal? European Journal of Operational Research 285(3):965-976 (draft here)

Acknowledgements

This material is based upon work supported by the National Science Foundation under Grant No. CMMI-1935826.