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

Visibility
Navigation
Robots
Data structures
Sensors
Robotics

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).

Gap navigation trees : Minimal representation for visibility-based tasks. / Tovar, Benjamín; Guilamo, Luis; LaValle, Steven M.

Algorithmic Foundations of Robotics VI. ed. / Michael Erdmann; Mark Overmars; A. Frank van der Stappen; Hsu Hsu. 2005. p. 425-440 (Springer Tracts in Advanced Robotics; Vol. 17).

Research output: Chapter in Book/Report/Conference proceedingChapter

Tovar, B, Guilamo, L & LaValle, SM 2005, Gap navigation trees: Minimal representation for visibility-based tasks. in M Erdmann, M Overmars, AF van der Stappen & H Hsu (eds), Algorithmic Foundations of Robotics VI. Springer Tracts in Advanced Robotics, vol. 17, pp. 425-440.
Tovar B, Guilamo L, LaValle SM. Gap navigation trees: Minimal representation for visibility-based tasks. In Erdmann M, Overmars M, van der Stappen AF, Hsu H, editors, Algorithmic Foundations of Robotics VI. 2005. p. 425-440. (Springer Tracts in Advanced Robotics).
Tovar, Benjamín ; Guilamo, Luis ; LaValle, Steven M. / Gap navigation trees : Minimal representation for visibility-based tasks. Algorithmic Foundations of Robotics VI. editor / Michael Erdmann ; Mark Overmars ; A. Frank van der Stappen ; Hsu Hsu. 2005. pp. 425-440 (Springer Tracts in Advanced Robotics).
@inbook{3384879f22434e70ad175f9fe082b9a8,
title = "Gap navigation trees: Minimal representation for visibility-based tasks",
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.",
author = "Benjam{\'i}n Tovar and Luis Guilamo and LaValle, {Steven M.}",
year = "2005",
month = "12",
day = "1",
language = "English (US)",
isbn = "9783540257288",
series = "Springer Tracts in Advanced Robotics",
pages = "425--440",
editor = "Michael Erdmann and Mark Overmars and {van der Stappen}, {A. Frank} and Hsu Hsu",
booktitle = "Algorithmic Foundations of Robotics VI",

}

TY - CHAP

T1 - Gap navigation trees

T2 - Minimal representation for visibility-based tasks

AU - Tovar, Benjamín

AU - Guilamo, Luis

AU - LaValle, Steven M.

PY - 2005/12/1

Y1 - 2005/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84872041573&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84872041573&partnerID=8YFLogxK

M3 - Chapter

AN - SCOPUS:84872041573

SN - 9783540257288

T3 - Springer Tracts in Advanced Robotics

SP - 425

EP - 440

BT - Algorithmic Foundations of Robotics VI

A2 - Erdmann, Michael

A2 - Overmars, Mark

A2 - van der Stappen, A. Frank

A2 - Hsu, Hsu

ER -