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

Abstract

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
EditorsMichael Erdmann, Mark Overmars, A. Frank van der Stappen, Hsu Hsu
Pages425-440
Number of pages16
StatePublished - Dec 1 2005

Publication series

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

    Fingerprint

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence

Cite this

Tovar, B., Guilamo, L., & LaValle, S. M. (2005). Gap navigation trees: Minimal representation for visibility-based tasks. In M. Erdmann, M. Overmars, A. F. van der Stappen, & H. Hsu (Eds.), Algorithmic Foundations of Robotics VI (pp. 425-440). (Springer Tracts in Advanced Robotics; Vol. 17).