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

巩慧; 倪翠; 王朋; 程诺

doi:10.13700/j.bh.1001-5965.2022.0377

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

doi: 10.13700/j.bh.1001-5965.2022.0377

巩慧¹,
倪翠^1, ,,
王朋^{1, 2},
程诺¹

1.
山东交通学院信息科学与电气工程学院，济南 250357
2.
山东省科学院自动化研究所，济南 250013

基金项目: 中国博士后科学基金(2021M702030)；山东省交通运输厅科技计划项目(2021B120)

详细信息

通讯作者:
E-mail：1149993471@qq.com

中图分类号: TP391.4
计量
- 文章访问数: 709
- HTML全文浏览量: 91
- PDF下载量: 24
- 被引次数: 0
出版历程
- 收稿日期: 2022-05-18
- 录用日期: 2022-06-23
- 网络出版日期: 2022-09-15
- 整期出版日期: 2024-02-27

A smooth path planning method based on Dijkstra algorithm

GONG Hui¹,
NI Cui^{1
, ,},
WANG Peng^{1, 2},
CHENG Nuo¹

1.
College of Information Science and Electrical Engineering，Shandong Jiao Tong University，Jinan 250357，China
2.
Institute of Automation，Shandong Academy of Sciences，Jinan 250013，China

Funds: China Postdoctoral Science Foundation (2021M702030); Science and Technology Plan Project of Transportation Department of Shandong (2021B120)

More Information

Corresponding author: E-mail：1149993471@qq.com

摘要

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

HTML全文

图 1 Prim算法生成的模拟地图

Figure 1. Simulation map generated by Prim’s algorithm

下载: 全尺寸图片幻灯片

图 2 模拟地图中随机生成的离散点示意图

Figure 2. A sketch of randomly generated discrete points on a simulated map

下载: 全尺寸图片幻灯片

图 3 由离散点生成的离散图

Figure 3. A discrete graph generated from discrete points

下载: 全尺寸图片幻灯片

图 4 Dijkstra算法在离散图中规划的路径

Figure 4. A path planned by Dijkstra's algorithm in a discrete graph

下载: 全尺寸图片幻灯片

图 5 引导路径获取方法

Figure 5. Method for obtaining boot path

下载: 全尺寸图片幻灯片

图 6 获取的引导路径示意图

Figure 6. Acquired boot path diagram

下载: 全尺寸图片幻灯片

图 7 移动机器人行走轨迹示意图

Figure 7. Mobile robot walking track diagram

下载: 全尺寸图片幻灯片

图 8 移动机器人矫正路径示意图

Figure 8. Path correction diagram of mobile robot

下载: 全尺寸图片幻灯片

图 9 路径规划部分结果示意图

Figure 9. Schematic diagram of partial result of path planning

下载: 全尺寸图片幻灯片

图 10 累计转弯角度比较

Figure 10. Comparison of cumulative turning angles

下载: 全尺寸图片幻灯片

图 11 最小转折角度比较

Figure 11. Comparison of minimum turning angles

下载: 全尺寸图片幻灯片

图 12 总路程与起止距离之比

Figure 12. Ratio of total distance to start-stop distance

下载: 全尺寸图片幻灯片

图 13 移动机器人沿规划路径运动时间比较

Figure 13. Comparison of motion time of mobile robot along planned path

下载: 全尺寸图片幻灯片

参考文献(18)

