Technical Report CIS9618

Title: 3DBug: A Three-Dimensional Range-Sensor Based Globally Convergent Navigation Algorithm
Authors: Ishay Kamon, Ehud Rivlin and Elon Rimon
Abstract: 3DBug is a new range-sensor based algorithm for navigating a point robot in an unknown three-dimensional polyhedral environment. When moving towards the target, the robot moves in a purely reactive fashion along the locally optimal path, such that its distance to the target decreases. We develop efficient methods for computing the locally shortest path for this motion mode. When circumnavigating an obstacle, the robot uses the range data to incrementally construct the obstacle shape. The robot attempts to reach a suitable leave point along the shortest possible path, while simultaneously expanding its knowledge of the obstacle. If the target is reachable, the robot always finds a leave point and resumes its motion towards the target. Otherwise the robot eventually possesses full knowledge of the obstacle, and determines that the target is unreachable. Thus 3DBug provides a new and effective sensor-based navigation algorithm for three-dimensions. We analyze the convergence of 3DBug, and present preliminary simulation results, showing that 3DBug produces paths that in simple environments resemble the globally shortest path.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 1996
To the main CS technical reports page

Computer science department, Technion