基于RRT-Dubins的无人机航迹优化方法

doi:10.12382/bgxb.2023.0611

摘要/Abstract

摘要：

针对多障碍物环境下考虑无人机(Unmanned Aerial Vehicle,UAV)始末位姿、转弯半径和航迹长度的1阶光滑约束的UAV航迹规划问题,提出一种基于快速搜索随机树(Rapidly-exploring Random Trees,RRT)算法和Dubins曲线以局部最优逼近全局最优的UAV航迹优化方法。利用RRT算法和基于贪心算法的剪枝优化方法,在二维任务空间中规划出满足避障要求的可行离散航路点。采用多条Dubins曲线平滑连接航路点,根据UAV始末位姿确定首尾曲线端点,基于UAV性能、障碍物和飞行参数的约束关系,建立多约束的航迹优化数学模型。通过粒子群优化算法确定曲线类型,同时优化曲线连接处位姿和曲线半径,获得最短航迹。仿真结果表明:所提方法得到的航迹与其他方法相比,在不同障碍物数量和始末位姿的多种场景中,平均长度缩短了11.48%,在避开障碍物的同时,满足UAV动力学约束。

关键词: 无人机航迹规划, 快速搜索随机树算法, Dubins曲线, 粒子群优化算法, 航迹优化

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

中图分类号:

V249

王东振, 张岳, 赵宇, 黄大庆. 基于RRT-Dubins的无人机航迹优化方法[J]. 兵工学报, 2024, 45(8): 2761-2773.

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.

图/表 18

图1 参考航迹规划示意图

Fig.1 Illustration of reference trajectory planning

图2 航迹优化示意图

Fig.2 Illustration of trajectory optimization

图3 RRT算法拓展方式

Fig.3 Expansion mode of RRT algorithm

图4 剪枝优化前后的航迹变化示意图

Fig.4 Illustration of trajectory changes before and after pruning optimization

图5 LSR类型Dubins曲线

Fig.5 LSR-type Dubins curve

图6 N个航路点Dubins曲线连接

Fig.6 N-waypoint Dubins curve connection

图7 位姿点方向角约束范围

Fig.7 Range of orientation angle constraint for pose points

表1 任务空间模型障碍物参数

Table 1 Task space model parameters

障碍物类型	编号	圆心坐标	半径
风暴	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

图8 UAV轨迹优化方法3个阶段对应的航迹

Fig.8 Trajectories corresponding to the three steps of UAV trajectory optimization method

图9 PSO算法收敛曲线

Fig.9 Convergence curve of PSO algorithm

图10 位姿点寻优变化示意图

Fig.10 Illustration of pose point optimization changes

表2 PSO算法的各项初始参数

Table 2 Initial parameters of PSO algorithm

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

图11 不同安全距离下航迹

Fig.11 Trajectories at different safety distances

图12 3种dmin下PSO算法收敛曲线

Fig.12 Convergence curves of PSO algorithm at different dmin

表3 不同安全距离下航迹长度对比

Table 3 Comparison of trajectory lengths at different safety distances

起始位姿	目标位姿	障碍物数量	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

表4 不同障碍数量下3种方法仿真结果对比

Table 4 Simulated results of three methods for different numbers of obstacles

图13 3种场景下PSO算法收敛曲线

Fig.13 Convergence curves of PSO algorithm in 3 scenarios

表5 3种平滑方法10次仿真平均长度对比

Table 5 Comparison of the trajectory lengths obtained by 3 smoothing methods in 10 simulations

起始位姿	目标位姿	障碍物数量	航迹长度
起始位姿	目标位姿	障碍物数量	Dubins 曲线方法	B样条曲线方法	文献[21] 方法
(50,50, 0.34π rad)	(950,950, 2π rad)	5	1234	1388	1403
50,50, 1.75π rad)	(500,950, 0.3π rad)	5	967	1066	1102
(50,50, 0.67π rad)	(950,950, 0.25π rad)	10	1355	1497	1509
(50,50, 0.7π rad)	(950,700, 1.5π rad)	10	1244	1403	1438
(500,20, 2π rad)	(950,950, 0.25π rad)	15	1046	1203	1235
(50,50, 2π rad)	(950,950, 0.8π rad)	15	1375	1524	1566

参考文献 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)