面向多无人机协同对地攻击的双层任务规划方法

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

摘要/Abstract

摘要：

无人机(unmanned aerial vehicles, UAVs)的任务规划包含任务分配、执行顺序确定以及航迹优化等。为了达到任务规划的全局最优，需要全盘梳理任务的各个方面，提出高效的优化策略。综合考虑任务规划过程中任务分配、执行顺序确定以及航迹优化等方面的需求和相互间影响，首先从优化框架出发, 设计了双层互耦的任务规划求解策略, 而后将任务规划模型分为上层任务分配和下层任务序列优化, 并对每一层的优化方法和优化步骤进行了详细设计。在任务分配问题中, 基于模拟退火算法, 提出了可跳出局部最优的模拟退火-撒点(simulated-annealing-shooting, SAS)算法, 并详细探讨了算法参数的设计原则。最后通过仿真分析, 验证了所提出的规划框架和SAS优化算法的有效性。

关键词: 无人机, 任务规划, 模拟退火算法, 规划框架, 优化算法

Abstract:

The unmanned aerial vehicles (UAVs) mission planning consists of task allocation, mission sequence assignment and trajectory planning. These optimization problems are interacted. To achieve the global optimal solution of the UAVs mission planning, these three optimization problems should be fully considered and organized. In this paper, considering the requirements and interactions among the three optimization problems, a double-level planning framework is firstly introduced, and then the whole mission planning problem is decomposed into two parts: the high level task allocation and the low level sequence optimization. The optimization models and methods for each level are subsequently developed and detailed. In the process of task allocation, a simulated-annealing-shooting (SAS) is proposed for overcoming the local-optimal-trap, and the configuration principle of the algorithm parameters are discussed. Finally, the simulation results demonstrate the effectiveness of the proposed planning framework and the SAS algorithm.

Key words: unmanned aerial vehicle (UAV), mission planning, simulated-annealing algorithm, planning framework, optimization algorithm

中图分类号:

TP391

余婧, 雍恩米, 陈汉洋, 郝东, 张显才. 面向多无人机协同对地攻击的双层任务规划方法[J]. 系统工程与电子技术, 2022, 44(9): 2849-2857.

Jing YU, Enmi YONG, Hanyang CHEN, Dong HAO, Xiancai ZHANG. Bi-level mission planning method for multi-cooperative UAV air-to-ground attack[J]. Systems Engineering and Electronics, 2022, 44(9): 2849-2857.

图/表 22

图1

图2

图3

图4

图5

图6

表1

表2

表3

表4

表5

图7

图8

图9

表6

表7

表8

表9

图10

图11

图12

图13

参考文献 19

1	沈林成, 陈璟, 王楠. 飞行器任务规划技术综述[J]. 航空学报, 2014, 35 (3): 539- 606.
	SHEN L C , CHEN J , WANG N . Overview of air vehicle mission planning techniques[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35 (3): 539- 606.
2	ALEMAYEHU T S , KIM J H . Efficient nearest neighbor heuristic TSP algorithms for blueucing data acquisition latency of UAV relay WSN[J]. Wireless Personal Communications, 2017, 95 (3): 3271- 3285. doi: 10.1007/s11277-017-3994-9
3	杜于飞, 覃太贵, 邓秀方, 等. 多无人机协同任务规划问题[J]. 数学的实践和认识, 2017, 47 (14): 52- 62.
	DU Y F , QIN T G , DENG X F , et al. Mission planning of multiple unmanned aerial vehicles[J]. Mathematics in Practice and Theory, 2017, 47 (14): 52- 62.
4	侯玉梅, 贾震环, 田歆, 等. 带软时间窗整车物流配送路径优化研究[J]. 系统工程学报, 2015, 30 (2): 240- 250.
	HOU Y M , JIA Z H , TIAN X , et al. Research on the optimization on the vehicle logistics distribution with soft time windows[J]. Journal of Systems Engineering, 2015, 30 (2): 240- 250.
5	ROURKE K P O , CARLTON W B , BAILEY T G , et al. Dynamic routing of unmanned aerial vehicles using reactive tabu search[J]. Military Operations Research, 2001, 6 (1): 5- 30. doi: 10.5711/morj.6.1.5
6	GUERRERO J A , BESTAOUI Y . UAV path planning for structure inspection in windy environments[J]. Journal of Intelligent and Robotic Systems, 2013, 69 (1/4): 297- 311.
7	SCHUMACHER C, CHANDLER P R, RASMUSSEN S R. Task allocation for wide area search munitions via network flow optimization[C]//Proc. of the AIAA Guidance, Navigation, and Control Conference, 2001: AIAA 2001-4147.
8	SCHUMACHER C, CHANDLER P R, RASMUSSEN S R. Task allocation for wide area search munitions via iterative network flow[C]//Proc. of the AIAA Guidance, Navigation, and Control Conference, 2002: AIAA 2002-4586.
9	梁国伟, 王社伟, 赵雪森. 多无人机协同任务分配方法[J]. 火力与指挥控制, 2014, 39 (11): 13- 17. doi: 10.3969/j.issn.1002-0640.2014.11.004
	LIANG G W , WANG S W , ZHAO X S . Method research on cooperative task allocation for multiple UCAVs[J]. Fire Control and Command Control, 2014, 39 (11): 13- 17. doi: 10.3969/j.issn.1002-0640.2014.11.004
10	李大东, 孙秀霞, 孙彪, 等. 基于混合整数线性规划的无人机任务规划[J]. 飞行力学, 2010, 28 (5): 88- 91.
	LI D D , SUN X X , SUN B , et al. Mission planning for UAVs based on MILP[J]. Flight Dynamics, 2010, 28 (5): 88- 91.
11	ALIGHANBARI M, HOW J P. Cooperative task assignment of unmanned aerial vehicles in adversarial environments[C]//Proc. of the American Control Conference, 2005: 4661-4666.
12	CORMEN T H , LEISERSON C E , RIVEST R L , et al. Introduction to algorithms[M]. Massachusetts: MIT Press, 2009.
13	CHOI H , KIM Y , KIM H J . Genetic algorithm based decentralized task assignment for multiple unmanned aerial vehicles in dynamic environments[J]. International Journal of Aeronautical and Space Sciences, 2011, 12 (12): 163- 174.
14	ROBERGE V , TARBOUCHI M , LABONTE G . Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J]. Trans.on Industrial Informatics, 2012, 9 (1): 132- 141.
15	马华伟, 朱益民, 胡笑旋. 基于粒子群算法的无人机舰机协同任务规划[J]. 系统工程与电子技术, 2016, 38 (7): 1583- 1588.
	MA H W , ZHU Y M , HU X X . Cooperative task planning for ship and UAVs based on particle swarm optimization algorithm[J]. Systems Engineering and Electronics, 2016, 38 (7): 1583- 1588.
