Research on 3D Path Planning Algorithm Based on Fast RRT Algorithm

doi:10.16182/j.issn1004731x.joss.20-0829

Abstract

Abstract:

RRT (rapidly exploring random tree) algorithm is a sampling-based path planning algorithm, which can search a path in high-dimensional environment. The traditional RRT algorithm has the problems of low node utilization and large amount of calculation. To solve these problems, the fast RRT* (Quick RRT*) algorithm is improved by optimizing the strategy of reselection of parent node and pruning range, improving the sampling method and introducing adaptive step size, which makes the algorithm time-consuming and path length shorter. At the same time, the node connection screening strategy is added to eliminate the excessive turning angle in the path. Experimental results show that the improved algorithm can quickly find the shortest collision free path in three-dimensional environment, and the running time is greatly reduced.

Key words: path planning, improved Quick RRT(rapidly exploring random tree)* algorithm, the node connection screening strategy, adaptive step-size

CLC Number:

TP249

Zhaoqiang Li, Shiyu Zhang. Research on 3D Path Planning Algorithm Based on Fast RRT Algorithm[J]. Journal of System Simulation, 2022, 34(3): 503-511.

Figures/Tables 16

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Table 1

Fig. 11

Fig. 12

Fig. 13

Fig. 14

Table 2

References 10

1	Ammar A, Bennaceur H, Chaari I, et al. Relaxed Dijkstra and A* with Linear Complexity for Robot Path Planning Problems in Large-Scale Grid Environments[J]. Soft Computing (S1432-7643), 2016, 20(10): 1-23.
2	王殿君. 基于改进A~*算法的室内移动机器人路径规划[J]. 清华大学学报(自然科学版), 2012, 52(8): 1085-1089.
	Wang Dianjun.Indoor Mobile-Robot Path Planning Based on an Improved A* Algorithm[J]. Journal of Tsinghua University(Science and Technology), 2012, 52(8): 1085-1089.
3	王全. 基于RRT的全局路径规划方法及其应用研究[D]. 长沙: 国防科技大学, 2014.
	Wang Quan. Research on Rapidly-Exploring Random Trees Based Global Path Planning and its Application[D]. Changsha: National University of Defense Science and Technology, 2014.
4	宋晓琳, 周南, 黄正瑜, 等. 改进RRT在汽车避障局部路径规划中的应用[J]. 湖南大学学报(自然科学版), 2017, 44(4): 30-37.
	Song Xiaolin, Zhou Nan, Huang Zhengyu, et al. An Improved RRT Algorithm of Local Path Planning for Vehicle Collision Avoidance[J]. Journal of Hunan University(Natural Sciences Edition), 2017, 44(4): 30-37.
5	冯楠. 自主移动机器人路径规划的RRT算法研究[D]. 大连: 大连理工大学, 2014.
	Feng Nan. Research on RRT Algorithm of Path Planning for Autonomous Mobile Robot[D]. Dalian: Dalian University of Technology, 2014.
6	刘成菊, 韩俊强, 安康. 基于改进RRT算法的RoboCup机器人动态路径规划[J]. 机器人, 2017, 39(1): 8-15.
	Liu Chengju, Han Junqiang, An Kang. Dynamic Path Planning Based on an Improved RRT Algorithm for RoboCup Robo[J]. Robot, 2017, 39(1): 8-15.
7	李加东. 基于RRT算法的非完整移动机器人运动规划[D]. 上海: 华东理工大学, 2014.
	Li Jiadong. The Study of RRT Algorithm Based Motion Planning for Non-Holonomic Mobile Robot[D]. Shanghai: East China University of Science and Technology, 2014.
8	武晓晶, 许磊, 甄然, 等. 动态步长BI-RRT的无人机航迹规划算法[J]. 河北科技大学学报, 2019, 40(5): 414-422.
	Wu Xiaojing, Xu Lei, Zhen Ran, et al. Dynamic Step BI-RRT UAV Path Planning Algorithm[J]. Journal of Hebei University of Science and Technology, 2019, 40(5): 414-422.
9	向金林, 王鸿东, 欧阳子路, 等. 基于改进双向RRT的无人艇局部路径规划算法研究[J]. 中国造船, 2020, 61(1): 157-166.
	Xiang Jinlin, Wang Hongdong, Ouyang Zilu, et al. Local Path Planning Algorithm for Unmanned Aerial Vehicle Based on Improved Bidirectional RRT[J]. Shipbuilding of China, 2020, 61(1): 157-166.
