Pursuit-evasion problems on terrains

在许多情况下，一组移动的代理，如警察、士兵甚至机器人，必须在规定的区域搜索一个或多个移动的逃犯。例如，考虑一个搜索队在荒野中寻找一个失踪的人。 协调这群搜索者是一项艰巨的任务，确保搜索队不会忽视一个地区似乎是压倒性的。 GPS等技术可以帮助搜索者提高协调性，但搜索方仍然依赖于人类开发的搜索策略。我们提出的研究重点是在这种情况下自动计算搜索策略。 我们通过所谓的地形对需要搜索的区域进行建模，这是一种可以轻松捕获不同海拔信息的数学模型。 我们关心的是寻找算法计算搜索策略的地形，保证找到失踪的人。 许多有趣的问题与这个问题有关。 例如，给定一个地形，搜索地形所需的最少搜索人数是多少？搜索地形的最低成本是多少 这些问题对于搜索者数量有限的应用程序尤其重要。我们对研究人类常用的搜索策略的数学模型非常感兴趣。 例如，考虑我们的激励示例，其中搜索队正在寻找失踪人员。为了确保没有任何区域被忽视，搜索方通常会采用链式搜索策略：搜索者形成一个扫描搜索区域的链。 研究人员已经考虑了用于计算建筑平面图数学模型的链搜索策略的算法，但这些算法不能用于搜索区域包含山丘和山谷的场景。我们的研究将提供新的算法，并最终提供有助于各种搜索和救援应用的软件。

There are many situations where a group of mobile agents, such as police officers, soldiers, or even robots, must search a prescribed area for one or more mobile fugitives. For example, consider a search party looking for a missing person in the wilderness.  Coordinating this group of searchers is an intimidating task, and guaranteeing that the search party does not overlook an area seems overwhelming.  Technology such as GPS can help searchers improve coordination, but the search party still relies on search strategies that are developed by humans. Our proposed research focuses on automating the computation of search strategies in such scenarios.  We model the area that needs to be searched by a so-called terrain, a mathematical model that easily captures information about different elevations.  We are concerned with finding algorithms for computing search strategies of terrains that are guaranteed to find the  missing person.  Many interesting questions arise with relation to this problem.  For  example, given a terrain, what is the minimum number of searchers required to search the  terrain? and what is the minimum cost to search the terrain?  These questions are particularly important for applications where the number of searchers is limited.We are very interested in investigating mathematical models of search strategies that are commonly  used by humans.  For example, consider our motivating example where a search party is looking for a missing person. In order to ensure that no area is overlooked, the search party will often employ a chain-search strategy: the searchers form a chain that sweeps over the search area.  Reseachers have considered algorithms for computing chain-search strategies for mathematical models of building floorplans, but these algorithms cannot be used in scenarios where the search area contains hills and valleys. Our research will provide new algorithms and eventually software that will assist in various search-and-rescue applications.