王 輝， 劉 爽

（華東理工大學機械與動力工程學院，上海 200237）

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

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

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

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

1 問題描述

1.1 資源模型

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

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

表1 無人機的資源Table 1 Resources of UAV

1.2 基于資源約束的無人機模型和任務約束

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

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

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

2 問題求解

2.1 算法描述

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

2.2 成功率

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

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

2.3 代價函數(shù)

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

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

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

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

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

2.4 獎勵函數(shù)

盡管執(zhí)行任務會產(chǎn)生一定的成本，但是任務執(zhí)行成功也會獲取相應的獎勵，每成功地執(zhí)行完一個任務，無人機都會獲取相應的獎勵[10]

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

2.5 效能函數(shù)

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

3 結果及分析

3.1 實驗結果

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

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

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

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

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

圖1 第1 組多無人機任務分配Fig. 1 The first group of multi-UAV task allocation

圖2 第2 組多無人機任務分配Fig. 2 The second group of multi-UAV task allocation

圖3 第3 組多無人機任務分配Fig. 3 The third group of multi-UAV task allocation

3.2 實驗對比

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

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

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

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

4 結束語

研究了基于資源的多無人機任務分配，提出了一種任務分配算法，重點介紹了在該算法的有效性，同時考慮了任務的成功率、獎勵值、代價值和效能值，將任務分配給最佳的無人機組合，從而提升了任務分配的準確性以及任務的成功率。為了驗證該算法的有效性，在Matlab 中進行了仿真實驗,做了仿真動畫，并且對比了該算法與遺傳算法、匈牙利算法和拍賣算法的成功率、獎賞值、代價值和效能值，證明該算法可以大大提升任務的成功率和效能值。