基于改进狼群算法的无人机协同任务规划

doi:10.19678/j.issn.1000-3428.0067993

摘要/Abstract

摘要：

多无人机在现代化作战中的运用日渐增多, 无人机任务规划在无人机智能作战中至关重要。针对子系统能力约束下的无人机任务分配问题, 提出一种Levy Flight(LF)优化下基于拍卖机制的混沌反向学习狼群优化算法CRL-AMIWPA。首先, 定义无人机能力矩阵和任务场景, 对无人机异构性、任务执行能力、执行任务能力最低需求建立同一矩阵描述, 根据距离油耗和最迟任务完成时间的加权和建立目标函数, 建立子系统约束下的任务分配模型; 然后, 设计狼群个体编码, 每个编码方案包含一种任务分配策略, 针对未达到任务需求最低能力的解, 采用基于合同网的拍卖策略予以修正。另外, 在狼群初始化阶段, 采用Tent混沌算子和反向学习策略, 将狼群个体均匀地分布在解空间中, 以提高初始种群的多样性, 最后, 利用LF策略优化寻优过程, 提高跳出局部最优解的能力。仿真实验结果表明, 所提算法能有效解决在子系统约束场景下无人机任务分配问题, 相比其他群智能算法和狼群算法, 具有更优的寻优性和收敛速度。

关键词: 狼群算法, 任务分配, 混沌优化, 变步长优化, 群智能算法

Abstract:

The use of multiple Unmanned Aerial Vehicles (UAV) in modern warfare is increasing, making UAV mission planning crucial for intelligent UAV operations. In response to the UAV task allocation problem under subsystem capability constraints, this study proposes a chaos reverse learning wolf pack optimization algorithm, CRL-AMIWPA, based on Levy Flight(LF) optimization and auction mechanism. First, the UAV capability matrix and task scenario are defined. The heterogeneity of the UAVs, task execution capability, and minimum task execution requirements are described in the same matrix. The objective function is established by considering the weighted sum of distance fuel consumption and latest task completion time, and the task allocation model is established under subsystem constraints. Subsequently, the individual coding of the wolf pack is designed, whereby each coding scheme represents a task allocation strategy. A corrective auction strategy based on contract network is used for solutions that fail to satisfy the minimum task capability requirements. In addition, during the initialization stage of the wolf pack, the Tent chaos operator and reverse learning strategy are applied to distribute the wolf pack individuals evenly in the solution space and improve the diversity of the initial population. Finally, LF strategy is used to optimize the search process, thereby enhancing the ability to escape local optima. Simulation results demonstrate that the proposed algorithm effectively solves the UAV task allocation problem under subsystem-constraint scenarios and exhibits better optimization performance and convergence speed than other swarm intelligence and Wolf Pack Algorithms(WPA).

Key words: Wolf Pack Algorithm(WPA), task allocation, chaotic optimization, variable step size optimization, swarm intelligence algorithm

彭泫滈, 张娟, 李辉, 胡术. 基于改进狼群算法的无人机协同任务规划[J]. 计算机工程, 2024, 50(10): 69-79.

PENG Xuanhao, ZHANG Juan, LI Hui, HU Shu. Cooperative Mission Planning for UAV Based on Improved Wolf Pack Algorithm[J]. Computer Engineering, 2024, 50(10): 69-79.

https://www.ecice06.com/CN/Y2024/V50/I10/69

图/表 22

图1 狼群捕猎过程

Fig.1 The hunting process of wolf pack

图2 任务分配序列

Fig.2 Task assignment sequence

图3 游走行为位置更新

Fig.3 Position update of wandering behavior

图4 召唤行为位置更新

Fig.4 Position update of the calling behavior

图5 围攻阶段的位置更新

Fig.5 Position update of the siege phase

图6 反向学习个体的编码变化

Fig.6 Coding changes of reverse learning individual

图7 算例1中初始个体混沌分布

Fig.7 Chaos distribution of initial individual under example 1

图8 算例1中LF变步长分布

Fig.8 Distribution of LF variable step size under example 1

图9 算例1中无人机任务分配路线图

Fig.9 Task allocation roadmap of UAV under example 1

图10 算例2中初始个体分布

Fig.10 The distribution of initial individuals under example 2

图11 算例2中LF变步长分布

Fig.11 LF variable step size distribution under example 2

图12 算例2中无人机任务分配路线图

Fig.12 Task allocation roadmap for UAV under example 2

图13 算例2下的算法分离显著性测试

Fig.13 Separation significance test of algorithm under example 2

图14 不同算法的目标函数值对比

Fig.14 Comparison of objective function values for different algorithms

参考文献 25

1	韩冰, 张秋菊, 徐世录. 无人战斗机的现状与发展趋势. 飞航导弹, 2005, (10): 45-49, 64.
	HAN B, ZHANG Q J, XU S L. Present situation and development trend of unmanned combat aircraft. Aerodynamic Missile Journal, 2005, (10): 45-49, 64.
