This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Kamon, I. Articles by Rivlin, E. Search for Related Content Social Bookmarking                         What's this?

Range-Sensor-Based Navigation in Three-Dimensional Polyhedral Environments

CS Department, Technion—Israel Institute of Technology, Technion City, Israel

Elon Rimon

ME Department, Technion—Israel Institute of Technology, Technion City, Israel

Ehud Rivlin

CS Department, Technion—Israel Institute of Technology, Technion City, Israel

This paper is concerned with the problem of sensor-based navigation in three dimensions. The robot, which is modeled as a "bug" or a "point robot," has no a priori knowledge of the environment. It must rather use its sensors to perceive the environment and plan a collision-free path to various targets. The robot is further required to navigate in the most reactive way possible, retaining the smallest amount of information required for global convergence to the target. We assume a three-dimensional polyhedral environment and present two basic results for sensor-based navigation in this environment. First we establish sufficient conditions for range-sensor-based exploration of the entire surface of a general polyhedron and present a strategy for performing this task. Then we characterize the locally shortest path from the current robot location to the target and present a method for estimating this path in time that is linear with the problem size. Based on these results, we present a range-sensor-based navigation algorithm for a bug robot in a general three-dimensional polyhedral environment. The algorithm, called 3 DBug, strives to process the sensory data in the most reactive way possible, without sacrificing its global convergence guarantee. The algorithm uses two modes of motion, called motion-toward-the-target and obstacle- surface-traversal. During the first mode of motion, the robot follows the locally shortest path to the target in a purely reactive fashion. During the second mode of motion, the robot attempts to reach exit points along an obstacle surface, while simultaneously expanding its knowledge of the obstacle based on range data. We provide analysis of the algorithm, showing that if the target is reachable, the robot always finds obstacle exit points from which it reaches the target. Otherwise, the robot eventually possesses full knowledge of the obstacle blocking its path to the target and determines that the target is unreachable. We have also implemented and verified the algorithm on three-dimensional simulated environments. The simulation results show that 3 DBug generates paths that resemble the globally shortest path in simple scenarios and reasonably short paths in concave roomlike environments.

The International Journal of Robotics Research, Vol. 20, No. 1, 6-25 (2001)
DOI: 10.1177/02783640122067246


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?