Quadrotor UAV Path Planning Based on Rapidly-exploration Directional Tree Algorithm

doi:10.16182/j.issn1004731x.joss.23-1165

Abstract

Abstract:

Aiming at the problems of low planning success rate, slow convergence speed, and suboptimal paths in the RRT algorithm for quadrotor UAV path planning of in complex environments, a directional exploration tree algorithm is proposed, which uses a directional sampling strategy to improve the directionality of the tree expansion, and by introducing an adaptive target adjustment strategy and a branch expansion strategy, the tree can expand quickly towards the target point while avoiding obstacles. The redundant points in the initial path are removed by the pruning process, and then the trajectory correction and smoothing process are performed on the pruned path to obtain the optimal route. Simulation results show that the proposed algorithm is successful in all tests. relative to the traditional RRT and improved RRT algorithms in multi-obstacle environments, in multi-obstacle environments, in terms of planning time, the proposed algorithm reduces 91.9% and 67%, in terms of path length, the proposed algorithm reduces 37% and 6%; in narrow environments compared in terms of planning time, the proposed algorithm reduces 88.3% and 70%, in terms of path length, the proposed algorithm reduces 36% and 5.6%.

Key words: directional sampling, adaptive target, pruning optimization, smoothing, quadrotor UAV

CLC Number:

TP311.5

Hu Shijun, Liu Hailiang, Wang Binglei, Su Wenke. Quadrotor UAV Path Planning Based on Rapidly-exploration Directional Tree Algorithm[J]. Journal of System Simulation, 2025, 37(2): 311-324.

Figures/Tables 23

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Fig. 13

Fig. 14

Fig. 15

Fig. 16

Table 1

Fig. 17

Fig. 18

Fig. 19

Fig. 20

Table 2

Fig. 21

References 24