2	岳源, 屈高敏. 分布式多无人机协同侦察目标分配研究. 兵器装备工程学报, 2018, 39 (3): 57-61, 82.
	YUE Y, QU G M. Research on distributed multi UAV cooperative reconnaissance task allocation. Journal of Ordnance Equipment Engineering, 2018, 39 (3): 57-61, 82.
3	杨晨, 张少卿, 孟光磊. 多无人机协同任务规划研究. 指挥与控制学报, 2018, 4 (3): 234- 248. doi: 10.3969/j.issn.2096-0204.2018.03.0234
	YANG C, ZHANG S Q, MENG G L. Multi-UAV cooperative mission planning. Journal of Command and Control, 2018, 4 (3): 234- 248. doi: 10.3969/j.issn.2096-0204.2018.03.0234
4	胡中华, 赵敏. 无人机研究现状及发展趋势. 航空科学技术, 2009, 20 (4): 3-5, 8.
	HU Z H, ZHAO M. Research status and development trend of UAV. Aeronautical Science & Technology, 2009, 20 (4): 3-5, 8.
5	ZOU D X, LIU H K, GAO L Q, et al. An improved differential evolution algorithm for the task assignment problem. Engineering Applications of Artificial Intelligence, 2011, 24 (4): 616- 624. doi: 10.1016/j.engappai.2010.12.002
6	马云红, 井哲, 周德云. 一种任务分配问题的快速剪枝优化算法[J]. 西北工业大学学报, 2013, 31(1): 40-43.
	MA Y H, JING Z, ZHOU D Y. A faster pruning optimization algorithm for task assignment[J]. Journal of Northwestern Polytechnical University, 2013, 31(1): 40-43. (in Chinese)
7	SCHUMACHER C, CHANDLER P, PACHTER M, et al. UAV task assignment with timing constraints via mixed-integer linear programming[C]∥Proceedings of the 3rd "Unmanned Unlimited" Technical Conference, Workshop and Exhibit. [S. l. ]: AAAI Press, 2004: 6410.
8	刘少睿, 田威, 沈建新, 等. 多机器人协同制造系统时序约束任务调度优化方法. 计算机集成制造系统, 2022, 28 (12): 3897- 3909.
	LIU S R, TIAN W, SHEN J X, et al. Schedule optimization of temporal and ordering constrained tasks in multi-robot cooperative machining system. Computer Integrated Manufacturing Systems, 2022, 28 (12): 3897- 3909.
9	王然然, 魏文领, 杨铭超, 等. 考虑协同航路规划的多无人机任务分配. 航空学报, 2020, 41 (S2): 24- 35.
	WANG R R, WEI W L, YANG M C, et al. Task allocation of multiple UAVs considering cooperative route planning. ACTA Aeronauticaet Astronautica Sinica, 2020, 41 (S2): 24- 35.
10	潘登, 高东, 郑建华. 均衡聚类市场拍卖机制的异构无人机集群任务规划方法. 国防科技大学学报, 2022, 44 (6): 151- 162.
	PAN D, GAO D, ZHENG J H. Task planning of heterogeneous UAV swarm based on balanced clustering market auction mechanism. Journal of National University of Defense Technology, 2022, 44 (6): 151- 162.
11	谭威, 胡永江, 李文广, 等. 多无人机协同任务规划研究综述. 微型电脑应用, 2021, 37 (9): 189- 192.
	TAN W, HU Y J, LI W G, et al. A survey of multi-UAV cooperative mission planning. Microcomputer Applications, 2021, 37 (9): 189- 192.
12	WU X L, YIN Y N, XU L, et al. Multi-UAV task allocation based on improved genetic algorithm. IEEE Access, 2021, 9, 100369- 100379.
13	张祥银, 夏爽, 张天. 基于自适应遗传学习粒子群算法的多无人机协同任务分配. 控制与决策, 2023, 38 (11): 3103- 3111.
	ZHANG X Y, XIA S, ZHANG T. Adaptive genetic learning particle swarm optimization based on collaborative task allocation for multi-UAVs. Control and Decision, 2023, 38 (11): 3103- 3111.
14	苏菲, 陈岩, 沈林成. 基于蚁群算法的无人机协同多任务分配. 航空学报, 2008, (S1): 184- 191.
	SU F, CHEN Y, SHEN L C. UAV cooperative multi-task assignment based on colony algorithm. Acta Aeronautica Et Astronautica Sinica, 2008, (S1): 184- 191.
15	SUJIT P, GEORGE J, BEARD R. Multiple UAV task allocation using particle swarm optimization[C]∥Proceedings of the AAAI Guidance, Navigation and Control Conference and Exhibit. [S. l. ]: AAAI Press, 2008: 6837.
16	BELLO-ORGAZ G, RAMIREZ-ATENCIA C, FRADERA-GIL J, et al. GAMPP: genetic algorithm for UAV mission planning problems[C]∥Proceedings of Conference on Intelligent Distributed Computing IX. Berlin, Germany: Springer, 2016: 167-176.
17	WU H S, ZHANG F M. Wolf pack algorithm for unconstrained global optimization. Mathematical Problems in Engineering, 2014, 2014 (1): 465082.
18	张鸿运, 王磊, 张旭, 等. 考虑子系统执行能力的多无人机协同任务规划. 系统工程与电子技术, 2023, 45 (1): 127- 138.
	ZHANG H Y, WANG L, ZHANG X, et al. Multi-UAV cooperative mission planning considering subsystem execution capability. Systems Engineering and Electronics, 2023, 45 (1): 127- 138.
