New Range-sensor Based Globally Convergent Navigation Algorithm for Mobile Robots

Ishay Kamon, Ehud Rivlin, and Elon Rimon.
New range-sensor based globally convergent navigation algorithm for mobile robots.
In Proceedings - IEEE International Conference on Robotics and Automation., 1:429--435, 1996

Online Version

A pdf version is available for download.

Abstract

We present TangentBug, a new range-sensor based navigation algorithm for two degrees-of-freedom mobile robots. The algorithm combines local reactive planning with globally convergent behavior. For the local planning, TangentBug uses the range data to compute a locally shortest path based on a novel structure termed the local tangent graph, or LTG. The robot uses the LTG for choosing the locally optimal direction while moving towards the target. The robot also uses the LTG in its other motion mode, where it follows an obstacle boundary. In this mode the robot uses the LTG for making local shortcuts and testing a leaving condition which allows the robot to resume its motion towards the target. We analyze the convergence and performance properties of TangentBug. We also present simulation results, showing that TangentBug consistently performs better than the classical VisBug algorithm. Moreover, TangentBug produces paths that in simple environments approach the globally optimal path as the sensor's maximal detection range increases.

Co-authors

Bibtex Entry

@inproceedings{KamonRR96i,
  title = {New range-sensor based globally convergent navigation algorithm for mobile robots},
  author = {Ishay Kamon and Ehud Rivlin and Elon Rimon},
  year = {1996},
  month = {April},
  booktitle = {Proceedings - IEEE International Conference on Robotics and Automation.},
  volume = {1},
  pages = {429--435},
  abstract = {We present TangentBug, a new range-sensor based navigation algorithm for two degrees-of-freedom mobile robots. The algorithm combines local reactive planning with globally convergent behavior. For the local planning, TangentBug uses the range data to compute a locally shortest path based on a novel structure termed the local tangent graph, or LTG. The robot uses the LTG for choosing the locally optimal direction while moving towards the target. The robot also uses the LTG in its other motion mode, where it follows an obstacle boundary. In this mode the robot uses the LTG for making local shortcuts and testing a leaving condition which allows the robot to resume its motion towards the target. We analyze the convergence and performance properties of TangentBug. We also present simulation results, showing that TangentBug consistently performs better than the classical VisBug algorithm. Moreover, TangentBug produces paths that in simple environments approach the globally optimal path as the sensor's maximal detection range increases.}
}