Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (5): 1551-1556.DOI: 10.11772/j.issn.1001-9081.2022040592
Special Issue: 先进计算
• Advanced computing • Previous Articles Next Articles
Yanan SUN, Jiehong WU(), Junling SHI, Lijun GAO
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.Supported by:
通讯作者:
吴杰宏
作者简介:
孙亚男(1996—),女,辽宁朝阳人,硕士研究生,主要研究方向:无人机系统路径规划和任务分配基金资助:
CLC Number:
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.
孙亚男, 吴杰宏, 石峻岭, 高利军. 改进自组织映射的多无人机协同任务分配方法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1551-1556.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2022040592
编号 | 位置 | 编号 | 位置 |
---|---|---|---|
T1 | (1 425,915) | T2 | (1 137,747) |
T3 | (865,422) | T4 | (885,111) |
T5 | (381,447) | T6 | (147,675) |
T7 | (867,963) | T8 | (327,207) |
T9 | (1 011,555) | T10 | (1 685,147) |
Tab. 1 Location information of task points
编号 | 位置 | 编号 | 位置 |
---|---|---|---|
T1 | (1 425,915) | T2 | (1 137,747) |
T3 | (865,422) | T4 | (885,111) |
T5 | (381,447) | T6 | (147,675) |
T7 | (867,963) | T8 | (327,207) |
T9 | (1 011,555) | T10 | (1 685,147) |
UAV | 航迹长度/m | 执行数量 | 完成时间/s |
---|---|---|---|
U1 | 2 950.22 | 5 | 84.00 |
U2 | 3 549.69 | 3 | 85.99 |
U3 | 3 384.14 | 2 | 77.68 |
Tab. 2 Execution results of ISOM algorithm
UAV | 航迹长度/m | 执行数量 | 完成时间/s |
---|---|---|---|
U1 | 2 950.22 | 5 | 84.00 |
U2 | 3 549.69 | 3 | 85.99 |
U3 | 3 384.14 | 2 | 77.68 |
算法 | UAV | 航迹长度/m | 执行数量 | 完成时间/s |
---|---|---|---|---|
GA-PSO | U1 | 2 513.41 | 3 | 65.26 |
U2 | 3 838.94 | 5 | 101.77 | |
U3 | 1 220.35 | 2 | 34.40 | |
Gurobi | U1 | 3 195.02 | 4 | 83.90 |
U2 | 3 675.28 | 5 | 98.50 | |
U3 | 3 386.94 | 1 | 72.73 | |
ORTools | U1 | 3 387.33 | 3 | 82.74 |
U2 | 2 762.46 | 3 | 70.24 | |
U3 | 3 640.56 | 4 | 92.81 |
Tab. 3 Task execution data of comparison algorithms
算法 | UAV | 航迹长度/m | 执行数量 | 完成时间/s |
---|---|---|---|---|
GA-PSO | U1 | 2 513.41 | 3 | 65.26 |
U2 | 3 838.94 | 5 | 101.77 | |
U3 | 1 220.35 | 2 | 34.40 | |
Gurobi | U1 | 3 195.02 | 4 | 83.90 |
U2 | 3 675.28 | 5 | 98.50 | |
U3 | 3 386.94 | 1 | 72.73 | |
ORTools | U1 | 3 387.33 | 3 | 82.74 |
U2 | 2 762.46 | 3 | 70.24 | |
U3 | 3 640.56 | 4 | 92.81 |
参数 | 极差 | 时间 |
---|---|---|
ISOM | 8.31 | 85.99 |
GA-PSO | 67.37 | 101.77 |
Gurobi | 15.77 | 98.50 |
ORTools | 22.57 | 92.81 |
Tab. 4 Task complementation time of different algorithms
参数 | 极差 | 时间 |
---|---|---|
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 |
Tab. 5 Track lengths of task assignment schemes of different algorithms
实例 | 算法 | 无人机数量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 | 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 |
[1] | Ming ZHANG, Le FU, Haifeng WANG. Relay control model for concurrent data flow in edge computing [J]. Journal of Computer Applications, 2024, 44(12): 3876-3883. |
[2] | Peiyao ZHANG, Xiaodong FU. Incentive mechanism of crowdsourcing multi-task assignment against malicious bidding [J]. Journal of Computer Applications, 2024, 44(1): 261-268. |
[3] | Yunbo LONG, Dan TANG. Load balancing method based on local repair code in distributed storage [J]. Journal of Computer Applications, 2023, 43(3): 767-775. |
[4] | Li YANG, Jianting CHEN, Yang XIANG. Performance optimization strategy of distributed storage for industrial time series big data based on HBase [J]. Journal of Computer Applications, 2023, 43(3): 759-766. |
[5] | ZHAO Quan, TANG Xiaochun, ZHU Ziyu, MAO Anqi, LI Zhanhuai. Low-latency cluster scheduling framework for large-scale short-time tasks [J]. Journal of Computer Applications, 2021, 41(8): 2396-2405. |
[6] | MA Hua, CHEN Yuepeng, TANG Wensheng, LOU Xiaoping, HUANG Zhuoxuan. Survey of research progress on crowdsourcing task assignment for evaluation of workers’ ability [J]. Journal of Computer Applications, 2021, 41(8): 2232-2241. |
[7] | MA Jianhong, CAO Wenbin, LIU Yuangang, XIA Shuang. Patent clustering method based on functional effect [J]. Journal of Computer Applications, 2021, 41(5): 1361-1366. |
[8] | XU Hongliang, YANG Guiqin, JIANG Zhanjun. Data center adaptive multi-path load balancing algorithm based on software defined network [J]. Journal of Computer Applications, 2021, 41(4): 1160-1164. |
[9] | YANG Ling, JIANG Chunmao. Strategy of energy-aware virtual machine migration based on three-way decision [J]. Journal of Computer Applications, 2021, 41(4): 990-998. |
[10] | Cui LI, Qingkui CHEN. Dynamic monitoring model based on DPDK parallel communication [J]. Journal of Computer Applications, 2020, 40(2): 335-341. |
[11] | QIN Haiyan, ZHANG Yonglong, LI Bin. Truthful mechanism for crowdsourcing task assignment in social network [J]. Journal of Computer Applications, 2020, 40(10): 3019-3024. |
[12] | YANG Zhengqing, ZHOU Zhaorong, YUAN Shu. Task assignment based on discrete cuckoo search algorithm in mobile crowd sensing system [J]. Journal of Computer Applications, 2019, 39(9): 2778-2783. |
[13] | ZHANG Xingsheng, YU Dunhui, ZHANG Wanshan, WANG Chenxu. Time utility balanced online task assignment algorithm under spatial crowdsourcing environment [J]. Journal of Computer Applications, 2019, 39(5): 1357-1363. |
[14] | LI Zhuhong, ZHAO Canming, YAN Long, ZHANG Xinming. Load balancing opportunistic routing protocol for power line communication network in smart grids [J]. Journal of Computer Applications, 2019, 39(3): 812-816. |
[15] | CHEN Youling, ZUO Lidan, NIU Yufei, WANG Long. Task assignment method of product development based on knowledge similarity [J]. Journal of Computer Applications, 2019, 39(2): 323-329. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||