動態環境下的多UCAV協同任務分配研究

楊尚君， 王社偉， 陶 軍， 溫 攀， 周維杰

(空軍航空大學航空控制工程系，長春 130022)

0 引言

近年來，多無人作戰飛機(Unmanned Combat Aerial Vehicle，UCAV)協同控制已經成為UCAV領域的一個研究熱點，而任務分配是多機協同控制的保障和基礎［1-3］。雖然任務開始前通過預先規劃為參戰的UCAV分配了初始任務，但在戰場環境中，由于作戰的動態性和不確定性以及協同控制的復雜性，使得任務開始后會出現許多無法預料的情況，因此，必須根據戰場態勢和編隊狀態的變化快速調整UCAV編隊的任務計劃，通過動態重調度實現 UCAV之間的任務重分配，以真正適應復雜的作戰環境。目前，已有學者應用拍賣機制［4-5］、在線滾動策略［6］、遺傳算法［7-8］等對多UCAV的任務重分配問題進行了求解，文獻［4-5］對動態環境中的突發事件利用拍賣機制進行任務重分配，但并沒有對動態環境中不同性質的事件進行分類處理;文獻［6］提出的在線滾動策略只是在任務層次上解決了動態環境中的任務分配問題，對動態環境中任務分配的方法研究不夠。因此，現有的研究雖然取得了一定的成果，但只從動態任務分配策略或者動態任務分配方法進行單方面的研究，由于動態環境的復雜性和不確定性，動態環境中的任務分配研究應該從重調度策略和重調度方法兩個方面進行研究。本文首先建立了多機協同目標分配的數學模型，提出一種改進的動態重調度策略，然后利用混合細菌覓食算法對UCAV的作戰任務進行任務重分配，對動態任務分配問題在策略和方法上進行了深入研究，并通過仿真實驗驗證了本文提出的策略和方法的有效性。

1 多機協同目標分配的數學模型

1.1 問題的提出

本文以UCAV編隊執行空對地任務為背景，戰場地形以及存在于戰場中的一系列目標位置在UCAV執行任務之前已經預先獲得。V={V1，V2，…，VNV}為執行任務的UCAV集合，NV為對應的目標集合，NT為目標數量;M={Mt1，Mt2，…，MtNtype}為各目標 Ti上需要完成的任務類型集合，Ntype為任務類型數;考慮到未來UCAV作戰使用的發展趨勢，每個目標Ti包含3類待執行任務，分別為偵察、攻擊和毀傷評估，即任務集合M={Classify，Attack，Verify}，由此可將任務集合表達為

其中，Nm=NTNtype為任務總數量。

為簡化問題，假設UCAV編隊在一個二維空間執行任務，在任意時刻 t時，UACV Vi的位置表示為((t)(t))(i∈1，2，…，NV)，目標 Ti的位置表示為()(j∈1，2，…，NT)，設 P 為 UCAV 編隊的執行路線集合，任務分配的結果就是為每架無人機分配一條任務執行路線Pi，Pi={((0)，(0)，()，…，()，((t)，(t))}，其中((0)，(0))表示UCAV Vi的出發位置，((t)，(t))表示UCAV Vi的返回位置，并且((0)，(0))=((t)(t))。

1.2 決策變量的設計

1.3 協同多任務分配模型

在多UCAV協同任務分配問題中，任務分配結果的優劣程度可以通過多種評價指標予以表達。本模型將重點考慮3個指標:任務總飛行航程指標、任務完成時間最短指標、目標價值收益最大指標。為降低模型中次要因素對問題復雜度帶來的影響，本模型假設無人機Vi執行任務時的速度恒定為si。本文的協同多任務分配模型定義為

式中:Pi=sixi，j;Lixi，j表示無人機 Vi執行任務 Mj所獲得的收益。

本文建模重點考慮以下4種約束條件。

1)多機協同約束。

多機協同約束是指UCAV編隊在執行任務時要保證任務的執行效率和UCAV執行編隊任務的方式，主要包括3個方面。

①每一個任務都只能被完成一次，表示為

②每架飛機一次只能執行一個任務，表示為

