宋育武， 賈林通， 李 娟， 郭 浩

(1.空軍哈爾濱飛行學院理論訓練系，哈爾濱 150001； 2.哈爾濱工程大學水下機器人技術(shù)重點實驗室，哈爾濱 150001；3.哈爾濱工程大學自動化學院，哈爾濱 150001)

無人機(unmanned aerial vehicle， UAV)根據(jù)任務使命的不同，裝有等不同類型的任務載荷傳感器，可遂行偵察、攻擊等任務。隨著UAV智能水平的提高及任務的復雜性，UAV群體協(xié)同作業(yè)成為未來空戰(zhàn)領(lǐng)域的一種重要工作模式[1]。異構(gòu)型UAV群體任務分配問題就是在考慮不同任務特性與UAV自身能力的前提下，為每個UAV分配需完成任務的集合，使得協(xié)同效能達到最優(yōu)。在已有的研究中，現(xiàn)代智能優(yōu)化算法因為具有易于實現(xiàn)、計算復雜度低、性能優(yōu)越等特點，在無人系統(tǒng)的任務分配中得到廣泛應用，比較常用的方法有粒子群算法[2-3]、蟻群算法[4]、遺傳算法[5-6]、基于市場機制的拍賣算法[7]、合同網(wǎng)算法[8]等。文獻[3]針對標準量子粒子群算法對多無人機任務分配中離散狹長解空間適應性差的問題，提出了基于粒子收斂程度的自適應慣性權(quán)重與量子門變異算子，將標準量子粒子群算法進行改進。文獻[7]研究異構(gòu)無人機對不同類型目標執(zhí)行偵察、打擊和評估任務的協(xié)同任務分配問題，采用信息論中熵的變化量對偵察與評估任務中所獲取的信息量進行度量, 設(shè)計了基于相鄰局部通信的分布式拍賣算法, 實現(xiàn)了多無人機協(xié)同任務分配問題的優(yōu)化求解。文獻[8]針對傳統(tǒng)合同網(wǎng)的任務分配算法在動態(tài)環(huán)境下存在效率較低的問題，通過引入任務信任度和負載均衡度指標，對傳統(tǒng)合同網(wǎng)的任務分配方法進行改進。本文針對裝有異構(gòu)型UAV群體，建立多UAV任務分配模模型，以時間消耗最短為優(yōu)化目標，對UAV執(zhí)行區(qū)域進行子域劃分，最大限度地利用可用的UAV，建立多UAV任務分配模型及最優(yōu)化函數(shù)，對基本遺傳算法進行改進，以期有效解決了并行任務下的任務分配。

1 問題描述

異構(gòu)型UAV群體由具備不同功能的個體UAV組成。在對UAV進行任務分配時必須考慮各方面因素。首先，異構(gòu)型UAV群體在協(xié)作完成復雜使命時，個體UAV由于功能的差異及各種任務的不同，決定了不同任務可供選擇的接受者不同。其次，多功能UAV(如果有能力)在某一區(qū)域能夠同時執(zhí)行多個并行子任務，因而可以有效減少完成任務的時間。

為了使異構(gòu)UAV群體能夠在完成總體任務的基礎(chǔ)上，實現(xiàn)對數(shù)量及時間的優(yōu)化，必須建立完善的群體UAV任務分配模型，以保證任務的合理分配，并且起到優(yōu)化目標的作用。

討論的異構(gòu)型多UAV系統(tǒng)任務分配問題可描述為：使用分散在Nstart不同出發(fā)區(qū)域且裝有不同類型任務傳感器的UAV對Nareas個區(qū)域進行數(shù)據(jù)采集、目標搜索等任務，協(xié)同任務分配的目標滿足所有約束條件下，以最少數(shù)量的UAV或以最短時間實現(xiàn)對異構(gòu)型群體UAV的任務分配完成該任務。

2 并行任務分配模型

2.1 并行任務概念

