Pursuit-evasion problems on terrains

地形上的追逃问题

• 批准号: 261290-2007
• 负责人: Yang, Boting
• 金额: $ 1.46万
• 依托单位: University of Regina
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2010
• 资助国家: 加拿大
• 起止时间: 2010-01-01 至 2011-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=455855
• 关键词: Pursuit; evasion; problems; terrains

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.

在许多情况下，一组移动代理（如警察、士兵甚至机器人）必须在指定区域搜索一个或多个移动逃犯。例如，假设一个搜索队在荒野中寻找一个失踪的人。协调这群搜索者是一项艰巨的任务，而保证搜索队伍不会忽视某个区域似乎是一项艰巨的任务。GPS等技术可以帮助搜索者提高协调能力，但搜索方仍然依赖于人类开发的搜索策略。我们提出的研究重点是在这种情况下自动计算搜索策略。我们通过所谓的地形对需要搜索的区域进行建模，这是一种容易捕获不同海拔信息的数学模型。我们关注的是寻找算法，用于计算保证找到失踪者的地形的搜索策略。与这个问题有关，产生了许多有趣的问题。例如，给定一个地形，搜索该地形所需的最少搜索者数量是多少？搜索地形的最小成本是多少？这些问题对于搜索者数量有限的应用程序尤为重要。