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

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

0 引言

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

1 多機協(xié)同目標分配的數(shù)學模型

1.1 問題的提出

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

其中，Nm=NTNtype為任務總數(shù)量。

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

1.2 決策變量的設計

1.3 協(xié)同多任務分配模型

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

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

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

1)多機協(xié)同約束。

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

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

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

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

2)任務時序約束。

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

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

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

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

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

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

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

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

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

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

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

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

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

圖中:M1∈De，M2∈Pr。

3 動態(tài)重調度方法

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

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

3.1 混合細菌覓食算法

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

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

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

3.2 算法設計

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

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

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

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

3.2.2 菌群更新機制

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

3.2.3 適應度函數(shù)

根據(jù)協(xié)同多任務分配模型建立適應度函數(shù)為

3.3 PBFO算法流程

PBFO算法流程如圖3所示。

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

4 仿真實驗

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

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

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

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

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

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

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

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

按照飛行前規(guī)劃的分配方案，t=80 s時，UCAV編隊的即時狀態(tài)為:V1正在由目標T4飛往目標T5執(zhí)行偵察任務，預定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}都未被執(zhí)行。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

通過以上兩組仿真可知，改進的混合重調度策略根據(jù)任務的緊急程度判斷是否執(zhí)行重調度策略，避免了頻繁地進行任務重調度，節(jié)約了系統(tǒng)的資源，并通過混合細菌覓食算法對動態(tài)環(huán)境中的突發(fā)任務進行了合理的分配。

5 結論

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

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

［2］朱華勇，張慶杰，沈林成.提高無人作戰(zhàn)飛機協(xié)同作戰(zhàn)能力的關鍵技術［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］施展，陳慶偉.突發(fā)情況下多UAV協(xié)同任務重分配方法研究［C］//2009中國智能自動化會議論文集，2009:331-336.

［6］霍霄華，彭輝，沈林成.動態(tài)環(huán)境中多UCAV協(xié)同控制的滾動優(yōu)化［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］袁偉東，唐敦兵，王雷，等.基于遺傳算法的動態(tài)任務分配研究［J］.中國制造業(yè)信息化，2010，39(3):57-60.

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

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