1	Zhang Hao, Xin Bin, Dou Lihua, et al. A Review of Cooperative Path Planning of an Unmanned Aerial Vehicle Group[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(12): 1671-1694.
2	杨旭, 王锐, 张涛. 面向无人机集群路径规划的智能优化算法综述[J]. 控制理论与应用, 2020, 37(11): 2291-2302.
	Yang Xu, Wang Rui, Zhang Tao. Review of Unmanned Aerial Vehicle Swarm Path Planning Based on Intelligent Optimization[J]. Control Theory & Applications, 2020, 37(11): 2291-2302.
3	李文刚, 汪流江, 方德翔, 等. 联合A^*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43(12): 3694-3702.
	Li Wengang, Wang Liujiang, Fang Dexiang, et al. Path Planning Algorithm Combining A^* with DWA[J]. Systems Engineering and Electronics, 2021, 43(12): 3694-3702.
4	郭一聪, 刘小雄, 章卫国, 等. 基于改进势场法的无人机三维路径规划方法[J]. 西北工业大学学报, 2020, 38(5): 977-986.
	Guo Yicong, Liu Xiaoxiong, Zhang Weiguo, et al. 3D Path Planning Method for UAV Based on Improved Artificial Potential Field[J]. Journal of Northwestern Polytechnical University, 2020, 38(5): 977-986.
5	方群, 徐青. 基于改进粒子群算法的无人机三维航迹规划[J]. 西北工业大学学报, 2017, 35(1): 66-73.
	Fang Qun, Xu Qing. 3D Route Planning for UAV Based on Improved PSO Algorithm[J]. Journal of Northwestern Polytechnical University, 2017, 35(1): 66-73.
6	李文广, 胡永江, 庞强伟, 等. 基于改进遗传算法的多无人机协同侦察航迹规划[J]. 中国惯性技术学报, 2020, 28(2): 248-255.
	Li Wenguang, Hu Yongjiang, Pang Qiangwei, et al. Track Planning of Multi-UAV Cooperative Reconnaissance Based on Improved Genetic Algorithm[J]. Journal of Chinese Inertial Technology, 2020, 28(2): 248-255.
7	王宇, 王文浩, 徐凡, 等. 基于改进蚁群算法的植保无人机路径规划方法[J]. 农业机械学报, 2020, 51(11): 103-112, 92.
	Wang Yu, Wang Wenhao, Xu Fan, et al. Path Planning Approach Based on Improved Ant Colony Optimization for Sprayer UAV[J]. Transactions of the Chinese Society for Agricultural Machinery, 2020, 51(11): 103-112, 92.
8	Zhou Ying, Zhang Endong, Guo Hongling, et al. Lifting Path Planning of Mobile Cranes Based on an Improved RRT Algorithm[J]. Advanced Engineering Informatics, 2021, 50: 101376.
9	刘光才, 马寅松, 齐福强, 等. 基于改进A^*-人工势场法的城市物流无人机路径规划[J]. 飞行力学, 2022, 40(6): 16-23.
	Liu Guangcai, Ma Yinsong, Qi Fuqiang, et al. Flight Path Planning for Urban Logistics UAV Based on Improved A^*-APF Algorithm[J]. Flight Dynamics, 2022, 40(6): 16-23.
10	宋超, 李波, 马云红, 等. 基于优化A^*和MPC融合算法的三维无人机航迹规划[J]. 系统工程与电子技术, 2023, 45(12): 3995-4004.
	Song Chao, Li Bo, Ma Yunhong, et al. 3D UAV Trajectory Planning Based on Optimized A^* and MPC Fusion Algorithm[J]. Systems Engineering and Electronics, 2023, 45(12): 3995-4004.
11	孔维立, 王峰, 周平华, 等. 改进蚁群算法的无人机三维路径规划[J]. 电光与控制, 2023, 30(3): 63-69.
	Kong Weili, Wang Feng, Zhou Pinghua, et al. Three-dimensional Path Planning of UAVs Based on Improved Ant Colony Algorithm[J]. Electronics Optics & Control, 2023, 30(3): 63-69.
12	邓灏, 唐希浪, 蔡忠义, 等. 基于改进遗传算法的多无人机搜索航路规划[J]. 电光与控制, 2024, 31(4): 12-17.
	Deng Hao, Tang Xilang, Cai Zhongyi, et al. Multi-UAV Search Route Planning Based on Improved Genetic Algorithm[J]. Electronics Optics & Control, 2024, 31(4): 12-17.
13	刘文倩, 单梁, 张伟龙, 等. 复杂环境下基于改进Informed RRT^*的无人机路径规划算法[J]. 上海交通大学学报, 2024, 58(4): 511-524.
	Liu Wenqian, Shan Liang, Zhang Weilong, et al. Unmanned Aerial Vehicle Path Planning Algorithm Based on Improved Informed RRT^* in Complex Environment[J]. Journal of Shanghai Jiao Tong University, 2024, 58(4): 511-524.
14	Jain Gatij, Yadav Gaurav, Prakash Dhruv, et al. MVO-based Path Planning Scheme with Coordination of UAVs in 3-D Environment[J]. Journal of Computational Science, 2019, 37: 101016.
15	王庆禄, 吴冯国, 郑成辰, 等. 基于优化人工势场法的无人机航迹规划[J]. 系统工程与电子技术, 2023, 45(5): 1461-1468.
	Wang Qinglu, Wu Fengguo, Zheng Chengchen, et al. UAV Path Planning Based on Optimized Artificial Potential Field Method[J]. Systems Engineering and Electronics, 2023, 45(5): 1461-1468.
16	魏武, 韩进, 李艳杰, 等. 基于双树Quick-RRT^*算法的移动机器人路径规划[J]. 华南理工大学学报(自然科学版), 2021, 49(7): 51-58.
	Wei Wu, Han Jin, Li Yanjie, et al. Path Planning of Mobile Robots Based on Dual-Tree Quick-RRT^* Algorithm[J]. Journal of South China University of Technology(Natural Science Edition), 2021, 49(7): 51-58.
17	向金林, 王鸿东, 欧阳子路, 等. 基于改进双向RRT的无人艇局部路径规划算法研究[J]. 中国造船, 2020, 61(1): 157-166.
	Xiang Jinlin, Wang Hongdong, Ouyang Zilu, et al. Algorithm of Local Path Planning for Unmanned Surface Vehicles Based on Improved Bi-RRT[J]. Shipbuilding of China, 2020, 61(1): 157-166.
18	李磊, 吴翔, 包祥威, 等. 基于改进RRT-connect算法的机械臂抓取路径规划[J]. 机器人技术与应用, 2021(2): 28-32.
	Li Lei, Wu Xiang, Bao Xiangwei, et al. Robotic Arm Grasping Path Planning Based on Improved RRT-connect Algorithm[J]. Robot Technique and Application, 2021(2): 28-32.
19	Li Binghui, Chen Badong. An Adaptive Rapidly-exploring Random Tree[J]. IEEE/CAA Journal of Automatica Sinica, 2022, 9(2): 283-294.
20	Karaman S, Frazzoli E. Sampling-based Algorithms for Optimal Motion Planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
21	Gammell J D, Srinivasa S S, Barfoot T D. Informed RRT^*: Optimal Sampling-based Path Planning Focused Via Direct Sampling of an Admissible Ellipsoidal Heuristic[C]//2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE, 2014: 2997-3004.
22	Jeong I B, Lee S J, Kim J H. Quick-RRT^: Triangular Inequality-based Implementation of RRT^ with Improved Initial Solution and Convergence Rate[J]. Expert Systems with Applications, 2019, 123: 82-90.
23	Huang Jie, Sun Wei. A Method of Feasible Trajectory Planning for UAV Formation Based on Bi-directional Fast Search Tree[J]. Optik, 2020, 221: 165213.
24	王硕, 段蓉凯, 廖与禾. 机器人路径规划中快速扩展随机树算法的改进研究[J]. 西安交通大学学报, 2022, 56(7): 1-8.
	Wang Shuo, Duan Rongkai, Liao Yuhe. Research on Improvement of Rapidly Exploring Random Tree Algorithm in Robot Path Planning[J]. Journal of Xi'an Jiaotong University, 2022, 56(7): 1-8.

算法	平均时间/s	平均路径/m	成功率/%
传统RRT	2.000	1 786.0	100
改进RRT	0.494	1 197.0	100
RDT	0.161	1 124.4	100

算法	平均时间/s	平均路径/m	成功率/%
传统RRT	1.770	1 580.41	85
改进RRT	0.693	1 073.45	100
RDT	0.207	1 012.41	100

[1]	Lai Rongshen, Dou Lei, Wu Zhiyong, Sun Shuai. Fusion of Improved A* and Dynamic Window Approach for Mobile Robot Path Planning [J]. Journal of System Simulation, 2024, 36(8): 1884-1894.
[2]	Chen Zhen, Yang Haikuan, Jiang Nan, Wang Yuancheng, Jiang Tianjiao. Design of Universal Control Load System of Helicopter Flight Simulator [J]. Journal of System Simulation, 2019, 31(11): 2408-2412.
[3]	Pan Jian, Liu Changlong. UAV Attitude Control with LQR Controller Based on Extended State Observer [J]. Journal of System Simulation, 2018, 30(2): 753-759.
[4]	Li Dongxia, Song Fuhan, Liu Ruihua. Assessment and Verification of Code-carrier Coherence on BDS [J]. Journal of System Simulation, 2018, 30(10): 3949-3957.
[5]	Zhu Chunli, Li Xin. Speech Endpoint Detection Method Based on LMS Noise Reduction and Improved Dual-threshold [J]. Journal of System Simulation, 2017, 29(9): 1950-1960.
[6]	Qi Pengcheng, Zhao Zhonggai, Liu Fei. State Estimation Approach by Fusing Delayed Measurements and Its Application [J]. Journal of System Simulation, 2016, 28(8): 1818-1823.
[7]	Liang Feng, Zhang Zhili, Li Xiangyang, Tang Zhibo, Ma Chao. Research on Motion Control Technology of Virtual Human’s Lower Limb Based on Optical Motion Capture Data [J]. Journal of System Simulation, 2015, 27(2): 327-335.