能夠執(zhí)行并行任務是UAV智能化的體現(xiàn)之一，也是模型能夠優(yōu)化目標函數(shù)的關(guān)鍵。UAV執(zhí)行并行任務，顧名思義，是指一個UAV可以同時執(zhí)行多個子任務或者一個任務可由多個UAV同時執(zhí)行。

異構(gòu)型UAV系統(tǒng)由功能不同的UAV組成，各UAV之間的傳感器配置可能不盡相同，UAV個體也可能配備多種不同類型的傳感器。并行任務[9]主要是從以下兩個方面來考慮。

單個UAV執(zhí)行并行任務。主要是指在一個區(qū)域分布著需要多種傳感器的多個子任務，而某個UAV單體均配備這些類型的傳感器，倘若該區(qū)域的所有子任務均分配給該UAV，則該UAV能夠同時執(zhí)行這些子任務，并且各任務在執(zhí)行時，相互之間互不干擾。

多UAV同時執(zhí)行并行任務。是指一個區(qū)域分布著需要某種傳感器的子任務，而配備有該類型的傳感器的多個UAV能夠同時執(zhí)行該任務，完成該任務的時間會相應減少。

如某一區(qū)域的任務有兩個子任務：子任務1為需要傳感器S1完成的任務，完成時間為30 min；子任務2為需要傳感器S2完成的任務，完成時間為40 min。有兩個UAV均配備這傳感器。

在不受時間、能源限制的條件下，這兩個UAV均可以獨立完成該任務，如果由單個UAV執(zhí)行該完成任務，則可以同時執(zhí)行這兩個子任務，并且各子任務之間互不干擾，那么執(zhí)行子任務1時需要30 min，執(zhí)行子任務2需要40 min，最后完成總?cè)蝿盏目倳r間只需40 min。在使用這兩個UAV共同完成該任務時，需要將該重新劃分為兩個相同的區(qū)域，兩個UAV分別執(zhí)行其中一個區(qū)域，且同時執(zhí)行各自任務區(qū)域的任務，則總?cè)蝿罩恍枰?0 min便可完成。UAV系統(tǒng)在執(zhí)行這種并行任務時，可以減少完成每個UAV的掃描時間，從而可以起到減少總?cè)蝿諘r間的作用，但也可能使UAV的使用數(shù)量增多。

2.2 假設(shè)條件

群體UAV任務分配與任務協(xié)調(diào)問題中的相關(guān)元素可以用四元組〈V,A,S,C〉來表示，V={1,2,…,Nuav}是UAV集合，每個UAV裝配有不同的傳感器；A={a1,a2,…,ak,…,ap}是任務執(zhí)行區(qū)域集合，其中1≤k≤p，每個偵察區(qū)域ak的大小不一定相同，完成該區(qū)域的任務可能需要多種類型的傳感器，S={1,2,…,Nsensor}是傳感器集合；C是約束條件的集合，根據(jù)用戶任務的需求約束條件不相同。

為了便于討論問題，又不失一般性，在建立任務分配模型之前，作如下假設(shè)。

(1)在任務分配前，任務區(qū)已劃分完畢，而且彼此之間相鄰，從而形成了不同的子任務，接受到子任務的UAV可以準確到達該區(qū)域執(zhí)行任務。

(2)不考慮UAV從出發(fā)點到任務作業(yè)區(qū)的時間和能源消耗，而僅僅考慮在任務作業(yè)區(qū)域內(nèi)的時間。

(3)具備某一相同功能的不同UAV去完成某一子任務時，所需要的時間相同。

(4)具備某一相同功能的不同UAV可以在同一區(qū)域同時執(zhí)行任務，彼此之間互不干擾，效果同一個UAV執(zhí)行任務一樣，但完成任務時間不同。

(5)任務作業(yè)區(qū)域如果存在重疊，可以進行重新劃分。

(6)UAV不受工作時間，能源限制，且具有相同的物理尺寸和效率。

2.3 時間消耗最短的任務分配模型

