A fast path planning algorithm for robot navigation with limited visibility

Abstract

This paper presents a new algorithm to the motion planning problem for a mobile robot in a local environment. The algorithm uses the step-by-step approach to move the robot along the line that joins the starting point and the goal point. When an obstacle is met the algorithm assigns a value to each one of the eight surrounding points that surround the current point then the robot moves to the point that has the minimum value. Each obstacle point is assigned a relatively large value, while the value assigned to a non-obstacle point is the algebraic sum of the horizontal and the vertical distances from the goal point. The proposed algorithm completely eliminates the local minima problem, which is exhibited in most artificial-potential based methods, and most important it eliminates the "flat-regions" problem. The proposed algorithm is superior to other algorithms because of its low-computational cost besides simplicity. It also outperforms the blind-follow based algorithms. Simulation results demonstrates the validity and the potential of the proposed algorithm.