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

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

Abstract

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

CLC Number:

TP242.6

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.

Figures/Tables 16

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Table 1

Table 2

Weights of DWA evaluation function

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

Table 2

Table 3

Weights of fusion algorithm evaluation function

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

Table 3

Table 4

Weights of improved fusion algorithm evaluation function

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

Table 4

Table 5

Fig. 9

Fig. 10

Fig. 11

References 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]	Jiang Zhaozhen, Wang Wenlong, Sun Wenqi. Path Planning Rapid Algorithm Based on Modified RRT* for Unmanned Surface Vessel [J]. Journal of System Simulation, 2024, 36(4): 888-900.
[2]	Li Gaoyang, Li Xiangfeng, Zhao Kang, Jin Yuchao, Yi Zhidong, Zuo Dunwen. Three-Dimensional Path Planning of UAV Based on All Particles Driving Wild Horse Optimizer Algorithm [J]. Journal of System Simulation, 2024, 36(3): 595-607.
[3]	Liu Fulin, Li Qingxin. Formation Strategy of Hybrid Obstacle Avoidance Algorithm for Multiple Mobile Robots [J]. Journal of System Simulation, 2024, 36(3): 726-734.
[4]	Yu Xiang, Jiang Chen, Duan Sirui, Deng Qianrui. Path Planning for Improvement of A* Algorithm and Artificial Potential Field Method [J]. Journal of System Simulation, 2024, 36(3): 782-794.
[5]	Tang Yunchao, Qi Shaojun, Zhu Lixue, Zhuo Xianrong, Zhang Yunqi, Meng Fan. Obstacle Avoidance Motion in Mobile Robotics [J]. Journal of System Simulation, 2024, 36(1): 1-26.
[6]	Chen Dejun, Fang Zihao, Zeng Yunxiu, Xu Kai. Deceptive Path Planning in Fog of War [J]. Journal of System Simulation, 2023, 35(9): 1895-1908.
[7]	Li Wenjing, Luo Yanlin, Wang Yuhui, Zhu Li. Virtual Navigation Path Planning Based on Octree Potential Field for Endonasal Endoscope [J]. Journal of System Simulation, 2023, 35(9): 2054-2063.
[8]	Junqiang Lin, Hongjun Wang, Xiangjun Zou, Po Zhang, Chengen Li, Yipeng Zhou, Shujie Yao. Obstacle Avoidance Path Planning and Simulation of Mobile Picking Robot Based on DPPO [J]. Journal of System Simulation, 2023, 35(8): 1692-1704.
[9]	Laiyi Yang, Jing Bi, Haitao Yuan. Intelligent Path Planning for Mobile Robots Based on SAC Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1726-1736.
[10]	Menglong Cao, Wenbin Zhao, Zhiqiang Chen. Robot Path Planning by Fusing Particle Swarm Algorithm and Improved Grey Wolf Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1768-1775.
[11]	Hailan Yang, Yongqiang Qi, Baolei Wu, Dan Rong, Miaoying Hong, Jun Wang. Path Planning of Mobile Robots Based on Memristor Reinforcement Learning in Dynamic Environment [J]. Journal of System Simulation, 2023, 35(7): 1619-1633.
[12]	Dalei Song, Wenhao Gan, Yingzhi Xu, Xiuqing Qu, Jiangli Cao. Simulation of Real-Time Path Planning and Formation Control for Unmanned Surface Vessel [J]. Journal of System Simulation, 2023, 35(5): 957-970.
[13]	Yuwen Wu, Zhiyue Niu, Zhenping Li. Picking Path Planning of Container Robots Based on Improved Genetic Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1086-1097.
[14]	Junxiao Xue, Xiangyan Kong, Bowei Dong, Hao Tao, Haiyang Guan, Lei Shi, Mingliang Xu. Obstacle Avoidance and Simulation of Carrier-Based Aircraft on the Deck of Aircraft Carrier [J]. Journal of System Simulation, 2023, 35(3): 592-603.
[15]	Guohui Zhang, Xuan Wang, Yanan Zhang, Ang Gao. Research on Cooperative Path Planning Model of Multiple Unmanned Vehicles in Real Environment [J]. Journal of System Simulation, 2023, 35(2): 408-422.