Abstract: For the unmanned vehicle path planning problem in uneven terrain environment, an interleaved granularity map model is proposed, and then a path planning algorithm named Interleaved granularity A^*(IGA^*) algorithm is established. First, an interleaved granularity map model is established to store relevant environmental information by interleaving two sub-maps to generate the corresponding steepness map and complete the theoretical description of environmental information. Then, based on the traditional A^* algorithm, combined with the interleaved granularity map model, the path nodes are evaluated in terms of terrain slope, ground step height, and terrain steepness for passability, and a new cost function is established to guide the algorithm to avoid terrain path points that are not suitable for passing, and the IGA^* algorithm path planning strategy is established finally. The proposed IGA^* algorithm is tested and evaluated in four different map conditions and compared with the traditional A^* algorithm and the improved A^* algorithm reported in literature. The results reveal that the proposed IGA^* algorithm can well balance the algorithm efficiency and the path quality, and the planning time can be reduced by 65.5% on average, the change of unit path elevation can be reduced by 61.2% on average, and the change of unit path ground steepness can be reduced by 73.2% on average. Compared with the improved A^* algorithm reported in literatures,the planning time can be reduced by 87.3% on average, the change of unit path elevation can be reduced by 18.2% on average, and the change of unit path ground steepness can be reduced by 38.1% on average,and thus more efficient and safer path planning can be achieved.

Key words: unmanned vehicle, path planning, uneven terrain, A^* algorithm, digital elevation model