基于資源約束的多無(wú)人機(jī)聯(lián)盟的任務(wù)分配

王 輝， 劉 爽

（華東理工大學(xué)機(jī)械與動(dòng)力工程學(xué)院，上海 200237）

近些年，多無(wú)人機(jī)（Multi Unmanned Aerial Vehicles, 簡(jiǎn)稱(chēng)Multi-UAV）任務(wù)分配問(wèn)題受到人們的廣泛關(guān)注，旨在將無(wú)人機(jī)分組，組成聯(lián)盟，從而更高效快捷地完成任務(wù)。資源分配是為了完成目標(biāo)任務(wù)，確定無(wú)人機(jī)擁有的資源數(shù)量。隨著控制技術(shù)、通訊技術(shù)、傳感器技術(shù)和智能調(diào)度技術(shù)的快速發(fā)展[1-3]，任務(wù)分配問(wèn)題已廣泛應(yīng)用于生產(chǎn)規(guī)劃、貨物運(yùn)輸和工作安排等，而多無(wú)人機(jī)任務(wù)分配更是廣泛應(yīng)用于軍事、農(nóng)業(yè)、服務(wù)業(yè)等領(lǐng)域。由于單個(gè)無(wú)人機(jī)資源有限，很難完成現(xiàn)實(shí)中復(fù)雜多變的任務(wù)，因此為了更有效地解決軍事上的復(fù)雜問(wèn)題，應(yīng)采用多無(wú)人機(jī)聯(lián)盟。

國(guó)內(nèi)外的學(xué)者對(duì)任務(wù)分配問(wèn)題已進(jìn)行了大量的研究。Chopra 等[4]提出了匈牙利方法的分布式來(lái)解決任務(wù)分配問(wèn)題。在多無(wú)人機(jī)應(yīng)用的情況下，所有無(wú)人機(jī)協(xié)同計(jì)算共同分配，在對(duì)等網(wǎng)絡(luò)進(jìn)行有限局部計(jì)算。Lee[5]提出了一種基于市場(chǎng)機(jī)制的拍賣(mài)算法，在執(zhí)行任務(wù)期間，無(wú)人機(jī)會(huì)不斷消耗其資源，這些資源必須在運(yùn)行期間重新填充。在該算法中，考慮了無(wú)人機(jī)的資源，從而也產(chǎn)生相應(yīng)的成本。Jiao 等[6]提出了基于拍賣(mài)的市場(chǎng)模型，有效地最大化區(qū)塊鏈網(wǎng)絡(luò)的社會(huì)福利，并為云/霧計(jì)算服務(wù)供應(yīng)商提供有效的策略。Kurd 等[7]提出了一種新的自主生物啟發(fā)方法，在執(zhí)行任務(wù)期間，利用該方法對(duì)多個(gè)無(wú)人機(jī)進(jìn)行高效分配。每個(gè)無(wú)人機(jī)根據(jù)與各個(gè)無(wú)人機(jī)運(yùn)行狀態(tài)和任務(wù)參數(shù)有關(guān)的標(biāo)準(zhǔn)動(dòng)態(tài)調(diào)整任務(wù)分配，而不參與任務(wù)的無(wú)人機(jī)之間可以進(jìn)行直接通信。Fang 等[8]提出了一種基于情緒傳染（PTA-EC）的任務(wù)分配算法，建立了人格和情感模型，將人格映射到行為并設(shè)計(jì)了情感互動(dòng)。文獻(xiàn)[9]提出了一種自組織的多機(jī)器人任務(wù)分配算法，研究了集中通信策略下的性能。這些結(jié)果表明本地策略可以在集中任務(wù)策略方面提高系統(tǒng)性能，降低總體通信吞吐量，并降低通信成本，從而擴(kuò)展了對(duì)通信效果的理解。所采用的框架是從對(duì)螞蟻、人類(lèi)和機(jī)器人社會(huì)系統(tǒng)的觀察中得出的自組織分工的通用模型。Gulpinar 等[10]提出了一種構(gòu)造啟發(fā)式算法，該算法基于估計(jì)的邊際效用，將代理和資源按順序分配給任務(wù)。基于這種啟發(fā)式算法，還提出了各種近似動(dòng)態(tài)規(guī)劃方法和一種進(jìn)化算法。Jin 等[11]提出了一種分布式協(xié)調(diào)模型，針對(duì)競(jìng)爭(zhēng)性有限的通信，以競(jìng)爭(zhēng)性方式為多個(gè)非完整機(jī)器人開(kāi)發(fā)了一種新的協(xié)調(diào)控制。在這種建議的控制方法中，只有比賽的獲勝者才會(huì)得到任務(wù)并被激活以朝著目標(biāo)前進(jìn)。

