Gap navigation trees: Minimal representation for visibility-based tasks

Benjamín Tovar, Luis Guilamo, Steven M. LaValle

Research output: Chapter in Book/Report/Conference proceedingChapter


In this paper we present our advances in a data structure, the Gap Navigation Tree (GNT), useful for solving different visibility-based robotic tasks in unknown planar environments. We present its use for optimal robot navigation in simply-connected environments, locally optimal navigation in multiply-connected environments, pursuit-evasion, and robot localization. The guiding philosophy of this work is to avoid traditional problems such as complete map building and exact localization by constructing a minimal representation based entirely on critical events in online sensor measurements made by the robot. The data structure is introduced from an information space perspective, in which the information used among the different visibility-based tasks is essentially the same, and it is up to the robot strategy to use it accordingly for the completion of the particular task. This is done through a simple sensor abstraction that reports the discontinuities in depth information of the environment from the robot's perspective (gaps), and without any kind of geometric measurements. The GNT framework was successfully implemented on a real robot platform.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics VI
Number of pages16
ISBN (Print)9783540257288
StatePublished - 2005

Publication series

NameSpringer Tracts in Advanced Robotics
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'Gap navigation trees: Minimal representation for visibility-based tasks'. Together they form a unique fingerprint.

Cite this