Technical Report CIS9712

Title: Range-Sensor Based Navigation in Three Dimensions
Authors: Ishay Kamon, Elon Rimon and Ehud Rivlin
Abstract: We present new results in range-sensor based navigation of a point robot in three-dimensional polyhedral environments, and incorporate them into a new globally convergent navigation algorithm. We show that the entire surface of a polyhedral obstacle is visible from a finite number of view points, which are located on convex edges within theconvex hull of the obstacle. We introduce the locally shortest path in three dimensions, investigate its properties and present a novel method for estimating it. Based on these results we described a novel data structure, termed the Conves Edges Graph or CEG, which consists of convex obstacle edges and supports both surface exploration and calculation of shortest paths. We then describe the new algorithm, termed 3DBug. The 3DBug algorithm strives to process the sensory data in the most reactive way possible, without sacrificing the global convergence guarantee. 3DBug is the first Bug-type algorithm which uses three-dimensional range data and plans three-dimensional motion throughout the navigation process. During motion towards the target the robot follows the locally shortest path in a purely reactive fashion. During traversal of obstacle surface, which is the second motion mode of the algorithm, the robot incrementally constructs the CEG of the obstacle being followed, while performing local shortcuts based on range data. Simulations show that $3DBug$ generates paths which resemble the globally shortest paths in simple scenarios. Moreover, the algorithm generates reasonably short paths even in a concave, room-like environment.
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 1997
To the main CS technical reports page

Computer science department, Technion