Continuous Search and Patrolling on Networks

点击翻译按钮获取中文摘要

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.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.