Pursuit Evasion and Related Problems

在一个典型的追捕逃避问题中，一个或多个移动搜索者（或警察）正在追捕一个或多个聪明的劫匪。许多现实世界的问题都可以通过适当的追捕-逃避问题来建模。一些例子包括：警察搜寻逃犯，搜救队搜寻失踪者，军队清除敌人或地雷区域，计算机技术人员在计算机网络上搜索移动病毒，甚至消防员从受污染的建筑物中清除有毒气体。在选择逃避追踪的模型时，我们必须首先选择域的表示。研究人员通常用图形和多边形来建模该领域。图形和多边形为道路和建筑物等许多领域提供了自然模型。它们是特别好的模型，因为在考虑搜索数时可以使用图论和计算几何的许多相关结果。在这个提议中，我们考虑了一个非常快速的强盗（或病毒）隐藏在图形、多边形、地形或网络中的追捕-逃避问题。我们提出的研究重点是在这种情况下自动计算搜索策略。我们关心的是寻找算法来计算保证捕获抢劫犯的搜索策略。与这个问题有关，产生了许多有趣的问题。例如，给定一个图形/多边形，搜索图形/多边形所需的最小搜索者数量是多少，这样抢劫者就一定会被找到？搜索图/多边形的最小代价是多少？这些问题对于搜索者数量有限的应用程序尤为重要。

In a typical pursuit-evasion problem, one or more mobile searchers (or cops) are seeking the capture of one or more clever robbers. Many real-world problems can be modeled by an appropriate pursuit-evasion problem. Some examples include: police officers searching for a fugitive, a search-and-rescue team searching for a missing person, a military troop clearing an area of enemies or mines, computer technicians searching for a mobile virus on a computer network, or even firefighters clearing poisonous gas from a contaminated building. When selecting a model for pursuit evasion, we must first choose a representation for the domain. Researchers have typically modeled the domain by graphs and polygons. Graphs and polygons provide natural models for many domains such as roadways and buildings. They are especially good models since many relevant results from graph theory and computational geometry can be employed when considering the search number. In this proposal we consider the pursuit-evasion problems in which a very fast robber (or virus) is hiding in graphs, polygons, terrains, or networks. Our proposed research focuses on automating the computation of search strategies in such scenarios. We are concerned with finding algorithms for computing search strategies that are guaranteed to capture the robber. Many interesting questions arise with relation to this problem. For example, given a graph/polygon, what is the minimum number of searchers required to search the graph/polygon so that the robber will definitely be found? and what is the minimum cost to search the graph/polygon? These questions are particularly important for applications where the number of searchers is limited.