韓慶田

(海軍航空大學，山東 煙臺 264001)

目標任務分配是指在多任務和多UAV之間進行合理規(guī)劃，充分考慮任務約束、UAV性能約束和環(huán)境約束，對UAV進行任務指派，使它們能夠以最佳的方式完成既定任務，從而提高資源的利用率，UAV形成能力互補，提高任務完成率。

在對多UAV任務分配問題的研究中，研究人員已經(jīng)提出了多種基于經(jīng)典問題的任務分配模型，主要包括多旅行商問題(Multiple Traveling Salesman Problem，MTSP)模型、車輛路由問題(Vehicle Routing Problem，VRP)模型、混合整數(shù)線性規(guī)劃(Mixed-Integer Linear Programming，MILP)、動態(tài)網(wǎng)絡流優(yōu)化(Dynamic Network Flow Optimization)模型、多處理器資源分配(Multiple Processors resources Allocation)模型等[1]。任務分配問題的研究一般分為分布式和集中式兩大類[2]?；诜植际娇刂葡到y(tǒng)結構的任務分配方法主要包括基于合同網(wǎng)(Contract Net)市場競拍機制的方法、基于粒子群優(yōu)化算法(PSO)的多UAV任務分配方法、分布式模型預測控制方法(DMPC)、基于蟻群算法的多UAV任務分配方法等。集中式算法適應于數(shù)據(jù)鏈組網(wǎng)/退網(wǎng)時間較長且UAV計算能力和智能性較差的場景，其關注算法本身對建模后的組合優(yōu)化問題的求解能力，由中心節(jié)點匯總全部信息，采用優(yōu)化算法求解協(xié)同攻擊方案后進行分配[3-4]。主要采用混合整數(shù)線性規(guī)劃方法、神經(jīng)網(wǎng)絡方法[5]、分布估計算法[6]、遺傳算法[7-8]、蟻群算法[4]、粒子群算法[9]等優(yōu)化算法進行求解。PSO也廣泛應用于解決UAV不確定環(huán)境任務分配[10-11]、協(xié)同偵察任務[12]、協(xié)同攻擊行動序列規(guī)劃[13]等問題。邢煥革等[14]運用買賣合同策略來調(diào)整PSO算法解決了異構UAV對多類型任務規(guī)劃的最優(yōu)分配，王強等[15]利用多分支樹結構特點，采用重構策略改善粒子搜索能力，但是計算較為復雜。

任務分配問題是一類組合優(yōu)化問題，其解空間隨著任務數(shù)量、UAV數(shù)目、約束等的增多而大幅度提高。學者們提出的多種求解模型和改進算法加以求解，但在求解具體環(huán)境下任務分配問題的解的質(zhì)量、計算效率等問題上各有不同。本文主要利用UAV特性和相應的任務類型，研究啟發(fā)信息的引入，以及任務之間的沖突消解問題，來改進粒子群算法，提高算法的優(yōu)化效率。

1 多UAV協(xié)同目標任務分配指標建模

為了更好地使UAV執(zhí)行各任務，以UAVUi執(zhí)行任務Tj時收益、相應代價、負載均衡值等組成評價函數(shù)作為分配時的效能指標。

1.1 任務分配的收益

UAV執(zhí)行任務的能力是由任務本身的價值和UAV執(zhí)行該任務的能力來決定的。UAV執(zhí)行任務能力由其攜帶的載荷(如探測裝置、武器系統(tǒng)等)和其本身性能所決定。如假設UAVUi執(zhí)行攻擊Tj的價值為Value(Tj)，殺傷概率為Pi(Tj)，則Ui執(zhí)行此Tj的收益為：

Rewardij=Valuei(Tj)·Pi(Tj)

(1)

式(1)中，i=1,2,…,Nu，表示第i個UAV，即UAVUi。

1.2 任務分配的代價

假設UAV飛行速度、單位距離內(nèi)的燃油消耗量都為常數(shù)，則第k階段飛行時間tf的取值與第k-1階段UAV的位置有關，則總飛行時間為：

(2)

式(2)中，Nv表示UAV的數(shù)量；Nt表示目標的數(shù)量；Nc表示任務的數(shù)量；xi, j,k表示第k階段第i個UAV是否執(zhí)行目標j的任務；1表示得到了分配,0表示未得到分配。

任務時間是UAVi完成為其分配的所有任務所消耗的時間Vti，該時間包含飛行時間tf，執(zhí)行任務時間te以及延遲時間td，則最大任務時間為：

(3)

式(3)中，Nt表示目標的數(shù)量；Nc表示任務的數(shù)量；xi, j,k表示第k階段第i個UAV是否執(zhí)行目標j的任務；1表示得到了分配,0表示未得到分配。

1.3 負載均衡值

考慮負載在各個UAV間的均衡分配對系統(tǒng)效能的影響，若某個UAV分配的任務較多，則會影響其任務的執(zhí)行。因此，定義UAVUi的負載均衡因子為：

