Range-sensor-based navigation in three-dimensional polyhedral environments

This paper is concerned with the problem of sensor-based navigation in thre e dimensions. The robot, which is modeled as a "bug" or a "point robot," ha s no a priori knowledge of the environment. A must rather use its sensors t o perceive the environment and plan a collision-free path to various target s. The robot is further required to navigate in the most reactive way possi ble, retaining the smallest amount of information required for global conve rgence to the target. We assume a three-dimensional polyhedral environment and present two basic results for sensor-based navigation in this environme nt. First we establish sufficient conditions for range-sensor-based explora tion of the entire surface of a general polyhedron and present a a strategy for performing this task. Then we characterize the locally shortest path f rom the current robot location to the target and present a method for estim ating this path in time that is linear with the problem size. Based on thes e results, we present a range-sensor-based navigation algorithm for a bug r obot in a general three-dimensional polyhedral environment. The algorithm, called 3 D Bug, strives to process the sensory data in the most reactive wa y possible, without sacrificing its global convergence guarantee. The algor ithm 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 th e second mode of motion, the robot attempts to reach exit points along an o bstacle surface, while simultaneously expanding its knowledge of the obstac le based on range data. We provide analysis of the algorithm, showing that if the target is reachable, the robot always finds obstacle exit points fro m which it reaches the target. Otherwise the robot eventually possesses ful l knowledge of the obstacle blocking its path to the target and determines that the target is unreachable. We have also implemented and verified the a lgorithm on three-dimensional simulated environments. The simulation result s show that 3 D Bug generates paths that resemble the globally shortest pat h in simple scenarios and reasonably short paths in concave roomlike enviro nments.