基于优化A*和MPC融合算法的三维无人机航迹规划

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

摘要/Abstract

摘要：

针对传统A*算法在二维无人机(unmanned aerial vehicle, UAV)航迹规划中存在的不足, 提出了一种优化A*算法与模型预测控制融合的三维UAV航迹规划方法。通过压缩搜索空间和平滑处理, 提出了一种基于三维空间的优化A*算法, 综合考虑全局规划与实时避障需求, 构建了优化A*算法与模型预测控制的融合算法。仿真验证表明, 融合算法能够实现三维复杂环境下UAV实时避障航迹规划, 搜索节点少, 路径长度短且更加平滑, 具有很好的环境适应性。

关键词: 无人机航迹规划, 优化A*算法, 模型预测控制, 三维空间模型

Abstract:

In view of the shortcomings of the traditional A* algorithm in 2D unmanned aerial vehicle (UAV) trajectory planning, a 3D UAV trajectory planning method that fuses the optimized A* algorithm with model predictive control is proposed. An optimized A* algorithm based on 3D space is proposed by compressing the search space and smoothing operation, and a fusion algorithm of optimised A* algorithm and model predictive control is constructed by considering the global planning and real-time obstacle avoidance requirements. Simulation verification shows that the proposed fusion algorithm can achieve real-time UAV obstacle avoidance trajectory planning in 3D complex environment, with fewer search nodes, shorter and smoother path lengths, and has good environmental adaptability.

Key words: unmanned aerial vehicle (UAV) trajectory planning, optimized A* algorithm, model predictive control, 3D spatial model

中图分类号:

V249.3

宋超, 李波, 马云红, 黄晶益. 基于优化A*和MPC融合算法的三维无人机航迹规划[J]. 系统工程与电子技术, 2023, 45(12): 3995-4004.

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.

图/表 19

图1

图2

图3

图4

图5

图6

图7

表1

图8

图9

图10

表2

表3

图11

表4

图12

图13

图14

图15

参考文献 34

1	SONG R, LONG T, WANG Z, et al. Multi-UAV cooperative target tracking method using sparse a search and standoff tracking algorithms[C]//Proc. of the IEEE CSAA Guidance, Navigation and Control Conference, 2018. DOI: 10.1109/GNCC42960.2018.9019171.
2	SONG Y J, XING X J, XI Q B, et al. Route planning method for UAV in unknown environment based on improved SAS algorithm[C]//Proc. of the Chinese Control and Decision Confe-rence, 2020: 3163-3168.
3	SHAO S K , SHI W L , ZHAO Y J , et al. A new method of solving UAV trajectory planning under obstacles and multi-constraint[J]. IEEE Access, 2021, 9, 161161- 161180. doi: 10.1109/ACCESS.2021.3132650
4	ZHANG C J, MENG X Y. Spare A* search approach for UAV route planning[C]//Proc. of the IEEE International Conference on Unmanned Systems, 2017: 413-417.
5	绳红强, 黄海英, 崔毅刚. 基于A*蚁群融合算法的避障路径规划研究[J]. 机电工程技术, 2022, 51 (7): 45- 49.
	SHENG H Q , HUANG H Y , CUI Y G . Research on obstacle avoidance path planning based on A* ant colony fusion algorithm[J]. Mechatronic Engineering Technology, 2022, 51 (7): 45- 49.
6	NIU Z J , JIA X H , YAO W . Communication free MPC based neighbors trajectory prediction for distributed multi-UAV motion planning[J]. IEEE Access, 2022, 10, 13481- 13489. doi: 10.1109/ACCESS.2022.3148145
7	CAO Y, LONG T, WANG Z, et al. Aircraft route planning for stealth penetration based on sparse A* search[C]//Proc. of the 29th Chinese Control and Decision Conference, 2017: 5380-5385.
8	薄宁, 李相民, 代进进, 等. 基于变步长稀疏A*搜索和MPC的多无人机层次化协同航迹规划[J]. 指挥控制与仿真, 2018, 40 (2): 65- 71.
	BO N , LI X M , DAI J J , et al. Hierarchical cooperative multi-UAV track planning based on variable-step sparse A* search and MPC[J]. Command, Control and Simulation, 2018, 40 (2): 65- 71.
9	张志文, 张鹏, 毛虎平, 等. 改进A*算法的机器人路径规划研究[J]. 电光与控制, 2021, 28 (4): 21- 25.
	ZHANG Z W , ZHANG P , MAO H P , et al. Research on improved A* algorithm for robot path planning[J]. Electronics Optics & Control, 2021, 28 (4): 21- 25.