在現(xiàn)有的研究中，假定無(wú)人機(jī)具有自動(dòng)執(zhí)行任務(wù)的能力，并且任務(wù)分配框架只專(zhuān)注于最大限度地減少總成本。但在任務(wù)分配中，尚未廣泛考慮任務(wù)的難度、成功率以及任務(wù)的個(gè)數(shù)。現(xiàn)實(shí)情況是無(wú)人機(jī)沒(méi)有足夠的資源和能力來(lái)執(zhí)行每一項(xiàng)任務(wù)，任務(wù)也是多變的。在完成特定任務(wù)中，如果無(wú)人機(jī)數(shù)量不足，聯(lián)盟可能無(wú)法成功完成任務(wù)；或者該聯(lián)盟能夠完成任務(wù)，倘若再加入幾架無(wú)人機(jī)，任務(wù)的成功率和效率可能更高。

本文提出了一種基于資源的建模方法和多無(wú)人機(jī)任務(wù)分配算法，旨在為每個(gè)任務(wù)分配最佳的聯(lián)盟組合，同時(shí)考慮了任務(wù)執(zhí)行的成功率和效能。

1 問(wèn)題描述

1.1 資源模型

將Rn表示為任務(wù)所需的資源，其中n是資源索引，n=1,2,··· ；R是資源類(lèi)型。

6 種資源模型及相關(guān)參數(shù)詳見(jiàn)表1。

表1 無(wú)人機(jī)的資源Table 1 Resources of UAV

1.2 基于資源約束的無(wú)人機(jī)模型和任務(wù)約束

此外，定義資源約束任務(wù)Ti為施加的無(wú)人機(jī)聯(lián)盟C的約束，聯(lián)盟級(jí)別約束通過(guò)任務(wù)Ti反映了高級(jí)資源需求，即促進(jìn)聯(lián)盟中的多個(gè)無(wú)人機(jī)擁有分組完成任務(wù)Ti的能力。強(qiáng)調(diào)多個(gè)無(wú)人機(jī)的協(xié)作技能，例如一個(gè)無(wú)人機(jī)視覺(jué)系統(tǒng)引導(dǎo)其他多個(gè)無(wú)人機(jī)執(zhí)行攻擊任務(wù)。定義Niu為執(zhí)行任務(wù)Ti時(shí)聯(lián)盟必須擁有的資源數(shù)量，如下所示：

此外，每個(gè)聯(lián)盟可能要執(zhí)行多個(gè)任務(wù)，任務(wù)的難度有所不同，因此將任務(wù)的難度定義為DT。DT與任務(wù)所需資源、時(shí)間有關(guān)，需要的資源越多，花費(fèi)的時(shí)間越多，表示該任務(wù)難度越大，因此可以將DT定義為:

并且DT的函數(shù)表示為[10]：

2 問(wèn)題求解

2.1 算法描述

