A sensor-based direct search algorithm for autonomous path planning on 3-D terrain surfaces

A practical path planning algorithm for 3-D terrain navigation is presented. Path planning is formulated as an unconstrained optimization problem of finding parameters of the parametric equations describing the paths on the terrain surface. When obstacles are present, a traversability test is performed on each candidate path during the searching process. Penalties are added to the cost of every path failing the traversability test. This algorithm produces paths of desired degrees of smoothness which are readily usable by the steering mechanisms of mobile robots. These planned paths optimize the cost of travel. The algorithm uses terrain information derived directly from the online range data. Experimental results reveal that the algorithm has significant computation advantage over existing ones for planning paths on 3-D terrain surfaces