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

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

Abstract

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

CLC Number:

TP29

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.

Figures/Tables 16

Fig.1

Fig.2

Fig.3

Table 1

Fig.4

Fig.5

Table 2

Table 3

Table 4

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

References 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]	Sijia HUANG, Chunfeng SONG, Xuan LI. Target detection in sonar images based on variable scale prior frame [J]. Systems Engineering and Electronics, 2024, 46(3): 771-778.
[2]	Weifeng SUN, Linlin ZHAO, Yonggang JI, Yongshou DAI. A false plot identification method based on multi-frame clustering for compact HFSWR [J]. Systems Engineering and Electronics, 2024, 46(2): 419-427.
[3]	Jiayi LUO, Xuanpeng LI, Jianghao LI, Qifan XUE, Feng YANG, Weigong ZHANG. Radiation signal sorting method based on PDW multi-feature fusion [J]. Systems Engineering and Electronics, 2024, 46(1): 80-87.
[4]	Zhiqiang CAO, Jia ZHANG, Bin XIN. UAV search coverage planning under intermittent information transmission condition [J]. Systems Engineering and Electronics, 2024, 46(1): 152-161.
[5]	Weijian SI, Yue ZHANG, Zhian DENG. Connected k-nearest neighbor clustering algorithm for radar signal sorting [J]. Systems Engineering and Electronics, 2023, 45(8): 2463-2470.
[6]	Wenhao BI, Jie ZHOU, An ZHANG, Li LIU. JPDA algorithm based on maximum entropy fuzzy clustering in clutter environment [J]. Systems Engineering and Electronics, 2023, 45(7): 1920-1927.
[7]	Xiangyu WANG, Yanyu ZHANG, Long LI, Chunxiao JIAN, Weijia CUI. Weighted clustering algorithm based on adaptive fruit fly optimization algorithm [J]. Systems Engineering and Electronics, 2023, 45(7): 2259-2268.
[8]	Jianhao WANG, Long WANG, Liang ZHANG, Lijie CUI. Supplier selection VIKOR multi-attribute decision making of grey group clustering and improved CRITIC weighting [J]. Systems Engineering and Electronics, 2023, 45(1): 155-164.
[9]	Lei WANG, Zhiyong ZHANG, Weigui ZENG, Silei CAO, Tianhe ZHANG. An improved GMM clustering based on data field and decision graph [J]. Systems Engineering and Electronics, 2022, 44(9): 2743-2751.
[10]	Jianfeng YANG, Heye XIAO, Liang LI, Junqiang BAI, Weihao DONG. Multi-level module partition method of UAV based on fuzzy clustering and expert scoring mechanism [J]. Systems Engineering and Electronics, 2022, 44(8): 2530-2539.
[11]	Haolun GU, Guorong ZHAO, Jinbo YAO, Chao GAO. Cross layer MAC protocol design of NNSs based on graded nodes [J]. Systems Engineering and Electronics, 2022, 44(7): 2329-2340.
[12]	Jun MA, Jingyu YANG, Xi WU. Evaluation of operational system of systems effectiveness based on pre-clustering active semi-supervised learning [J]. Systems Engineering and Electronics, 2022, 44(6): 1889-1896.
[13]	Pengyu CAO, Chengzhi YANG, Limeng SHI, Hongchao WU. Unknown radar signal processing based on PSO-DBSCAN and SCGAN [J]. Systems Engineering and Electronics, 2022, 44(4): 1158-1165.
[14]	Haibin WANG, Xin GUAN, Xiao YI. Method of target grouping based on interval number clustering [J]. Systems Engineering and Electronics, 2022, 44(2): 577-583.
[15]	Bowen YU, Lin YU, Ming LYU, Jie ZHANG. Target threat assessment model based on M-ANFIS-PNN [J]. Systems Engineering and Electronics, 2022, 44(10): 3155-3163.

Heterogeneous UAV swarm grouping deployment for complex multiple tasks

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 31

Related Articles 15

Recommended Articles

Metrics

Comments