16	杜继永, 张凤鸣, 杨骥, 等. 多UCAV协同任务分配模型及粒子群算法求解[J]. 控制与决策, 2012, 27 (11): 1752- 1755.
	DU J Y , ZHANG F M , YANG J , et al. Cooperative task assignment for multiple UCAV using particle swarm optimization[J]. Control and Decision, 2012, 27 (11): 1752- 1755.
17	王强, 丁全心, 张安, 等. 多机协同对地攻击目标分配算法[J]. 系统工程与电子技术, 2012, 34 (7): 1400- 1405. doi: 10.3969/j.issn.1001-506X.2012.07.18
	WANG Q , DING Q X , ZHANG A , et al. Target allocation algorithm for multi-coorperative air-to-ground attack[J]. Systems Engineering and Electronics, 2012, 34 (7): 1400- 1405. doi: 10.3969/j.issn.1001-506X.2012.07.18
18	GLOBUS A, CRAWFORD J, LOHN J, et al. A comparison of techniques for scheduling earth observing satellites[C]//Proc. of the National Conference on Artificial Intelligence and the 16th Conference on Innovative Applications on Artificial Intelligence, 2004: 836-843.
19	WU G H , WANG H L , PEDRYCZ W , et al. Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy[J]. Compu-ters and Industrial Engineering, 2017, 113, 576- 588. doi: 10.1016/j.cie.2017.09.050

UAV_i	tar₁	tar₂	tar₃	tar₄	tar₅	tar₆	tar₇	tar₈	tar₉	tar₁₀
UAV₁	0.864	0.811	0.846	0.945	0.805	0.762	0.768	0.829	0.777	0.767
UAV₂	0.789	0.888	0.831	0.938	0.982	0.790	0.751	0.755	0.823	0.735
UAV₃	0.923	0.934	0.834	0.893	0.963	0.841	0.768	0.971	0.878	0.789
UAV₄	0.757	0.724	0.792	0.814	0.865	0.769	0.831	0.994	0.779	0.796
UAV₅	0.906	0.979	0.853	0.943	0.887	0.953	0.793	0.832	0.881	0.827
UAV₆	0.755	0.933	0.853	0.860	0.876	0.758	0.977	0.733	0.913	0.852

UAV_i	tar₁	tar₂	tar₃	tar₄	tar₅	tar₆	tar₇	tar₈	tar₉	tar₁₀
UAV₁	0.732	0.725	0.755	0.865	0.821	0.825	0.801	0.773	0.873	0.713
UAV₂	0.989	0.820	0.779	0.743	0.723	0.715	0.970	0.821	0.718	0.751
UAV₃	0.701	0.778	0.744	0.956	0.772	0.971	0.811	0.729	0.770	0.895
UAV₄	0.932	0.940	0.741	0.887	0.737	0.983	0.733	0.740	0.806	0.920
UAV₅	0.945	0.829	0.961	0.805	0.755	0.847	0.934	0.983	0.946	0.894
UAV₆	0.961	0.973	0.874	0.854	0.772	0.847	0.817	0.987	0.705	0.835

参数	数值
起始温度	250
终止温度	10
降温系数	0.99
常温迭代次数	250
邻域搜索位置数目	1, 3, 5, 10
撒点算子规模	5, 10, 50, 100

运行	1	2	3	4	5	均值	方差
1	4.025 0	4.025 0	4.003 5	3.987 0	3.963 0	4.000 7	0.000 699
3	4.003 5	3.981 5	4.025 0	3.997 5	4.025 0	4.006 5	0.000 350
5	4.003 5	3.997 5	3.977 5	3.973 5	3.973 5	3.985 1	0.000 205
10	3.960 0	3.997 5	3.988 5	3.957 5	3.979 0	3.976 5	0.000 306

运行	1	2	3	4	5	均值	方差
5	3.940 0	3.952 0	3.948 0	3.956 0	3.959 5	3.951 1	0.000 057
10	3.973 5	3.961 5	3.968 5	3.988 5	3.987 0	3.975 8	0.000 137
50	4.003 5	3.981 5	4.025 0	3.997 5	4.025 0	4.006 5	0.000 350
100	3.979 0	3.997 5	4.003 5	4.025 0	4.025 0	4.006 0	0.000 382