(4)

式(4)中，ELoadi為UAVUi的最佳負載任務數(shù)目；Loadi為UAVUi的實際負載任務數(shù)。

設UAV編隊U={U1,U2,…,UNu}分別從初始位置P={P1,P2,…,PNu}出發(fā)至目標M={M1,M2,…,MNt}，執(zhí)行各任務T={T1,T2,…,TNt}。

1.4 任務分配效能

考慮任務的分配收益、消耗值及負載均衡值后，UAVUi的任務分配效能為：

(5)

式(5)中，ω1>0，ω2>0為權系數(shù)，反映了各指標的重要程度；xij用來表明是否將第i個UAV分配給第j個任務，為布爾量，xij=1表示得到了分配。

若只是考慮時間消耗值和負載均衡值，UAVUi執(zhí)行Tj時的任務分配效能定義為：

(6)

式(6)中，ω>0為常系數(shù)。

UAVUi自主任務分配問題的性能指標為：

Fi=maxJi

(7)

約束條件如下：

(8)

(9)

(10)

其中，式(8)表示第i個UAV的最大執(zhí)行能力約束，不超過任務數(shù)Taski。式(9)表示第k個階段，只能為將一項任務分配給一個UAV。式(10)表示確保所有任務都被執(zhí)行完。

3 改進離散粒子群算法

本文采用改進PSO，即基于整數(shù)矩陣編碼方式和粒子移位運算更新對問題進行求解。

3.1 粒子編碼說明

建立粒子編碼與多UAV系統(tǒng)多任務分配問題之間的映射，是將粒子群算法用于求解分配問題的重要步驟。比較實用的粒子編碼規(guī)則有：一是應使用能夠易于產(chǎn)生與所求解問題相關，且具有遞階、短定義長度模式粒子編碼方案；二是應使用能夠使得題得到自然表示或描述的具有編碼字符集的編碼方案。這些設計編碼方案的指導原則，有助于建立相應的編碼方案。

根據(jù)多UAV協(xié)同任務分配的特點，UAV在執(zhí)行任務過程中，通常要對同一目標執(zhí)行一系列的任務，包括對目標的分類、實施攻擊，以及毀傷評估等，必須使得每一項任務都有UAV來執(zhí)行，而且同一目標的任務分配應當滿足先后順序，對于特殊的目標還需要滿足優(yōu)先級約束。這樣，要求每一個粒子編碼，需要表示出可能的分配方案，既要有各個目標的各項任務及其順序約束，又要表示出執(zhí)行該項任務的UAV。將粒子表示為雙層矩陣，即2行Nc列的矩陣，第一層表示執(zhí)行任務的UAV編號；第二層表示與第一行UAV編號所對應的階段目標序列，每個目標在第二行出現(xiàn)3次，同一目標在矩陣第二行從左到右一次出現(xiàn)的次序，表示對目標執(zhí)行任務的不同，第一次出現(xiàn)表示UAV對目標執(zhí)行的是分類的任務，第二次出現(xiàn)表示UAV對目標執(zhí)行的是打擊的任務，第三次出現(xiàn)標識UAV對目標執(zhí)行毀傷評估的任務。表1為一種編碼方案。

表1 粒子編碼方案

這種編碼方法的優(yōu)點在于：保證了粒子表示的UAV任務規(guī)劃方案服從任務優(yōu)先序約束，同時滿足任務協(xié)同約束，粒子能夠較直觀表示UAV對各目標執(zhí)行的任務情況。

3.2 粒子更新方式

根據(jù)多UAV協(xié)同任務規(guī)劃問題和本文粒子編碼的實際特點，粒子的第二維數(shù)據(jù)應當需要始終滿足任務總數(shù)約束，也就是說，不同目標標號的總數(shù)應該保持不變，以保證任務的完整性。在基本粒子群算法中，速度位置更新與協(xié)同任務分配的離散域問題是存在一定差異的。因此，根據(jù)實際的問題，建立相關的粒子群算法到離散問題的映射，通過粒子追隨個體極值和全局極值的過程進行信息更新，在離散問題空間中重構粒子群算法的位置速度更新公式，設計新的粒子更新方式，這里借助移位向量完成粒子更新，具體術語與操作符定義如下[15]。

SV(shift vector)：移位向量，該向量的元素表示移位對象在粒子中的位數(shù)，移位對象按移位向量從左至右依次移位，并將末位移至首位。

SVS(shift vector set)：移位向量集，各個移位向量組成的集合。

Fs(x,y)：操作集獲取函數(shù)，該函數(shù)表示粒子x轉換至粒子y所需SVS。

?：選擇操作符，從SVS中選擇一定數(shù)量的SV，構成新的SVS′，可知SVS′?SVS。

⊕：移位操作符，按移位向量集進行移位操作。

