基于Dijkstra算法的平滑路径规划方法

A smooth path planning method based on Dijkstra algorithm

移动机器人在复杂环境下沿Dijkstra算法规划的路径运动时,由于所规划的路径存在转折点多、部分转折角度小等问题,导致移动机器人不得不频繁转向,甚至要暂停才能完成转向,严重影响机器人的工作效率。利用几何拓扑学方法,结合实际场景信息,提出一种基于Dijkstra算法的平滑路径规划方法。根据应用场景获取连续化地图,将连续化地图离散化后随机生成离散点阵,计算各点之间的欧氏距离,选取与各离散点距离较近、且连线不跨越障碍的多个点,将其连接并生成离散图。在离散图中利用Dijkstra算法搜索最优路径作为引导路径。当移动机器人沿引导路径运动时,结合实际场景信息,采用几何拓扑学计算出移动机器人每一时刻应该采取的最佳动作和运行路线。实验结果表明:所提方法能够有效减少移动机器人运动中的累计转弯角度,增大最小平均转折角度,提高所规划路径的平滑度,从而缩短移动机器人的运动时间,提升机器人的工作效率。

When the mobile robot moves along the path planned by the Dijkstra algorithm in a complex environment,due to the planned path having many turning points and some turning angles being small,the mobile robot has to turn frequently or even pause to complete the turning,which seriously affects the working efficiency of the robot.In this study,the mobile robot’s actual scene data is combined with the geometric topology method to propose smooth path planning method based on Dijkstra algorithm.The continuous map is obtained according to the application scenario,and the discrete lattice is randomly generated after the discretization of the continuous map,and the Euclidean distance between the points is calculated.Multiple points which are close to the discrete points and whose connection does not cross the barrier are selected to connect them and generate the discrete graph.The Dijkstra algorithm is used to search the optimal path as the guidance path in the discrete graph.The geometric topology is utilized to determine the optimum action and the running path that the mobile robot should follow at each time as it proceeds along the guidance path in conjunction with the actual scene information.Experimental results show that the proposed method can effectively reduce the cumulative turning angles,increase the minimum average turning angle,and improve the smoothness of the planned path,thus shortening the movement time of the mobile robot and improving the working efficiency of the robot.