彭雅蘭，段海濱，魏 晨

1) 北京航空航天大學自動化科學與電氣工程學院仿生自主飛行系統(tǒng)研究組，北京 100083 2) 鵬城實驗室，深圳 518000

無人機（Unmanned aerial vehicle, UAV）是一種“平臺無人，系統(tǒng)有人”的無人駕駛飛行器.電子信息與人工智能技術(shù)的迅猛發(fā)展使無人機在戰(zhàn)爭中的地位日益提高.隨著作戰(zhàn)任務的多樣性、復雜性和危險性不斷增強，未來空戰(zhàn)的作戰(zhàn)方式將不再局限于單機作戰(zhàn)，而逐步向無人化、智能化和集群化發(fā)展[1].

作為無人機集群自主協(xié)同控制技術(shù)的重要內(nèi)容之一，無人機集群任務分配是指基于一定的環(huán)境態(tài)勢信息和無人機集群狀態(tài)，為每架無人機分配一個或一組有序任務，使得集群綜合效能達到最大[2].任務分配問題是一個非確定性多項式（Nondeterministic polynomially, NP）問題，其求解方法有匈牙利算法（Hungarian algorithm）、窮舉法（Enumeration method）以及人工神經(jīng)網(wǎng)絡（Artificial neural network, ANN）、遺傳算法（Genetic algorithm,GA）等基于現(xiàn)代優(yōu)化理論的研究方法[3-4].當任務分配問題中涉及的變量規(guī)模不斷增大時，過大的計算代價是NP問題的求解難點，多數(shù)時候，問題求解計算的實時性難以保障，無法滿足在線動態(tài)任務分配要求.無人機集群動態(tài)任務分配本質(zhì)上是一個多約束、強耦合的復雜多目標整數(shù)優(yōu)化問題，其決策量是離散的，且滿足約束條件的解不止一個，需要在解集中選擇出能夠滿足決策者意圖的最優(yōu)解[5].

國內(nèi)外學者針對無人機集群任務分配展開了諸多研究.針對無人機集群協(xié)同搜索任務分配問題，王瑞和肖冰松[6]提出了一種基于改進鴿群優(yōu)化和馬爾科夫鏈的方法，通過建立蜂窩狀環(huán)境模型，降低對搜索區(qū)域的重復搜索，從而提高了無人機集群任務分配效率；Luo等[7]考慮無人機的有限執(zhí)行能力和任務資源需求，以全局收益最大化為目標，提出了一種基于拍賣機制的任務分配算法來得到無人機的無沖突任務序列；為研究資源分配對子任務的影響，Zhang等[8]提出了一種基于多目標粒子群優(yōu)化算法，通過構(gòu)建多目標分配模型來優(yōu)化任務資源分配；Yavuz等[9]提出了一種適用于大規(guī)模無人機集群任務分配問題的算法，根據(jù)位置信息將無人機集群進行聚類處理后再利用匈牙利算法進行任務分配，并利用蟻群算法為每個任務子集規(guī)劃最優(yōu)路線；針對多目標監(jiān)視任務，Li等[10]提出了一種基于惰性貪婪樣本的無人機集群任務分配算法，對非單調(diào)目標函數(shù)進行求解，并通過調(diào)整采樣頻率來優(yōu)化任務分配效率.

交替方向法（Alternating direction method of multipliers, ADMM）是一種典型利用“分而治之”思想的算法[11].近年來由于在統(tǒng)計學習、語音識別與圖像處理等領(lǐng)域中，對大規(guī)模非光滑系數(shù)優(yōu)化問題求解的迫切需求，交替方向法得到了大量關(guān)注和研究[12].交替方向法采用分解-協(xié)調(diào)過程，分步協(xié)調(diào)各個子問題的解決方案，以尋求全局最優(yōu)，在凸函數(shù)優(yōu)化問題上顯現(xiàn)出良好的求解效果.針對單個無人機任務策略生成問題，考慮無人機多類屬性與任務需求多元素制約，利用交替方向法將單無人機任務收益函數(shù)中的多個變量進行拆分求解.