③所有的任務都應該被執行，表示為

2)任務時序約束。

任務時序約束是指同一目標的不同任務Mi和Mj之間必須按照特定順序完成，表示為

3)無人機任務類型及能力約束。

UCAV任務類型約束是指對單架UCAV，其續航能力和攜帶的任務載荷是有限的，表示為

2 一種改進的混合重調度策略

在多UCAV編隊執行任務的過程中，由于作戰的動態性和不確定性以及協同控制的復雜性，可能會出現許多無法預料的突發情況，預訂的執行方案將不能適應改變的戰場環境，因此，必須對原來的預訂方案進行改進，對現有方案的改進就屬于動態重調度問題。對于重調度問題的研究，首先應該確定重調度策略，再根據確定的策略制定重調度方法。

在動態重調度相關的研究工作中，通常采用3種類型的動態重調度策略:周期性重調度策略、事件驅動重調度策略以及混合重調度策略。由于周期性重調度和事件驅動重調度策略存在著一定的不足，因此本文選擇將兩種策略有效地結合，提出一種改進的混合型重調度策略。

目前，關于混合型重調度策略大多是將周期性重調度策略和事件驅動重調度策略簡單地疊加到一起，為了讓混合性重調度更加有效，本文設計了一種混合重調度策略。首先給出3個定義。

定義1 根據不確定事件對系統干擾的嚴重程度和緊急程度，設置重調度請求的響應方式有兩種，分別記為有序集合Pr、De;Pr表示立即型重調度，當不確定事件對系統干擾嚴重或緊急程度高時，比如無人機失效，應當進行此種重調度響應;De表示可延遲型重調度，當不確定事件對系統的干擾程度和緊急程度適中時，比如發現不影響其他任務執行的新目標，可考慮延遲重調度響應，以獲得良好的系統穩定性，并減少重調度次數。

定義2 為避免過度重復地啟動重調度策略，設置最小重調度時間為ΔTmin，如果當前調度結束后的ΔTmin時間內，除發生緊急任務，否則待執行任務延遲到下一次重調度啟動時執行。

定義3 設Lq為重調度請求表，其中按照時間順序，依次存放等待響應重調度請求。由于立即型重調度會被立即執行，所以Lq中僅存放可延遲型重調度任務。

基于以上定義，現設計混合重調度策略執行步驟如下。1)無人機執行任務開始時，啟動周期性重調度的策略。2)如果在執行任務中出現新任務Mi，對Mi進行判斷，如果Mi∈Pr，立即啟動重調度策略，此時，無論周期性重調度執行是否到達一個執行周期，都重新開始周期性重調度策略;如果Mi∈De，若上一次重調度到本次任務的時間間隔Δt＞ΔTmin，則啟動一次重調度，同時重新執行周期性重調度;若Δt＜ΔTmin，則將Mi加入Lq列表中，等待下一次重調度啟動時執行。3)當周期性重調度策略到達時間周期T時，檢查Lq列表中是否有待執行的任務，如果有待執行任務，則對列表中的任務進行任務重調度，將新任務以目標價值收益最大的原則分配給無人機。

本文設計的混合重調度策略如圖1所示。

圖1 混合重調度策略Fig.1 The mixed re-schedule strategy

圖中:M1∈De，M2∈Pr。

3 動態重調度方法

在決定了重調度策略之后，下面是選擇重調度方法。現在在重調度領域中，主要有3種方式:1)生成式重調度，即根據當前狀態重新生成調度方案;2)右移式重調度，它是對已有的調度方案進行整體的移動，以消除不確定事件的影響;3)修正式重調度，即根據干擾情況，對已有的調度方案進行針對性調整。由于戰場環境的瞬息萬變，必須選擇一種反應快且能得到相對最優的方法，修正式重調度可以滿足戰場的快速實時性要求，因此，本文選擇修正式重調度方法。

