Grant: Discovery Grants Program - Individual

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.