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

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

Abstract

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

CLC Number:

V249.3

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.

Figures/Tables 19

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Table 1

Fig.8

Fig.9

Fig.10

Table 2

Table 3

Fig.11

Table 4

Fig.12

Fig.13

Fig.14

Fig.15

References 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]	Hong ZHANG, Yunhua WU, Shengjun ZHONG, Haibo GUO. Space target compound pointing control method based on backstepping [J]. Systems Engineering and Electronics, 2023, 45(9): 2884-2893.
[2]	Wenfeng XU, Yinghui LI, Binbin PEI, Zhilong YU. Coordinated optimization control of morphing aircraft based on multi-model MPC [J]. Systems Engineering and Electronics, 2023, 45(9): 2902-2911.
[3]	Ziran LIU, Zijian DAI, Chengfei YUE, Peiji WANG, Xibin CAO. Gaussian-mixture-process-based task-space predictive control method for space robot [J]. Systems Engineering and Electronics, 2023, 45(11): 3597-3605.
[4]	Tianye SUN, Wei SUN, Jianjun WU. UAV formation rapid assembly method based on improved Quatre algorithm [J]. Systems Engineering and Electronics, 2022, 44(9): 2840-2848.
[5]	Biao XU, Xiang LI, Shuang LI, Jinpeng ZHANG. Intelligent guidance method based on nonlinear model predictive control for Mars atmospheric entry [J]. Systems Engineering and Electronics, 2021, 43(7): 1943-1953.
[6]	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.
[7]	ZHU Mengyuan, LYU Na, CHEN Kefan, ZHONG Yun, LIU Chuang, GAO Weiting. Collaborative aeronautic swarm search of Markov moving targets [J]. Systems Engineering and Electronics, 2019, 41(9): 2041-2047.
[8]	SONG Min, DAI Jing, KONG Tao. UAV autonomous collision avoidance control method based on NMPC [J]. Systems Engineering and Electronics, 2019, 41(9): 2092-2099.
[9]	WANG Chao, ZHANG Shengxiu, SONG Zibiao, YANG Jianye, WU Xiaolu. Aircraft anti-windup of robust adaptive nonlinear predictive control [J]. Systems Engineering and Electronics, 2018, 40(2): 393-400.
[10]	GAI Jun-feng, ZHAO Guo-rong, SONG Chao. Model predictive control based on linearization and neural network approach [J]. Systems Engineering and Electronics, 2015, 37(2): 394-399.
[11]	TANG Xian-lun，LI Yang，LI Peng，ZHANG Yi. Multi-step model predictive control based on SVR multi-Agent particle swarm optimization algorithm [J]. Systems Engineering and Electronics, 2014, 36(5): 958-964.
[12]	GAO Xiao-guang, LI Qing-yuan, DI Ruo-hai. MPC three dimensional dynamic path planning for UAV based on DBN threat assessment [J]. Systems Engineering and Electronics, 2014, 36(11): 2199-2205.
[13]	CHEN Jin-dong，PAN Feng. Online support vector machine and genetic algorithm based predictive control [J]. Journal of Systems Engineering and Electronics, 2013, 35(6): 1275-1280.
[14]	TANG Xiao-ming, DING Bao-cang. Model predictive control for networked control systems with arbitrary and bounded packet loss [J]. Journal of Systems Engineering and Electronics, 2011, 33(10): 2295-2300.
[15]	ZHU Zhi-bin, WANG Yan, CHEN Xing-lin. Research on numerical algorithms for nonlinear predictive control problems based on segmented state constraints [J]. Journal of Systems Engineering and Electronics, 2009, 31(6): 1436-1440.

3D UAV trajectory planning based on optimized A* and MPC fusion algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 19

References 34

Related Articles 15

Recommended Articles

Metrics

Comments