10	Jeong In-Bae, Lee Seung-Jae, Kim Jong-Hwan. Quick-RRT: Triangular Inequality-Based Implementation of RRT with Improved Initial Solution and Convergence Rate[J]. Expert Systems With Applications (S0957-4174), 2019, 123: 82-90.

算法类别	规划时间/s	采样点个数	路径长度/km
Quick-RRT*	15.33	7 695	154.91
Quick-RRT*1	13.73	5 966	151.19
Quick-RRT*2	8.60	5 689	146.07
Quick-RRT*3	0.93	373	145.49
Quick-RRT*4	1.33	496	144.29

算法类别	规划时间/s	采样点个数	路径长度/km	是否产生有较大转弯角的路径
Quick-RRT*	121.14	42 791	184.97	是
Quick-RRT*1	100.31	33 479	181.35	是
Quick-RRT*2	85.33	32 362	176.48	是
Quick-RRT*3	5.58	971	175.39	是
Quick-RRT*4	10.39	1 898	174.61	否

[1]	Li Zhang, Huizhen Zhang, Dong Liu, Yuxin Lu. Particle Swarm Algorithm for Solving Emergency Material Dispatch Considering Urgency [J]. Journal of System Simulation, 2022, 34(9): 1988-1998.
[2]	Teng Li, Peipei Ding, Jinfang Liu. Multi-Stage Multi-AGV Path Planning with Walk under Shelves for Robotic Mobile Fulfillment Systems [J]. Journal of System Simulation, 2022, 34(7): 1512-1523.
[3]	Sen Zhang, Mengyan Zhang, Jingping Shao, Jiexin Pu. Multi-UAVs 3D Path Planning Method Based on Random Strategy Search [J]. Journal of System Simulation, 2022, 34(6): 1286-1295.
[4]	Dun Meng, Zhuo Hu, Huajun Zhang. Simulation of Multi-layer Ship Evacuation System Based on Improved A* Algorithm [J]. Journal of System Simulation, 2022, 34(6): 1375-1382.
[5]	Xiangyang Deng, Limin Zhang, Wei Fang, Miao Tang. Robot Path Planning Based on Bidirectional Aggregation Ant Colony Optimization [J]. Journal of System Simulation, 2022, 34(5): 1101-1108.
[6]	Qiming Wang, Gaoqiang Zong, Jinming Xu. Optimal Path Planning for Multi-stage Automatic Parking and Simulation Analysis [J]. Journal of System Simulation, 2022, 34(2): 385-395.
[7]	Chen Zhimei, Li Min, Shao Xuejuan, Zhao Zhicheng. Obstacle Avoidance Path Planning of Bridge Crane Based on Improved RRT Algorithm [J]. Journal of System Simulation, 2021, 33(8): 1832-1838.
[8]	Li Qi, Wang Wei. Path Designing of Multi-omnidirectional Wheel Collaborative Sorting Platform [J]. Journal of System Simulation, 2021, 33(3): 698-709.
[9]	Huang Xiaodong, Yuan Haitao, Bi Jing, Liu Tao. DQN-based Path Planning Method and Simulation for Submarine and Warship in Naval Battlefield [J]. Journal of System Simulation, 2021, 33(10): 2440-2448.
[10]	Lin Bin, Han Guanghui, Song Chenchen, Zhang Yajing. Traversal Path Planning and Simulation of Robot based on Radiation Scanning [J]. Journal of System Simulation, 2021, 33(1): 84-90.
[11]	Zhu Daqi, Zhu Tingting, Yan Mingzhong. Multi-AUV Complete Coverage Path Planning Based on Improved Neural Network [J]. Journal of System Simulation, 2020, 32(8): 1505-1514.
[12]	Shi Yan, Zhang Lihua, Dong Shouquan, Wang Jue. Cruise Missile Path Planning Based on ACO Algorithm and Bezier Curve Optimization [J]. Journal of System Simulation, 2020, 32(1): 122-129.
[13]	Shi Min, Wei Yukun, Jin Xiangchen, Wang Suqin, Mao Tianlu. Virtual Scene Roaming Method Supporting Multi-layer Path Planning [J]. Journal of System Simulation, 2019, 31(7): 1358-1366.
[14]	Zhao Ping, Lei Xinyu, Chen Bozhi, Yang Jiaoyun. TI-A* Based Multi-robot Dynamic Planning and Coordination Method [J]. Journal of System Simulation, 2019, 31(5): 925-935.
[15]	Ji Shanshan. Path Planning for Mobile Sink Based on Enhanced Ant Colony Optimization Algorithm in Wireless Sensor Networks [J]. Journal of System Simulation, 2019, 31(11): 2543-2552.