無人機編隊執行任務的動態任務重調度需要解決的問題是:當有新的任務出現時，如何對任務進行實時合理的分配，使得所獲得的目標收益最大，在上一節提出的混合優化策略的前提下，動態重分配可描述為:如何把新出現的任務分配給無人機，使得收益最大，這屬于組合優化問題，且待執行任務不多，利用群智能算法完全可以滿足實時性要求。因此，本文設計一種混合細菌覓食算法來解決動態重分配問題。

3.1 混合細菌覓食算法

基本粒子群算法(PSO)優點是算法實現簡單，收斂速度快，缺點是易早熟，陷入局部最優值。基本細菌覓食算法優點［9-10］是能夠較好地找到全局最優解，缺點是收斂速度慢。本文結合這兩種算法的優點，提出了一種混合細菌覓食優化算法(PBFO)。

細菌覓食算法共有3步操作，分別是趨向、復制和遷徙操作，對細菌覓食算法的改進描述如下:1)用粒子群來代替細菌覓食的趨向操作，趨向操作替換為粒子群尋優的迭代過程;2)將復制操作與遷徙操作合并為以適應度作為判斷條件的遷徙操作，若細菌個體適應度小于菌群的平均適應度，則對該細菌個體執行遷徙操作，即對該個體進行初始化;3)借鑒粒子群尋優思想，保留遷徙細菌個體的歷史極值，以便遷徙后的細菌個體在下一次搜索中依然朝著最優的方向尋找，保證算法的快速性;4)在每一迭代過程中保留細菌個體的歷史最優解和菌群的全局最優解。

這樣的設計既保持了粒子群的優點能夠快速收斂，又保持了細菌覓食的優點能夠找到全局最優值。

3.2 算法設計

3.2.1 任務分配問題的編碼方式

與遺傳算法類似，編碼是應用PBFO算法要解決的首要問題，鑒于多UCAV協同任務分配問題的約束性和復雜性，綜合考慮編碼方法的合法性和可行性，本文中的細菌個體使用的兩層編碼方式及其解碼過程如圖2所示。圖中，第1行表示執行任務的UCAV Vi(i∈NV)，第2行表示與第1行UCAV序列所對應的執行目標Tj(j∈NT)序列。目標出現的次序表示對應的UCAV執行的任務類型。圖中表示的兩架無人機執行3個目標任務的任務分配計劃具體如下所述。

首先無人機1對目標2實施偵察然后轉到目標3實施攻擊任務，與此同時，無人機2對目標3進行偵察然后轉到1對其實施偵察。在無人機2已對目標1執行完偵察任務之后，無人機1對其發起攻擊，此時無人機2對目標3實施評估，然后轉到目標2對其進行攻擊;待無人機1對目標1完成攻擊后，無人機1對目標2進行評估，無人機2對目標1進行評估。

圖2 菌體的編碼及解碼過程Fig.2 Bacterial encoding and decoding process

3.2.2 菌群更新機制

因為任務分配問題屬于離散優化問題，因此對菌群速度和位置更新采用類似遺傳算法的策略，交叉策略:在第2個串選取1個隨機交叉區域，替換掉第1個串中對應的位置，并對第1個串進行修復，使其滿足約束條件。變異策略:對第1行編碼進行單點變異策略。

3.2.3 適應度函數

根據協同多任務分配模型建立適應度函數為

3.3 PBFO算法流程

PBFO算法流程如圖3所示。

圖3 PBFO算法流程圖Fig.3 The flow chart of PBFO

4 仿真實驗

由于本文建立的多UCAV任務分配模型是一個多目標問題，根據決策者不同的決策要求，會有多個Pareto最優解，但如何求解多目標優化問題不是本文研究的重點內容，并且介于多個Pareto最優解代表的任務分配計劃在該問題的研究分析中具有相似性，本文在不影響研究分析的前提下簡化仿真實驗過程，將任務的價值設為常矩陣，以滿足既要盡量降低作戰風險，又要用盡量短的時間完成作戰任務為仿真實驗和分析的評價標準，即要求任務總飛行航程最短且任務完成時間最短。

