[發(fā)明專利]一種基于改進k-means聚類的異構(gòu)無人集群隨機環(huán)境任務分配方法和系統(tǒng)

在審

• 申請?zhí)枺?/td>: 202211213666.6
• 申請日: 2022-09-30
• 公開（公告）號: CN115509710A
• 公開（公告）日: 2022-12-23
• 發(fā)明（設計）人: 王錚;邱楊鴻;劉鈞圣;寧昕;王弘炎
• 申請（專利權(quán)）人: 西北工業(yè)大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06K9/62
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 錢宇婧

1.一種基于改進k-means聚類的異構(gòu)無人集群隨機環(huán)境任務分配方法，其特征在于，包括以下步驟：

通過K-meas聚類方法對異構(gòu)飛行器分組，獲得若干個飛行器編隊，所述飛行器編隊的數(shù)量和待執(zhí)行任務的數(shù)量相等；

建立協(xié)同任務分配的數(shù)學模型；

通過差分進化算法建立航程代價矩陣，所述航程代價矩陣中的元素為第i個飛行器編隊從出發(fā)點執(zhí)行第j個任務時需要的航程代價，建立航程代價矩陣過程中滿足環(huán)境約束模型及運動學模型，所述環(huán)境約束模型為隨機生成的山峰地圖，所述運動學模型為飛行器的質(zhì)心運動方程；

通過匈牙利算法求解航程代價矩陣中系統(tǒng)任務分配的數(shù)學模型，求解過程中以最小化的任務完成航程，所有飛行器編隊執(zhí)行任務航程最大值為優(yōu)化目標，獲得每一個飛行器編隊對應的待執(zhí)行任務。

2.根據(jù)權(quán)利要求1所述的一種基于改進k-means聚類的異構(gòu)無人集群隨機環(huán)境任務分配方法，其特征在于，通過該K-means聚類對異構(gòu)無人分組的過程包括以下步驟：

S1、確定待執(zhí)行任務的數(shù)量，設定N個集結(jié)點，將M個飛行器分為N個編隊，所述M＞N；

S2、計算所有飛行器到N個集結(jié)點的距離，找出和每個飛行器最近的集結(jié)點，將所述飛行器劃分到所述最近的集結(jié)點編隊中，記錄所有距離之和作為初始指標函數(shù)值；

S3、計算N個編隊的質(zhì)心，作為下次聚類的中心點；

S4、判斷出不能滿足具備完成所有任務能力的編隊，將懲罰值加入到初始指標函數(shù)中；

S5、隨機選擇一個未滿足所有任務能力編隊的質(zhì)心，向滿足具備完成所有任務能力編隊的質(zhì)心靠近；

S6、重復步驟S3～S5，直至迭代次數(shù)達到規(guī)定的最大次數(shù)，或者是編隊質(zhì)心不再變化且指標函數(shù)值不再變化。

3.根據(jù)權(quán)利要求2所述的一種基于改進k-means聚類的異構(gòu)無人集群隨機環(huán)境任務分配方法，其特征在于，所述指標函數(shù)為：

其中，M為飛行器數(shù)量；

N為飛行器編隊數(shù)量；

r_ij表示第i個飛行器是否屬于第j類，是為1否則為0；

C_j第j個集結(jié)點；

c_k表示懲罰值。

4.根據(jù)權(quán)利要求1所述的一種基于改進k-means聚類的異構(gòu)無人集群隨機環(huán)境任務分配方法，其特征在于，所述協(xié)同任務分配的數(shù)學模型為：

5.根據(jù)權(quán)利要求4所述的一種基于改進k-means聚類的異構(gòu)無人集群隨機環(huán)境任務分配方法，其特征在于，函數(shù)f為：

其中，w₁和w₂為權(quán)重系數(shù)，A＝{A₁,A₂,...,A_N}為待執(zhí)行任務集合，其中A_i為第i個編隊執(zhí)行的任務，A_i,j為編隊i執(zhí)行第j個目標；L_i,i＝1,2,3...N為編隊i完成所分配任務的估計航程。

6.根據(jù)權(quán)利要求1所述的一種基于改進k-means聚類的異構(gòu)無人集群隨機環(huán)境任務分配方法，其特征在于，所述航程代價矩陣的建立過程包括以下步驟：

S1、設置參數(shù)；所述參數(shù)包括編隊集結(jié)點、目標位置信息和差分進化算法中的參數(shù)；

S2、隨機生成山峰地圖并定義山峰個數(shù)；

S3、通過差分進化算法進行迭代尋優(yōu)；具體的過程為：通過隨機函數(shù)生成多個個體，每個個體有基因隨機初始值，獲得父代的種群，通過DE算法對父代的種群變異后獲得假子代的種群，通過交叉因子比較假子代的種群和父代的種群，獲得真子代的子群；比較同位置的父代的子群和真子代的子群的目標函數(shù)函數(shù)值，獲得下一代種群中的個體；

S4、記錄每次迭代過程中滿足環(huán)境約束及運動學模型約束的最優(yōu)基因序列。