适合复杂环境的改进A^(*)路径规划算法

An improved A(*)path planning algorithm for complex environments

针对传统A算法在机器人路径规划中存在的缺陷,提出一种改进的A^(*)路径规划算法;对实际代价函数和预估代价函数进行动态权重分配,提高前端路径搜索的初始轨迹质量。结合曼哈顿距离和对角线距离设计非传统表达的启发函数,准确地估计每个节点与目标节点的距离,实现全局路径最短,减少寻路时间和转向次数;针对大幅转角情况下路径不够平滑问题,应用贝塞尔曲线拟合生成的路径点。仿真结果表明:改进的A算法能够在复杂环境中生成最短全局路径,平均转向次数减少24.75%,平均寻路时间缩短30.66%,具有耗时短、转向次数少、路径更平滑等优点。

To overcome the shortcomings of traditional A algorithm in robot path planning,an improved A(*)path planning algorithm was proposed.By assigning dynamic weights to the actual cost function and the predicted cost function,the initial trajectory quality of the front-end path search was improved effectively.Then,the non-traditional expression of the heuristic function was designed by combining Manhattan distance and the diagonal distance,which can improve the accuracy of the distance estimation between each source node and target node,thus achieve the shortest global path and reduce the searching time and steering number.Furthermore,to smooth the path in the case of large corners,Bessel curve equations were applied to curve-fit the generated paths,so the trajectories at the corners became smoother.The simulation results show that the proposed improved A(*)algorithm in this paper can generate the shortest global paths in complex environments.The average number of steering times is reduced by 24.75%,and the average path finding time is shortened by 30.66%.Therefore,the proposed A algorithm has the advantages of the least time-consuming,the least steering number and smoother paths.