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.