Leader-follower 聯(lián)盟算法主要是通過(guò)啟發(fā)的方式來(lái)形成多無(wú)人機(jī)聯(lián)盟，而任務(wù)分配算法（Task Allocation Algorithm，簡(jiǎn)稱(chēng)TA 算法）是通過(guò)計(jì)算的方式來(lái)實(shí)現(xiàn)多無(wú)人機(jī)的分組，計(jì)算每個(gè)分組方式執(zhí)行任務(wù)的效能值(Utility)、獎(jiǎng)勵(lì)值(Reward)、代價(jià)函數(shù)值(Cost) 和成功率STCtr，將任務(wù)分配給成功率和效能值最大的組合，從而可以更高效地完成任務(wù)。算法核心如下：

2.2 成功率

每架無(wú)人機(jī)具有相同的能力和技能，并且是同類(lèi)型的無(wú)人機(jī)，在給定的時(shí)間t內(nèi)，根據(jù)資源來(lái)定義決策變量，將資源Rn分配給無(wú)人機(jī)Ui來(lái)執(zhí)行任務(wù)T，用RTru表示該資源的數(shù)量。X是一個(gè)二維變量，表示無(wú)人機(jī)聯(lián)盟C在時(shí)間t使用資源Rn完成任務(wù)T產(chǎn)生的影響，當(dāng)任務(wù)Ti在時(shí)間t分配給無(wú)人機(jī)聯(lián)盟C時(shí)，XTCtr為1，否則為0。

因此，可以在t時(shí)刻將任務(wù)T分配給聯(lián)盟C，來(lái)定義任務(wù)執(zhí)行的成功率[12]STCtr，

2.3 代價(jià)函數(shù)

代價(jià)函數(shù)是衡量多無(wú)人機(jī)聯(lián)盟在執(zhí)行任務(wù)的過(guò)程中所產(chǎn)生不理想結(jié)果的函數(shù)。首先，在執(zhí)行任務(wù)的過(guò)程中，飛機(jī)會(huì)不斷消耗機(jī)油和彈藥，這會(huì)產(chǎn)生很大的成本；其次，飛機(jī)在飛行的過(guò)程可能會(huì)發(fā)生其他系統(tǒng)損壞，導(dǎo)致飛機(jī)墜毀；然后，任務(wù)初期，可能還有一些飛機(jī)不執(zhí)行任務(wù)，在空中懸停，這也會(huì)產(chǎn)生一定的成本，這些都會(huì)影響無(wú)人機(jī)聯(lián)盟執(zhí)行任務(wù)的成功率。因此，飛機(jī)的成本函數(shù)可以描述為[10]

式中：r表示無(wú)人機(jī)的總數(shù)；ns（T）表示在任務(wù)區(qū)域，執(zhí)行T任務(wù)的無(wú)人機(jī)數(shù)量；ncrash（T）表示執(zhí)行任務(wù)T時(shí)，發(fā)生墜毀的無(wú)人機(jī)數(shù)量；nb（T）和nf（T）表示執(zhí)行任務(wù)T時(shí)，分別消耗的彈藥和機(jī)油數(shù)量；Cloc、Ccrash、Cb和Cf分別表示無(wú)人機(jī)不執(zhí)行任務(wù)、發(fā)生墜毀、消耗彈藥和機(jī)油所產(chǎn)生的成本。

此外，在許多無(wú)人機(jī)任務(wù)分配的應(yīng)用中，為了確定無(wú)人機(jī)聯(lián)盟是否執(zhí)行任務(wù)以及任務(wù)執(zhí)行情況，增加了通信中繼的應(yīng)用程序，確保無(wú)人機(jī)之間、基地和無(wú)人機(jī)之間可以相互交流通信[12-15]。人工操作人員或基于地面的操作系統(tǒng)可以使用此程序向無(wú)人機(jī)發(fā)送命令，或收集和分析來(lái)自無(wú)人機(jī)的實(shí)時(shí)傳感器數(shù)據(jù)。例如，在配備攝像頭的無(wú)人機(jī)進(jìn)行搜索和攻擊的任務(wù)中，操作人員可能需要觀察來(lái)自每個(gè)無(wú)人機(jī)的實(shí)時(shí)視頻來(lái)確定敵方的可能位置。此外，在許多情況下每個(gè)無(wú)人機(jī)的通信范圍可能會(huì)受到限制，特別是可能小于基地和監(jiān)視區(qū)域之間的距離。因此，在這種情況下，有必要形成通信“鏈”，由空間分隔的一串無(wú)人飛行器組成，用于中繼消息在基地和任務(wù)執(zhí)行區(qū)之間來(lái)回傳遞。

