基于改进RRT*算法的无人机在线航迹规划

doi:10.12305/j.issn.1001-506X.2024.12.24

Abstract

Abstract:

In order to solve the problems of low sampling efficiency, slow convergence speed and high trajectory cost when the rapidly-exploring random tree (RRT)* algorithm is applied to unmanned aerial vehicle (UAV) trajectory planning, the potential field method is used to guide the tree expansion to accelerate the convergence speed of the algorithm. The optimization algorithm is applied to reselect the parent node and reroute the process to generate the initial trajectory with the cost which is reduced comparing with the cost of the RRT* algorithm. The heuristic sampling area is constructed based on the initial trajectory to optimize the initial trajectory more effectively, and an improved RRT* algorithm is proposed. Based on model predictive control (MPC), a trajectory planning strategy is designed to enable the UAV to respond well to dynamic threats in the environment during flight. Mathematical simulation results show that the improved algorithm can quickly generate an initial trajectory with less cost, and reduce the trajectory cost in the subsequent trajectory optimization process more effectively, which can be applied to the online planning task of UAV.

Key words: trajectory planning, RRT* algorithm, model predictive control (MPC), potential field

CLC Number:

V249

Haikuo ZHANG, Xiuyun MENG. UAV online trajectory planning based on improved RRT* algorithm[J]. Systems Engineering and Electronics, 2024, 46(12): 4157-4164.

Figures/Tables 22

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Table 1

Table 2

Fig.12

Fig.13

Fig.14

Table 3

Fig.15

Fig.16

Fig.17

Fig.18

Fig.19

References 31

1	DOSHI A A , POSTULA A J , FLETCHER A , et al. Development of micro-UAV with integrated motion planning for open-cut mining surveillance[J]. Microprocessors and Microsystems, 2015, 39 (8): 829- 835. doi: 10.1016/j.micpro.2015.07.008
2	POŁKA M , PTAK S , ŁUKASZ K . The use of UAV's for search and rescue operations[J]. Procedia Engineering, 2017, 192, 748- 752. doi: 10.1016/j.proeng.2017.06.129
3	IVUSHKIN K, BARTHOLOMEUS H, BREGT A, et al. UAV based soil salinity assessment of cropland[J]. 2018, 338: 502-512.
4	DELMERICO J , MUEGGLER E , NITSCH J , et al. Active autonomous aerial exploration for ground robot path planning[J]. IEEE Robotics and Automation Letters, 2017, 2 (2): 664- 671. doi: 10.1109/LRA.2017.2651163
5	张海阔, 孟秀云. 基于改进粒子群算法的无人机航迹规划[J]. 飞行力学, 2024, 42 (2): 29- 35.
	ZHANG H K , MENG X Y . UAV route planning based on improved particle swarm optimization algorithm[J]. Flight Dynamics, 2024, 42 (2): 29- 35.
6	刘玉杰, 崔凯凯, 韩维, 等. 基于IPSO的舰载机出动离场规划研究[J]. 系统工程与电子技术, 2024, 46 (4): 1337- 1345. doi: 10.12305/j.issn.1001-506X.2024.04.22
	LIU Y J , CUI K K , HAN W , et al. Research on departure planning of carrier aircraft based on IPSO[J]. Systems Engineering and Electronics, 2024, 46 (4): 1337- 1345. doi: 10.12305/j.issn.1001-506X.2024.04.22
7	GUANGSHENG L I , CHOU W . Path planning for mobile robot using self-adaptive learning particle swarm optimization[J]. Science China (Information Sciences), 2018, 61 (5): 267- 284.
8	CAO Y , WEI W Y , BAI Y , et al. Multi-base multi-UAV cooperative reconnaissance path planning with genetic algorithm[J]. Cluster Computing, 2019, 22 (3): 5175- 5184.
9	LI D D , WANG L , CAI J C , et al. Research on path planning of mobile robot based on improved genetic algorithm[J]. International Journal of Modeling, Simulation, and Scientific Computing, 2023, 14 (6): 2341030. doi: 10.1142/S1793962323410301
10	文超, 董文瀚, 解武杰, 等. 基于CEA-GA的多无人机三维协同曲线航迹规划方法[J]. 北京航空航天大学学报, 2023, 49 (11): 3086- 3099.
	WEN C , DONG W H , XIE W J , et al. Multi-UAVs 3D cooperative curve path planning method based on CEA-GA[J]. Journal of Beijing University of Aeronautics and Astronautics, 2023, 49 (11): 3086- 3099.
