[發(fā)明專利]基于改進(jìn)聚類擴(kuò)展一致性束算法的多無(wú)人機(jī)任務(wù)分配方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202011481261.1
• 申請(qǐng)日: 2020-12-15
• 公開(kāi)（公告）號(hào): CN112633654A
• 公開(kāi)（公告）日: 2021-04-09
• 發(fā)明（設(shè)計(jì)）人: 李一兵;孟憲禎;葉方;孫騫;田園
• 申請(qǐng)（專利權(quán)）人: 哈爾濱工程大學(xué)
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06;G06F30/27;G06K9/62
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.基于改進(jìn)聚類擴(kuò)展一致性束算法的多無(wú)人機(jī)任務(wù)分配方法，其特征在于：步驟如下：

步驟1：利用密度聚類算法對(duì)待分配的任務(wù)進(jìn)行聚類處理；

步驟2：根據(jù)每個(gè)簇內(nèi)任務(wù)的數(shù)量與類型，為每個(gè)簇分配相應(yīng)數(shù)量的無(wú)人機(jī)；

步驟3：初始化變量；

步驟4：對(duì)每個(gè)簇內(nèi)待分配的任務(wù)和無(wú)人機(jī)使用改進(jìn)擴(kuò)展一致性束算法，完成無(wú)人機(jī)本地任務(wù)序列構(gòu)建，具體如下：

4.1：無(wú)人機(jī)i在添加任務(wù)的過(guò)程中嘗試將任務(wù)j加入束集合b_i中，其中，束集合b_i中保存著無(wú)人機(jī)i目前競(jìng)拍所獲得的任務(wù)序號(hào)；路徑集合p_i中保存著無(wú)人機(jī)i目前準(zhǔn)備執(zhí)行的任務(wù)序號(hào)；

4.2：若插入任務(wù)j后無(wú)人機(jī)i得分變大，則將任務(wù)j加入無(wú)人機(jī)i的束集合b_i中的最后一個(gè)位置；

4.3：將任務(wù)j插入p_i中使無(wú)人機(jī)執(zhí)行任務(wù)獲得最大得分的位置；

4.4：循環(huán)步驟4.2至步驟4.3，直到無(wú)人機(jī)i達(dá)到可執(zhí)行任務(wù)的最大數(shù)量N_i；

步驟5：為了避免任務(wù)分配沖突，對(duì)同一任務(wù)投標(biāo)的無(wú)人機(jī)間依照共識(shí)規(guī)則進(jìn)行一致性協(xié)商；

步驟6：循環(huán)步驟3至步驟4，直至無(wú)人機(jī)的任務(wù)分配序列不再發(fā)生變化；

步驟7：輸出最終任務(wù)分配效果圖、時(shí)間表。

2.根據(jù)權(quán)利要求1所述的基于改進(jìn)聚類擴(kuò)展一致性束算法的多無(wú)人機(jī)任務(wù)分配方法，其特征在于：步驟4.1中無(wú)人機(jī)i在添加任務(wù)的過(guò)程中嘗試將任務(wù)j加入束集合b_i中，其中，束集合b_i中保存著無(wú)人機(jī)i目前競(jìng)拍所獲得的任務(wù)序號(hào)；路徑集合p_i中保存著無(wú)人機(jī)i目前準(zhǔn)備執(zhí)行的任務(wù)序號(hào)；對(duì)當(dāng)前路徑集合p_i中的所有位置分別插入任務(wù)j并比較插入后得分；無(wú)人機(jī)i的得分公式構(gòu)造如下：

其中，c_ij(p_i)為將任務(wù)j加入序列后無(wú)人機(jī)i執(zhí)行的總得分；為將任務(wù)j插入p_i中的第n個(gè)位置；為無(wú)人機(jī)i沿著路徑順序集合p_i執(zhí)行任務(wù)的總得分，即任務(wù)分配所獲得的總得分公式構(gòu)造如下：

其中，r_ij(p_i)和cost_ij分別為無(wú)人機(jī)i執(zhí)行任務(wù)j的收益和代價(jià)，r_ij(p_i)構(gòu)造公式如下：

其中，先執(zhí)行任務(wù)j_p再執(zhí)行j最后執(zhí)行任務(wù)j_n，且三者執(zhí)行順序相鄰；σ為距離獎(jiǎng)懲系數(shù)，由無(wú)人機(jī)當(dāng)前所執(zhí)行任務(wù)的上一段航程與下一段預(yù)計(jì)航程的比值決定，σ可以迫使無(wú)人機(jī)傾向選擇距離自身較近的任務(wù)執(zhí)行，cost_ij構(gòu)造公式如下：