[1]	LU H W. Artificial intelligence and robotics[M]. Berlin: Springer, 2021: 267-275.
[2]	KO J H. An adaptive path-planning for intelligent AGV system[J]. Journal of the Institute of Electronics and Information Engineers, 2017, 54(4): 115-121.
[3]	CHEN X, ZHAO M Y, YIN L Y. Dynamic path planning of the UAV avoiding static and moving obstacles[J]. Journal of Intelligent & Robotic Systems, 2020, 99(3-4): 909-931.
[4]	殷建军, 董文龙, 梁利华, 等. 复杂环境下农业机器人路径规划优化方法[J]. 农业机械学报, 2019, 50(5): 17-22. YIN J J, DONG W L, LIANG L H, et al. Optimization method of agricultural robot path planning in complex environment[J]. Transactions of the Chinese Society for Agricultural Machinery, 2019, 50(5): 17-22(in Chinese).
[5]	SANG H Q, YOU Y S, SUN X J, et al. The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations[J]. Ocean Engineering, 2021, 223: 108709. doi: 10.1016/j.oceaneng.2021.108709
[6]	ZHONG X Y, TIAN J, HU H S, et al. Hybrid path planning based on safe A* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment[J]. Journal of Intelligent & Robotic Systems, 2020, 99(1): 65-77.
[7]	TIAN X E, LIU L, LIU S A, et al. Path planning of mobile robot based on improved ant colony algorithm for logistics[J]. Mathematical Biosciences and Engineering, 2021, 18(4): 3034-3045. doi: 10.3934/mbe.2021152
[8]	魏彤, 龙琛. 基于改进遗传算法的移动机器人路径规划[J]. 北京航空航天大学学报, 2020, 46(4): 703-711. WEI T, LONG C. Path planning for mobile robot based on an improved genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(4): 703-711(in Chinese).
[9]	车建涛, 高方玉, 解玉文, 等. 基于Dijkstra算法的水下机器人路径规划[J]. 机械设计与研究, 2020, 36(1): 44-48. CHE J T, GAO F Y, XIE Y W, et al. Path planning of underwater robots based on the Dijkstra algorithm[J]. Mechanical Design and Research, 2020, 36(1): 44-48(in Chinese).
[10]	邓叶, 姜香菊. 基于改进人工势场法的四旋翼无人机航迹规划算法[J]. 传感器与微系统, 2021, 40(7): 130-133. DENG Y, JIANG X J. Four-rotor UAV trark planning algorithm based on improved artificial potential field method[J]. Transducer and Microsystem Technologies, 2021, 40(7): 130-133(in Chinese).
[11]	TANG G, TANG C Q, CLARAMUNT C, et al. Geometric A-star algorithm: An improved A-star algorithm for AGV path planning in a port environment[J]. IEEE Access, 2021, 9: 59196-59210. doi: 10.1109/ACCESS.2021.3070054
[12]	HE C W, MAO J A. AGV optimal path planning based on improved ant colony algorithm[J]. EDP Sciences, 2018, 232: 03052.
[13]	LI Y H, HUANG Z H, XIE Y. Path planning of mobile robot based on improved genetic algorithm[C]//2020 3rd International Conference on Electron Device and Mechanical Engineering. Piscataway: IEEE Press, 2020: 691-695.
[14]	SUN Y H, FANG M, SU Y X. AGV path planning based on improved Dijkstra algorithm[J]. Journal of Physics, 2021, 1746(1): 012052.
[15]	ZHU D D, SUN J Q. A new algorithm based on Dijkstra for vehicle path planning considering intersection attribute[J]. IEEE Access, 2021, 9: 19761-19775. doi: 10.1109/ACCESS.2021.3053169
[16]	李全勇, 李波, 张瑞, 等. 基于改进Dijkstra算法的AGV路径规划研究[J]. 机械工程与自动化, 2021(1): 23-25. LI Q Y, LI B, ZHANG R, et al. Research on AGV path planning based on improved Dijkstra algorithm[J]. Mechanical Engineering and Automation, 2021(1): 23-25(in Chinese).
[17]	ZHANG J, WU J, SHEN X, et al. Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star[J]. International Journal of Advanced Robotic Systems, 2021, 18(5): 172988142110427.
[18]	LUAN P G, THINH N T. Hybrid genetic algorithm based smooth global-path planning for a mobile robot[J]. Mechanics Based Design of Structures and Machines, 2023, 51(3): 1758-1774.