系统工程与电子技术 ›› 2024, Vol. 46 ›› Issue (3): 972-981.doi: 10.12305/j.issn.1001-506X.2024.03.23
高程1, 都延丽1,*, 步雨浓2, 刘燕斌1, 王宇飞2
收稿日期:
2022-12-02
出版日期:
2024-02-29
发布日期:
2024-03-08
通讯作者:
都延丽
作者简介:
高程(1997—), 男, 硕士研究生, 主要研究方向为集群飞行器任务规划基金资助:
Cheng GAO1, Yanli DU1,*, Yunong BU2, Yanbin LIU1, Yufei WANG2
Received:
2022-12-02
Online:
2024-02-29
Published:
2024-03-08
Contact:
Yanli DU
摘要:
针对复杂多任务下的异构无人机(unmanned aerial vehicle, UAV)集群分组调配问题, 提出一种基于改进K均值和延迟接受(deferred-acceptance, DA)算法的先聚类后匹配方法。在任务聚类分组环节, 通过离群点检测和固定初始聚类中心的方法来提高K-means聚类的精度, 并设计余量裕度下的分组均衡性调整策略, 在最优性的前提下提高分组的均衡性。在集群匹配分组环节, 改进了DA算法, 通过任务倾向的偏好列表快速生成预中选方案, 并设计两阶段冲突消除来保证匹配的稳定性和收敛性。仿真实验表明, 所提方法能够快速有效地解决复杂多任务下的UAV集群分组调配问题, 具备良好的最优性和时效性。
中图分类号:
高程, 都延丽, 步雨浓, 刘燕斌, 王宇飞. 面向复杂多任务的异构无人机集群分组调配[J]. 系统工程与电子技术, 2024, 46(3): 972-981.
Cheng GAO, Yanli DU, Yunong BU, Yanbin LIU, Yufei WANG. Heterogeneous UAV swarm grouping deployment for complex multiple tasks[J]. Systems Engineering and Electronics, 2024, 46(3): 972-981.
表1
目标区域参数"
目标区域编号 | 位置/km | 载荷需求 | 目标区域编号 | 位置/km | 载荷需求 | |
1 | (3, 24) | [2, 1, 1] | 11 | (28, 22) | [3, 2, 1] | |
2 | (6, 18) | [1, 1, 1] | 12 | (28, 37) | [1, 2, 1] | |
3 | (8, 37) | [1, 1, 1] | 13 | (29, 8) | [1, 1, 1] | |
4 | (9, 20) | [2, 1, 1] | 14 | (32, 18) | [1, 1, 1] | |
5 | (10, 9) | [1, 2, 1] | 15 | (32, 31) | [1, 1, 1] | |
6 | (11, 31) | [2, 2, 1] | 16 | (34, 13) | [2, 1, 1] | |
7 | (17, 29) | [1, 1, 1] | 17 | (39, 27) | [2, 2, 1] | |
8 | (17, 14) | [1, 2, 1] | 18 | (41, 30) | [1, 1, 1] | |
9 | (20, 26) | [1, 1, 1] | 19 | (43, 13) | [2, 2, 1] | |
10 | (26, 45) | [1, 1, 1] | 20 | (47, 38) | [1, 1, 1] |
表4
无人机匹配分组结果"
分区 | 无人机序列 | 各类无人机数量 |
1 | 2, 9, 14, 16, 19, 22, 24, 25, 30, 31, 33, 41, 43, 46, 50, 57, 60 | [5, 6, 6] |
2 | 6, 7, 8, 13, 17, 20, 27, 28, 36, 38, 39, 49, 51, 52, 54, 56 | [6, 5, 5] |
3 | 1, 3, 4, 15, 18, 21, 23, 26, 32, 35, 45, 47, 53, 58, 59 | [5, 5, 5] |
4 | 5, 10, 11, 12, 29, 34, 37, 40, 42, 44, 48, 55 | [4, 4, 4] |
1 |
MENG Y F , XU J C , HE J H . A cluster UAV inspired honeycomb defense system to confront military IoT: a dynamic game approach[J]. Soft Computing, 2023, 27 (2): 1033- 1043.
doi: 10.1007/s00500-021-05881-4 |
2 |
YAN F , ZHU X P , ZHOU Z , et al. Real-time task allocation for a heterogeneous multi-UAV simultaneous attack[J]. Scientia Sinica Information, 2019, 49 (5): 555- 569.
doi: 10.1360/N112018-00338 |
3 |
WANG J F , JIA G W , LIN J C , et al. Cooperative task allocation for heterogeneous multi-UAV using multi-objective optimization algorithm[J]. Journal of Central South University, 2020, 27 (2): 432- 448.
doi: 10.1007/s11771-020-4307-0 |
4 |
ELGIBREEN H , YOUCEF K . Dynamic task allocation in an uncertain environment with heterogeneous multi-agents[J]. Autonomous Robots, 2019, 43 (7): 1639- 1664.
doi: 10.1007/s10514-018-09820-5 |
5 | KIM Y D , CHOI H L , OH G , et al. Market-based task assignment for cooperative timing missions in dynamic environments[J]. Journal of Intelligent & Robotic Systems, 2017, 87 (1): 97- 123. |
6 |
KORSAH G A , STENTZ A , DIAS M B . A comprehensive taxo-nomy for multi-robot task allocation[J]. The International Journal of Robotics Research, 2013, 32 (12): 1495- 1512.
doi: 10.1177/0278364913496484 |
7 |
PENG Q , WU H S , XUE R S . Review of dynamic task allocation methods for UAV swarms oriented to ground targets[J]. Complex System Modeling and Simulation, 2021, 1 (3): 163- 175.
doi: 10.23919/CSMS.2021.0022 |
8 | XU T S , CHIANG H D , LIU G Y , et al. Hierarchical K-means method for clustering large-scale advanced metering infrastructure data[J]. IEEE Trans. on Power Delivery, 2015, 32 (2): 609- 616. |
9 | CHEN J , XIAO K , YOU K , et al. Hierarchical task assignment strategy for heterogeneous multi-UAV system in large-scale search and rescue scenarios[J]. International Journal of Aerospace Engineering, 2021, 7 (2): 7353697. |
10 | MA Y H, ZHANG H, ZHANG Y Z, et al. Coordinated optimization algorithm combining GA with cluster for multi-UAVs to multi-tasks task assignment and path planning[C]//Proc. of the IEEE 15th International Conference on Control and Automation, 2019: 1026-1031. |
11 | 郑习羽, 徐梓毓, 王京华. 基于聚类分组的异构多机器人任务分配算法研究[J]. 航空兵器, 2022, 29 (4): 100- 109. |
ZHENG X Y , XU Z Y , WANG J H . Research on task allocation of heterogeneous multi-robot based on cluster grouping algorithm[J]. Aero Weaponry, 2022, 29 (4): 100- 109. | |
12 |
ELANGO M , NACHIAPPAN S , TIWARI M K . Balancing task allocation in multi-robot systems using K-means clustering and auction based mechanisms[J]. Expert Systems with Applications, 2011, 38 (6): 6486- 6491.
doi: 10.1016/j.eswa.2010.11.097 |
13 |
FADAEI S , POOYA A , SOLEYMANIFARD O . Taxonomy of production systems with combining K-means and evolutionary algorithms[J]. Journal of Advanced Manufacturing Systems, 2022, 21 (3): 515- 536.
doi: 10.1142/S0219686722500172 |
14 | WANG C R , SHAO X H . An improving majority weighted minority oversampling technique for imbalanced classification problem[J]. IEEE Access, 2020, 9, 5069- 5082. |
15 |
LI X , XU S W . Summary of subspace clustering algorithms research based on CLIQUE[J]. Computer Simulation, 2010, 27 (5): 174- 177.
doi: 10.3969/j.issn.1006-9348.2010.05.042 |
16 | VENTORIMR I M , LUCHI D , RODRIGUES A L , et al. Birchscan: a sampling method for applying DBSCAN to large datasets[J]. Expert Systems with Applications, 2021, 184 (1): 115518- 115528. |
17 | FARD M M , THONET T , GAUSSIER E . Deep K-means: jointly clustering with K-means and learning representations[J]. Pattern Recognition Letters, 2020, 138 (10): 185- 192. |
18 | XIA S Y , PENG D W , MENG D Y , et al. A fast adaptive K-means with no bounds[J]. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2020, 44 (1): 87- 99. |
19 | 廖纪勇, 吴晟, 刘爱莲. 基于相异性度量选取初始聚类中心改进的K-means聚类算法[J]. 控制与决策, 2021, 36 (12): 3083- 3090. |
LIAO J Y , WU S , LIU A L . Improved K-means clustering algorithm for selecting initial clustering centers based on dissi-milarity measure[J]. Control and Decision, 2021, 36 (12): 3083- 3090. | |
20 |
RAJU Y , DEVARAKONDA N . A cluster medoid approach for cloud task scheduling[J]. International Journal of Knowledge-based and Intelligent Engineering Systems, 2021, 25 (1): 65- 73.
doi: 10.3233/KES-210053 |
21 | 程万里, 张晶, 王慧. 超密集网络中基于聚类的资源分配方案[J]. 系统工程与电子技术, 2020, 42 (7): 1623- 1629. |
CHENG W L , ZHANG J , WANG H . Cluster-based resource allocation scheme in ultra-dense network[J]. Systems Engineering and Electronics, 2020, 42 (7): 1623- 1629. | |
22 | WANG R , LI D F , YU G F . Research on bilateral matching decision method considering attribute association in heterogeneous information environment[J]. Journal of Intelligent & Fuzzy Systems, 2020, 38 (4): 4779- 4792. |
23 |
MI X R , YANG C G , SONG Y B , et al. A distributed matching game for exploring resource allocation in satellite networks[J]. Peer-to-Peer Networking and Applications, 2021, 14 (5): 3360- 3371.
doi: 10.1007/s12083-021-01158-7 |
24 |
GALE D , SHAPLEY L S . College admissions and the stability of marriage[J]. The American Mathematical Monthly, 2013, 120 (5): 386- 391.
doi: 10.4169/amer.math.monthly.120.05.386 |
25 | 王赵文. 基于匹配博弈的异构无线网络能耗优化研究[D]. 北京: 中国矿业大学, 2022. |
WANG Z W. Research on energy consumption optimization of heterogeneous wireless network based on matching game[D]. Beijing: China University of Mining and Technology, 2022. | |
26 | 李恒杰, 夏宇轩, 周云, 等. 基于改进延迟接受算法的电动汽车-快充桩匹配策略[J]. 电力自动化设备, 2023, 43 (6): 46- 52. |
LI H J , XIA Y X , ZHOU Y , et al. Matching strategy between electric vehicles and fast charging piles based on improved deferred-acceptance algorithm[J]. Electric Power Automation Equipment, 2023, 43 (6): 46- 52. | |
27 |
ZHANG J Z , CHEN Y , LIU Y X , et al. Two-stage stable matching based dynamic spectrum allocation in heterogeneous networks[J]. IEEE Access, 2019, 7, 40982- 40990.
doi: 10.1109/ACCESS.2019.2907995 |
28 | 向竹, 杨志伟, 杨克巍, 等. 基于双层稳定匹配的异构无人机集群"分布式"协同算法[J]. 控制与决策, 2022, 37 (4): 871- 880. |
XIANG Z , YANG Z W , YANG K W , et al. "Decentralized" colla-borative algorithm for heterogeneous UAV swarm based on bi-level stable matching[J]. Control and Decision, 2022, 37 (4): 871- 880. | |
29 | LV Y , LIU M D , XIANG Y . Fast searching density peak clustering algorithm based on shared nearest neighbor and adaptive clustering center[J]. Symmetry, 2020, 12 (12): 2014. |
30 | CHEN J G , YU P S . A domain adaptive density clustering algorithm for data with varying density distribution[J]. IEEE Trans. on Knowledge and Data Engineering, 2019, 33 (6): 2310- 2321. |
31 | CHANDRAWANSHI V S , TRIPATHI R K , PACHAURI R . An intelligent energy efficient clustering technique for multiple base stations positioning in a wireless sensor network[J]. Journal of Intelligent & Fuzzy Systems, 2019, 36 (3): 2409- 2418. |
[1] | 黄思佳, 宋纯锋, 李璇. 基于可变尺度先验框的声呐图像目标检测[J]. 系统工程与电子技术, 2024, 46(3): 771-778. |
[2] | 孙伟峰, 赵林林, 纪永刚, 戴永寿. 基于多帧聚类的紧凑型HFSWR虚假点迹识别方法[J]. 系统工程与电子技术, 2024, 46(2): 419-427. |
[3] | 罗佳奕, 李煊鹏, 李江浩, 薛启凡, 杨凤, 张为公. 基于PDW多特征融合的辐射源信号分选方法[J]. 系统工程与电子技术, 2024, 46(1): 80-87. |
[4] | 曹志强, 张佳, 辛斌. 间歇式信息传输条件下无人机搜索覆盖规划[J]. 系统工程与电子技术, 2024, 46(1): 152-161. |
[5] | 司伟建, 张悦, 邓志安. 用于雷达信号分选的连通k近邻聚类算法[J]. 系统工程与电子技术, 2023, 45(8): 2463-2470. |
[6] | 毕文豪, 周杰, 张安, 刘力. 杂波环境下基于最大熵模糊聚类的JPDA算法[J]. 系统工程与电子技术, 2023, 45(7): 1920-1927. |
[7] | 禄晓飞, 靳硕静, 洪灵, 戴奉周. 基于聚类求解TVAR模型的目标微多普勒分析[J]. 系统工程与电子技术, 2023, 45(3): 660-668. |
[8] | 王坚浩, 王龙, 张亮, 崔利杰. 灰色群组聚类和改进CRITIC赋权的供应商选择VIKOR多属性决策[J]. 系统工程与电子技术, 2023, 45(1): 155-164. |
[9] | 王磊, 张志勇, 曾维贵, 曹司磊, 张天赫. 基于数据场联合决策图改进的GMM聚类[J]. 系统工程与电子技术, 2022, 44(9): 2743-2751. |
[10] | 杨建峰, 肖和业, 李亮, 白俊强, 董维浩. 基于模糊聚类和专家评分机制的无人机多层次模块划分方法[J]. 系统工程与电子技术, 2022, 44(8): 2530-2539. |
[11] | 马骏, 杨镜宇, 吴曦. 基于预聚类主动半监督的作战体系效能评估[J]. 系统工程与电子技术, 2022, 44(6): 1889-1896. |
[12] | 曹鹏宇, 杨承志, 石礼盟, 吴宏超. 基于PSO-DBSCAN和SCGAN的未知雷达信号处理方法[J]. 系统工程与电子技术, 2022, 44(4): 1158-1165. |
[13] | 王海滨, 关欣, 衣晓. 基于区间数聚类的目标分群算法[J]. 系统工程与电子技术, 2022, 44(2): 577-583. |
[14] | 于博文, 于琳, 吕明, 张捷. 基于M-ANFIS-PNN的目标威胁评估模型[J]. 系统工程与电子技术, 2022, 44(10): 3155-3163. |
[15] | 张一迪, 王悦斌, 王培志, 杨沁, 陆起涌, 张建秋, 李旦. 恒虚警检测信源数的方法[J]. 系统工程与电子技术, 2022, 44(1): 1-9. |
阅读次数 | ||||||||||||||||||||||||||||||||||||||||||||||||||
全文 248
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||
摘要 244
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||