融合RRT*与DWA算法的移动机器人动态路径规划

doi:10.16182/j.issn1004731x.joss.22-1543

系统仿真学报 ›› 2024, Vol. 36 ›› Issue (4): 957-968.doi: 10.16182/j.issn1004731x.joss.22-1543

融合RRT*与DWA算法的移动机器人动态路径规划

张瑞¹(), 周丽¹^,²^,³(), 刘正洋¹

^1.南京信息工程大学, 江苏南京 210000
^2.江苏省大气环境与装备技术协同创新中心, 江苏南京 210000
^3.江苏省气象能源利用与控制工程技术研究中心, 江苏南京 210000

收稿日期:2022-12-23 修回日期:2023-03-11 出版日期:2024-04-15 发布日期:2024-04-18
通讯作者: 周丽 E-mail:1220617335@qq.com;lk_zhouli@163.com
第一作者简介:张瑞(1995-)，男，硕士生，研究方向为移动机器人路径规划算法。E-mail：1220617335@qq.com
基金资助:
国家自然科学基金面上项目(61573190)

Dynamic Path Planning for Mobile Robot Based on RRT* and Dynamic Window Approach

Zhang Rui¹(), Zhou Li¹^,²^,³(), Liu Zhengyang¹

^1.Nanjing University of Information Science &Technology, Nanjing 210000, China
^2.Jiangsu Collaborative Innovation Center of Atmospheric Environment and Equipment Technology, Nanjing 210000, China
^3.Jiangsu Engineering Research Center on Meteorological Energy Using and Control (C-MEIC), Nanjing 210000, China

Received:2022-12-23 Revised:2023-03-11 Online:2024-04-15 Published:2024-04-18
Contact: Zhou Li E-mail:1220617335@qq.com;lk_zhouli@163.com

摘要/Abstract

摘要：

为实现移动机器人在复杂动态障碍物环境中的避障，提出一种改进的快速随机扩展树(rapidly-exploring random tree，RRT*)与动态窗口法(dynamic window approach，DWA)相融合的动态路径规划方法。基于已知环境信息，利用改进RRT*算法生成全局最优安全路径。通过消除RRT*算法产生的危险节点，来确保全局路径的安全性；使用贪婪算法去除路径中的冗余节点，以缩短全局路径的长度。利用DWA算法跟踪改进RRT*算法规划的最优路径。当全局路径上出现静态障碍物时，通过二次调整DWA算法评价函数的权重来避开障碍物并及时回归原路线；当环境中出现移动障碍物时，通过提前检测危险距离并转向加速的方式安全驶离该区域。仿真结果表明：该算法在复杂动态环境中运行时间短、路径成本小，与障碍物始终保持安全距离，确保在安全避开动态障碍物的同时，跟踪最优路径。

关键词: 移动机器人, 路径规划, 改进RRT*算法, 动态窗口法, 动态避障

Abstract:

A dynamic path planning method combining RRT* and dynamic window approach(DWA) is proposed to realize the obstacle avoidance of mobile robot in complex environment of dynamic obstacles. Improved RRT* algorithm is used to generate the global optimal safe path based on the known environment information. By eliminating the dangerous nodes generated by RRT* algorithm, the security of global path is ensured.Greedy algorithm is used to remove the redundant nodes in the path to reduce the length of global path. DWA is used to track along the global optimal path planned by the improved RRT* algorithm. When static obstacles appear on the global path, the weights of DWA algorithm evaluation function is adjusted twice to avoid the obstacles and return to the original path in time. When moving obstacles is in the environment. By detecting the dangerous distance in advance, changing direction and speeding up, the robot can safely drive away from the area. Simulation experiments verify that the improved fusion algorithm proposed in complex dynamic environment has shorter running time, smaller path cost, and always keeps safe distance from obstacles, which ensures the optimal tracked path while safely avoiding the dynamic obstacles.

Key words: mobile robot, path planning, improved RRT* algorithm, dynamic window approach, dynamic obstacle avoidance

中图分类号:

TP242.6

张瑞,周丽,刘正洋 . 融合RRT*与DWA算法的移动机器人动态路径规划[J]. 系统仿真学报, 2024, 36(4): 957-968.

Zhang Rui,Zhou Li,Liu Zhengyang . Dynamic Path Planning for Mobile Robot Based on RRT* and Dynamic Window Approach[J]. Journal of System Simulation, 2024, 36(4): 957-968.

图/表 16

图1

图2

图3

图4

图5

图6

图7

图8

表1

表2

DWA评价函数权重

参数	固定权重	参数	固定权重
$α$	0.1	$γ$	0.4
$β$	0.3

表2

表3

融合算法评价函数权重

参数	固定权重	参数	固定权重
$α$	0.1	$γ$	0.4
$β$	0.3	$θ$	0.1

表3

表4

改进融合算法评价函数权重

参数	逼近权重	避障权重
$α$	0.4	0.1
$β$	0.3	0.3
$γ$	0.2	0.4
$θ$	0.2	0.1

表4

表5

图9

