Sensory based motion planning with global proofs

A sensory based algorithm DistBug, that is guaranteed to reach the target in an unknown environment or report that the target is unreachable, is presented. The algorithm is reactive in the sense that it relies on range data to make local decisions, and does not create a world model. The algorithm consists of two behaviors (modes of motion): straight motion between obstacles and obstacle boundary following. Simulation results as well as experiments with a real robot are presented. The condition for leaving obstacle boundary is based on the free range in the direction to the target. This condition allows the robot to leave the obstacle as soon as the local conditions guarantee global convergence. Range data is utilized for choosing the turning direction when the robot approaches an obstacle. A criterion for reversing the boundary following direction when it seems to be the wrong direction is also introduced. As a direct result of these local decisions, a significant improvement in the performance was achieved.