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.