Please wait a minute...
浙江大学学报(工学版)  2024, Vol. 58 Issue (8): 1748-1756    DOI: 10.3785/j.issn.1008-973X.2024.08.021
计算机技术、控制工程     
战场环境下遗传黏菌算法的多机协同任务分配
薛雅丽1(),李寒雁1,欧阳权1,*(),崔闪2,洪君2
1. 南京航空航天大学 自动化学院,江苏 南京 211106
2. 上海机电工程研究所,上海 201109
Multi-UAVs collaborative task allocation based on genetic slime mould algorithm in battlefield environment
Yali XUE1(),Hanyan LI1,Quan OUYANG1,*(),Shan CUI2,Jun HONG2
1. School of Automation, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
2. Shanghai Electro-Mechanical Engineering Institute, Shanghai 201109, China
 全文: PDF(2660 KB)   HTML
摘要:

针对已知战场环境下的多无人机协同任务分配问题, 提出基于融合遗传黏菌算法的任务分配方法. 综合单机约束、机群总体收益和损耗以及任务需求等条件, 构建多机协同任务分配目标函数. 针对遗传算法易陷入局部最优、黏菌算法收敛慢的问题, 改进遗传迭代和黏菌探索行为. 将离散黏菌算法引入遗传算法,增强融合算法的搜索能力. 在种群迭代中加入干扰操作, 提高求解精度. 在已知环境下进行分配试验和路径演示,并与其他算法进行对比. 结果表明, 利用所提出的融合算法,能够获得目标函数值更高的任务分配方案.

关键词: 多机协同任务分配遗传算法黏菌算法局部收敛    
Abstract:

A task allocation method based on the fusion genetic slime mould algorithm (FGSMA) was proposed aiming at the problem of collaborative multi-drone task allocation in a known battlefield environment. The objective function for multi-drone collaborative task allocation was constructed by considering the constraints of individual drones, the overall benefit and loss of the drone group, as well as the task requirements. The genetic iteration and slime mould exploration behaviors were improved in order to address the issues of genetic algorithms’ tendency to fall into local optima and the slow convergence of slime mould algorithms. The discrete slime mould algorithm was introduced into the genetic algorithm to enhance the search capability of the fused algorithm. A disturbance operation was added to the population iteration in order to improve the solution accuracy. Allocation experiments and path demonstrations were conducted in a known environment, and comparisons with other algorithms were conducted. Results show that the proposed fusion algorithm can obtain a task allocation scheme with a higher objective function value.

Key words: multi-machine collaboration    task allocation    genetic algorithm    slime mould algorithm    local convergence
收稿日期: 2023-07-13 出版日期: 2024-07-23
CLC:  TP 273  
基金资助: 国家自然科学基金资助项目(62073164);航天集成基金资助项目(U22B6001);上海市航天科技创新基金资助项目(SAST2022-013).
通讯作者: 欧阳权     E-mail: xueyali@nuaa.edu.cn;ouyangquan@nuaa.edu.cn
作者简介: 薛雅丽(1974—),女,副教授,博士,从事多目标协同控制的研究. orcid.org/0000-0002-6514-369X. E-mail:xueyali@nuaa.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
薛雅丽
李寒雁
欧阳权
崔闪
洪君

引用本文:

薛雅丽,李寒雁,欧阳权,崔闪,洪君. 战场环境下遗传黏菌算法的多机协同任务分配[J]. 浙江大学学报(工学版), 2024, 58(8): 1748-1756.

Yali XUE,Hanyan LI,Quan OUYANG,Shan CUI,Jun HONG. Multi-UAVs collaborative task allocation based on genetic slime mould algorithm in battlefield environment. Journal of ZheJiang University (Engineering Science), 2024, 58(8): 1748-1756.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2024.08.021        https://www.zjujournals.com/eng/CN/Y2024/V58/I8/1748