以時間消耗最短為目標實現(xiàn)對異構(gòu)型群體UAV的任務分配，任務區(qū)域劃分為不同的子區(qū)域，且多個UAV可以同時執(zhí)行子任務，這將會使不同的任務分配方案下總?cè)蝿胀瓿蓵r間不同。該模型用以在以上所做各種假設(shè)下，實現(xiàn)對總體任務時間的優(yōu)化，可以建立一個整數(shù)線性規(guī)劃(ILP)模型,參數(shù)定義如表1所示。

表1 ILP模型中所使用的參數(shù)定義Table 1 Parameter definition of used in ILP model

異構(gòu)型UAV群體面向多個目標區(qū)域進行任務分配問題時，為了能夠使UAV群體能夠在最短時間內(nèi)完成總體任務，進行任務分配的問題可以表述為[10]

(1)

式(1)中：?i∈V,?j∈S,?k∈A

第一個約束條件表明：任務工作區(qū)域k需要第j種傳感器，即xsa(j,k)=1，則到該區(qū)域執(zhí)行任務的UAV可以不止一個，否則不使用UAV，這種分配方案將能夠使多UAV執(zhí)行并行任務，起到減少總?cè)蝿諘r間的作用.

第二個約束條件表明：如果任務工作區(qū)域k需要第j種傳感器，且第i個UAV到該區(qū)域執(zhí)行任務，那么該UAV必須配備該類型傳感器，否則該UAV可以不具備此種傳感器，此約束條件是對UAV傳感器的配備所做出的要求。

第三個約束條件表明：如果第i個UAV被派遣到需要某種傳感器的某個特定區(qū)域，表明該UAV已被使用；該約束條件是為了判斷UAV是否被使用。

3 異構(gòu)多UAV并行任務優(yōu)化分配的遺傳算法

遺傳算法以編碼空間代替參數(shù)空間，以適應度函數(shù)為評價依據(jù)，以編碼群體為進化基礎(chǔ)，以對群體中個體位串的遺傳操作實現(xiàn)選擇和遺傳機制，建立起一個迭代過程。在這一過程中，通過隨機重組編碼位串中重要的基因，使新一代的位串集合優(yōu)于老一代的位串集合，群體的個體不斷進化，逐漸接近最優(yōu)解，最終達到求解問題的目的。

3.1 UAV群體并行任務分配的編碼

種群中個體的編碼結(jié)構(gòu)(染色體的編碼方式)屬于知識表示范疇。遺傳算法中常用的編碼方式有二進制編碼、實數(shù)或浮點數(shù)編碼、二維染色體編碼樹結(jié)構(gòu)編碼等。

3.1.1 任務序列的編碼方案

UAV的多任務分配問題首先需要了解系統(tǒng)的任務組成，然后對總?cè)蝿者M行劃分，將劃分的子任務進行統(tǒng)一編號，如表2所示，表中列出了各區(qū)域所需要的傳感器，1代表對應區(qū)域需要相應類型的傳感器完成該任務，0表示沒有任務。任務編號如下：任務1為(S1，a1)、任務2為(S1，a2)、任務3為(S1，a3)。

表2 任務描述Table 2 Description of mission

為了計算出UAV在每個任務區(qū)域的任務時間，除了以上對所有任務進行編號外，該算法還必須對任務區(qū)的子任務進行編號。如表2所示，任務區(qū)域編號如下：mission(a1，1)為任務1，表示任務區(qū)域a1的第一個任務為任務1；mission(a1，2)為任務4，表示任務區(qū)域a1的第二個任務為任務4。

3.1.2 傳感器配備的描述

每個UAV配備的傳感器的種類如表3所示，以二進制表示各UAV的配備情況，1表示相應的UAV配備有該種類型的傳感器，否則未配備相應傳感器。

3.1.3 模型可行解的產(chǎn)生

在對模型的任務序列進行編號和每個UAV傳感器配備后，就可以確定各子任務的執(zhí)行者的集合，從而產(chǎn)生分配模型的可行解。

表3 裝備配備描述Table 3 Description of sensor equipment

