Tangentbug: a Range-Sensor-Based Navigation Algorithm
.
Tangentbug: A Range-Sensor-Based Navigation Algorithm.
The International Journal of Robotics Research, 17(9):934-953, 1998
Online Version
A pdf version is available for download.
Abstract
The Bug family algorithms navigate a 2-DOF mobile robot in a completely unknown environment using sensors. TungetBug is a new algorithm in this family, specifically designed for using a range sensor. TungetBug uses the range data to compute a locally shortest path, based on a novel structure termed the local tangent graph (LTG). The robot uses the LTG for choosing the locally optimal direction while moving toward the target, and for making local shortcuts and testing the leaving condition while moving along an obstacle boundary. The transition between these two modes of motion is governed by a globally convergent criterion which is based on the distance of the robot from the target. We analyze the properties of TungetBug, and present simulation results that show that TungetBug consistently performs better than the classical Bug algorithms. The simulation results also show that TungetBug produces paths that in simple environments approach the globally optimal path, as the sensor's maximal detection-range increases. The algorithm ca be readily implemented on a mobile robot, and we discuss one such implementation.
Co-authors
Bibtex Entry
@article{KamonRR98a,
title = {Tangentbug: A Range-Sensor-Based Navigation Algorithm},
author = {Ishay Kamon and Elon Rimon and Ehud Rivlin},
year = {1998},
month = {September},
journal = {The International Journal of Robotics Research},
volume = {17},
number = {9},
pages = {934-953},
abstract = {The Bug family algorithms navigate a 2-DOF mobile robot in a completely unknown environment using sensors. TungetBug is a new algorithm in this family, specifically designed for using a range sensor. TungetBug uses the range data to compute a locally shortest path, based on a novel structure termed the local tangent graph (LTG). The robot uses the LTG for choosing the locally optimal direction while moving toward the target, and for making local shortcuts and testing the leaving condition while moving along an obstacle boundary. The transition between these two modes of motion is governed by a globally convergent criterion which is based on the distance of the robot from the target. We analyze the properties of TungetBug, and present simulation results that show that TungetBug consistently performs better than the classical Bug algorithms. The simulation results also show that TungetBug produces paths that in simple environments approach the globally optimal path, as the sensor's maximal detection-range increases. The algorithm ca be readily implemented on a mobile robot, and we discuss one such implementation.}
}