Title: Resolving the pursuit evasion problem in known environment using graph theory

Authors: Rabah Lakel, Adel Djellal

Addresses: Laboratoire d'Automatique et Signaux Avances (LASA), Faculty of Engineering, Electronics Department, Badji Mokhtar University – Annaba, P.O. Box 12, Annaba, Algeria. ' Faculty of Engineering, Electronics Department, Badji Mokhtar University – Annaba, P.O. Box 12, Annaba, Algeria

Abstract: 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 a graph 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.

Keywords: pursuit evasion; robotics; graph theory; bio-inspired computation.

DOI: 10.1504/IJBIC.2010.037023

International Journal of Bio-Inspired Computation, 2010 Vol.2 No.6, pp.434 - 439

Published online: 21 Nov 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article