改进自组织映射的多无人机协同任务分配方法

doi:10.11772/j.issn.1001-9081.2022040592

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (5): 1551-1556.DOI: 10.11772/j.issn.1001-9081.2022040592

所属专题：先进计算

改进自组织映射的多无人机协同任务分配方法

孙亚男, 吴杰宏(), 石峻岭, 高利军

沈阳航空航天大学计算机学院，沈阳 110136

收稿日期:2022-04-27 修回日期:2022-06-22 接受日期:2022-06-24 发布日期:2022-07-11 出版日期:2023-05-10
通讯作者: 吴杰宏
作者简介:孙亚男（1996—），女，辽宁朝阳人，硕士研究生，主要研究方向：无人机系统路径规划和任务分配
吴杰宏（1971—），女，黑龙江齐齐哈尔人，教授，博士，CCF高级会员，主要研究方向：无人机系统协同控制、安全通信 wujiehong@sau.edu.cn
石峻岭（1989—），女，辽宁沈阳人，讲师，博士，主要研究方向：车载网络、无人机网络
高利军（1977—），男，辽宁沈阳人，教授，博士，主要研究方向：信息安全、人工智能攻防对抗算法。
基金资助:
国防基础科研项目(JH2021010);国家自然科学基金资助项目(61902261)

Multi-UAV collaborative task assignment method based on improved self-organizing map

Yanan SUN, Jiehong WU(), Junling SHI, Lijun GAO

School of Computer Science，Shenyang Aerospace University，Shenyang Liaoning 110136，China

Received:2022-04-27 Revised:2022-06-22 Accepted:2022-06-24 Online:2022-07-11 Published:2023-05-10
Contact: Jiehong WU
About author:SUN Yanan， born in 1996， M. S. candidate. Her research interests include path planning and task assignment for Unmanned Aerial Vehicle （UAV） system.
WU Jiehong， born in 1971， Ph. D.， professor. Her research interests include cooperative control of UAV system， secure communication.
SHI Junling， born in 1989， Ph. D.， lecturer. Her research interests include in-vehicle network， UAV network.
GAO Lijun， born in 1977， Ph. D.， professor. His research interests include information security， artificial intelligence attack-defense confrontation algorithm.
Supported by:
Defense Basic Research Project(JH2021010);National Natural Science Foundation of China(61902261)

摘要/Abstract

摘要：

针对现有算法对多无人机（UAV）协同进行多任务分配时存在负载均衡和执行效率方面的不足，提出一种改进的自组织映射（ISOM）算法。该算法根据飞行时间和任务执行时间设计了UAV的负载均衡度，以提升任务完成的效率；还设计了新的非线性变化的学习率和邻域函数保证ISOM算法的稳定性和快速收敛。然后，在不同任务环境对ISOM算法进行了有效性验证。实验结果表明，与结合遗传算法的粒子群优化（GA-PSO）、Gurobi和ORTools算法相比，ISOM算法的任务完成时间可分别减少15.5%、12.7%和7.3%；在TSPLIB数据集的实例KroA100、KroA150、KroA200上进行航迹长度减小的有效性验证时，与杂草优化（IWO）算法、改进的单亲遗传算法（IPGA）和蚁群单亲遗传算法（AC-PGA）的对比结果表明，ISOM算法在无人机数量为2、3、4、5、8时，均获得了最小的航迹长度。由此可见，ISOM算法在解决多UAV协同多任务分配问题时效果显著。

关键词: 多无人机, 任务分配, 自组织映射, 负载均衡, 执行效率

Abstract:

