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

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

摘要/Abstract

摘要：

针对快速扩展随机树(rapidly-exploring random tree, RRT)*算法应用于无人机(unmanned aerial vehicle, UAV)航迹规划时采样效率低、收敛速度慢、航迹代价大的问题, 采用势场法引导树扩展加快算法收敛速度。采用优化算法重选父节点及重新布线，生成比RRT*算法代价更小的初始航迹。基于初始航迹构建启发式采样区域，以更有效地优化初始航迹, 给出一种改进RRT*算法; 基于模型预测控制, 设计航迹规划策略, UAV在飞行中能良好地应对环境中的动态威胁。数学仿真实验结果表明, 改进算法能快速地生成代价更小的初始航迹, 并在后续航迹优化的过程中更有效地减少航迹代价, 可被应用于无人机在线规划任务。

关键词: 航迹规划, RRT*算法, 模型预测控制, 势场法

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

中图分类号:

V249

张海阔, 孟秀云. 基于改进RRT*算法的无人机在线航迹规划[J]. 系统工程与电子技术, 2024, 46(12): 4157-4164.

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

图/表 22

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

表1

表2

图12

图13

图14

表3

图15

图16

图17

图18

图19

参考文献 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]	熊子淳, 刘永善. 针对低速目标的飞行器中段航迹快速规划[J]. 系统工程与电子技术, 2024, 46(7): 2424-2436.
[2]	陶灿灿, 周锐. 面向空地中继网络优化的无人机运动控制方法[J]. 系统工程与电子技术, 2024, 46(5): 1712-1723.
[3]	杨登峰, 闫晓东. 基于视线协同和DMPC的载机-防御弹群协同主动防御制导策略[J]. 系统工程与电子技术, 2024, 46(5): 1724-1733.
[4]	孙家玮, 余明晖, 杨大鹏, 汤皓泉, 卞大鹏. 基于CL-RRT与MPC的舰载机牵引系统路径规划[J]. 系统工程与电子技术, 2024, 46(5): 1745-1755.
[5]	余婧, 吴晓军, 蒋安林, 雍恩米. 基于多精度规划窗口的无人机航迹规划方法研究[J]. 系统工程与电子技术, 2024, 46(5): 1767-1776.
[6]	卜瑞宇, 王彪, 李宏成, 唐超颖, 朱日楠. 地形跟随中航迹跟踪模型预测控制方案设计[J]. 系统工程与电子技术, 2024, 46(4): 1383-1392.
[7]	郝文康, 陈琪锋. 无人机编队模糊约束分布式模型预测节能控制[J]. 系统工程与电子技术, 2024, 46(3): 1021-1030.
[8]	胡树欣, 张安, 孙嫚憶, 李铭浩. 基于一致性理论和S-MPC的四旋翼编队协同避障[J]. 系统工程与电子技术, 2024, 46(2): 658-667.
[9]	刘玉杰, 李樾, 韩维, 崔凯凯. 基于改进凸优化算法的多机编队突防航迹规划[J]. 系统工程与电子技术, 2023, 45(9): 2819-2830.
[10]	张宏, 吴云华, 钟胜钧, 郭海波. 基于反步法的空间目标复合指向控制方法研究[J]. 系统工程与电子技术, 2023, 45(9): 2884-2893.
[11]	徐文丰, 李颖晖, 裴彬彬, 禹志龙. 基于多模型MPC的变体飞机协调优化控制[J]. 系统工程与电子技术, 2023, 45(9): 2902-2911.
[12]	陈子豪, 李娟, 刘畅, 李杰, 刘笑宇. 时间约束下对地面目标协同攻击任务规划方法[J]. 系统工程与电子技术, 2023, 45(8): 2353-2360.
[13]	权申明, 王松艳, 晁涛, 杨明. 基于改进人工势场法的再入制导方法[J]. 系统工程与电子技术, 2023, 45(7): 2158-2169.
[14]	吴立尧, 苏析超, 王垒, 潘子双. 有人/无人机编队队形集结控制研究[J]. 系统工程与电子技术, 2023, 45(7): 2192-2202.
[15]	王庆禄, 吴冯国, 郑成辰, 李辉. 基于优化人工势场法的无人机航迹规划[J]. 系统工程与电子技术, 2023, 45(5): 1461-1468.