图10

图11

参考文献 19

1	朱久德. 复杂环境下移动机器人的路径规划算法研究[D]. 昆明: 云南大学, 2021.
	Zhu Jiude. Research on Path Planning Algorithm of Mobile Robot in Complex Environment[D]. Kunming: Yunnan University, 2021.
2	吕雪飞. 复杂动态障碍物环境下的移动机器人路径规划研究[D]. 哈尔滨: 哈尔滨理工大学, 2021.
	Xuefei Lü. Research on Path Planning of Mobile Robot in Complex Dynamic Obstacle Environment[D]. Harbin: Harbin University of Science and Technology, 2021.
3	张新艳, 邹亚圣. 基于改进A^*算法的自动导引车无碰撞路径规划[J]. 系统工程理论与实践, 2021, 41(1): 240-246.
	Zhang Xinyan, Zou Yasheng. Collision-free Path Planning for Automated Guided Vehicles Based on Improved A^* Algorithm[J]. Systems Engineering-Theory & Practice, 2021, 41(1): 240-246.
4	王乐乐, 眭泽智, 蒲志强, 等. 一种改进RRT的多机器人编队路径规划算法[J]. 电子学报, 2020, 48(11): 2138-2145.
	Wang Lele, Sui Zezhi, Pu Zhiqiang, et al. An Improved RRT Algorithm for Multi-robot Formation Path Planning[J]. Acta Electronica Sinica, 2020, 48(11): 2138-2145.
5	江洪, 蒋潇杰. 基于RRT改进的路径规划算法[J]. 重庆理工大学学报(自然科学), 2021, 35(7): 10-16, 124.
	Jiang Hong, Jiang Xiaojie. Improved Path Planning Algorithm Based on RRT[J]. Journal of Chongqing University of Technology(Natural Science), 2021, 35(7): 10-16, 124.
6	韩尧, 李少华. 基于改进人工势场法的无人机航迹规划[J]. 系统工程与电子技术, 2021, 43(11): 3305-3311.
	Han Yao, Li Shaohua. UAV Path Planning Based on Improved Artificial Potential Field[J]. Systems Engineering and Electronics, 2021, 43(11): 3305-3311.
7	张瑜, 宋荆洲, 张琪祁. 基于改进动态窗口法的户外清扫机器人局部路径规划[J]. 机器人, 2020, 42(5): 617-625.
	Zhang Yu, Song Jingzhou, Zhang Qiqi. Local Path Planning of Outdoor Cleaning Robot Based on an Improved DWA[J]. Robot, 2020, 42(5): 617-625.
8	常路, 单梁, 戴跃伟, 等. 未知环境下基于改进DWA的多机器人编队控制[J]. 控制与决策, 2022, 37(10): 2524-2534.
	Chang Lu, Shan Liang, Dai Yuewei, et al. Multi-robot Formation Control in Unknown Environment Based on Improved DWA[J]. Control and Decision, 2022, 37(10): 2524-2534.
9	刘亚秋, 赵汉琛, 刘勋, 等. 一种基于改进的快速扩展随机树的工业机器人路径避障规划算法[J]. 信息与控制, 2021, 50(2): 235-246, 256.
	Liu Yaqiu, Zhao Hanchen, Liu Xun, et al. An Improved RRT Based Obstacle Avoidance Path Planning Algorithm for Industrial Robot[J]. Information and Control, 2021, 50(2): 235-246, 256.
10	Kuffner J J, LaValle S M. RRT-connect: An Efficient Approach to Single-query Path Planning[C]//Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings. Piscataway, NJ, USA: IEEE, 2000: 995-1001.
11	Karaman S, Frazzoli E. Sampling-based Algorithms for Optimal Motion Planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
12	Nasir Jauwairia, Islam Fahad, Malik Usman, et al. RRT^-SMART: A Rapid Convergence Implementation of RRT^ [J]. International Journal of Advanced Robotic Systems, 2013, 10(7): 299.
13	Wang Wei, Zuo Lei, Xu Xin. A Learning-based Multi-RRT Approach for Robot Path Planning in Narrow Passages[J]. Journal of Intelligent & Robotic Systems, 2018, 90(1): 81-100.
14	王海芳, 张瑶, 朱亚锟, 等. 基于改进双向RRT^*的移动机器人路径规划算法[J]. 东北大学学报(自然科学版), 2021, 42(8): 1065-1070, 1142.
	Wang Haifang, Zhang Yao, Zhu Yakun, et al. Mobile Robot Path Planning Based on Improved Bidirectional RRT^* [J]. Journal of Northeastern University(Natural Science), 2021, 42(8): 1065-1070, 1142.
15	Chang Lu, Shan Liang, Jiang Chao, et al. Reinforcement Based Mobile Robot Path Planning with Improved Dynamic Window Approach in Unknown Environment[J]. Autonomous Robots, 2021, 45(1): 51-76.
16	王永雄, 田永永, 李璇, 等. 穿越稠密障碍物的自适应动态窗口法[J]. 控制与决策, 2019, 34(5): 927-936.
	Wang Yongxiong, Tian Yongyong, Li Xuan, et al. Self-adaptive Dynamic Window Approach in Dense Obstacles[J]. Control and Decision, 2019, 34(5): 927-936.