11	SUN L. Path planning of mobile robot based on improved ant colony algorithm[C]//Proc. of the IEEE 11th Joint International Information Technology and Artificial Intelligence Conference, 2023: 985-989.
12	SHEN Z P , DING W N , LIU Y C , et al. Path planning optimization for unmanned sailboat in complex marine environment[J]. Ocean Engineering, 2023, 269, 113475. doi: 10.1016/j.oceaneng.2022.113475
13	MAVROVOUNIOTIS M , YANG S X . Ant algorithms with immigrants schemes for the dynamic vehicle routing problem[J]. Information Sciences, 2015, 294, 456- 477. doi: 10.1016/j.ins.2014.10.002
14	FARAHBAKHSH H , POURFAR I , ARA A L . A modified artificial bee colony algorithm using accept-reject method: theory and application in virtual power plant planning[J]. IETE Journal of Research, 2023, 69 (8): 5364- 5379. doi: 10.1080/03772063.2021.1973597
15	MIRJALILI S , GANDOMI A H , MIRJALILI S Z , et al. Salp swarm algorithm: a bio-inspired optimizer for engineering design problems[J]. Advances in Engineering Software, 2017, 114 (1): 163- 191.
16	宋超, 李波, 马云红, 等. 基于优化A*和MPC融合算法的三维无人机航迹规划[J]. 系统工程与电子技术, 2023, 45 (12): 3995- 4004. doi: 10.12305/j.issn.1001-506X.2023.12.30
	SONG C , LI B , MA Y H , et al. Trajectory planning based on optimized A* and MPC fusion algorithm[J]. Systems Engineering and Electronics, 2023, 45 (12): 3995- 4004. doi: 10.12305/j.issn.1001-506X.2023.12.30
17	潘登, 郑建华, 高东. 基于二维连通图的无人机快速三维路径规划[J]. 北京航空航天大学学报, 2023, 49 (12): 3419- 3431.
	PAN D , ZHENG J H , GAO D . Fast 3D path planning of UAV based on 2D connected graph[J]. Journal of Beijing University of Aeronautics and Astronautics, 2023, 49 (12): 3419- 3431.
18	LI S D , ZHOU H H , HU J , et al. A fast path planning approach for unmanned aerial vehicles[J]. Concurrency and Computation: Practice and Experience, 2015, 27 (13): 3446- 3460. doi: 10.1002/cpe.3291
19	YU F J , SHANG H Q , ZHU Q L , et al. An efficient RRT-based motion planning algorithm for autonomous underwater vehicles under cylindrical sampling constraints[J]. Autonomous Robots, 2023, 47 (3): 281- 297. doi: 10.1007/s10514-023-10083-y
20	CHAO N , LIU Y K , XIA H , et al. DL-RRT* algorithm for least dose path re-planning in dynamic radioactive environments[J]. Nuclear Engineering and Technology, 2018, 51 (3): 825- 836.
21	ELBANHAWI M , SIMIC M . Sampling-based robot motion planning: a review[J]. IEEE Access, 2014, 2 (1): 56- 77.
22	KARAMAN S , FRAZZOLI E . Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30 (7): 846- 894. doi: 10.1177/0278364911406761
23	LEE D, SHIM D H. Path planner based on bidirectional spline-RRT* for fixed-wing UAVs[C]//Proc. of the International Conference on Unmanned Aircraft Systems, 2016: 77-86.
24	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]//Proc. of the International Conference on Intelligent Robots and Systems, 2014: 2997-3004.
25	QURESHI A H , AYAZ Y . Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments[J]. Robotics & Autonomous Systems, 2015, 68, 1- 11.
26	ADIYATOV O, VAROL H A. Rapidly-exploring random tree based memory efficient motion planning[C]//Proc. of the Mechatronics and Automation, 2013: 354-359.
27	KAWABE T, NISHI T. A flexible collision-free trajectory planning for multiple robot arms by combining Q-learning and RRT*[C]//Proc. of the IEEE 18th International Conference on Automation Science and Engineering, 2022: 2363-2368.
28	LIU H S, GU Y Q, LI X J, et al. Deep reinforcement learning integrated RRT algorithm for path planning[C]//Proc. of the WRC Symposium on Advanced Robotics and Automation, 2023: 239-244.
29	MAMMARELLA M , CAPELLO E , DABBENE F , et al. Sample-based SMPC for tracking control of fixed-wing UAV[J]. IEEE Control Systems Letters, 2018, 2 (4): 611- 616. doi: 10.1109/LCSYS.2018.2845546
30	SANTOS M A , FERRAMOSCA A , RAFFO G V . Tube-based MPC with nonlinear control for load transportation using a UAV[J]. IFAC PapersOnLine, 2018, 51 (25): 459- 465. doi: 10.1016/j.ifacol.2018.11.180
31	王晓海, 孟秀云, 李传旭. 基于MPC的无人机航迹跟踪控制器设计[J]. 系统工程与电子技术, 2021, 43 (1): 191- 198. doi: 10.3969/j.issn.1001-506X.2021.01.23
	WANG X H , MENG X Y , LI C X . Design of trajectory tracking controller for UAV based on MPC[J]. Systems Engineering and Electronics, 2021, 43 (1): 191- 198. doi: 10.3969/j.issn.1001-506X.2021.01.23