10	WANG Z, LIU L, LONG T, et al. Enhanced sparse A* search for UAV path planning using dubins path estimation[C]//Proc. of the 33rd Chinese Control Conference, 2014: 738-742.
11	KIM D J , JEONG Y W , CHUNG C C . Lateral vehicle trajectory planning using a model predictive control scheme for an automated perpendicular parking system[J]. IEEE Trans.on Industrial Electronics, 2023, 70 (2): 1820- 1829. doi: 10.1109/TIE.2022.3163567
12	张阳伟, 乔越, 李成凤. 基于四叉树栅格环境的变步长双向A*算法[J]. 控制工程, 2021, 28 (10): 1960- 1966.
	ZHANG Y W , QIAO Y , LI C F . A variable-step bidirectional A* algorithm based on a quadtree raster environment[J]. Control Engineering of China, 2021, 28 (10): 1960- 1966.
13	张浩杰, 张玉东, 梁荣敏, 等. 改进A*算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45 (2): 513- 520.
	ZHANG H J , ZHANG Y D , LIANG R M , et al. Improved A* algorithm for optimal path planning method for robot energy consumption[J]. Systems Engineering and Electronics, 2023, 45 (2): 513- 520.
14	VEKSLER A , JOHANSEN T A , BORRELLI F , et al. Dynamic positioning with model predictive control[J]. IEEE Trans.on Control Systems Technology, 2016, 24 (4): 1340- 1353.
15	MAXIM A, CARUNTU C F, LAZAR C. Cruise and headway control for vehicle platooning using a distributed model predictive control algorithm[C]//Proc. of the 21st International Conference on System Theory, Control and Computing, 2017: 146-151.
16	MERABTI H, BOUCHACHI I, BELARBI K. Nonlinear model predictive control of quadcopter[C]//Proc. of the 16th International Conference on Sciences and Techniques of Automatic Control and Computer Engineering, 2015: 208-211.
17	李晓辉, 苗苗, 冉保健, 等. 基于改进A*算法的无人机避障路径规划[J]. 计算机系统应用, 2021, 30 (2): 255- 259.
	LI X H , MIAO M , RAN B J , et al. UAV obstacle avoidance path planning based on improved A* algorithm[J]. Computer System Applications, 2021, 30 (2): 255- 259.
18	CHOWDHURY M I, SCHWARTZ D G. The PRM-A path planning algorithm for UAVs: an application to navy mission planning[C]//Proc. of the Conference on Global Oceans, 2020. DOI: 10.1109/IEEECONF38699.2020.9388987.
19	LI X X, HU X G, WANG Z Q, et al. Path planning based on combination of improved A-STAR algorithm and DWA algorithm[C]//Proc. of the 2nd International Conference on Artificial Intelligence and Advanced Manufacture, 2020: 99-103.
20	WANG Y H, ZHANG W J, ZHOU T X. Path planning of surface unmanned craft based on variable step-length sparse A-star algorithm[C]//Proc. of the 33rd Chinese Control and Decision Conference, 2021: 1917-1920.
21	牛佳伟. 基于协同A*算法的多无人机航迹规划[J]. 舰船电子工程, 2021, 41 (9): 66- 68.
	NIU J W . Multi-UAV track planning based on cooperative A* algorithm[J]. Ship Electronic Engineering, 2021, 41 (9): 66- 68.
22	范铮铮, 王正平, 葛佳昊. 基于A*算法的多无人机实时打击航迹规划[J]. 战术导弹技术, 2021, (5): 94-101, 112.
	FAN Z Z , WANG Z P , GE J H . Real-time multi-UAV strike trajectory planning based on A* algorithm[J]. Tactical Missile Technology, 2021, (5): 94-101, 112.
23	HU C, ZHOU X L, DOU R, et al. Combined fast control of drifting state and trajectory tracking for autonomous vehicles based on MPC controller[C]//Proc. of the International Conference on Robotics and Automation, 2022: 1373-1379.
24	SHAO S K , HE C L , ZHAO Y J , et al. Efficient trajectory planning for UAVs using hierarchical optimization[J]. IEEE Access, 2021, 9, 60668- 60681.
25	TENGESDAL T , JOHANSEN T A , GRANDE T D , et al. Ship collision avoidance and anti grounding using parallelized cost evaluation in probabilistic scenario-based model predictive control[J]. IEEE Access, 2022, 10, 111650- 111664.
26	LEE C, KIM J. Nonlinear model predictive control of an auto-nomous underwater vehicle for terrain profile tracking[C]//Proc. of the 16th International Conference on Ubiquitous Robots, 2019: 771-774.
27	SAHU A, KANDATH H, KRISHNA K M. Model predictive control based algorithm for multi-target tracking using a swarm of fixed wing UAVs[C]//Proc. of the IEEE 17th International Conference on Automation Science and Engineering, 2021: 1255-1260.
28	ILLE M, NAMERIKAWA T. Collision avoidance between multi-UAV systems considering formation control using MPC[C]//Proc. of the IEEE International Conference on Advanced Intelligent Mechatronics, 2017: 651-656.
29	YUAN S T, ZHAO P C, ZHANG Q Y, et al. Research on model predictive control-based trajectory tracking for unmanned vehicles[C]//Proc. of the 4th International Conference on Control and Robotics Engineering, 2019: 79-86.
30	CAO G, LAI E M K, ALAM F. Gaussian process model predictive control of unmanned quadrotors[C]//Proc. of the 2nd International Conference on Control, Automation and Robotics, 2016: 200-206.
31	GUO J X, ZHENG Y K, QU D X, et al. An algorithm of foot end trajectory tracking control for quadruped robot based on model predictive control[C]//Proc. of the IEEE International Conference on Robotics and Biomimetics, 2019: 828-833.
32	刘玄冰, 周绍磊, 肖支才, 等. 无人机避障方法研究综述[J]. 兵器装备工程学报, 2022, 43 (5): 40- 47.
	LIU X B , ZHOU S L , XIAO Z C , et al. A review of research on obstacle avoidance methods for drones[J]. Journal of Ordnance Equipment Engineering, 2022, 43 (5): 40- 47.
