A graph search algorithm for indoor pursuit/evasion

November 2009

A graph search algorithm for indoor pursuit/evasion

Authors:

Athanasios Kehagias, Geoffrey Hollinger, and Sanjiv Singh

Abstract:

Using concepts from both robotics and graph theory, we formulate the problem of indoor pursuit/evasion in terms of searching the nodes of a graph for a mobile evader. We present the IGNS (Iterative Greedy Node Search) algorithm, which performs offline guaranteed search (i.e. no matter how the evader moves, it will eventually be captured). Furthermore, the algorithm produces an internal search (the searchers move only along the edges of the graph; “teleporting” is not used) and exploits non-monotonicity, extended visibility and finite evader speed to reduce the number of searchers required to clear an environment. We present search experiments for several indoor environments, in all of which the algorithm succeeds in clearing the graph (i.e. capturing the evader).
@article{Kehagias-2009-10364,
author = {Athanasios Kehagias And Geoffrey Hollinger And Sanjiv Singh},
title = {A graph search algorithm for indoor pursuit/evasion},
journal = {Proceedings of Mathematical and Computer Modelling},
year = {2009},
month = {November},
volume = {50},
number = {10},
pages = {1305 - 1317},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.