A UAV Trajectory Optimization Method Based on RRT-Dubins

doi:10.12382/bgxb.2023.0611

Abstract

Abstract:

A unmanned aerial vehicle (UAV) trajectory optimization method based on the rapidly-exploring random trees (RRT) algorithm and Dubins curves is proposed to address the problem of UAV trajectory planning in multi-obstacle environments. The initial and final poses, turning radius, and trajectory length, and first-order smoothness constraint of UAV are considered in the trajectory planning. The RRT algorithm and a pruning optimization method based on a greedy algorithm are utilized to plan the feasible discrete waypoints that satisfy the obstacle avoidance requirements in a two-dimensional task space. Multiple Dubins curves are employed to smoothly connect the waypoints. A multi-constraint trajectory optimization mathematical model is established based on the UAV's initial and final poses, and the constraints related to the UAV's performance and obstacles. The particle swarm optimization (PSO) algorithm is employed to determine the curve types and optimize the poses at the curve connections and the curve radii, thereby obtaining the shortest trajectory. Simulated results demonstrate that the proposed method reduces the average trajectory length by 11.48% in various scenarios with different numbers of obstacles and varying initial and final positions, while satisfying the UAV's kinematic constraints and avoiding obstacles compared to other methods.

Key words: unmanned aerial vehicle trajectory planning, rapidly-exploring random trees algorithm, Dubins curve, particle swarm optimization algorithm, trajectory optimization

CLC Number:

V249

WANG Dongzhen, ZHANG Yue, ZHAO Yu, HUANG Daqing. A UAV Trajectory Optimization Method Based on RRT-Dubins[J]. Acta Armamentarii, 2024, 45(8): 2761-2773.

Figures/Tables 18

References 21

[1]	GUANG G, HAQUE A. Path planning for autonomous drones: challenges and future directions[J]. Drones, 2023, 7(3): 169.
[2]	LI W H, WANG L, ZOU A W, et al. Path planning for UAV based on improved PRM[J]. Energies, 2022, 15(19): 7267.
[3]	左松涛, 毛占利, 范传刚, 等. 基于地铁站场景的改进型Dijkstra算法疏散路径规划研究[J]. 铁道科学与工程学报, 2023, 20(5): 1624-1635.
	ZUO S T, MAO Z L, FAN C G, et al. Evacuation path planning based on improved Dijkstra algorithm in metro station scene[J]. Journal of Railway Science and Engineering, 2023, 20(5): 1624-1635. (in Chinese)
[4]	何志强, 专祥涛, 梁杰, 等. 基于区域人工势场的无人船目标跟踪策略研究[J]. 中国造船, 2023, 64(1): 236-245.
	HE Z Q, ZHUAN X T, LIANG J, et al. Research on target tracking strategy of unmanned surface vessel based on regional artificial potential field[J]. Shipbuilding of China, 2023, 64(1): 236-245. (in Chinese)
[5]	DUBINS L E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents[J]. American Journal of Mathematics, 1957, 79: 497-516.
[6]	张家闻, 房浩霖, 李家旺. 基于复杂约束条件的欠驱动AUV三维路径规划[J]. 兵工学报, 2022, 43(6): 1407-1414. doi: 10.12382/bgxb.2021.0340
	ZHANG J W, FANG H L, LI J W. 3D path planning of underactuated AUV based on complex constraints[J]. Acta Armamentarii, 2022, 43(6): 1407-1414. (in Chinese) doi: 10.12382/bgxb.2021.0340