任務分配時執(zhí)行各區(qū)域子任務的UAV個數(shù)可以不止一個，即單一子任務不僅須考慮執(zhí)行者的不同，還需要考慮執(zhí)行者個數(shù)的不同，采用如下兩層編碼方式。

任務序列：1，2，3，4，5，6，7，8,…。

UAV編號：1，2，0，4；0，2，3，0；1，2，3，4；0，0，0，0；1，0，3，4；…。

以上為隨機產(chǎn)生的任務分配方案，任務1可以由V1、V2、V3、V4四個UAV去完成該任務，但V3并沒有分配該任務；任務2有V2，V3兩個UAV去執(zhí)行，V1、V4并沒有分配該任務…，可以看到分配方案中任務4并沒有分配UAV完成該任務，這顯然不滿足任務分配約束條件。

3.2 適應度函數(shù)的建立

上述編碼方式只滿足了模型的部分約束條件，為了將原約束問題轉(zhuǎn)化為無約束問題，可以對模型適應度函數(shù)施加一個懲罰項，便可將帶約束條件的問題轉(zhuǎn)變?yōu)闊o約束問題。

懲罰函數(shù)如下：

(2)

式(2)中：1≤m≤maxmission。

綜合目標函數(shù)和懲罰函數(shù)得出適應度函數(shù)如下：

(3)

式(3)中：maxmission表示任務的總數(shù)；pun表示懲罰系數(shù)。

計算適應度時，可以將懲罰系數(shù)pun設(shè)置較大，由于每個染色體對應全部任務的一個分配方案，將得出每個染色體的適應度，但是如果該染色體只滿足部分約束條件而不能滿足全部的約束條件，罰函數(shù)將不為0，較大的懲罰系數(shù)pun將會使染色體的適應度變得很大，染色體的適應能力將大大降低，在分配方案擇優(yōu)時便可根據(jù)適應度剔除不滿足約束條件染色體，從而將原約束問題轉(zhuǎn)變?yōu)闊o約束問題。

3.3 算子選取

3.3.1 交叉策略

設(shè)置好染色體總數(shù)以后，將前一半染色體隨機與后一半染色體進行交叉，交叉時隨機產(chǎn)生一個位置，互換該位置到最后的基因組成，并更新原染色體，圖1給出了遺傳算法在該問題中的交叉方式。

圖1 交叉策略Fig.1 Crossing strategy

3.3.2 變異策略

為了使結(jié)果不至陷入局部最優(yōu)，必須進行染色體的變異。采用基本變異策略變異時只改變隨機產(chǎn)生的位置處的任務分配方案，發(fā)現(xiàn)結(jié)果并不能實現(xiàn)最優(yōu)。為了得到最優(yōu)解，跳出局部最優(yōu)，對變異策略進行改進。

為了減少每個UAV在每個區(qū)域的完成相應任務的時間，可以使任務區(qū)域盡可能地使用較多的UAV，從而可以起到減小UAV的時間。在變異策略設(shè)計時，隨機選擇一條染色體及一個位串，將該位串變異成所有它能變異成的基因，其變異策略示意圖如圖2所示。采用該變異策略的目的是由于任務分配目標是最短時間完成任務，對每一個任務最大限度的派遣UAV才能減小該任務的時間，從而起到減小總?cè)蝿盏臅r間的作用。

圖2 變異策略Fig.2 Mutation strategy

并行任務分配算法步驟如下。

Step1參數(shù)初始化。隨機產(chǎn)生初始種群gen(0)；確定最大遺傳代數(shù)T；置遺傳代數(shù)計數(shù)器t為0。

Step2對種群中所有個體的適應度進行評價。

Step3選擇操作。對群體按照輪盤賭進行選擇。

Step4交叉操作。對群體按照交叉算子進行交叉操作。

Step5變異操作。對群體按照變異算子進行變異操作。群體gen(t)按照選擇、交叉和變異操作后就得到了下一代的群體gen(t+1)。

Step6適應度計算。

