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

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.