異構(gòu)型無人機(jī)群體并行任務(wù)分配算法

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

(1.空軍哈爾濱飛行學(xué)院理論訓(xùn)練系，哈爾濱 150001； 2.哈爾濱工程大學(xué)水下機(jī)器人技術(shù)重點(diǎn)實(shí)驗(yàn)室，哈爾濱 150001；3.哈爾濱工程大學(xué)自動(dòng)化學(xué)院，哈爾濱 150001)

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

1 問題描述

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

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

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

2 并行任務(wù)分配模型

2.1 并行任務(wù)概念

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

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

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

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

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

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

2.2 假設(shè)條件

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

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

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

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

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

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

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

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

2.3 時(shí)間消耗最短的任務(wù)分配模型

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

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

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

(1)

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

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

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

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

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

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

3.1 UAV群體并行任務(wù)分配的編碼

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

3.1.1 任務(wù)序列的編碼方案

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

表2 任務(wù)描述Table 2 Description of mission

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

3.1.2 傳感器配備的描述

每個(gè)UAV配備的傳感器的種類如表3所示，以二進(jìn)制表示各UAV的配備情況，1表示相應(yīng)的UAV配備有該種類型的傳感器，否則未配備相應(yīng)傳感器。

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

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

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

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

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

UAV編號(hào)：1，2，0，4；0，2，3，0；1，2，3，4；0，0，0，0；1，0，3，4；…。

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

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

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

懲罰函數(shù)如下：

(2)

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

綜合目標(biāo)函數(shù)和懲罰函數(shù)得出適應(yīng)度函數(shù)如下：

(3)

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

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

3.3 算子選取

3.3.1 交叉策略

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

圖1 交叉策略Fig.1 Crossing strategy

3.3.2 變異策略

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

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

圖2 變異策略Fig.2 Mutation strategy

并行任務(wù)分配算法步驟如下。

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

Step2對種群中所有個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)。

Step3選擇操作。對群體按照輪盤賭進(jìn)行選擇。

Step4交叉操作。對群體按照交叉算子進(jìn)行交叉操作。

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

Step6適應(yīng)度計(jì)算。

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

4 仿真算例

4.1 仿真案例的基本描述

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

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

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

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

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

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

4.2 仿真結(jié)果

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

表6 任務(wù)分配方案Table 6 Task allocation scheme

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

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

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

5 結(jié)論

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