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. We are especially interested in investigating computational issues of search strategies that are commonly used by people. For example, in some real-life scenarios, the cost of a searcher may be relatively low in comparison to the cost of allowing a fugitive to be free for a long period of time. If a dangerous fugitive is hiding along streets in an area, the police always want to capture the fugitive as soon as possible. Our research will provide new algorithms and eventually software that will assist in various fast search applications.