無人機集群協(xié)同任務分配問題中涉及多個智能體之間的沖突與合作，為解決這一問題，網(wǎng)絡進化博弈在問題建模和算法設計方面都有較好優(yōu)勢[13].將每架無人機定義為一個博弈參與者，利用網(wǎng)絡進化博弈的納什均衡策略，通過參與者與鄰居間的信息交互進行自身行動策略調(diào)整，最終達到全局最優(yōu)策略.

本文設計了一種基于交替方向網(wǎng)絡進化博弈的無人機集群任務分配算法，融合交替方向法與網(wǎng)絡進化博弈算法的優(yōu)勢，將無人機集群任務分配過程拆分為局部收益優(yōu)化與全局收益優(yōu)化兩部分.首先，考慮無人機自身能力特性與任務資源需求異質(zhì)性，求解單無人機局部最優(yōu)收益任務分配策略.最后，利用網(wǎng)絡進化博弈模型，考慮任務執(zhí)行過程中機間協(xié)作與沖突，通過每個博弈參與者與鄰域內(nèi)無人機個體進行實時信息交互，從而得到全局最優(yōu)任務收益分配策略.

1 系統(tǒng)建模

1.1 無人機集群任務分配模型

無人機集群任務分配問題可描述為：求得一個N架無人機協(xié)同執(zhí)行M項任務的無沖突全覆蓋任務分配方案，以最大限度提高無人機集群完成所有任務的全局收益與執(zhí)行效率.全局收益函數(shù)為局部收益函數(shù)之和，任務執(zhí)行成本是每個局部收益函數(shù)的重要因素.

1.1.1 代價函數(shù)設計

假設無人機集群U={ui|i∈ (1,2,···，N)}協(xié)同執(zhí)行任務集合，其中N為總無人機數(shù)量，M為總?cè)蝿諗?shù)量[14].對于無人機i，其可單獨執(zhí)行的任務集合為，si為的子集，無人機i可執(zhí)行的備選任務組合為式中ni為所有子集總數(shù).為簡化分析，假設每架無人機可執(zhí)行任務組合都存在一個非空可執(zhí)行任務子集.對于無人機集群協(xié)同任務分配問題，假設當且僅當兩架無人機共同執(zhí)行同一任務時，兩架無人機之間存在通信鏈路并進行信息交互，與無人機i有信息交互的所有無人機組成無人機i的鄰居集合Ψi，表示為：

由于無人機能力特性與每項任務執(zhí)行資源需求不同，所以各架無人機執(zhí)行不同任務時的執(zhí)行成本也有差異.為有效完成某一項任務，無人機需要向任務點位置移動，且無人機需要具備完成該任務的載荷資源，因此，考慮任務執(zhí)行成本由負載成本與航路成本組成.任務所需執(zhí)行時間越長，無人機需要攜帶的燃料就越多，即負載成本隨實際執(zhí)行時間單調(diào)增加，無人機i執(zhí)行任務組合si的負載成本LCi(si)具體計算公式為[15]：

其中，α1與γ1為負載成本系數(shù)，β為負載成本衰減因子，Rk為任務k的資源需求量，LDi為無人機i的載荷能力，tsj為任務j開始執(zhí)行時間，etj(si)為任務j實際開始執(zhí)行時間，具體計算公式為：

航路成本PCi(si)計算公式為[16]：

其中，α2為航路成本系數(shù)，MFLi為無人機i的最長飛行航路，TPLi為無人機i的總飛行航路長度，其具體計算公式為：

無人機i對任務組合si的任務執(zhí)行成本為上述負載成本與航路成本之和，即：

在此無人機ui對任務組合si的任務執(zhí)行成本函數(shù)基礎上，給出了全局任務執(zhí)行成本函數(shù)[17]：

1.1.2 任務分配模型

無人機集群任務分配目標就是找到全局任務執(zhí)行成本最小的無沖突、全覆蓋任務分配方案，可將該問題描述為不等式約束下的最小化問題.受現(xiàn)有模型啟發(fā)[18-20]，無人機集群任務分配模型可以定義為：

每架無人機需要具備能夠順利完成已分配任務序列的載荷資源，即任務資源需求約束；在攜帶資源有限的條件下，每架無人機任務航路總長度不得大于其最大飛行距離，且需要平衡每架無人機剩余飛行長度距離，以確保整個無人機集群執(zhí)行能力的持久性；每項任務的實際開始執(zhí)行時間需滿足其執(zhí)行開始時間窗約束.

