基于改进A^*算法的无人车路径规划

Path planning for unmanned vehicle based on improved A^*algorithm

传统的A^*算法在无人车路径规划中存在规划时间较长和搜索范围较大的缺点。综合分析A^*算法的计算流程后,从四个方面对A^*算法进行改进:1)目标性拓展,即根据待扩展节点和目标节点的相对位置来有目标性地选择不同的象限进行节点拓展;2)目标可见性判断,即判断待扩展节点与目标点之间有无障碍物,若无障碍物则跳出A^*算法的探索过程,以此减少多余的搜索;3)改变A^*算法的启发函数,即增加待扩展节点的n辈父节点到目标点的代价估计,以此减少到目标点的代价估计的局部最优情况;4)改变扩展节点的选取方略,即改变传统的最小化启发函数来选择扩展节点的方式,通过引入模拟退火法来优化扩展节点的选择方式,使得搜索过程尽可能向靠近目标点的方向进行。最后通过Matlab仿真实验结果表明,在模拟的地图环境下,提出的改进A^*算法在运行时间上减少67.06%,经历的栅格数减少73.53%,优化路径长度浮动范围在±0.6%。

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%.