改进A*算法融合改进动态窗口法的移动机器人路径规划

Mobile Robot Path Planning by Improved A*Algorithm Fused with Improved Dynamic Window Approach

针对机器人路径规划对于路径最短、搜索效率以及平滑度的性能要求,提出一种改进A*算法与改进动态窗口法(DWA)相融合的算法。针对传统A*算法在复杂场景下输出非最优路径、寻路效率低等问题,结合曼哈顿距离和对角线距离设计新的启发函数,并对其动态分配权重,实现全局路径最短,减少寻路时间。针对传统8邻域8方向搜索方式搜索效率低、耗时长等问题,提出一种基于8邻域改进的搜索策略,对当前节点实时动态分配最优的搜索方向。针对路径存在多余无用节点的问题,使用Floyd算法去除冗余节点,减少转向次数,缩短路径长度。针对传统动态窗口法规划的路径非全局最优、目标点附近存在障碍物时规划的路径长度增加或者规划失败的问题,加入全局关键节点信息和引入目标点距离评估子函数。针对关键节点距离较长导致融合算法规划的路径偏离全局最优路径的问题,提出关键点密集化策略。最后,将提出的改进A*算法、融合算法和已有的其他改进算法进行比较,仿真结果表明:改进的A*算法能够在复杂环境中生成最短全局路径,平均转向次数减少16.3%,平均寻路时间缩短55.66%;融合算法在临时障碍物环境下,平均路径长度和平均运行时间分别缩短6.1%和14.7%,在移动障碍物环境下,平均路径长度和平均运行时间分别缩短1.6%和39.8%。

To satisfy the performance requirements for robot path planning,an algorithm integrating improved A*algorithm and improved Dynamic Window Approach(DWA)is proposed,which shortens the path length and improves the searching efficiency and path smoothness.To combat the challenges of the traditional A*algorithm in complex scenarios,a new heuristic function is designed based on Manhattan distance and the diagonal distance.The weights are assigned dynamically,and the global shortest path and the least searching time are obtained.Next,an improved search strategy based on the 8-neighborhood is proposed,which involves dynamically assigning the optimal search direction to the current node,thus improving the searching efficiency and reducing the time consumption compared to the traditional 8-neighborhood 8-direction search method.Subsequently,the Floyd algorithm is employed to remove redundant nodes,reduce the steering times,and shorten the path distance.Additionally,the traditional DWA faces certain challenges;for instance,the path is not globally optimal,the path planning may fail,or the path length may increase.To solve these problems,a keypoint densification strategy is proposed to modify the deflective path.Finally,the proposed improved A*algorithm and fusion algorithm are compared with existing methods.The simulation results show that the improved A*algorithm can generate the shortest global path in complex environments,reducing the average steering time by 16.3%and shortening the average path searching time by 55.66%.For the fused algorithm,the average path length and average runtime shorten by 6.1%and 14.7%in the temporary obstacle environment,respectively,and shorten by 1.6%and 39.8%,respectively,in the moving obstacle environment.