面向复杂多任务的异构无人机集群分组调配

doi:10.12305/j.issn.1001-506X.2024.03.23

摘要/Abstract

摘要：

针对复杂多任务下的异构无人机(unmanned aerial vehicle, UAV)集群分组调配问题, 提出一种基于改进K均值和延迟接受(deferred-acceptance, DA)算法的先聚类后匹配方法。在任务聚类分组环节, 通过离群点检测和固定初始聚类中心的方法来提高K-means聚类的精度, 并设计余量裕度下的分组均衡性调整策略, 在最优性的前提下提高分组的均衡性。在集群匹配分组环节, 改进了DA算法, 通过任务倾向的偏好列表快速生成预中选方案, 并设计两阶段冲突消除来保证匹配的稳定性和收敛性。仿真实验表明, 所提方法能够快速有效地解决复杂多任务下的UAV集群分组调配问题, 具备良好的最优性和时效性。

关键词: 异构无人机集群, 分组调配, 聚类, 延迟接受算法, 稳定匹配

Abstract:

A method of clustering before matching based on the improved K-means and deferred-acceptance (DA) algorithm is presented to solve the group deployment problem of heterogeneous unmanned aerial vehicle (UAV) swarm for complex multiple tasks. During the task clustering grouping stage, the approach of outlier detection and fixed initial cluster centers is exploited to increase the K-means clustering accuracy, and the grouping equalization adjustment strategy under margin is designed to enhance the grouping equalization based on the optimality condition. In the swarm grouping stage of matching, DA algorithm is developed by the preference list of task preferences to quickly generate a pre-selected scheme, and a two-stage conflict resolution is designed to ensure the matching stability and convergence. The simulation results show that the proposed method can solve the UAV swarm grouping deployment problem for complex multiple tasks quickly and effectively, and possess good optimality and timeliness.

Key words: heterogeneous unmanned aerial vehicle (UAV) swarm, group deployment, clustering, deferred-acceptance algorithm, stable matching

中图分类号:

TP29

高程, 都延丽, 步雨浓, 刘燕斌, 王宇飞. 面向复杂多任务的异构无人机集群分组调配[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.

图/表 16

图1

图2

图3

表1

图4

图5

表2

表3

表4

图6

图7

图8

图9

图10

图11

图12

参考文献 31

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.

目标区域编号	位置/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]

分区	目标点序列	目标点数量	各类无人机需求数量
1	10, 12, 15, 17, 18, 20	6	[5, 6, 6]
2	11, 13, 14, 16, 19	5	[6, 5, 5]
3	1, 2, 4, 5, 8	5	[5, 5, 5]
4	3, 6, 7, 9	4	[4, 4, 4]

无人机类型	数量	载荷资源上限
1	20	[INF, 0, 0]
2	20	[0, 4, 0]
3	20	[0, 0, INF]

分区	无人机序列	各类无人机数量
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]	黄思佳, 宋纯锋, 李璇. 基于可变尺度先验框的声呐图像目标检测[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.