Continuous Search and Patrolling on Networks

该奖项将通过建模和解决网络上的搜索和巡逻问题，为保障国防安全做出贡献。该项目将解决如何以最佳方式在机场或购物中心巡逻以最大限度地减少恐怖袭击的风险，如何在边境巡逻以防止渗透，或如何以最佳方式搜索简易爆炸装置或失踪的徒步旅行者。对此类问题进行建模的一个主要挑战是，智能对手可能有能力查看当前的搜索或巡逻策略，并利用它们的弱点。该奖项支持更好地理解搜索和巡逻问题的战略性质，以便可以采用更好的政策来改善公共安全和安保。它还将解决了解搜索和巡逻策略如何受环境拓扑限制的需要。该奖项将支持一名有才华的研究生参与这项研究，PI将把研究结果整合到博弈论的研究生水平课程中。该研究模拟了网络上连续时间和空间上的搜索和巡逻问题，而不是以往大多数工作所采取的将有限方法应用于离散搜索空间的方法。该项目将考虑寻找(I)使智能对手成功攻击或渗透的概率最小化的网络巡逻以及(Ii)根据已知或未知的概率分布对隐藏在网络上的目标进行最小时间搜索的问题。博弈论框架将被用来处理对手和未知的概率分布，而在已知概率分布的情况下，将使用“单边”方法。这项研究将利用网络的图论属性，基于对网络结构的理解，而不是使用黑盒算法来产生最优或接近最优的策略。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.