面向復雜多任務的異構無人機集群分組調配

高 程, 都延麗,*, 步雨濃, 劉燕斌, 王宇飛

(1. 南京航空航天大學航天學院, 江蘇 南京 211106; 2. 北京機電工程研究所, 北京 100854)

0 引 言

近年來,無人機作戰樣式正從單機作戰向集群協同作戰方向轉變[1]。無人機集群分為同構集群和異構集群兩種類型,異構集群中各無人機之間功能互補,能力協同,能夠適應復雜多樣的作戰任務需求,逐漸成為集群作戰的主力[2-3]。

合理的任務分配是提高異構集群作戰系統效能的關鍵[4]。集群任務分配問題可以看作是復雜多約束條件下的組合優化問題[5-6],隨著集群任務規模的增大,作戰任務分配問題的求解難度劇增[7]。因此,將大規模集群的任務分配問題進行分解,轉化為中小規模問題后再進行求解,能夠顯著提高任務分配問題的求解效率[8-9]。

大規模任務分配問題的分解[10]包括任務分組和無人機集群分組兩個環節,任務分組是無人機集群分組的前提。為了減小分組對全局任務分配的影響,通常按照任務的地理位置進行分組,將地理位置相近的任務聚類為一組,因此任務的分組問題可以采用聚類方法進行求解[11-12]。典型的聚類算法包括基于劃分的聚類[13]、基于層次的聚類[14]、基于網格的聚類[15]、基于密度的聚類[16]等。其中,K-means算法是一種應用十分廣泛的基于劃分的聚類方法,原理簡單,計算高效,但是對初始值和噪聲十分敏感,容易陷入局部最優[17-18]。文獻[19]提出一種基于相異性度量選取初始聚類中心改進的K-means聚類算法,并利用各簇中數據點的中位數代替均值,消除離群點對聚類準確率的影響。文獻[20]提出了一種基于K-medoids算法和粒子群優化算法的任務調度技術,用于最小化云計算中的任務完成時間。文獻[21]設計了一種加權密度的改進K-means聚類算法,將超密集網絡中的毫微微基站劃分為不同的簇。

異構無人機集群的分組不同于任務分組,其本質上是一類多對一的雙邊穩定匹配問題[22-23]。Gale等[24]提出了穩定匹配的概念和延遲接受(deferred-acceptance, DA)算法,用于解決“婚姻市場”中一對一的雙邊匹配問題,并證明了DA算法所得匹配結果的穩定性。文獻[25]針對終端用戶和基站的匹配問題,采用基于DA算法的多對一匹配博弈實現網絡能效的最大化。文獻[26]提出了基于改進DA算法的電動汽車-快充樁匹配策略,通過多輪次算法解決充電服務市場中的多對一匹配問題。文獻[27]以異構網絡中網絡吞吐量和用戶性能作為優化指標,提出了一種基于兩階段穩定匹配的動態頻譜分配算法。文獻[28]提出了一種基于雙層穩定匹配的異構無人機集群“分布式”協同算法,將三邊匹配問題轉化為雙層-雙邊穩定匹配問題進行求解。雙邊穩定匹配方法應用廣泛,并且具有良好的穩定性和最優性,因此可以將穩定匹配的相關方法應用于無人機集群的分組問題中。

本文中設計了一種異構無人機集群按任務進行分組的方法。整個分組的過程分為兩個環節,在任務聚類分組環節,首先利用局部密度對目標點樣本集合進行離群點檢測預處理,通過虛擬目標點替換異常點的方法提高K-means聚類精度。然后,對目標進行固定初始聚類中心的聚類分組,并進行分組均衡性的調整,任務分組完成后計算分組需求的各類無人機的數量。在無人機集群分組環節,運用穩定匹配的思想,對DA算法進行改進,首先基于最優性的考慮,通過任務傾向的偏好列表快速地將無人機映射到匹配度高的分區,然后設計兩階段的沖突消除保證匹配的穩定性和收斂性,得到無沖突的分配方案,完成無人機集群的分組調配。最后,通過仿真實驗驗證了該方法的有效性。

1 問題描述