To deal with the deficiencies in load balancing and execution efficiency of existing algorithms for cooperative multi-task assignment of multi-Unmanned Aerial Vehicle （UAV）， an Improved Self-Organizing Map （ISOM） algorithm was proposed. In the algorithm， the load balancing degree of UAVs was designed according to the flight time and task execution time in order to improve the efficiency of the task completion. And a novel non-linearly changing learning rate and neighborhood function were designed to ensure the stability and fast convergence of ISOM algorithm. Then， the validity of ISOM algorithm was verified in different task environments. Experimental results show that compared with Particle Swarm Optimization combined with Genetic Algorithm （GA-PSO）， Gurobi and ORTools algorithms， the proposed algorithm has the task completion time reduced by 15.5%， 12.7% and 7.3% respectively. When the effectiveness of track length reduction was verified on KroA100， KroA150， and KroA200 examples of TSPLIB dataset， comparison results with Invasive Weed Optimization （IWO） algorithm， Improved Partheno Genetic Algorithm （IPGA） and Ant Colony-Partheno Genetic Algorithm （AC-PGA） show that ISOM algorithm has the minimum track length when the number of UAVs is 2， 3， 4， 5， 8. It can be seen that ISOM algorithm has a significant effect on solving the problem of multi-UAV cooperative multi-task assignment.

Key words: multi-Unmanned Aerial Vehicle (UAV), task assignment, Self-Organizing Map (SOM), load balancing, execution efficiency

中图分类号:

TP301.6

孙亚男, 吴杰宏, 石峻岭, 高利军. 改进自组织映射的多无人机协同任务分配方法[J]. 计算机应用, 2023, 43(5): 1551-1556.

Yanan SUN, Jiehong WU, Junling SHI, Lijun GAO. Multi-UAV collaborative task assignment method based on improved self-organizing map[J]. Journal of Computer Applications, 2023, 43(5): 1551-1556.

图/表 9

参考文献 27

1	WEI X L， HUANG X L， LU T， et al. An improved method based on deep reinforcement learning for target searching［C］// Proceedings of the 4th International Conference on Robotics and Automation Engineering. Piscataway： IEEE， 2019： 130-134. 10.1109/icrae48301.2019.9043821
2	BIRCHER A， KAMEL M， ALEXIS K， et al. Receding horizon “next-best-view” planner for 3D exploration［C］// Proceedings of the 2016 IEEE International Conference on Robotics and Automation. Piscataway： IEEE， 2016： 1462-1468. 10.1109/icra.2016.7487281
3	HILDMANN H， KOVACS E. Review： using Unmanned Aerial Vehicles （UAVs） as Mobile Sensing Platforms （MSPs） for disaster response， civil security and public safety［J］. Drones， 2019， 3（3）： No.59. 10.3390/drones3030059
4	SAMPEDRO C， RODRIGUEZ-RAMOS A， BAVLE H， et al. A fully-autonomous aerial robot for search and rescue applications in indoor environments using learning-based techniques［J］. Journal of Intelligent and Robotic Systems， 2019， 95（2）： 601-627. 10.1007/s10846-018-0898-1
5	FARINHA A， ZUFFEREY R， ZHENG P， et al. Unmanned aerial sensor placement for cluttered environments［J］. IEEE Robotics and Automation Letters， 2020， 5（4）： 6623-6630. 10.1109/lra.2020.3015459
6	XU J W， OTA K， DONG M X. Aerial edge computing： flying attitude-aware collaboration for multi-UAV［J］. IEEE Transactions on Mobile Computing， 2022（Early Access）： 1-1. 10.1109/tmc.2022.3179399
7	ZHEN Z Y， WEN L D， WANG B L， et al. Improved contract network protocol algorithm based cooperative target allocation of heterogeneous UAV swarm［J］. Aerospace Science and Technology， 2021， 119： No.107054. 10.1016/j.ast.2021.107054
8	FAIGL J， VÁŇA P， DECKEROVÁ J. Fast heuristics for the 3-D multi-goal path planning based on the generalized traveling salesman problem with neighborhoods［J］. IEEE Robotics and Automation Letters， 2019， 4（3）： 2439-2446. 10.1109/lra.2019.2900507
9	SHI K X， ZHANG H W， ZHANG Z Z， et al. The algorithm of terminal logistics path planning based on TSP problem［C］// Proceedings of the 2020 International Conference on Artificial Intelligence and Computer Engineering. Piscataway： IEEE， 2020： 130-133. 10.1109/icaice51518.2020.00031
10	GAVISH B， PIRKUL H. Efficient algorithms for solving multi constraint zero-one knapsack problems to optimality［J］. Mathematical Programming， 1985， 31（1）： 78-105. 10.1007/bf02591863
11	JIANG C， WAN Z P， PENG Z H. A new efficient hybrid algorithm for large scale multiple traveling salesman problems［J］. Expert Systems with Applications， 2020， 139： No.112867. 10.1016/j.eswa.2019.112867
12	ZHOU H L， SONG M L， PEDRYCZ W. A comparative study of improved GA and PSO in solving multiple traveling salesmen problem［J］. Applied Soft Computing， 2018， 64： 564-580. 10.1016/j.asoc.2017.12.031
13	胡士娟，鲁海燕，向蕾，等. 求解MMTSP的模糊聚类单亲遗传算法［J］.计算机科学， 2020， 47（6）：219-224. 10.11896/jsjkx.190500137
	HU S J， LU H Y， XIANG L， et al. Fuzzy C-means clustering based partheno-genetic algorithm for solving MMTSP［J］. Computer Science， 2020， 47（6）： 219-224. 10.11896/jsjkx.190500137
