Computationally efficient path planning algorithm for autonomous navigation over natural terrain

The present investigation focuses on the development of computationally efficient path planning algorithms for autonomous ground vehicles. The approach selected is based on a heuristic hill climbing local search. The cost index employed incorporates a traversability cost average, which offers two primary benefits: 1) the average extends the region of knowledge of the search algorithm, increasing optimality of the solution; and 2) the avoidance of hazardous regions is added to the decision making process. A binary traversability map representation is first utilized to analyze the performance of the enhanced heuristic hill climbing algorithm in comparison to the more traditional techniques. Next, the search algorithm is applied to a multi-valued traversability map to test the capabilities of the algorithm over natural terrain. For this purpose, a digital elevation map is automatically processed to obtain multi-valued traversability values through the de nition of a roughness, inclination and step index. The complete path planning architecture for natural terrain then consists of a three step approach, computation of the multi-valued traversability map, implementation of the enhanced heuristic hill climbing search algorithm, and a path relaxation step. This last step is employed to fine-tune and smooth the trajectory, eliminating sharp turns caused by the regular characteristics of the search space.