A Graph Search Algorithm for Indoor Pursuit / Evasion

Athanasios Kehagias, Geoffrey Hollinger, and Sanjiv Singh
tech. report CMU-RI-TR-08-38, Robotics Institute, Carnegie Mellon University, August, 2008


Download
  • Adobe portable document format (pdf) (964KB)
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.

Abstract
Using concepts from both robotics and graph theory, we formulate the problem of indoor pursuit / evasion in terms of searching a graph for a mobile evader. We present an offline, greedy, iterative algorithm which performs guaranteed search, i.e. no matter how the evader moves, it will eventually be captured; in fact our algorithm can be applied to either an adversarial (actively trying to avoid capture) or randomly moving evader. Furthermore the algorithm produces an internal search (the searchers move only along the edges of the graph, teleporting is not used) and can accommodate extended (across nodes) visibility and finite or infinite evader speed. We present search experiments for several indoor environments, some of them quite complicated, in all of which the algorithm succeeds in clearing the graph (i.e. capturing the evader).

Keywords
graph search, multi-robot coordination, pursuit / evasion

Notes
Associated Center(s) / Consortia: Field Robotics Center
Associated Project(s): EMBER
Number of pages: 27

Text Reference
Athanasios Kehagias, Geoffrey Hollinger, and Sanjiv Singh, "A Graph Search Algorithm for Indoor Pursuit / Evasion," tech. report CMU-RI-TR-08-38, Robotics Institute, Carnegie Mellon University, August, 2008

BibTeX Reference
@techreport{Kehagias_2008_6124,
   author = "Athanasios Kehagias and Geoffrey Hollinger and Sanjiv Singh",
   title = "A Graph Search Algorithm for Indoor Pursuit / Evasion",
   booktitle = "",
   institution = "Robotics Institute",
   month = "August",
   year = "2008",
   number= "CMU-RI-TR-08-38",
   address= "Pittsburgh, PA",
}