图 1  无人机约束示意图
图 2  黏菌算法离散化的示意图
图 3  遗传算子编码的示意图
图 4  选择算子的示意图
图 5  FGSMA算法流程的示意图
算法试验次数旅行商数平均最短路径长度
GA10104.41
SMA10104.29
FGSMA10102.82
表 1  旅行商问题的测试
序号坐标/km速度/(m·s?1最大任务数航程/km
1(18, 38, 0.5)403300
2(12, 9, 0.6)403200
3(87, 10, 0.3)403300
4(52, 6, 1.1)403400
5(12, 51, 0.9)402400
6(41, 9, 1.3)403200
7(70, 9, 0.5)402200
8(40, 32, 1.3)403300
表 2  实验1的无人机参数
任务点坐标/km时间窗口/min任务点坐标/km时间窗口/min
1(90, 70, 0.5)[200, 400]9(64, 56, 0.1)[200, 400]
2(47, 94, 0.6)[100, 300]10(94, 29, 0.9)[250, 350]
3(23, 85, 0.9)[300, 400]11(71, 48, 0.7)[350, 450]
4(94, 90, 1.1)[200, 300]12(46, 67, 0.7)[200, 300]
5(20, 82, 0.7)[300, 400]13(95, 53, 0.5)[300, 600]
6(79, 63, 0.6)[300, 500]14(65, 27, 0.5)[200, 300]
7(88, 52, 0.7)[300, 600]15(46, 67, 0.7)[400, 500]
8(79, 63, 0.6)[150, 400]
表 3  实验1的任务目标参数
UAV任务地点
123456789101112131415
10.80.60.650.630.380.270.670.720.430.580.170.070.770.620.47
20.50.30.10.450.30.10.850.730.370.370.620.200.50.7
30.180.070.770.620.70.60.40.350.40.30.250.40.60.850.5
40.80.750.630.480.370.370.620.850.830.580.470.670.650.450.6
50.50.30.10.450.30.10.850.730.750.630.480.370.370.580.72
60.180.070.770.620.70.60.40.350.750.630.480.370.370.620.52
70.80.60.650.630.380.270.670.720.380.270.670.220.250.050.08
80.50.30.150.70.20.250.830.670.620.70.30.10.450.10.58
表 4  实验1中无人机执行任务的综合收益
任务编号任务序列总收益是否满足约束时间/s
12345678
1[1, 6, 15][9, 14][5][2, 3][10, 11][8][12, 7][4, 13]65.7968.05
2[1, 6, 15][9, 14][5][2, 3][10, 11][8][12, 7][4, 13]65.7969.94
3[1, 6, 15][9, 14][5][2, 3][10, 11][8][12, 7][4, 13]65.7967.94
表 5  实验1中的3次任务分配结果
图 6  实验1条件下任务分配结果对应的三维航迹图
图 7  实验2中的种群适应度(目标函数值)对比
图 8  实验3中的种群适应度(目标函数值)对比
图 9  某次求解过程中的种群适应度(目标函数值)变化曲线
1 ZHU X. Analysis of military application of UAV swarm technology [C]// 3rd International Conference on Unmanned Systems . Harbin: IEEE, 2020: 1200-1204.
2 GANCHIMEG B, GEETHA S, JEONGHWAN J Analysis of technological trends and technological portfolio of unmanned aerial vehicle[J]. Journal of Open Innovation: Technology, Market, and Complexity, 2020, 6 (3): 48
doi: 10.3390/joitmc6030048
3 ZHOU Y, RAO B, WANG W UAV swarm intelligence: recent advances and future trends[J]. IEEE Access, 2020, 8: 183856- 183878
doi: 10.1109/ACCESS.2020.3028865
4 TANG J, DUAN H, LAO S Swarm intelligence algorithms for multiple unmanned aerial vehicles collaboration: a comprehensive review[J]. Artificial Intelligence Review, 2023, 56 (5): 4295- 4327
doi: 10.1007/s10462-022-10281-7
5 齐小刚, 李博, 范英盛, 等 多约束下多无人机的任务规划研究综述[J]. 智能系统学报, 2020, 15 (2): 204- 217
QI Xiaogang, LI Bo, FAN Yingsheng, et al A survey of mission planning on UAVs systems based on multiple constraints[J]. CAAI Transactions on Intelligent Systems, 2020, 15 (2): 204- 217
6 KIM J, OH H, YU B, et al. [J]. International Journal of Aeronautical and Space Sciences , 2020, 22(2): 456-467.
7 LU Y, MA Y, WANG J, et al Task assignment of UAV swarm based on wolf pack algorithm[J]. Applied Sciences, 2020, 10 (23): 8335
doi: 10.3390/app10238335
8 POZNA C, PRECUP R E, HORVÁTH E, et al Hybrid particle filter–particle swarm optimization algorithm and application to fuzzy controlled servo systems[J]. IEEE Transactions on Fuzzy Systems, 2022, 30 (10): 4286- 4297
doi: 10.1109/TFUZZ.2022.3146986
9 HUO L, ZHU J, WU G, et al A novel simulated annealing based strategy for balanced UAV task assignment and path planning[J]. Sensors (Basel), 2020, 20 (17): 4769
doi: 10.3390/s20174769
10 DENG W, ZHANG X, ZHOU Y, et al An enhanced fast non-dominated solution sorting genetic algorithm for multi-objective problems[J]. Information Sciences, 2022, 585: 441- 453
doi: 10.1016/j.ins.2021.11.052
11 GONG X, RONG Z, WANG J, et al A hybrid algorithm based on state-adaptive slime mould model and fractional-order ant system for the travelling salesman problem[J]. Complex and Intelligent Systems, 2023, 9 (4): 3951- 3970
doi: 10.1007/s40747-022-00932-1
12 CHEN X, LIU Y, YIN L, et al Cooperative task assignment and track planning for multi-UAV attack mobile targets[J]. Journal of Intelligent and Robotic Systems, 2020, 100 (3): 1383- 1400
13 QIN B, ZHANG D, TANG S, et al Distributed grouping cooperative dynamic task assignment method of UAV swarm[J]. Applied Sciences, 2022, 12 (6): 2865
doi: 10.3390/app12062865
14 LUO R, ZHENG H, GUO J Solving the multi-functional heterogeneous UAV cooperative mission planning problem using multi-swarm fruit fly optimization algorithm[J]. Sensors, 2020, 20 (18): 5026
doi: 10.3390/s20185026
15 魏兆恬, 赵晓林, 李俊涛, 等 考虑时间窗约束的多无人机任务分配[J]. 电光与控制, 2022, 29 (8): 17- 22
WEI Zhaotian, ZHAO Xiaolin, LI Juntao, et al Multi-UAV task allocation under time window constraints[J]. Electronics Optics and Control, 2022, 29 (8): 17- 22
16 AN Y, CHEN X, GAO K, et al A hybrid multi-objective evolutionary algorithm for solving an adaptive flexible job-shop rescheduling problem with real-time order acceptance and condition-based preventive maintenance[J]. Expert Systems with Applications, 2023, 212: 118711
doi: 10.1016/j.eswa.2022.118711
17 JIANG S, ZOU J, YANG S, et al Evolutionary dynamic multi-objective optimisation: a survey[J]. ACM Computing Surveys, 2022, 55 (4): 1- 47
18 HU C, QU G, ZHANG Y Pigeon-inspired fuzzy multi-objective task allocation of unmanned aerial vehicles for multi-target tracking[J]. Applied Soft Computing, 2022, 126: 109310
doi: 10.1016/j.asoc.2022.109310
19 CHEN L, LIU W L, ZHONG J An efficient multi-objective ant colony optimization for task allocation of heterogeneous unmanned aerial vehicles[J]. Journal of Computational Science, 2022, 58: 101545
doi: 10.1016/j.jocs.2021.101545
20 PENG H, MEI C, ZHANG S, et al Multi-strategy dynamic multi-objective evolutionary algorithm with hybrid environmental change responses[J]. Swarm and Evolutionary Computation, 2023, 82: 101356
doi: 10.1016/j.swevo.2023.101356
21 ZAREB M, NOUIBAT W, BESTAOUI Y, et al Evolutionary autopilot design approach for UAV quadrotor by using GA[J]. Iranian Journal of Science and Technology, Transactions of Electrical Engineering, 2020, 44 (1): 347- 375
doi: 10.1007/s40998-019-00214-6
22 LI S, CHEN H, WANG M, et al Slime mould algorithm: a new method for stochastic optimization[J]. Future Generation Computer Systems, 2020, 111: 300- 323
doi: 10.1016/j.future.2020.03.055
23 陈杰, 薛雅丽, 叶金泽 基于改进狼群算法的多机协同目标分配研究[J]. 吉林大学学报: 信息科学版, 2022, 40 (1): 20- 29
CHEN Jie, XUE Yali, YE Jinze Research on multi-aircraft cooperative target assignment based on improved wolves algorithm[J]. Journal of Jilin University: Information Science Edition, 2022, 40 (1): 20- 29
[1] 赵杰,刘锋,夏灵,范一峰. 基于遗传算法-序列二次规划的磁共振被动匀场优化方法[J]. 浙江大学学报(工学版), 2024, 58(6): 1305-1314.
[2] 李立峰,侯坤,邹德强,彭浩,李凌霄. 中等跨径钢板组合梁截面布置优化[J]. 浙江大学学报(工学版), 2024, 58(3): 510-517.
[3] 刘鹏,路庆昌,秦汉,崔欣. 道路网络多阶段抗灾能力优化模型构建与应用[J]. 浙江大学学报(工学版), 2024, 58(1): 96-108.
[4] 李煌,葛红娟,马莹,王永帅. 基于超平面NSGA-II的双输入双降压逆变器系统参数优化设计[J]. 浙江大学学报(工学版), 2023, 57(3): 606-615.
[5] 许丽丽,詹燕,鲁建厦,郎一丁. 四向穿梭车仓储系统复合作业调度优化[J]. 浙江大学学报(工学版), 2023, 57(11): 2188-2199.
[6] 查浩,费少华,傅云,吕震,朱伟东. 基于EtherCAT总线的六维力传感器在线解耦技术[J]. 浙江大学学报(工学版), 2023, 57(10): 2042-2050.
[7] 李勇,柳富强,孙柏青,张秋豪,杨俊友. 日常养老情境的异构多机器人动态多任务分配[J]. 浙江大学学报(工学版), 2022, 56(9): 1806-1814.
[8] 刘雪娇,王慧敏,夏莹杰,赵思苇. 具有隐私保护的车联网空间众包任务分配方法[J]. 浙江大学学报(工学版), 2022, 56(7): 1267-1275.
[9] 赵永胜,李瑞祥,牛娜娜,赵志勇. 数字孪生驱动的机身形状控制方法[J]. 浙江大学学报(工学版), 2022, 56(7): 1457-1463.
[10] 孙宝凤,张新康,李根道,刘娇娇. 第II类机器人混流装配线的平衡与排序联合决策[J]. 浙江大学学报(工学版), 2022, 56(6): 1097-1106.
[11] 张昕莹,陈璐,杨雯惠. 考虑系统时变效应与预防性维护的平行机调度[J]. 浙江大学学报(工学版), 2022, 56(2): 408-418.
[12] 胡鸿昊,李秀娟,于俊锋,张清周,柳景青. 基于耦合模拟的污水管网入流入渗定量识别[J]. 浙江大学学报(工学版), 2022, 56(11): 2313-2320.
[13] 邹贻权,黄浩洲,夏绪勇,王鑫. 成本导向下基于遗传算法的曲面幕墙设计优化[J]. 浙江大学学报(工学版), 2022, 56(10): 2049-2056.
[14] 向胜涛,王达. 基于改进量子遗传算法的模型交互修正方法[J]. 浙江大学学报(工学版), 2022, 56(1): 100-110.
[15] 鞠飞,庄伟超,王良模,刘经兴,王群. 混合动力汽车经济型巡航的车速规划策略[J]. 浙江大学学报(工学版), 2021, 55(8): 1538-1547.