无人机约束	数值
最大俯冲角/(°)	10
最大转弯角/(°)	30
最大爬升角/(°)	10
飞行高度约束/km	0.05
最小航迹段约束/km	6

算法	平均航迹代价	平均树节点个数	平均运行时间/s
RRT*	162.52	978.4	6.17
W-RRT*	151.94	486.8	1.06

算法	初始航迹代价	优化后航迹代价均值	改善初始航迹成功率/%
RRT*	151.51	151.38	51.23
Informed RRT*	151.51	150.17	65.78
C-RRT*	151.51	142.73	100.00

[1]	Zichun XIONG, Yongshan LIU. Flight vehicle midcourse trajectory fast planning for low-speed target [J]. Systems Engineering and Electronics, 2024, 46(7): 2424-2436.
[2]	Jiawei SUN, Minghui YU, Dapeng YANG, Haoquan TANG, Dapeng BIAN. Path planning of carrier aircraft traction system based on CL-RRT and MPC [J]. Systems Engineering and Electronics, 2024, 46(5): 1745-1755.
[3]	Yujie LIU, Yue LI, Wei HAN, Kaikai CUI. Trajectory planning for penetration of multi-aircraft for mation based on improved convex optimization algorithm [J]. Systems Engineering and Electronics, 2023, 45(9): 2819-2830.
[4]	Zhengda CUI, Mingying WEI, Yunqian LI. Cooperative trajectory planning method in later part of midcourse based on velocity estimation [J]. Systems Engineering and Electronics, 2023, 45(9): 2912-2921.
[5]	Shenming QUAN, Songyan WANG, Tao CHAO, Ming YANG. Reentry guidance method based on improved artificial potential field method [J]. Systems Engineering and Electronics, 2023, 45(7): 2158-2169.
[6]	Xiaocao YANG, Yanli DU, Yunong BU, Yanbin LIU, Cheng GAO. Online three-dimensional RRT^* cooperative route planning based on hierarchical decomposition [J]. Systems Engineering and Electronics, 2023, 45(5): 1409-1419.
[7]	Qinglu WANG, Fengguo WU, Chengchen ZHENG, Hui LI. UAV path planning based on optimized artificial potential field method [J]. Systems Engineering and Electronics, 2023, 45(5): 1461-1468.
[8]	Chao SONG, Bo LI, Yunhong MA, Jingyi HUANG. 3D UAV trajectory planning based on optimized A* and MPC fusion algorithm [J]. Systems Engineering and Electronics, 2023, 45(12): 3995-4004.
[9]	Xiaowei FU, Jing PAN. Distributed formation control of UAV swarm with dynamic obstacle avoidance [J]. Systems Engineering and Electronics, 2022, 44(2): 529-537.
[10]	Hanyang WANG, Liang CHEN, Hai XU, Jingbo BAI. UAV online trajectory planning based on MOEA/D-ARMS [J]. Systems Engineering and Electronics, 2022, 44(11): 3505-3514.
[11]	Yao HAN, Shaohua LI. UAV path planning based on improved artificial potential field [J]. Systems Engineering and Electronics, 2021, 43(11): 3305-3311.
[12]	Xiaohai WANG, Xiuyun MENG, Chuanxu LI. Design of trajectory tracking controller for UAV based on MPC [J]. Systems Engineering and Electronics, 2021, 43(1): 191-198.
[13]	Honghai ZHANG, Xiaopeng QIAN, Xinwei WU, Hao LIU, Yu TIAN, Lichao WANG. Cooperative trajectory planning for UAV formation based onpath-speed decoupling [J]. Systems Engineering and Electronics, 2020, 42(9): 1976-1987.
[14]	Daidai CHEN, Wanyou LI. Local path planning algorithm for USV with towed cable [J]. Systems Engineering and Electronics, 2020, 42(9): 1988-1994.
[15]	Fei WANG, Guangya SI, Zongping HE, Qiang WANG. Theory and calculation method of confrontational potential energy [J]. Systems Engineering and Electronics, 2020, 42(12): 2771-2778.

UAV online trajectory planning based on improved RRT* algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 22

References 31

Related Articles 15

Recommended Articles

Metrics

Comments