異構型無人機群體并行任務分配算法

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

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

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

1 問題描述

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

為了使異構UAV群體能夠在完成總體任務的基礎上，實現對數量及時間的優化，必須建立完善的群體UAV任務分配模型，以保證任務的合理分配，并且起到優化目標的作用。

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

2 并行任務分配模型

2.1 并行任務概念

能夠執行并行任務是UAV智能化的體現之一，也是模型能夠優化目標函數的關鍵。UAV執行并行任務，顧名思義，是指一個UAV可以同時執行多個子任務或者一個任務可由多個UAV同時執行。

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

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

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

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

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

2.2 假設條件

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

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

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

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

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

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

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

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

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

以時間消耗最短為目標實現對異構型群體UAV的任務分配，任務區域劃分為不同的子區域，且多個UAV可以同時執行子任務，這將會使不同的任務分配方案下總任務完成時間不同。該模型用以在以上所做各種假設下，實現對總體任務時間的優化，可以建立一個整數線性規劃(ILP)模型,參數定義如表1所示。

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

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

(1)

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

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

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

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

3 異構多UAV并行任務優化分配的遺傳算法

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

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

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

3.1.1 任務序列的編碼方案

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

表2 任務描述Table 2 Description of mission

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

3.1.2 傳感器配備的描述

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

3.1.3 模型可行解的產生

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

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

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

任務序列：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；…。

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

3.2 適應度函數的建立

上述編碼方式只滿足了模型的部分約束條件，為了將原約束問題轉化為無約束問題，可以對模型適應度函數施加一個懲罰項，便可將帶約束條件的問題轉變為無約束問題。

懲罰函數如下：

(2)

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

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

(3)

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

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

3.3 算子選取

3.3.1 交叉策略

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

圖1 交叉策略Fig.1 Crossing strategy

3.3.2 變異策略

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

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

圖2 變異策略Fig.2 Mutation strategy

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

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

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

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

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

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

Step6適應度計算。

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

4 仿真算例

4.1 仿真案例的基本描述

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

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

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

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

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

表5 異構型UAV系統的組成Table 5 Heterogeneous UAV sensor equipment

4.2 仿真結果

通過改進的遺傳算法來求解該案例時，其仿真結果如表6所示；從仿真結果可知完成總任務的時間為120 min，使用了8個UAV。

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

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

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

圖5 仿真結果對比Fig.5 Contrast of simulation results

5 結論

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