本文主要研究復雜多任務下異構無人機集群的分組調配問題,系統模型如圖1所示。首先對任務進行聚類分組,然后將無人機集群匹配到任務分組,將目標點任務-無人機集群之間的直接任務分配轉化為組內小規模任務分配。假設二維空間的任務區域中存在NT個目標區域T={T1,T2,…,TNT},目標區域是無人機集群執行任務的區域,在分組過程中將其簡化為目標點進行處理。每個目標點有多個類型的任務,在分組過程中默認將同一目標點的多個任務分為一組,因此任務聚類分組問題可以等效為目標點聚類分組問題。異構無人機集群U={U1,U2,…,UNV}有多個類型的無人機共NV架,不同類別的無人機攜帶的載荷資源不同,因此用于執行不同的任務。按照執行任務后是否發生變化將無人機的載荷資源分為消耗型載荷和非消耗型載荷,任務需求一個或多個載荷資源。同一無人機在某時刻只能滿足任務的一個載荷資源需求。由此可知,目標點需求某類無人機的數量即為任務需求對應類型載荷資源的數量。為了避免無人機冗余,規定某類任務的載荷需求數量不小于可分配的無人機數量。將目標點聚類后的分組稱為分區。

圖1 分組調配問題系統模型Fig.1 System model of grouping deployment problem

合理的分組調配能夠有效降低任務分配問題的求解難度。以某類需求單個非消耗型載荷的任務為例,假設任務數量為m,可分配的無人機數量為n,分組數量為k,則直接任務分配的解的數量級為nm,分組調配后組內任務分配的解的數量級為(n/k)m/k,分組數量k越大,則二者的數量級相差越大。因此,分組調配可以降低任務分配問題解的數量級,從而提高其求解效率。

(1)

2 目標聚類分組

聚類算法是一種無監督學習,考慮到訓練的對象只有目標的坐標值,本文采用改進的K-means聚類方法對目標點進行分組。

2.1 基于局部密度的離群點檢測

K-means聚類對異常點比較敏感,為了使最終的聚類效果更加理想,本文首先采用離群點檢測算法對目標點樣本集進行預處理,將離群點轉化為同類型的密集點,然后再對數據集進行聚類分組。根據文獻[29-30],離群點具有較大的相對距離和較小的局部密度,因此本文中通過求取局部密度進行離群點檢測,算法的相關定義如下。

(1) 第m距離dm(j):目標Tj的第m距離,定義為距離Tj第m遠的目標點到Tj的距離,不包括Tj本身。

(2) 第m距離鄰域Nm(j):目標點Tj的第m距離鄰域,定義為以Tj為圓心,以第m距離為半徑的區域內所有目標點的集合,包括第m距離上的目標點。

(3) 第m可達距離reach_dism(i,j):目標點Ti到Tj的第m可達距離表示為

reach_dism(i,j)=max{dm(i),d(i,j)}

(2)

式中:d(i,j)為目標點Ti到Tj的歐式距離。

(4) 第m局部可達密度lrdm(j):目標點Tj的第m局部可達密度lrdm(j)表示為

(3)

即Tj的第m距離鄰域內的所有目標點的平均第m可達距離的倒數。

(5) 第m局部離群因子lofm(j):Tj的第m局部離群因子表示為

(4)

即Tj的|Nm(j)|鄰域內所有目標點的平均局部可達密度與Tj的局部可達密度的比值。這個比值越接近 1,表明Tj與其鄰域點密度相近,Tj可能和鄰域同屬一簇;這個比值越大于1,表明Tj越小于其鄰域點的密度,Tj越可能是離群點。

離群點檢測算法的基本流程如下:首先計算每個目標點的第m可達距離和第m局部可達密度。然后,通過局部可達密度得到每個目標點的第m局部離群因子,該離群因子表示目標點的離群程度,因子值越大,離群程度越高,因子值越小,離群程度越低。最后,通過設定離群因子閾值的方式輸出密集點集合Ω1和離群點集合Ω2。

2.2 目標點初始聚類分組

(5)

圖2 k=3時的初始聚類中心Fig.2 Initial cluster center when k=3

以全局中心Cmap為圓心,設定各分區的聚類中心圍繞Cmap均勻分布,編號為i的分區聚類中心的坐標值為

(6)

K-means聚類的優化目標為最小化目標點到所在分組聚類中心距離的誤差平方和(sum of squared error, SSE):

(7)

式中:p∈Si為分組Si中的目標;μi=∑p∈Sip/|Si|為分組Si的質心,稱為分組的聚類中心。初始聚類算法如算法1所示,在計算得到初始的聚類中心后,分別計算每個目標距離聚類中心的距離,將目標加入到距離最近聚類中心所在的分組。每一輪分組完成后,重新計算新的聚類中心,若更新后的聚類中心發生變化,則重新計算各分區到新質心的距離,循壞迭代訪問直到聚類中心不再更新,即完成一次K-means聚類分組。

