Resolving the pursuit evasion problem in known environment using graph theory

摘要

In this article, we study a form of pursuit-evasion problem, in which one or more pursuers must find a strategy of moves in a given closed environment (such as building) to guarantee the detection of an unpredictable evader. The main idea is to use agraph of visibility between vertices and some techniques to bring this graph into a graph of building areas. Because of the increasing interest on the pursuit-evasion applications, such as: searching buildings for intruders, traffic control, military strategy and surgical operation, a lot of research (Basar and Olsder, 1999; Guibas et al, 1999; Hespanha et al., 1999, 2000; Suzuki and Yamashita, 1992) has been done on this problem. The main interest of this work is the simplification and test of the visibility graph. A technique to solve the pursuit-evasion problem has been proposed, this technique is the worst-case search. Finally, the used tool in the experimental work has been presented.