14	张瑞鹏，冯彦翔，杨宜康. 多无人机协同任务分配混合粒子群算法［J］. 航空学报， 2022， 43（12）：418-433. 10.7527/S1000-6893.2021.26011
	ZHNAG R P， FENG Y X， YANG Y K. Hybrid particle swarm algorithm for multi-UAV cooperative task allocation［J］. Acta Aeronautica et Astronautica Sinica， 2022， 43（12）：418-433. 10.7527/S1000-6893.2021.26011
15	KOHONEN T. Self-Organization and Associative Memory， SSINF 8 ［M］. 3rd ed. Berlin： Springer， 1988： 37. 10.1007/978-3-662-00784-6
16	KOHONEN T， KASKI S， LAGUS K， et al. Self organization of a massive document collection［J］. IEEE Transactions on Neural Networks， 2000， 11（3）： 574-585. 10.1109/72.846729
17	ZHU D Q， ZHOU B， YANG S X. A novel algorithm of multi-AUVs task assignment and path planning based on biologically inspired neural network map［J］. IEEE Transactions on Intelligent Vehicles， 2021， 6（2）：333-342. 10.1109/tiv.2020.3029369
18	LI X， ZHU D Q. An adaptive som neural network method for distributed formation control of a group of AUVs［J］. IEEE Transactions on Industrial Electronics， 2018， 65（10）： 8260-8270.
19	SUN B， ZHU D Q， TIAN C， et al. Complete coverage autonomous underwater vehicles path planning based on glasius bio-inspired neural network algorithm for discrete and centralized programming［J］. IEEE Transactions on Cognitive and Developmental Systems， 2019， 11（1）： 73-84. 10.1109/tcds.2018.2810235
20	ZHU D Q， CAO X， SUN B， et al. Biologically inspired self-organizing map applied to task assignment and path planning of an AUV system［J］. IEEE Transactions on Cognitive and Developmental Systems， 2018， 10（2）： 304-313. 10.1109/tcds.2017.2727678
21	ZHU A M， YANG S X. A neural network approach to dynamic task assignment of multirobots［J］. IEEE Transactions on Neural Networks， 2006， 17（5）： 1278-1287. 10.1109/tnn.2006.875994
22	YI X， ZHU A M， YANG S X， et al. A bio-inspired approach to task assignment of swarm robots in 3-D dynamic environments［J］. IEEE Transactions on Cybernetics， 2017， 47（4）： 974-983. 10.1109/tcyb.2016.2535153
23	YAN M， YUAN H M， XU J， et al. Task allocation and route planning of multiple UAVs in a marine environment based on an improved particle swarm optimization algorithm［J］. EURASIP Journal on Advances in Signal Processing， 2021， 2021： No.94. 10.1186/s13634-021-00804-9
24	Optimization Gurobi， LLC. Gurobi optimizer reference manual［EB/OL］. ［2022-04-06］..
25	Google. OR-Tools Python reference： algorithms［EB/OL］. ［2022-04-06］..
26	REINELT G. TSPLIB - a traveling salesman problem library［J］. ORSA Journal on Computing， 1991， 3（4）： 376-384. 10.1287/ijoc.3.4.376
27	VENKATESH P， SINGH A. Two metaheuristic approaches for the multiple traveling salesperson problem［J］. Applied Soft Computing， 2015， 26： 74-89. 10.1016/j.asoc.2014.09.029