算法 1 目標點初始K-means聚類分組算法輸入 目標點樣本集T,初始聚類分組數量k輸出 分組聚類中心集合μ,聚類分組劃分S1:按照式(5)和式(6)計算初始的k個聚類中心μ2:while flag=1 do3: flag=0;4: for ?Tj∈T5: 計算目標Tj與各聚類中心的距離列表;6: 選擇距離目標最近的聚類中心μi,將目標Tj加入μi的分組Si;7: end for8: for ?i≤k9: 計算新的聚類中心μ'i=1|Si|∑p∈Sip;10: if μ'i≠μi then11: μi=μ'i;12: flag=1;13: else14: 保持當前分組聚類中心不變;15: end if16:end for17: end while

2.3 分區均衡性調整

初始聚類得到的分區結果可能存在目標數量不均衡的問題,并且在聚類過程中使用了虛擬的密集點集合,因此需要將虛擬的目標點還原為實際的目標點,并進行分區均衡性調整。采用余量表示各分區的目標數量情況,首先根據總的目標數量和分區數量,計算余量基準值nd:

(8)

(9)

在所有分區都為近鄰的理想情況下,余量為正表明分區余量充足,可作為轉移分區加入新的目標;余量為0表明分區無法加入新的目標,但也無需向其他分區轉移目標;余量為負表明目標數量過多,須將多余的目標調整到余量充足的轉移分區。而在實際情況下,分區之間可能不存在近鄰關系,為了保證分組精度,轉移的策略也需要進行調整。分區均衡性調整的相關概念如下:

(2) 轉移代價矩陣C:C與M相對應,用于存儲目標到分區的轉移代價?？赊D移目標的轉移代價為轉移前后與分區聚類中心距離的差值,不可轉移目標的轉移代價為+∞。

算法 2 分區均衡性調整算法輸入 未進行均衡性調整的聚類分區S輸出 更新后的分區S'1: 計算轉移可行性矩陣M和分區余量;2: for ?i≤k3: ifi<0 then4: 查找分區中能夠轉移到其他分區的nMi個目標;5: if nMi≠06: for ?j≤min{nMi,|i|}7: ξ=arg minξCξm,ξ∈Si;8: m=arg minmCξm,ξ∈Si;9: Sm=Sm⊕{Tξ},Si=Si{Tξ};10: end for11: end if12: end if13: end for

K-means聚類和均衡性調整僅依靠目標點的距離關系進行分組,沒有考慮到可分配給各分區的無人機數量是否能夠滿足分區任務的最低需求,因此需要對分組結果進行可行性判斷。各分區需求的無人機數量滿足一定的區間要求,將此區間表示為[nmin,nmax],區間的上限nmax由分區中所有目標的載荷需求之和決定,區間的下限nmin是分區的最低需求。對于需求非消耗型載荷資源的任務,必須要保證載荷需求最多的任務能夠完成,因此區間的下限由分區中單個目標的載荷需求的最大值決定;而對于需求消耗型載荷資源的任務,要考慮單個無人機的最大載荷數量約束,區間的下限要保證所有任務的載荷需求都能得到滿足。因此,區間需求的最小無人機數量nmin的計算方法為

(10)

目標聚類分組將分區內的目標點信息傳遞到聚類中心,改進K-means聚類基于虛擬的密集點集合求解聚類中心,因此聚類中心更加靠近組內的大多數實際目標點,有效避免了離群點的影響。分組均衡性調整可以避免各分區的目標數量相差過大,提高分組的均衡性。通過計算比較無人機數量需求下限與實際可分配的無人機數量,保證當前分組方案的可行性。

3 無人機集群匹配分組

3.1 分區待分配無人機數量計算

在使用聚類分組算法得到目標點的分區后,需要根據分區數量,計算每個分區待分配的某類無人機的數量,各分區待分配的某類無人機的數量Mj的計算方式如下:

(11)

由于式(11)中存在取整運算符,可能導致無人機存在冗余的情況,因此需要調整個別分區的無人機需求數量,保證無人機分組后無冗余。為了提高任務執行的效率,通過計算各分區中無人機的平均負載來判斷分區對無人機的需求情況,平均負載較大的分區對無人機的需求更高,因此冗余的名額優先分配給平均負載較大的分區。若存在負載相同的情況,則計算分區的組內平均誤差,優先分配給平均誤差值較大的分區。

