Pursuit-evasion problems on 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.