基于改進PSO的多UAV協(xié)同任務(wù)分配研究

韓慶田

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

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

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

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

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

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

1.1 任務(wù)分配的收益

UAV執(zhí)行任務(wù)的能力是由任務(wù)本身的價值和UAV執(zhí)行該任務(wù)的能力來決定的。UAV執(zhí)行任務(wù)能力由其攜帶的載荷(如探測裝置、武器系統(tǒng)等)和其本身性能所決定。如假設(shè)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 任務(wù)分配的代價

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

(2)

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

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

(3)

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

1.3 負載均衡值

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

(4)

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

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

1.4 任務(wù)分配效能

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

(5)

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

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

(6)

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

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

Fi=maxJi

(7)

約束條件如下：

(8)

(9)

(10)

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

3 改進離散粒子群算法

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

3.1 粒子編碼說明

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

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

表1 粒子編碼方案

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

3.2 粒子更新方式

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

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

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

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

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

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

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

3.3 沖突消解處理策略

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

圖1 任務(wù)分配方案

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

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

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

圖2 任務(wù)分組后分配方案

3.3.2任務(wù)交叉消解策略

采用交叉協(xié)商的方法進行任務(wù)的互換。如圖3所示，M6和M7分別屬于不同的目標任務(wù)，由不同的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ù)任務(wù)M11和M12向后調(diào)整，同時滿足了在M10之后的執(zhí)行的條件，因此大幅度提高了調(diào)整效率。

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

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

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

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

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

為了減少調(diào)整量，采用從前往后的順序進行調(diào)整，這樣后面時間調(diào)整對前面時間調(diào)整不會產(chǎn)生影響。如圖5所示，UAV3的任務(wù)調(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)境設(shè)置為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ù)設(shè)置為種群大小為50，最大迭代次數(shù)為100。

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

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

表2 任務(wù)分配方案

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

表3 算法仿真結(jié)果比較

圖7 適應(yīng)度值收斂曲線

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

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

圖8 任務(wù)分配方案示意圖

5 結(jié)論

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