3.2 基于兩階段延遲接受算法的匹配分組

在得到各分區中各類無人機的待分配數量后,需要將無人機集群進行分組,映射到目標分區。每個無人機只能映射到一個分區,同一個分區需要多個無人機,因此將分組問題建模為多對一類型的穩定匹配問題。傳統的延遲接受算法在進行多對一穩定匹配時存在一定的局限性,分組的過程由“多”方依據其偏好發起,而后由“一”方根據其偏好選擇是否接受,從而得到穩定的匹配結果。在匹配過程中,“一”方只能被動地選擇部分“多”方對象,并因此錯過自身的最優解,得到的匹配結果容易陷入局部最優。本文中對延遲接受算法進行改進,提出了一種基于兩階段DA(two-phase DA, TPDA)算法的匹配分組方法。

本文中多對一穩定匹配問題的匹配度由無人機的載荷資源種類以及到各分區聚類中心的距離決定。計算各無人機到所有分區的航程代價矩陣E,并對所有分區所需的載荷資源進行匹配,目標Ti與分區Sj的匹配值的計算方法為

即若滿足載荷資源要求則將航程代價的倒數作為對應分區的匹配值,不滿足載荷要求則將匹配值設為0。在計算得到所有無人機的匹配值后,根據各分區需求無人機的數量對無人機進行匹配。按照每個分區的無人機匹配值大小生成任務傾向的偏好列表,偏好列表中只包含與其匹配值不為0的無人機,且匹配值越大的無人機匹配度越高,在偏好列表中的位置越靠前。結合各分區的載荷需求數量和任務傾向偏好列表,生成預中選方案。任務傾向偏好列表中位于各分區載荷需求范圍內的無人機稱為“預中選者”,位于各分區載荷需求范圍外的匹配值最大的無人機稱為“候補中選者”,將各分區的預中選者作為預中選方案的解。

3.3 兩階段沖突消除

預中選方案是每個分區的最優解,但不同分區的任務傾向偏好列表中可能存在相同的預中選者,導致其分配方案之間存在沖突。由于單個無人機只能分配到一個分區,因此定義一個列表match,用來存儲無人機的分配情況。沖突消除的流程圖如圖3所示。

圖3 兩階段沖突消除流程圖Fig.3 Two-phase conflict resolution flow chart

這個過程分為兩個階段進行,第一階段將沖突的預中選者替換為候補中選者,以消除當前方案中存在相同預中選者的沖突。具體策略為,若當前分區的預中選者已被分配到其他分區,則比較該無人機在當前分區以及已分配的分區中替換為候補中選者的匹配值之差,選擇使用候補中選者代價較小的方案,將對應的預中選者替換為候補中選者,并修正列表match中對應預中選者的已分配分區。由于當前分區的候補中選者可能是其他分區的預中選者,若此類候補中選者成為預中選者,則會再次出現沖突,因此需要多輪沖突消除。沖突消除的過程是將部分分區的最優解替換為次優解的過程,多輪沖突消除可能會使得部分分區資源冗余,導致其他分區的候補中選者不足,無法完成分區任務。通過設置閾值β控制沖突消除第一階段的迭代次數,若第一階段結束后不存在沖突,則接受預中選方案作為最終方案,否則仍對預中選方案延遲接受,并進行第二階段的局部調整。

沖突消除第二階段局部調整的目的是為了獲得可接受的全局可行解,首先對各分區的分配方案進行檢測,將存在沖突的分區和未分配的無人機進行回收。對于競爭同一無人機的分區,只有一個分區能夠保留原始解,其他分區需要從回收池中選擇次優解進行替換。通過計算優先級權值來判斷當前分區進行次優解替換的優先級,優先級較高的分區先進行次優解的選擇,優先級最小的分區不進行替換,保留原始解。優先級的計算方法為假設當前分區的優先級最高,計算替換前后的匹配值差值,作為計算優先級的權值。權值越小說明替換為次優解后對全局的影響越小,因此權值最小的分區優先級最高,優先進行可行解的選擇,已分配的分區和無人機從回收池中移除,不參與下一次的調整。不斷重復這個過程,直到競爭同一無人機的分區數量為1,表明沖突的分區都已替換為回收池中的可行解,各分區方案中的沖突已消除,此時接受預中選方案。