17	Zhang Xiaotian, Chen Xiyuan. Path Planning Method for Unmanned Surface Vehicle Based on RRT^* and DWA[C]//International Conference on Multimedia Technology and Enhanced Learning. Cham: Springer International Publishing, 2021: 518-527.
18	Jian Xinyu, Zou Ting, Vardy Andrew, et al. A Hybrid Path Planning Strategy of Autonomous Underwater Vehicles[C]//2020 IEEE/OES Autonomous Underwater Vehicles Symposium (AUV). Piscataway, NJ, USA: IEEE, 2020: 1-6.
19	张瑞, 周丽, 刘震锴. 基于MOBDB-RRT^*算法的移动机器人路径规划[J]. 电光与控制, 2022, 29(7): 12-16, 36.
	Zhang Rui, Zhou Li, Liu Zhenkai. Path Planning of Mobile Robot Based on MOBDB-RRT^* Algorithm[J]. Electronics Optics & Control, 2022, 29(7): 12-16, 36.

算法	路径规划长度	路径与障碍物的最短距离
传统RRT*	58.934 3	0.053 87
改进RRT*	58.932 6	0.560 90

算法	运行时间/s	路径长度/m	路径与静态障碍物最短距离/m	路径与动态障碍物最短距离/m
DWA	446	72.859 1	1.139 30	1.054 2
融合算法	547	65.162 1	0.045 90	0.216 4
改进融合算法	270	59.875 6	0.659 68	2.073 5

[1]	姜兆祯, 王文龙, 孙文祺. 基于改进RRT^*算法的无人艇路径规划快速求解算法[J]. 系统仿真学报, 2024, 36(4): 888-900.
[2]	李高扬, 黎向锋, 赵康, 金玉超, 易志东, 左敦稳. 全粒子推动野马优化算法的无人机三维路径规划[J]. 系统仿真学报, 2024, 36(3): 595-607.
[3]	闫星宇, 李大焱, 王妮娅, 张凯翔, 毛剑琳. 带障碍物惩罚因子的多机器人路径规划[J]. 系统仿真学报, 2024, 36(3): 673-685.
[4]	刘福琳, 李庆鑫. 多移动机器人混合避障算法的编队策略[J]. 系统仿真学报, 2024, 36(3): 726-734.
[5]	余翔, 姜陈, 段思睿, 邓千锐. 改进A*算法和人工势场法的路径规划[J]. 系统仿真学报, 2024, 36(3): 782-794.
[6]	庄鹤林, 夏小云, 李康顺, 陈泽丰, 张先超. 电动汽车路径规划模型与算法研究进展[J]. 系统仿真学报, 2024, 36(2): 320-337.
[7]	唐昀超, 祁少军, 朱立学, 卓献荣, 张芸齐, 孟繁. 移动机器人避障运动研究[J]. 系统仿真学报, 2024, 36(1): 1-26.
[8]	陈德峻, 方子豪, 曾云秀, 许凯. 战场迷雾中的欺骗路径规划[J]. 系统仿真学报, 2023, 35(9): 1895-1908.
[9]	李文静, 骆岩林, 王玉辉, 朱丽. 基于八叉树势场的鼻内镜虚拟导航路径规划[J]. 系统仿真学报, 2023, 35(9): 2054-2063.
[10]	林俊强, 王红军, 邹湘军, 张坡, 李承恩, 周益鹏, 姚书杰. 基于DPPO的移动采摘机器人避障路径规划及仿真[J]. 系统仿真学报, 2023, 35(8): 1692-1704.
[11]	杨来义, 毕敬, 苑海涛. 基于SAC算法的移动机器人智能路径规划[J]. 系统仿真学报, 2023, 35(8): 1726-1736.
[12]	曹梦龙, 赵文彬, 陈志强. 融合粒子群算法与改进灰狼算法的机器人路径规划[J]. 系统仿真学报, 2023, 35(8): 1768-1775.
[13]	杨海兰, 祁永强, 吴保磊, 荣丹, 洪妙英, 王军. 动态环境下基于忆阻强化学习的移动机器人路径规划[J]. 系统仿真学报, 2023, 35(7): 1619-1633.
[14]	陈奕梅, 石小凡, 李宝全. 基于改进虚拟弹簧模型的多机器人编队控制[J]. 系统仿真学报, 2023, 35(6): 1235-1244.
[15]	宋大雷, 干文浩, 许嘤枝, 曲秀青, 曹江丽. 无人船实时路径规划与编队控制仿真研究[J]. 系统仿真学报, 2023, 35(5): 957-970.

融合RRT*与DWA算法的移动机器人动态路径规划

Dynamic Path Planning for Mobile Robot Based on RRT* and Dynamic Window Approach

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 16

参考文献 19

相关文章 15

编辑推荐

Metrics

本文评价