关键词: 路径规划, A^*算法, 目标性拓展, 启发函数, 模拟退火

Abstract: The traditional A^* algorithm has the disadvantages of long planning time and large search range in unmanned vehicle path planning. After comprehensively analyzing the calculation process of the A^* algorithm, the A^* algorithm was improved from four aspects. Firstly, targeted expansion, that is, different quadrants were selected with target for node expansion according to the relative position of the node to be expanded and the target node. Secondly, target visibility judgment, that is, whether there were obstacles between the node to be expanded and the target point was determined, if there were no obstacles, A^* algorithm jumped out of the exploration process to reduce redundant searches. Thirdly, the heuristic function of the A^* algorithm was changed, that is, the cost estimation of the n-th generation parent node of the node to be expanded to the target point was increased, thereby reducing the local optimal situation of the cost estimation to the target point. Fourthly, the selection strategy of the expanded nodes was changed, that is, the traditional method of minimizing the heuristic function to select the expanded nodes was changed, and the simulated annealing method was introduced to optimize the selection method of the expanded nodes, so that the search process was performed as close to the target point as possible. Finally, the Matlab simulation experimental results show that, under the simulated map environment, the improved A^* algorithm has the running time reduced by 67.06%, the number of experienced grids decreased by 73.53%, and the fluctuation range of the optimized path length is ±0.6%.

Key words: path planning, A^* algorithm, targeted expansion, heuristic function, simulated annealing