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]	Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2397-2408.
[2]	Ni Peilong, Mao Pengjun, Wang Ning, Yang Mengjie. Robot Path Planning Based on Improved A-DDQN Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2420-2430.
[3]	Zhang Kaixiang, Mao Jianlin, Wang Niya, Xu Zhihao. Multi-robot Hierarchical Collaborative k-robust Path Planning for Path Interference [J]. Journal of System Simulation, 2025, 37(8): 2074-2088.
[4]	Wan Yuhang, Zhu Zilu, Zhong Chunfu, Liu Yongkui, Lin Tingyu, Zhang Lin. Dynamic Path Planning for Robotic Arms Based on an Improved PPO Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1462-1473.
[5]	Ye Chen, Shao Peng, Zhang Shaoping, Li Wenting, Zhou Tengming. Enhanced Artificial Gorilla Algorithm for Mobile Robot Path Planning [J]. Journal of System Simulation, 2025, 37(6): 1474-1485.
[6]	Zhang Yan, Li Binghua, Huo Tao, Liu Rong. Research on Robot Dynamic Obstacle Avoidance Method Based on Improved A* and Dynamic Window Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1555-1564.
[7]	Zhou Xiaohui, Li Yanqiang, Wang Yong, Zhao Decai, Yang Xiaoyao. Robot Path Planning Based on Ant Colony Algorithm with Dual Heuristic Information [J]. Journal of System Simulation, 2025, 37(5): 1280-1289.
[8]	Yu Die, Bao Baizhong, Si Yan, Duan Jian, Zhan Xiaobin, Shi Tielin. Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm [J]. Journal of System Simulation, 2025, 37(4): 1041-1050.
[9]	Zhang Sen, Dai Qiangqiang. UAV Path Planning Based on Improved Deep Deterministic Policy Gradients [J]. Journal of System Simulation, 2025, 37(4): 875-881.
[10]	He Zhigang, Li Dayan, Wang Niya, Mao Jianlin, Wang Ning. A Multi-robot Collaborative Path Planning Algorithm with Chain Working Mode [J]. Journal of System Simulation, 2025, 37(4): 953-967.
[11]	Lin Guijuan, Li Zihan, Wang Yu. Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction [J]. Journal of System Simulation, 2025, 37(3): 667-678.
[12]	Bai Yuxin, Chen Zhenya, Shi Ruitao, Su Weitao, Ma Zhuoqiang, Yang Shangjin. Research on Robot Path Planning Based on Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2025, 37(3): 742-752.
[13]	Jin Xu, Mo Yuanbin. Multi-strategy Hybrid Mountain Gazelle Optimizer for Robot Path Planning [J]. Journal of System Simulation, 2025, 37(3): 803-821.
[14]	Li Jiongyi, Li Qiang, Zhang Xinwen, Htet Zin Myo, Cai Yongbin. Improved Bidirectional A* Quadratic Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2025, 37(2): 498-507.
[15]	Peng Yi, Lei Yunkui, Yang Qingqing, Li Hui, Wang Jianming. Improved PID Search Algorithm for UAV Path Planning in Mountainous Environments [J]. Journal of System Simulation, 2025, 37(12): 3075-3086.