19	周同乐, 陈谋, 韩增亮, 等. 基于改进狼群算法的多无人机协同多目标分配. 导航定位与授时, 2022, 9 (5): 46- 55.
	ZHOU T L, CHEN M, HAN Z L, et al. Multi-UAV cooperative multiple targets assignment based on improved wolf pack algorithm. Navigation Positioning and Timing, 2022, 9 (5): 46- 55.
20	CHEN X, CHENG F, LIU C, et al. An improved wolf pack algorithm for optimization problems: design and evaluation. PLOS ONE, 2021, 16 (8): e0254239.
21	单梁, 强浩, 李军, 等. 基于Tent映射的混沌优化算法. 控制与决策, 2005, 20 (2): 179- 182.
	SHAN L, QIANG H, LI J, et al. Chaotic optimization algorithm based on Tent map. Control and Decision, 2005, 20 (2): 179- 182.
22	张浩, 张铁男, 沈继红, 等. Tent混沌粒子群算法及其在结构优化决策中的应用. 控制与决策, 2008, 23 (8): 857- 862.
	ZHANG H, ZHANG T N, SHEN J H, et al. Research on decision-makings of structure optimization based on improved Tent PSO. Control and Decision, 2008, 23 (8): 857- 862.
23	TIZHOOSH H R. Opposition-based learning: a new scheme for machine intelligence[C]∥Proceedings of the International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC'06). Washington D. C., USA: IEEE Press, 2005: 695-701.
24	EDWARDS A M, PHILLIPS R A, WATKINS N W, et al. Revisiting Levy flight search patterns of wandering albatrosses, bumblebees and deer. Nature, 2007, 449, 1044- 1048.
25	MANTEGNA R N. Fast, accurate algorithm for numerical simulation of Lévy stable stochastic processes. Veterinary Sciences, 1994, 49 (5): 4677- 4683.

[1]	杨佳珠, 余芳, 杨勇生. 考虑能耗的海铁联运集装箱码头多设备协同调度[J]. 计算机工程, 2024, 50(10): 393-404.
[2]	王辉, 张玉豪, 申自浩, 刘沛骞, 蔡尚卿, 刘琨. 边云协同群智感知中隐私增强多任务分配机制[J]. 计算机工程, 2023, 49(4): 52-60.
[3]	杨桂松, 吴笑天, 高丽, 何杏宇. 面向单任务质量保障的移动群智感知任务分配[J]. 计算机工程, 2022, 48(9): 45-54.
[4]	彭虎, 李源汉, 邓长寿, 吴志健. 多策略调和的布谷鸟搜索算法[J]. 计算机工程, 2022, 48(8): 85-97.
[5]	邢虎, 陈荣, 唐文君. 基于预测算法的在线空间众包任务分配策略[J]. 计算机工程, 2020, 46(9): 27-34,43.
[6]	尚蕾, 刘茜萍. 基于任务分配和数据集副本的科学工作流数据布局[J]. 计算机工程, 2020, 46(5): 122-130,138.
[7]	王毅然, 经小川, 贾福凯, 孙宇健, 佟轶. 基于多智能体协同强化学习的多目标追踪方法[J]. 计算机工程, 2020, 46(11): 90-96.
[8]	张兴盛,余敦辉,聂茜婵,袁旭. 基于预测分析的时空众包在线任务分配[J]. 计算机工程, 2019, 45(6): 67-74.
[9]	胡章芳,孙林,张毅,鲍合章. 一种基于改进QPSO的机器人路径规划算法[J]. 计算机工程, 2019, 45(4): 281-287.
[10]	陈超,宣士斌,雷红轩. 基于狼群算法与二维最大熵的图像分割[J]. 计算机工程, 2018, 44(1): 233-237.
[11]	肖晶,刘伟,唐伦. 基于任务分配模型的车载自组织网络路由算法[J]. 计算机工程, 2017, 43(2): 6-15.
[12]	孙闽红,邵章义,秦源,闫云珍. 基于差分进化狼群算法的GNSS欺骗干扰检测[J]. 计算机工程, 2016, 42(9): 89-93.
[13]	贺毅辉,潘明聪,徐伟,彭辉. 基于概率推理的不确定性任务分配评价方法[J]. 计算机工程, 2015, 41(2): 31-35.
[14]	盛冲冲,胡新明,李佳佳,吴百锋. 面向节点异构GPU 集群的编程框架[J]. 计算机工程, 2015, 41(2): 292-297.
[15]	杨先凤,李映洁,赖俊良,彭博. 基于GPU并行粒子群优化的超声弹性实时成像算法[J]. 计算机工程, 2015, 41(12): 220-225,230.

选择文件类型/文献管理软件名称

选择包含的内容