粒子通過這種移位方式更新時，始終可以滿足約束，確保了分配方案的可行性。

3.3 沖突消解處理策略

根據(jù)初始條件，可以生成各UAV執(zhí)行任務的情況，任務分配方案如圖1所示。

圖1 任務分配方案

任務分配的初始方案存在著時間沖突，如目標4的三個任務M10、M11、M12，三個任務是存在這先后順序的，即首先進行分類，然后進行攻擊，最后進行毀傷評估，后者必須在前者完成之后才可進行，因此需要進行任務執(zhí)行的沖突消解處理。針對沖突情況，本文提出以下幾種處理策略。

3.3.1分組任務調(diào)整策略

分組任務消解，采用先調(diào)整后續(xù)任務的方法，減少調(diào)整任務開始時間，即在分類、攻擊、評估任務中，滿足先后順序的作為一組進行調(diào)整，如圖2所示，比如M8和M9屬于目標3的任務，M11和M12屬于目標4的任務，在執(zhí)行時間允許的情況下，作為一組進行調(diào)節(jié)，或者保留兩者的先后順序，這樣就可以避免增加調(diào)整的次數(shù)，提高調(diào)整策略。

圖2 任務分組后分配方案

3.3.2任務交叉消解策略

采用交叉協(xié)商的方法進行任務的互換。如圖3所示，M6和M7分別屬于不同的目標任務，由不同的UAV執(zhí)行，但是存在著時間沖突，M6需要在M4、M5之后執(zhí)行，M7需要在M8之前執(zhí)行，如果采用交叉消解的方法，互換M6和M7的位置，換位后M7在M8之前執(zhí)行完畢，M6的時間向后調(diào)整，為再次調(diào)整M5和M6的時間提高了效率，同時M7的時間長于M6，互換后原來M6的后續(xù)任務M11和M12向后調(diào)整，同時滿足了在M10之后的執(zhí)行的條件，因此大幅度提高了調(diào)整效率。

圖3 分組任務調(diào)整

3.3.3飛行時間調(diào)整策略

為了滿足任務執(zhí)行順序，需要對任務次序進行調(diào)整的同時，通過調(diào)整飛行時間達到時間調(diào)整的目的。如圖4所示，M11的開始執(zhí)行時間，應向后調(diào)整它與M10結束時間的差值，從而滿足任務先后順序要求。

圖4 飛行時間調(diào)整

3.3.4時序先后調(diào)整策略

為了減少調(diào)整量，采用從前往后的順序進行調(diào)整，這樣后面時間調(diào)整對前面時間調(diào)整不會產(chǎn)生影響。如圖5所示，UAV3的任務調(diào)整過程中，首先調(diào)整M2和M3，然后再調(diào)整M8和M9。如果順序相反，先調(diào)整M8和M9，再調(diào)整M2和M3則M8和M9的執(zhí)行時間會受到影響，降低了沖突消解的效率。

圖5 時序先后調(diào)整

4 仿真實驗

仿真環(huán)境設置為UAV的初始坐標為V1(1，1)，V2(1，5)，V3(5，1)，V4(2，3)，V5(7，8)，目標坐標為T1(6，3)，T2(3，8)，T3(7，7)，T4(7，9)。

粒子群算法參數(shù)設置為種群大小為50，最大迭代次數(shù)為100。

對目標任務分配和航跡規(guī)劃進行仿真，優(yōu)化后任務分配方案如圖6所示，目標任務分配方案見表2，算法仿真計算結果比較見表3，加入啟發(fā)信息和改進沖突消解策略前后的算法收斂情況如圖7所示

圖6 優(yōu)化后的任務分配方案

表2 任務分配方案

方案UAV1UAV2UAV3UAV4UAV5目標任務執(zhí)行順序14710112851236

表3 算法仿真結果比較

圖7 適應度值收斂曲線

仿真結果表明，方案考慮了UAV任務均衡型、航跡長度，同時考慮了飛行約束，規(guī)劃方案可行有效。通過進行沖突消解策略改進PSO算法，計算得到的總任務時間優(yōu)于PSO算法，且仿真計算用時短、效率高，表明改進PSO算法的收斂性和全局搜索能力較好。

UAV任務執(zhí)行情況如圖8所示。

圖8 任務分配方案示意圖

5 結論

針對多UAV目標任務分配問題進行研究。本文考慮UAV總飛行時間代價、最大任務時間、負載均衡值以及任務時序約束因素的情況下，建立了多UAV協(xié)同任務分配模型。將任務類型匹配信息作為啟發(fā)信息，同時提出分組任務調(diào)整、飛行時間調(diào)整、任務交叉消解、時序先后調(diào)整等沖突消解處理策略，改進粒子群算法。仿真實驗結果表明，基于啟發(fā)信息和沖突消解策略的改進PSO算法，提高了算法的收斂性和全局搜索能力，提升了任務分配和航跡規(guī)劃效率。