1.2 網(wǎng)絡進化博弈模型

針對無人機集群任務分配問題，構(gòu)建網(wǎng)絡進化博弈模型G={U,{Si},{Ai}}，將每架無人機ui∈U定義為博弈參與者，對于無人機ui，其可執(zhí)行任務序列si∈Si作為其行動策略[21].為實現(xiàn)集群整體任務效用Ai最大化，每個博弈參與者都會根據(jù)自身鄰域Ψi中鄰居策略與收益，在行動策略集中不斷迭代更新自身策略.

對于可行任務組合si∈Si與未被分配任務集合為T0(s)，證明F(T)的最優(yōu)解與最優(yōu)任務分配方案之間的等效性：

定理1對與?j∈M，公式（8）的最優(yōu)解始終是無人機集群最優(yōu)任務分配解.

證明：假設s*是公式（8）的一個最優(yōu)解，但不是無人機集群最優(yōu)任務分配解，則必定存在一個子任務tk沒有被分配給任何一架無人機.由此，可得到一個將任務tk分配給無人機ui的新任務分配解≠s*，.根據(jù)公式（6）和公式（7），可得：

當s*不是最優(yōu)任務分配解時，不可能是公式（8）的最優(yōu)解，即如果s*是公式（8）的最優(yōu)解，則必然是無人機集群最優(yōu)任務分配解.

定義1 納什均衡[22]：對于有限策略集博弈模型G={U,{Si},{Ai}}，當任何一個參與者在某策略組合下單方面改變自身策略（其他參與者策略不變）都不能提高自身效用時，此策略組合成為納什均衡.

定義2 勢博弈[22]：對于有限策略集博弈模型G={U,{Si},{Ai}}，如果存在一個勢函數(shù)ξ滿足下式，則該博弈模型可成為勢博弈.

利用勢博弈模型，勢函數(shù)的最優(yōu)解即為博弈模型的納什均衡解，無人機集群分布式任務分配問題可以轉(zhuǎn)化為求解網(wǎng)絡進化博弈納什均衡解，得到最優(yōu)任務分配策略.

2 基于網(wǎng)絡進化博弈與交替方向法的分布式任務分配算法

2.1 交替方向法

交替方向法是一種適用于解決分布式凸函數(shù)優(yōu)化問題的簡單且強大的算法，求解過程中對變量進行交替迭代處理[23].交替方向法可有效解決如下形式優(yōu)化問題：

其中，h和C是凸函數(shù).該優(yōu)化問題可寫為另一種形式：

其中，g是C的指標函數(shù)，z是單獨變量，u是原始變量.

增廣拉格朗日函數(shù)定義為[24]：

其中，ρ為懲罰參數(shù)，a為縮放后的對偶參數(shù).交替方向法通過以下三個步驟將全局優(yōu)化問題分解為兩個可分離變量的子問題，并分別對u和z進行最小化處理：

除此之外，交替方向法還可以擴展到具有多個可分離變量、非凸函數(shù)優(yōu)化問題或者具有不等式約束的優(yōu)化問題[12].

考慮無人機集群任務分配優(yōu)化問題，針對1.1.2節(jié)中提出的無人機集群任務分配模型（如公式（8）所示），對于無人機ui，當fi(si)取最小值時，無人機個體i達到自身策略最優(yōu)點.

利用交替方向法求解公式（8）中的目標函數(shù)，引入?yún)f(xié)調(diào)變量φ，其增廣拉格朗日函數(shù)定義為：

其中，λ為對偶因子（拉格朗日乘子），ρ＞0是懲罰參數(shù)，為協(xié)調(diào)變量在當前循環(huán)中的實際計算值，將si作為函數(shù)變量，對fi(si)進行優(yōu)化求解，從而求得最小任務執(zhí)行成本fi(si).交替方向法具體實施步驟如下.

Step 1輸入原始數(shù)據(jù)及參數(shù)，包括無人機的最大飛行長度、巡航速度、負載能力，任務的位置、執(zhí)行時間、開始執(zhí)行時間窗和負載需求，拉格朗日乘子、懲罰因子等；

Step 2無人機i根據(jù)自身性能和任務屬性挑選有能力執(zhí)行的任務，生成初始可行任務組合，并根據(jù)公式（6）計算相應的任務執(zhí)行代價，得到協(xié)調(diào)變量φ；