為了建立通信鏈的需求，代價(jià)函數(shù)C（T，U）按以下方式修改為[10]

其中：邏輯函數(shù)m(T)取值0 或1，當(dāng)無(wú)人機(jī)之間存在通信聯(lián)系時(shí)，m(T)取1；否則取0。

2.4 獎(jiǎng)勵(lì)函數(shù)

盡管執(zhí)行任務(wù)會(huì)產(chǎn)生一定的成本，但是任務(wù)執(zhí)行成功也會(huì)獲取相應(yīng)的獎(jiǎng)勵(lì)，每成功地執(zhí)行完一個(gè)任務(wù)，無(wú)人機(jī)都會(huì)獲取相應(yīng)的獎(jiǎng)勵(lì)[10]

其中：ait表示任務(wù)分配參數(shù)，若已分配任務(wù)，則取1，否則取0；Rit表示單個(gè)無(wú)人機(jī)所獲取的獎(jiǎng)勵(lì)，Rit=1-e-au；a表示彈藥的性質(zhì)；u表示彈藥的數(shù)量。

2.5 效能函數(shù)

在執(zhí)行任務(wù)的過(guò)程中，每當(dāng)這個(gè)聯(lián)盟執(zhí)行完一個(gè)任務(wù)就更新這個(gè)效能函數(shù)值，效能函數(shù)由獎(jiǎng)勵(lì)函數(shù)（Reward）和代價(jià)函數(shù)（Cost）兩部分組成，獎(jiǎng)勵(lì)函數(shù)值減去代價(jià)函數(shù)值即為效能值，效能函數(shù)U[10-12]如下：

3 結(jié)果及分析

3.1 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證該算法的有效性，在Matlab 環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，該實(shí)驗(yàn)將3 組任務(wù)，共15 個(gè)任務(wù)分配給40 架無(wú)人機(jī)，每架無(wú)人機(jī)擁有的資源是相同的，因此，經(jīng)過(guò)計(jì)算，3 組任務(wù)的實(shí)驗(yàn)數(shù)據(jù)分別見(jiàn)表2、表3和表4。

表2 第1 組任務(wù)分配實(shí)驗(yàn)數(shù)據(jù)Table 2 The first set of experimental data on task allocation

表3 第2 組任務(wù)分配實(shí)驗(yàn)數(shù)據(jù)Table 3 The second set of experimental data on task allocation

表4 第3 組任務(wù)分配實(shí)驗(yàn)數(shù)據(jù)Table 4 The third set of experimental data on task allocation

此外，在Matlab 環(huán)境下做了仿真動(dòng)畫(huà)來(lái)進(jìn)一步驗(yàn)證該算法的有效性。動(dòng)畫(huà)中，五角星表示無(wú)人機(jī)，虛線代表飛行的路線，圓形表示無(wú)人機(jī)飛行的范圍，三角形表示任務(wù)點(diǎn)位置，三角形面積大小表示任務(wù)難度，顏色變化反映了任務(wù)的執(zhí)行進(jìn)展，分別是深紅、橙色、黃色、綠色和藍(lán)色，其中深紅表示任務(wù)還未執(zhí)行，藍(lán)色表示任務(wù)執(zhí)行完畢。另外，在動(dòng)畫(huà)的中央設(shè)定了一個(gè)飛機(jī)場(chǎng)，無(wú)人機(jī)從飛機(jī)場(chǎng)出發(fā)，如圖1（a）所示。首先，第1 組任務(wù)共有6 個(gè)任務(wù)，由于任務(wù)相對(duì)簡(jiǎn)單，故只由25 架飛機(jī)來(lái)執(zhí)行這些任務(wù)，其他飛機(jī)在飛機(jī)場(chǎng)內(nèi)待命。這6 個(gè)任務(wù)中如果有任務(wù)提前完成，該任務(wù)點(diǎn)就消失，同時(shí)飛機(jī)在原地盤(pán)旋，等待被分配第2 批任務(wù)，如圖1（b）所示。第2 組任務(wù)共有5 個(gè)任務(wù)，且難度較高，40 架飛機(jī)全部執(zhí)行任務(wù)，如圖2（a）所示，同樣的，當(dāng)某項(xiàng)任務(wù)先執(zhí)行完畢后，任務(wù)點(diǎn)就會(huì)消失，如圖2（b）所示。當(dāng)執(zhí)行完第2 批任務(wù)后，有15 架飛機(jī)發(fā)現(xiàn)油量和彈藥不足，不能繼續(xù)執(zhí)行接下來(lái)的任務(wù)，故這15 架無(wú)人機(jī)先返回飛基地，由剩余25 架無(wú)人機(jī)執(zhí)行第3 組任務(wù)，如圖3 所示。

