| 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 3DBug, 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 3DBug generates paths that resemble the
globally shortest path in simple scenarios and reasonably short paths in
concave roomlike environments.