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.