[7]	SHARF A A, ABDI K A, HOSSEINIAN S M, et al. Evaluation of the application of maximum radius in horizontal curves using vehicle dynamic simulation[J]. Advances in Civil Engineering, 2022, 2022: 5237541.
[8]	CELESTINI D, PRIMATESITA S, CAPELLO E. Trajectory planning for UAVs based on interfered fluid dynamical system and Bézier curves[J]. IEEE Robotics and Automation Letters, 2022, 7(4): 9620-9626.
[9]	DUAN H B, ZHAO J X, DENG Y M, et al. Dynamic discrete pigeon-inspired optimization for multi-UAV cooperative search-attack mission planning[J]. IEEE Transactions on Aerospace and Electronic Systems, 2021, 57(1): 706-720.
[10]	JIANG X J, HUANG B D. Global path planning of fixed-wing UAV based on improved RRT algorithm[J]. Journal of Applied Science and Engineering, 2023, 26(10): 1441-1450.
[11]	LI J L, KANG F, CHEN C C, et al. The improved A^* algorithm for quadrotor UAVs under forest obstacle avoidance path planning[J]. Applied Sciences, 2023, 13(7): 4290.
[12]	BLASI L, D’AMATO E, NOTARO I, et al. Clothoid-based path planning for a formation of fixed-wing UAVs[J]. Electronics, 2023, 12(10): 2204.
[13]	AHMED A, SOLIMAN A, MAGED A, et al. Path smoothing algorithm using thin-plate spline[C]// Proceedings of the 2021 7th International Conference on Control, Automation and Robotics. Singapore: IEEE, 2021.
[14]	YU W W, LIU J, ZHOU J. A novel sparrow particle swarm algorithm (SPSA) for unmanned aerial vehicle path planning[J]. Scientific Programming, 2021, 2021: 5158304.
[15]	LEI H, BO Q X, GUO X Y, et al. A multiple heterogeneous UAVs reconnaissance mission planning and re-planning algorithm[J]. Journal of Systems Engineering and Electronics, 2022, 33(6): 1190-1207. doi: 10.23919/JSEE.2022.000142
[16]	WU W N, XU J, SUN Y M. Integrate assignment of multiple heterogeneous unmanned aerial vehicles performing dynamic disaster inspection and validation task with Dubins path[J]. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(4): 4018-4032.
[17]	吴立尧, 苏析超, 王垒, 等. 有人/无人机编队队形集结控制研究[J]. 系统工程与电子技术, 2023, 45(7): 2192-2202. doi: 10.12305/j.issn.1001-506X.2023.07.30
	WU L Y, SU X C, WANG L, et al. Research of formation rendezvous control for manned/unmanned aerial vehicles formation[J]. Systems Engineering and Electronics, 2023, 45(7): 2192-2202. (in Chinese) doi: 10.12305/j.issn.1001-506X.2023.07.30
[18]	王福仪, 孟秀云, 张海阔. 基于ε-level蝙蝠算法的无人机三维航迹规划[J]. 北京航空航天大学学报, 2024, 50(5):1593-1603.
	WANG F Y, MENG X Y, ZHANG H K. UAV three-dimensional path planning based on ε-level bat algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2024, 50(5):1593-1603. (in Chinese)
[19]	YANG Y, LEEGHIM H, KIM D. Dubins path-oriented rapidly exploring random tree^* for three-dimensional path planning of unmanned aerial vehicles[J]. Electronics, 2022, 11(15):2338.
[20]	LIN X, WANG C Z, WANG K P, et al. Trajectory planning for unmanned aerial vehicles in complicated urban environments: a control network approach[J]. Transportation Research Part C: Emerging Technologies, 2021, 128: 103120.
[21]	陈良剑, 赵文龙, 娄嘉骏. 基于RRT的动态规避航迹规划算法[J]. 现代计算机, 2021(22): 72-76, 80.
	CHEN L J, ZHAO W L, LOU J J. RRT-based dynamic avoidance route planning algorithm[J]. Modern Computer, 2021(22):72-76,80. (in Chinese)

障碍物类型	编号	圆心坐标	半径
风暴	1	(744,634)	77
	2	(807,909)	73
高炮	1	(129,223)	76
	2	(464,877)	75
雷达	1	(332,267)	75
	1	(240,711)	75
	2	(715,298)	70
山丘	3	(460,512)	74
	4	(840,140)	78
	5	(471,102)	75

障碍物类型	编号	圆心坐标	半径
风暴	1	(744,634)	77
	2	(807,909)	73
高炮	1	(129,223)	76
	2	(464,877)	75
雷达	1	(332,267)	75
	1	(240,711)	75
	2	(715,298)	70
山丘	3	(460,512)	74
	4	(840,140)	78
	5	(471,102)	75

参数	数值	参数	数值
N_g	50	c₁、c₂	2
κ	100	ω	0.8

参数	数值	参数	数值
N_g	50	c₁、c₂	2
κ	100	ω	0.8

起始位姿	目标位姿	障碍物数量	d_min
起始位姿	目标位姿	障碍物数量	15	10	5
(50,50, 0.52π rad)	(950,500, 1.7π rad)	5	1042	1026	1007
(50,50, 1.75π rad)	(600,900, 0.3π rad)	5	1125	1123	1006
(100,50, 0.23π rad)	(900,900, 1.6π rad)	10	1164	1107	1059
(50,50, 0.3π rad)	(950,50, 0.5π rad)	10	1359	1352	1348
(200,20, 1.75π rad)	(950,50, 0.25π rad)	15	1767	1752	1722
(20,500, 1.5π rad)	(980,500, 1.33π rad)	15	1015	1011	1009