计算机应用

作者：祁玄玄, 黄家骏, 曹建安

单位：西安交通大学 电气工程学院, 西安 710049

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

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

来源：2020年第7期

《计算机应用》期刊编辑部

查看计算机应用杂志2020年第7期