Step 3通過優(yōu)化更新協(xié)調(diào)變量φ，φ[l]為第l次迭代計算待更新的協(xié)調(diào)變量，并據(jù)此得到更新后的拉格朗日乘子λ：

Step 4若第l次迭代結(jié)果滿足下列約束條件，則認為此時得到無人機i的最優(yōu)任務組合si_best，算法停止運行并輸出結(jié)果，否則，進入下一次迭代計算，跳轉(zhuǎn)至Step2.

其中，σpri與 σdual分別為原始殘差和對偶殘差.

2.2 無人機集群交替方向網(wǎng)絡進化博弈任務分配實現(xiàn)流程

根據(jù)2.1節(jié)中給出的交替方向法，求得每架無人機ui的最優(yōu)任務組合si_best，在整個無人機集群中，存在個體間交互與執(zhí)行任務耦合，借助1.2節(jié)中給出的網(wǎng)絡進化博弈模型，平衡各架無人機之間的任務沖突，實現(xiàn)全局任務收益最大化.基于交替方向網(wǎng)絡進化博弈的無人機集群任務分配算法流程如圖1所示.

圖1 基于交替方向法網(wǎng)絡進化博弈的無人機集群任務分配算法流程圖Fig.1 Flowchart of the unmanned aerial vehicle swarm task allocation algorithm, based on the alternating direction method of multipliers (ADMM)network potential game theory

對于第p輪迭代中無人機i的任務組合，記為第p輪循環(huán)中所有無人機的任務組合記為假設對于任務集合T，通過廣播機制，向所有無人機發(fā)送完整任務集信息，根據(jù)完整的任務集，每架無人機都可得到自己可單獨執(zhí)行的任務組合Sif.在算法初始化階段，設置所有無人機屬性與任務屬性，隨機在Sif中選擇si1和Si1.完成初始化后，執(zhí)行交替方向法所有算法步驟，得到每架無人機局部收益最大的任務組合，作為下一步算法初始輸入量，再逐步實施算法中剩余步驟.每輪迭代中，無人機i僅與自己鄰域內(nèi)鄰居交換信息，由此可給出博弈當前收益Aip、最佳響應Bip和后悔值Rip的計算[24]：

3 仿真實驗分析

為驗證本文所提出的無人機集群分布式任務分配算法的有效性，以4架無人機協(xié)同執(zhí)行20個目標點的打擊任務為例進行仿真驗證，并與文獻[25]中基于一致性拍賣包算法（Consensus-based bundle algorithm, CBBA）進行仿真實驗對比.對每組仿真實驗獨立運行150次，給出平均數(shù)值統(tǒng)計結(jié)果，并采用基于Unity3D平臺開發(fā)的無人機集群三維態(tài)勢視景仿真綜合驗證平臺對該無人機集群任務分配方法進行演示驗證.

在800 m×800 m×800 m三維空間內(nèi)，4架無人機對隨機分布的20個目標點執(zhí)行打擊任務.無人機最大飛行航路MFLi為2000 m，巡航速度V=20 m·s-1，單個任務所需執(zhí)行時間隨機設定為3 s或5 s，對應載荷需求隨機設定為2或3，單個任務收益隨機設定為5或8，交替方向法中原始殘差σpri與 對偶殘差σdual均設定為0.01.理想條件下，無人機i可與鄰域范圍Ψi內(nèi)所有鄰居個體進行信息交互.

任務完成效能指標選取總?cè)蝿帐找?、任務完成時間、資源消耗和無人機總飛行航路長度.其中，總?cè)蝿帐找鏋樗袩o人機局部收益總和，任務完成時間為無人機集群完成所有任務所需總時長，資源消耗則為完成所有任務所需飛行資源與載荷資源之和，無人機總飛行航路長度為所有無人機任務航路長度總和.

無人機集群在仿真的初始時刻、150、200和300 s的任務分配仿真結(jié)果如圖2所示，圖中紅色星號代表任務目標點的當前位置，當某個目標點被成功打擊后，將不再顯示.由圖2可知，在仿真實驗最后時刻，無人機集群完成了對所有目標的打擊任務.在單個無人機效用函數(shù)優(yōu)化階段，交替方向法中原始殘差與對偶殘差隨迭代次數(shù)的變化曲線如圖3所示.在98次迭代時原始殘差與對偶殘差均收斂至達到最大容錯度，所得結(jié)果滿足任務分配模型中的所有不等式約束條件且能夠穩(wěn)定收斂于最優(yōu)解.