假定飛行前任務控制站給UCAV編隊制定了3架UCAV對5個目標執行作戰任務的作戰計劃，需要對各個目標進行偵察、攻擊以及毀傷評估3類共計15個待執行任務，分別采用CL、AT、VE標識上述3類不同任務;出于在不影響任務分配算法驗證的前提下簡化仿真過程的目的，本仿真實驗取飛行航路為直線，其預先任務分配方案如表1所示。

表1 預訂任務分配方案Table 1 The reserved task allocation plan

UCAV編隊在進入戰區執行預定任務過程中發生了動態事件，一種是UCAV失效，另一種是發現了新的目標。PBFO算法主要參數設置如下:菌群規模N=15，趨化操作次數L=50，遷徙操作次數S=2，菌群的趨化操作采用粒子群的迭代更新策略，設置更新參數，慣性權重 ω =0.6，加速參數 c1=0.5，c2=0.7。混合重調度策略參數設置如下:周期性重調度的周期T=45 s，最小重調度時間ΔTmin=25 s。UCAV成員性能參數、任務參數見表2和表3。

表2 任務目標設置信息表Table 2 The information of the targets

表3 無人機性能參數表Table 3 The parameters of the UCAVs’performance

1)t=80 s時，UCAV V1失效。

按照混合重調度策略，當UCAV編隊開始執行任務的同時，啟動周期性重調度，到達周期性重調度的調度周期時，即t=45 s時，重調度請求表Lq為空，因此，不進行重調度，UCAV編隊按原任務分配方案繼續執行，到達t=80 s時，UCAV V1失效，由于UCAV失效屬于立即型重調度，因此立即執行任務重調度，同時重新啟動周期性重調度，在t=80 s時，任務重調度的執行過程描述如下。

按照飛行前規劃的分配方案，t=80 s時，UCAV編隊的即時狀態為:V1正在由目標T4飛往目標T5執行偵察任務，預定t=120.8 s時完成該任務，t=80 s時V1位置(310 m，220 m)，V1的剩余任務集{5-CL，3-CL，3AT}，由于 V1失效，V1的剩余任務集{5-CL，3-CL，3AT}都未被執行。

V2正在對目標T2執行偵察任務，預定t=80.6 s時完成該任務，t=80 s時V2位置(776 m，433 m)，V2的剩余任務集{2-CL，4-AT，2-VE};

V3正在等待對目標T2執行攻擊任務，預定t=80.6 s時完成該任務，t=80 s時 V3位置(776 m，433 m)，V3的剩余任務集{2-AT，1-VE，3-VE，5-AT，5-VE};

則整個UCAV編隊待執行任務集G={1-VE，2-CL，2-AT，2-VE，3-CL，3-AT，3-VE，4-VE，5-CL，5-AT，5-VE}，其當前態勢如圖 4 所示，利用PBFO算法所得到的新的任務分配方案如表4所示，計算耗時 3.1 s。

圖4 t=80 s時的態勢圖Fig.4 The situation on time t=80 s

2)t=100 s時，新增目標T6。

首先確定UCAV編隊的當前狀態，在t=80 s時，由于UCAV V2失效進行了一次任務重調度，周期性重調度從t=80 s時重新啟動，在t=100 s時，新增目標T6(884 m，752 m)，其偵察、攻擊和評估任務的價值分別為1、4、4，由于目標突然出現事件屬于可延遲型任務，因此，需要判斷重調度時間間隔與最小重調度時間ΔTmin之間的關系，由于重調度時間間隔 Δt=20 s，Δt＜ ΔTmin不滿足重調度條件，所以重調度將在下一個周期到來時刻t=125 s執行，在t=125 s重調度執行過程描述如下。

科瑪嘉顯色培養基、單核細胞增生李氏特菌、金黃色葡萄球菌等VITEK生化鑒定卡購自法國梅里埃公司。MYP顯色養基、培緩沖蛋白胨水、SC、HE、腸道增菌肉湯（2μg/ml新生霉素）、堿性蛋白胨水、TCBS、TSI|、SIM動力培養基和生化管由北京陸橋技術有限公司生產。沙門氏菌診斷血清由蘭州生物制品研究所生產，致瀉性大腸埃希氏菌標準菌株由甘肅省疾控中心微生物檢驗科提供，均在有效期內。