编号	位置	编号	位置
T₁	（1 425，915）	T₂	（1 137，747）
T₃	（865，422）	T₄	（885，111）
T₅	（381，447）	T₆	（147，675）
T₇	（867，963）	T₈	（327，207）
T₉	（1 011，555）	T₁₀	（1 685，147）

编号	位置	编号	位置
T₁	（1 425，915）	T₂	（1 137，747）
T₃	（865，422）	T₄	（885，111）
T₅	（381，447）	T₆	（147，675）
T₇	（867，963）	T₈	（327，207）
T₉	（1 011，555）	T₁₀	（1 685，147）

UAV	航迹长度/m	执行数量	完成时间/s
U₁	2 950.22	5	84.00
U₂	3 549.69	3	85.99
U₃	3 384.14	2	77.68

UAV	航迹长度/m	执行数量	完成时间/s
U₁	2 950.22	5	84.00
U₂	3 549.69	3	85.99
U₃	3 384.14	2	77.68

算法	UAV	航迹长度/m	执行数量	完成时间/s
GA-PSO	U₁	2 513.41	3	65.26
	U₂	3 838.94	5	101.77
	U₃	1 220.35	2	34.40
Gurobi	U₁	3 195.02	4	83.90
	U₂	3 675.28	5	98.50
	U₃	3 386.94	1	72.73
ORTools	U₁	3 387.33	3	82.74
	U₂	2 762.46	3	70.24
	U₃	3 640.56	4	92.81

改进自组织映射的多无人机协同任务分配方法

Multi-UAV collaborative task assignment method based on improved self-organizing map

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 27

相关文章 15

编辑推荐

Metrics

参数	极差	时间
ISOM	8.31	85.99
GA-PSO	67.37	101.77
Gurobi	15.77	98.50
ORTools	22.57	92.81

实例	算法	无人机数量N
实例	算法	2	3	4	5	8
KroA100	ISOM	22 316	25 094	23 757	25 316	25 130
	IWO	40 546	41 834	39 754	41 255	37 251
	IPGA	29 215	31 087	34 445	32 482	38 790
	AC-PGA	26 902	26 416	27 322	28 759	31 332
KroA150	ISOM	27 863	29 322	29 208	30 292	31 724
	IWO	68 012	67 788	67 089	67 045	66 258
	IPGA	46 123	45 686	55 490	67 419	73 317
	AC-PGA	33 986	35 053	36 292	37 102	38 862
KroA200	ISOM	34 323	34 751	33 000	33 126	33 877
	IWO	73 718	74 103	77 987	74 876	72 436
	IPGA	60 371	67 769	85 157	92 312	105 997
	AC-PGA	38 389	40 039	41 602	41 948	45 102

[1]	张明, 付乐, 王海峰. 面向边缘计算的并发数据流接转控制模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3876-3883.
[2]	张佩瑶, 付晓东. 防恶意竞价的众包多任务分配激励机制[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 261-268.
[3]	龙运波, 唐聃. 分布式存储中基于局部修复码的负载均衡方法[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 767-775.
[4]	杨力, 陈建廷, 向阳. 基于HBase的工业时序大数据分布式存储性能优化策略[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 759-766.
[5]	邓辅秦, 黄焕钊, 谭朝恩, 付兰慧, 张建民, 林天麟. 结合遗传算法和滚动调度的多机器人任务分配算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3833-3839.
[6]	高旗, 吕娜, 缪竞成. 基于负载均衡的无线虚拟网络映射算法[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3148-3153.
[7]	彭鹏, 倪志伟, 朱旭辉. 基于用户满意效用的空间众包任务分配方法[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3235-3243.
[8]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 《计算机应用》唯一官方网站, 2021, 41(8): 2232-2241.
[9]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[10]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[11]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[12]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[13]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.
[14]	韩俊樱, 张振宇, 孔德仕. 移动群智感知中面向用户区域的分布式多任务分配方法[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 358-362.
[15]	李翠, 陈庆奎. 基于DPDK并行通信的动态监控模型[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 335-341.