33	WAN K F , LI B , GAO X G , et al. A learning-based flexible autonomous motion control method for UAV in dynamic unknown environments[J]. Journal of Systems Engineering and Electronics, 2021, 32 (6): 1490- 1508.
34	LI B , LIANG S Y , CHEN D Q , et al. A decision-making method for air combat maneuver based on hybrid deep learning network[J]. Chinese Journal of Electronics, 2022, 31 (1): 107- 115.

参数	数值
无人机起始位置/m	(0, 0, 0)
无人机速度/(m·s^-1)	25
目标位置/m	(380, 450, 415)
最大偏航角/(°)	45
最大俯仰角/(°)	45
最小转弯半径/m	10
权值因子a	0.85
权值因子b	0.15
状态量个数	3
控制量个数	2

类型	节点数量/个	规划时间/s	航程/m
传统A*算法	50	2.78	1 125
稀疏A*算法	39	2.45	1 105
优化A*算法	36	2.35	1 044

序号	位置坐标/m	半径/m
1	(210, 280, 175)	50

序号	位置坐标	半径
1	(240, 235, 160)	50

[1]	张宏, 吴云华, 钟胜钧, 郭海波. 基于反步法的空间目标复合指向控制方法研究[J]. 系统工程与电子技术, 2023, 45(9): 2884-2893.
[2]	徐文丰, 李颖晖, 裴彬彬, 禹志龙. 基于多模型MPC的变体飞机协调优化控制[J]. 系统工程与电子技术, 2023, 45(9): 2902-2911.
[3]	柳子然, 戴梓健, 岳程斐, 王培基, 曹喜滨. 基于高斯混合过程的空间机器人任务空间预测控制方法[J]. 系统工程与电子技术, 2023, 45(11): 3597-3605.
[4]	孙田野, 孙伟, 吴建军. 改进Quatre算法的无人机编队快速集结方法[J]. 系统工程与电子技术, 2022, 44(9): 2840-2848.
[5]	胥彪, 李翔, 李爽, 张金鹏. 基于非线性模型预测控制的火星大气进入智能制导方法[J]. 系统工程与电子技术, 2021, 43(7): 1943-1953.
[6]	来磊, 吴德伟, 邹鲲, 韩昆, 李海林. 基于多准则交互膜进化算法的UAV三维航迹规划[J]. 系统工程与电子技术, 2021, 43(1): 138-146.
[7]	王晓海, 孟秀云, 李传旭. 基于MPC的无人机航迹跟踪控制器设计[J]. 系统工程与电子技术, 2021, 43(1): 191-198.
[8]	杨宇, 吴达, 高峰, 邓建军. 适用于超低空拦截的复合制导律设计方法[J]. 系统工程与电子技术, 2021, 43(1): 208-215.
[9]	朱梦圆, 吕娜, 陈柯帆, 钟赟, 刘创, 高维廷. 航空集群协同搜索马尔可夫运动目标方法[J]. 系统工程与电子技术, 2019, 41(9): 2041-2047.
[10]	宋敏, 戴静, 孔韬. 基于NMPC的无人机自主防撞控制方法[J]. 系统工程与电子技术, 2019, 41(9): 2092-2099.
[11]	王超, 张胜修, 宋仔标, 杨建业, 吴晓露. 飞行器抗饱和鲁棒自适应非线性模型预测控制[J]. 系统工程与电子技术, 2018, 40(2): 393-400.
[12]	盖俊峰, 赵国荣, 宋超. 基于线性近似和神经网络逼近的模型预测控制[J]. 系统工程与电子技术, 2015, 37(2): 394-399.
[13]	唐贤伦，李洋，李鹏，张毅. 基于多Agent粒子群优化的多步SVR模型预测控制[J]. 系统工程与电子技术, 2014, 36(5): 958-964.
[14]	祁晓明, 魏瑞轩, 沈东, 茹常剑, 周欢. 基于运动目标预测的多无人机分布式协同搜索[J]. 系统工程与电子技术, 2014, 36(12): 2417-2425.
[15]	高晓光，李青原，邸若海. 基于DBN威胁评估的MPC无人机三维动态路径规划[J]. 系统工程与电子技术, 2014, 36(11): 2199-2205.