圖1 第1 組多無(wú)人機(jī)任務(wù)分配Fig. 1 The first group of multi-UAV task allocation

圖2 第2 組多無(wú)人機(jī)任務(wù)分配Fig. 2 The second group of multi-UAV task allocation

圖3 第3 組多無(wú)人機(jī)任務(wù)分配Fig. 3 The third group of multi-UAV task allocation

3.2 實(shí)驗(yàn)對(duì)比

在利用Matlab 得到理想的效果和數(shù)據(jù)后，也不能確定所采用的TA 算法具有優(yōu)越性，于是，將該算法與遺傳算法[16-17]、匈牙利算法[4]和拍賣(mài)算法[6]進(jìn)行了對(duì)比，結(jié)果見(jiàn)表5、表6 和表7，對(duì)比分析了在這些算法的框架下，飛機(jī)執(zhí)行任務(wù)的成功率、獎(jiǎng)賞值、代價(jià)值和效能值。由于仿真實(shí)驗(yàn)的任務(wù)眾多，故只對(duì)比分析每一輪任務(wù)的第1 個(gè)任務(wù)，結(jié)果表明，通過(guò)上述數(shù)據(jù)對(duì)比分析可以得出TA 算法具有一定的優(yōu)越性，在該算法框架下，任務(wù)執(zhí)行的成功率最高且效能值最大。

表5 不同算法下第1 組第1 個(gè)任務(wù)實(shí)驗(yàn)數(shù)據(jù)對(duì)比Table 5 Comparison of experimental data of the first round of the first task under different algorithms

表6 不同算法下第2 組第1 個(gè)任務(wù)實(shí)驗(yàn)數(shù)據(jù)對(duì)比Table 6 Comparison of experimental data of the second round of the first task under different algorithms

表7 不同算法下第3 組第1 個(gè)任務(wù)實(shí)驗(yàn)數(shù)據(jù)對(duì)比Table 7 Comparison of experimental data of the third round of the first task under different algorithms

4 結(jié)束語(yǔ)

研究了基于資源的多無(wú)人機(jī)任務(wù)分配，提出了一種任務(wù)分配算法，重點(diǎn)介紹了在該算法的有效性，同時(shí)考慮了任務(wù)的成功率、獎(jiǎng)勵(lì)值、代價(jià)值和效能值，將任務(wù)分配給最佳的無(wú)人機(jī)組合，從而提升了任務(wù)分配的準(zhǔn)確性以及任務(wù)的成功率。為了驗(yàn)證該算法的有效性，在Matlab 中進(jìn)行了仿真實(shí)驗(yàn),做了仿真動(dòng)畫(huà)，并且對(duì)比了該算法與遺傳算法、匈牙利算法和拍賣(mài)算法的成功率、獎(jiǎng)賞值、代價(jià)值和效能值，證明該算法可以大大提升任務(wù)的成功率和效能值。