圖2 任務分配結(jié)果.(a) 初始時刻; (b) 150 s; (c) 200 s; (d) 300 sFig.2 Task allocation results: (a) initial moment; (b) 150 s; (c) 200 s; (d) 300 s

圖3 ADMM的殘差收斂曲線Fig.3 Residual convergence curve of the ADMM

如表1所示，本文所提出的基于交替方向網(wǎng)絡進化博弈無人機集群分布式任務分配算法(Distributed tasks allocation algorithm, DTAA)在四項指標中均不同程度優(yōu)于基于一致性的拍賣包算法.在總?cè)蝿帐找娣矫?，分布式任務分配算法較基于一致性的拍賣包算法增長了20.99%；在無人機集群完成所有任務總時間方面，分布式任務分配算法降低了16.50%；資源消耗方面，分布式任務分配算法降低了12.94%；航路總長度方面，分布式任務分配算法降低了12.69%.

表1 本文所提分布式任務分配算法與拍賣算法性能指標Table 1 Performance metrics of the distributed tasks allocation algorithm and CBBA algorithm

無人機集群在兩種算法下任務完成度與任務完成個數(shù)隨時間的變化趨勢如圖4和圖5所示.

圖4 任務完成度隨時間變化Fig.4 Changes of the degree of completion of tasks over time

圖5 任務完成個數(shù)隨時間變化Fig.5 Changes of the number of completed tasks over time

在任務開始階段，分布式任務分配算法較基于一致性的拍賣包算法效率優(yōu)勢還不明顯，隨著任務執(zhí)行時間的增加，由于設計代價函數(shù)時考慮任務點位置與資源消耗等因素，分布式任務分配算法在任務執(zhí)行中后期仍然能夠保證快速針對任務特征分配到具有執(zhí)行能力的適合執(zhí)行者.

無人機集群任務分配三維態(tài)勢視景仿真綜合實時推演驗證結(jié)果如圖6所示.

圖6 三維視景場景演示.(a) 任務分配場景1; (b) 任務分配場景2Fig.6 3D visual simulation platform snapshots: (a) task allocation scenario 1; (b) task allocation Scenario 2

圖6中紅色曲線表示無人機飛行軌跡，無人機先后飛抵所有任務目標點并無沖突、全覆蓋執(zhí)行完畢.基于此三維態(tài)勢視景仿真綜合驗證平臺，可實現(xiàn)無人機集群任務規(guī)劃與執(zhí)行情況的動態(tài)展示，使決策者便于觀察任務執(zhí)行過程，實時掌握集群整體態(tài)勢.

4 結(jié)論

本文針對無人機集群任務分配問題中各類資源約束的異質(zhì)性和無人機執(zhí)行能力因素，將任務分配問題公式化描述為不等式約束下求解最小值問題.利用交替方向法求解單架無人機局部收益最大化任務組合，在網(wǎng)絡進化博弈算法中，將每架無人機局部收益最大化任務組合作為初始任務分配方案，每架無人機作為博弈參與者與鄰域內(nèi)無人機個體交換任務策略與收益信息，將全局任務收益最大化作為求解目標進行二次優(yōu)化.基于本文所建立的無人機集群任務分配網(wǎng)絡進化博弈模型，分析了無人機集群最優(yōu)任務分配策略與網(wǎng)絡進化博弈的納什均衡解的等效性.

通過仿真實驗，驗證了本文所提出的基于交替方向網(wǎng)絡進化博弈的無人機集群任務分配算法可在有限迭代步驟內(nèi)穩(wěn)定收斂至最優(yōu)解，且能夠無沖突的分配所有任務目標點.與傳統(tǒng)方法比較，在總?cè)蝿帐找妗⑿?、資源消耗和航路總長度方面均有較強優(yōu)勢.最后，通過無人機集群三維態(tài)勢視景仿真綜合驗證平臺，以實時推演形式給出了無人機集群任務規(guī)劃與執(zhí)行的動態(tài)仿真過程.