TPDA算法的初始預中選方案為各分區的最優偏好,沖突消除第一階段通過計算預中選者替換為候補中選者的代價,將部分分區的最優解替換為次優解,以消除部分沖突。第二階段為局部的調整,按照分區的優先級從回收池中選擇可行解,直到所有無人機均匹配到唯一的分區。兩個階段均按照最優性原則消除沖突,因此得到的可行解仍是全局最優性較好的匹配方案。

4 仿真驗證與分析

本文在典型的異構無人機集群協同執行多任務場景下,通過仿真實驗來驗證所提出的集群任務分組調配算法的有效性,并與其他算法進行算法性能的對比。仿真平臺為具有Intel Core i5-6300HQ 2.30 GHz處理器和8G內存的PC機。

4.1 典型場景下集群分組仿真結果

任務場景設定如下:在50 km×50 km的范圍內有20個目標區域,待執行的任務類型共3種,目標區域的參數如表1所示。首先對目標樣本進行聚類分組仿真實驗,離群點檢測的離群因子閾值設為5,分組數量k設為4,余量裕度α設為10%,截斷系數dc設為1.35。目標聚類分組前后的對比如圖4和圖5所示,分組結果如表2所示。從圖4中可以看出,聚類算法在離群因子閾值設為5時檢測出2個離群點,將離群點替換為虛擬的密集點后,得到的聚類中心更加靠近分組中的大多數目標點,使得后續匹配分組的結果準確性更高。圖5中各分區的目標點均位于其聚類中心附近,聚類中心能夠有效地代表分區中的目標點,與無人機集群進行匹配。表2中各分區的目標點數量均位于平均值附近,因此在設置的余量裕度范圍內,各分組的目標數量基本保持均衡,避免了某些分組的任務分配問題規模仍舊過大,將復雜的大規模問題分解為中小規模問題,有效地提高了任務分配問題的求解效率。在50 km×20 km的區域中隨機生成無人機集群,集群中有3種類型的無人機共60架,各類無人機的參數如表3所示。表3中,INF表示非消耗型資源。利用目標聚類分組的結果進行無人機匹配分組仿真實驗,TPDA算法的閾值β設為4,得到的TPDA匹配分組的最終結果如表4所示。以匹配結果中出現沖突的無人機數量與無人機總數的比值作為沖突率,為了方便表示,在實際沖突率的基礎上加10%作為相對沖突率,得到的預中選結果、經過第一階段沖突消除的匹配結果、匹配分組的最終結果的沖突率對比如圖6所示。

表1 目標區域參數Table 1 Target area parameters

圖4 目標聚類分組前示意圖Fig.4 Schematic diagram of target clustering before grouping

圖5 目標聚類分組后示意圖Fig.5 Schematic diagram of target clustering after grouping

表2 目標聚類分組結果Table 2 Target cluster grouping results

表3 無人機集群參數Table 3 Unmanned aerival vehicle cluster parameters

表4 無人機匹配分組結果Table 4 Unmanned aerival vehicle matching grouping results

圖6 匹配分組3個階段沖突率對比Fig.6 Comparison of conflict rates of matching groups in three stages

從仿真結果中可以看出,表4中的匹配分組結果與各分區的需求一致,編號1～60的無人機均對應唯一的分區,因此所提出的TPDA算法能夠實現滿足分區要求的無人機集群匹配分組,集群中所有無人機均得到了匹配分組,分組結果無沖突。并且,受益于目標分組階段的負載均衡性調整算法,匹配到各分區的無人機數量比較均衡,各分區待求解的任務分配問題規?；疽恢?。圖6中的預中選結果由于沒有經過沖突檢測,3種類型任務的沖突率都較高;第一階段沖突消除按照最優性原則替換部分分區的最優解,因此經過第一階段沖突消除的匹配結果能夠有效地消除部分沖突,在某些情況下甚至能夠完全消除沖突,其沖突率明顯低于預中選結果;最終結果的沖突率為0%,這說明第二階段的沖突消除能夠完全消除匹配結果中的沖突情況。這是因為第二階段局部調整的策略是按照優先級依次為仍存在沖突的少量分區從回收池中選擇可行解,已選擇的無人機從回收池中移除,從而保證匹配的唯一性,消除所有沖突。

4.2 算法性能對比分析

