Pursuit-evasion in an unknown environment using Gap Navigation Trees

Luis Guilamo, Benjamin Tovar, Steven M Lavalle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we present an online algorithm for pursuit-evasion in a unknown simply connected environment, for one pursuer that has minimal sensing and carries a set of stationary sentries that it can drop off and pick up during the pursuit. In our sensing model, the pursuer is only able to detect discontinuities in depth information (gaps), and it is able to find all of the evaders without any explicit localization or geometric information, by using a Gap Navigation Tree. The strategy is based on growing an evader-free region, by reading "exploration" schedules from the Gap Navigation Tree, that is constructed online. We prove that a pursuer with k + 1 sentries can clear any environment that could be cleared by k pursuers using the algorithm in [6], which required a complete map and perfect sensing.

Original languageEnglish (US)
Title of host publication2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
Pages3456-3462
Number of pages7
StatePublished - Dec 1 2004
Event2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) - Sendai, Japan
Duration: Sep 28 2004Oct 2 2004

Publication series

Name2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
Volume4

Other

Other2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
CountryJapan
CitySendai
Period9/28/0410/2/04

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Pursuit-evasion in an unknown environment using Gap Navigation Trees'. Together they form a unique fingerprint.

  • Cite this

    Guilamo, L., Tovar, B., & Lavalle, S. M. (2004). Pursuit-evasion in an unknown environment using Gap Navigation Trees. In 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 3456-3462). (2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS); Vol. 4).