表4 混合重調度策略下生成的任務分配方案Table 4 The task allocation plan using mixed reschedule strategy

按照上一次重調度得到的任務分配方案，t=125 s時，UCAV編隊的即時狀態為:V2正飛向目標T2執行評估任務，預定t=147.7 s時完成該任務，此時 V2位置(565 m，516 m)，V2的剩余任務集{2-VE};

V3正在飛向目標T5執行攻擊任務，預定t=159.8 s時完成該任務，此時 V3位置(477 m，450 m)，V3的剩余任務集{5-AT，5-VE};

此時由于發現新目標T6，所以需進行任務的重新分配，整個UCAV編隊待執行任務集G={2-VE，5-AT，5-VE，6-CL，6-AT，6-VE}，其當前態勢如圖 5所示，利用PBFO算法所得到的新的任務分配方案如表5所示，計算耗時2.7 s。

圖5 t=125 s時的態勢圖Fig.5 The situation on time t=125 s

表5 混合重調度策略下生成的任務分配方案Table 5 The task allocation plan using mixed re-schedule strategy

從該實例可以看出，基于混合重調度策略的任務重調度能夠用較少的時間計算出較滿意的新任務分配方案，滿足戰場環境下的實時性要求。在仿真實驗中，如果采用周期性重調度策略，則在t=80 s時將不會對UCAV的失效情況作處理，導致其他UCAV的后續任務無法執行，整個編隊將不能按時完成任務;如果采用事件驅動重調度策略，則在t=100 s時將進行一次重調度，但由于Δt=20 s，如果進行重調度，則重調度過于頻繁，不能滿足實時性要求，因此混合重調度策略有效地避免了這種情況的發生。

通過以上兩組仿真可知，改進的混合重調度策略根據任務的緊急程度判斷是否執行重調度策略，避免了頻繁地進行任務重調度，節約了系統的資源，并通過混合細菌覓食算法對動態環境中的突發任務進行了合理的分配。

5 結論

本文建立了多UCAV任務分配模型，對動態重分配策略進行研究并做出改進，將周期性重調度和事件驅動重調度進行有機結合，提出了一種改進的混合重調度策略，增加了對突發事件的處理能力，并結合粒子群算法和細菌覓食算法的優缺點，提出了混合細菌覓食算法解決多UCAV的動態任務分配問題，通過仿真分析驗證了混合重調度策略和混合細菌覓食算法的有效性。

［1］王輝，陳紅林.一種改進的基于時間約束的無人機任務分配模型［J］.電光與控制，2010，17(2):92-94.

［2］朱華勇，張慶杰，沈林成.提高無人作戰飛機協同作戰能力的關鍵技術［J］.控制工程，2010，17(s):52-55.

［3］AN L T H,THUAN N Q.A robust approach for nonlinear UAV task assignment problem under uncertainty［J］.Lecture Notes in Computer Science,2010，6450:147-159.

［4］CHOI H J,KIM Y D.Decentralized task assignment of multiple UAVs based on the communication strategy for dynamic Environments［C］//The Proceedings of 2010 Asia-Pacific International Symposium on Aerospace Technology,2010:522-525.

［5］施展，陳慶偉.突發情況下多UAV協同任務重分配方法研究［C］//2009中國智能自動化會議論文集，2009:331-336.

［6］霍霄華，彭輝，沈林成.動態環境中多UCAV協同控制的滾動優化［J］.計算機工程，2008，34(4):22-27.

［7］TIAN Jing,SHEN Lincheng,ZHENG Yanxing.Genetic algorithm based approach for multi-UAV cooperative reconnaissance mission planning problem［J］.Computer Science,2006(4203):101-110.

［8］袁偉東，唐敦兵，王雷，等.基于遺傳算法的動態任務分配研究［J］.中國制造業信息化，2010，39(3):57-60.

［9］梁艷春，吳春國，時小虎，等.群智能優化算法理論與應用［M］.北京:科學出版社，2009:157-159.

［10］李亞楠.菌群優化算法的研究［D］.哈爾濱:哈爾濱工業大學，2009.