算例 1為了驗證所提出的目標聚類分組算法的性能,在50 km×50 km的范圍內隨機生成30個目標樣本點,首先在分組數量k固定為5的情況下進行50次分組的蒙特卡羅仿真實驗,與K-means、K-means++算法進行對比,得到的3種算法的SSE性能指標對比圖如圖7所示,分組結果的目標數量均衡性對比如圖8所示,算法的求解耗時對比如圖9所示。

圖7 SSE性能指標對比圖Fig.7 Comparison chart of SSE performance indexes

圖8 目標數量均衡性對比圖Fig.8 Comparison chart of target quantity balance

圖9 聚類算法的求解耗時對比圖Fig.9 Comparison chart of time consumption of clustering algorithms

從仿真結果中可以看出,本文中采用的聚類分組算法與另外兩種方法的求解耗時基本一致,但分組結果具有更優的SSE值和目標數量均衡性,并且算法的穩定性更高。這是因為K-means算法和K-means++算法沒有排除離群點的影響,并且初始聚類中心的選擇都具有隨機性,導致聚類結果容易陷入局部最優。而本文中的改進K-means算法在分組之前通過離群點檢測將目標點樣本中的離群點替換為密集點,同時保留了離群點的載荷信息,有效降低了離群點對聚類中心的影響。固定的初始聚類中心提高了算法的求解效率和穩定性,同時分區均衡性調整算法能夠對轉移代價較小的目標進行調整,在保證最優性的前提下使得分組的結果負載更加均衡。

算例 2為了驗證所提出的TPDA匹配分組算法的性能,利用表2中典型場景下的聚類分組結果,按照第4.1節中的參數隨機生成無人機集群,設定沖突消除第一階段的閾值β設為3,進行20次無人機集群匹配分組的仿真實驗,將TPDA的匹配分組結果與多對一的DA算法進行對比,得到的平均匹配值對比如圖10所示,算法求解耗時對比如圖11所示。從仿真結果中可以看出,TPDA算法的平均匹配值比DA算法更高,這是因為TPDA算法以所有分區的最優解為出發點,然后對替換代價較小的分區進行次優解替換,逐步消除沖突尋找可行解。而DA算法按照無人機的偏好發起匹配,分區只能被動地在發起匹配的無人機中選擇最優解,容易陷入局部最優,無法保證解的全局最優性。在閾值β設為3時,TPDA算法的求解耗時與DA算法基本一致,因此TPDA算法能夠在保證時效性的同時,提高匹配結果的全局最優性。

圖10 平均匹配值對比圖Fig.10 Comparison chart of average matching values

圖11 匹配算法求解耗時對比圖Fig.11 Comparison chart of matching algorithm solving time consumption

算例 3算例2的仿真驗證了無人機集群與聚類中心匹配的最優性,為了進一步地驗證所提出的集群分組調配方法的有效性,按照第4.1節中的參數在任務區域中隨機生成目標點和無人機集群,進行20次分組調配仿真實驗。利用式(1)中的性能指標函數對分組調配結果進行評價,調節系數λ設為0.000 5,將本文中的分組調配方法與采用K-means++聚類和DA算法匹配的方法進行對比,得到的目標函數值對比如圖12所示。圖12顯示,本文所提出的分組調配方法在20次仿真實驗中的目標函數值均高于對比方法,分組后的集群完成分組任務的代價更小。因此,改進的K-means算法和TPDA算法能夠有效地進行目標聚類分組和集群匹配分組,通過分組調配將大規模的直接任務分配轉化為組內小規模的任務分配,提高任務分配問題的求解效率。

圖12 分組調配算法目標函數值對比圖Fig.12 Comparison chart of objective function values of grouping deployment algorithm

5 結 論

本文中針對異構無人機集群按任務分組調配問題,設計了一種考慮分組均衡性的任務聚類分組方法和提高全局最優性的無人機匹配分組方法。在任務聚類分組環節,首先利用局部密度對目標點樣本集合進行離群點檢測預處理,通過虛擬目標點替換異常點的方法提高聚類精度。然后,對目標進行固定初始聚類中心的聚類分組,并進行分組均衡性的調整。在無人機集群分組環節,運用穩定匹配的思想,對延遲接受算法進行改進,首先基于最優性的考慮,通過任務傾向的偏好列表快速地將無人機映射到匹配度高的分區,然后設計了兩階段的沖突消除過程,選擇對全局最優性影響較小的可行解,保證匹配的最優性、穩定性和收斂性,得到無沖突的匹配分組方案。最后,通過仿真實驗分析并與其他方法進行對比,驗證了本文所提方法的有效性。