Step7算法終止判斷。如果t≤T，則gent← gen(t+1)，轉(zhuǎn)到Step 2：如果t>T，就輸出在遺傳進化過程中適應度最大的解，算法結(jié)束。

4 仿真算例

4.1 仿真案例的基本描述

仿真案例[10]如圖3所示，為了驗證改進的遺傳算法在求解異構(gòu)型群體UAV任務分配模型的有效性，各任務區(qū)之間相互重疊，圖3中分布著6個任務區(qū)域，由于任務區(qū)域的重疊，而且各區(qū)域所需要的傳感器種類不同，會導致同一區(qū)域中重疊區(qū)域與未重疊區(qū)域所需要的UAV種類不同，因而必須對任務區(qū)域進行更具體的劃分，如圖4所示，圖4中列出了各區(qū)域劃分的結(jié)果，將原任務區(qū)域劃分成了11個新的區(qū)域。表4列出了各任務區(qū)域所需要的傳感器類型及完成該任務的時間。

圖3 仿真案例任務區(qū)域分布 Fig.3 Mission areas distribution

圖4 多區(qū)域的劃分示意Fig.4 New mission muti-areas distribution

表5列出了用于完成該任務的異構(gòu)型UAV系統(tǒng)的組成及傳感器配備情況，共有8個UAV參加任務，V1，V2均配備傳感器S1，S2；V3，V4配備傳感器S2，S3；V5，V6只配備傳感器S4；V7，V8均配備傳感器S5，S6。此例中將任務限定在400 min以內(nèi)。

表4 仿真案例的任務描述Table 4 Mission description of simulation

表5 異構(gòu)型UAV系統(tǒng)的組成Table 5 Heterogeneous UAV sensor equipment

4.2 仿真結(jié)果

通過改進的遺傳算法來求解該案例時，其仿真結(jié)果如表6所示；從仿真結(jié)果可知完成總?cè)蝿盏臅r間為120 min，使用了8個UAV。

表6 任務分配方案Table 6 Task allocation scheme

與此同時采用了基本遺傳算法來求解此案例，并與改進的遺傳算法進行了對比，結(jié)果如圖5所示。

通過以上對比結(jié)果可知，運用基本遺傳算法求解該案例時，進化到5代時就出現(xiàn)了最優(yōu)值，完成任務的時間為140 min，但采用改進的遺傳算法的求解時，進化到7代時出現(xiàn)了最優(yōu)值，但完成任務的時間也為120 min。通過對比可知改進的遺傳算法加大了進化到該最優(yōu)值的代數(shù)，卻實現(xiàn)了對時間的優(yōu)化。究其原因，UAV能夠執(zhí)行并行任務，UAV的使用時間為在各區(qū)域中使用時間之和，為此需要增多各區(qū)域中各任務的執(zhí)行者個數(shù)以減少各UAV在每個區(qū)域的使用時間。因而改進的遺傳算法能夠起到的減小進化到最優(yōu)值的代數(shù)的作用，在更為復雜的任務構(gòu)成案例中將會起到優(yōu)化目標函數(shù)的效果。

圖5 仿真結(jié)果對比Fig.5 Contrast of simulation results

5 結(jié)論

研究了異構(gòu)型UAV群體并行任務分配的問題，以時間消耗最短為優(yōu)化目標，建立個整數(shù)線性規(guī)劃的任務優(yōu)化分配模型。通過建立最優(yōu)化函數(shù)，運用改進的遺傳算法完成了異構(gòu)型群體UAV并行任務分配問題的求解，重點對編碼方案、適應度函數(shù)和變異策略進行了詳細設(shè)計。仿真結(jié)果表明該算法能夠?qū)Ξ悩?gòu)型群體UAV并行任務問題的成功求解，具有較強的尋優(yōu)能力，極大地縮短了尋優(yōu)的時間，從而提高了整體任務的執(zhí)行效率。通信拓撲的優(yōu)化，以及變動目標環(huán)境下的協(xié)同式的任務分配是今后研究的重點。