多無人機協同任務分配混合粒子群算法

張瑞鵬，馮彥翔，楊宜康

西安交通大學 自動化科學與工程學院，西安 710049

無人機系統具有隱身性能好、自主能力強、可重復回收利用的特點，在目標偵察、目標打擊、毀傷評估等軍用領域和環境監測、災害救援、區域物流等民用領域均發揮著重要的作用[1]。在實際應用中為了解決單一無人機執行復雜任務時的不足，更多的采用多無人機協同方案，把單一無人機作為獨立任務處理單元，在執行任務時多個無人機利用設備或功能進行信息整合，實現高效統一的執行步驟，并利用相關設備完成不同的任務[2]。因此多無人機協同控制成為了一項重要的研究內容，而多無人機協同任務分配問題(Multi-UAV Task Allocation Problem, MTAP)，已成為無人集群協同自主導航領域需要解決的關鍵問題[3]。

多無人機任務分配是指在一定的決策時間內，分配異構無人機對給定的目標執行多個任務，形成協調配合，使系統綜合成本最小化，以達到最優效率[4]。在進行多無人機任務分配時，受多種約束條件的影響，如任務能力約束、任務時序約束、路徑安全性約束和規劃實時約束等。需要綜合協調任務優先級、時間約束、可飛行軌跡等，因此多無人機任務分配問題本質上是一個非確定性多項式(Non-deterministic Polynomial-hard, NP-hard)問題[5]。與此同時，待求解問題的規模(如：無人機數目、目標和任務的數量)也會影響求解過程的復雜性。目前，一些學者提出了多種計算可行的多無人機協同任務分配算法。文獻[6]通過豐富合同類型的改進合同網拍賣模型實現多無人機多任務拍賣，利用條件合同機制實現多無人機間的協調。文獻[7]提出了改進后的差分進化算法，進行尺度因子和交叉率動態調整。文獻[8]改進了和聲搜索算法，引入了一種調整音高的算子，將和聲搜索的解映射到聚類方法中。文獻[9]提出了基于分工機制的蟻群算法，利用基于任務能力評估的問題解構造策略和基于任務代價的狀態轉移規則，改進蟻群算法。文獻[10]提出了一種混合蟻群優化算法，將禁忌搜索算法與最大最小蟻群系統集合。文獻[11]基于不確定理論建立以信度函數為目標的最小風險模型,任務分配時規避不確定變量標準差較大的目標點。文獻[12]將分布式合同網拍賣算法與模擬退火算法結合協調任務執行次序。文獻[13]利用整數線性規劃模型，對遺傳算法進行改進，使用的編碼方案有效減低了算法的復雜度。此外，當任務之間存在時序關系或者多個任務需要同時執行時，有可能出現“死鎖”[14]。死鎖是由一系列需要順序執行的任務形成“循環等待”的關系引起的，文獻[14]描述了死鎖定義和死鎖產生的必要條件。文獻[15]針對任務時序約束導致的死鎖問題，提出了一種基于圖論和矩陣轉置的死鎖檢測修復方法。文獻[16]在文獻[15]的基礎上，提出了一種基于自由邊翻轉的死鎖修復方法。任務執行過程中，由于新目標發現等實時事件的發生，導致原任務分配方案失效，需要進行任務重分配。文獻[17]針對任務重分配場景，提出了一種匹配策略。文獻[18]使用匹配策略設計了重組和非重組兩種重調度方法。文獻[19]考慮了任務時序對重調度的影響。

同其他啟發式算法、智能優化算法相比，粒子群算法具有計算簡單、魯棒性好、搜索能力強且收斂速度快的特點，在求解多飛行器協同任務分配問題時，具有較大優勢[20-25]。文獻[20]基于啟發信息和沖突消解策略改進標準粒子群算法(Particle Swarm Optimization, PSO)，提高算法收斂性和全局搜索能力。文獻[21]利用混沌機制和變異算子增強量子粒子群算法的尋優能力。文獻[22]在粒子矩陣編碼中引入任務時序約束和多機協同約束。但因自身結構原因，粒子群算法不可避免的會出現粒子早熟和停滯傾向，容易陷入“局部收斂”，無法得到全局最優解。目前解決這個問題有2種方法，一是改進粒子群算法參數，擴大局部搜索范圍，文獻[23]設計最優粒子更新算法的控制參數。文獻[24]結合進化博弈理論動態調整粒子群算法3個主要控制參數，但是這樣的方法效果有限，沒有結合其它算法的混合算法性能好。另一種方法是利用其它智能優化算法的局部搜索能力，幫助粒子群算法跳出局部收斂，文獻[25]將模擬退火算法與粒子群算法相結合組成混合算法，提高算法尋優精度。但是這種方法每次迭代時都需要執行跳出局部收斂策略，大幅度增加計算開銷。

多飛行器協同攻擊地面目標場景中的任務分配問題，屬于典型的MTAP問題。部分目標需要多架無人機同時打擊，可能會出現死鎖。任務具有軟時間窗約束，即允許任務開始執行時間違背時間窗約束，但會產生相應的偏差代價?；贛TAP問題的數學模型，提出一種綜合考慮任務收益和代價的混合粒子群任務分配算法。主要創新點包括：

1) 針對同時打擊任務引起的死鎖問題，提出一種基于多打擊任務有向圖的死鎖檢測和修正算法。

2) 根據變鄰域算法強大的解空間搜索能力，提出一種能夠有效跳出局部收斂的策略，并將這種策略嵌入到粒子群算法中。

3) 設計了一種局部搜索的概率啟動準則，綜合考慮了跳出局部收斂與計算開銷之間的平衡關系。

4) 設計不同規模的仿真實驗，結果表明同其它智能分配算法相比，混合粒子群任務分配算法的性能更好、適應性更強。

1 MTAP模型

假設共有Nu架無人機U={U1,U2,…,UNu}和Nt個地面目標T={T1,T2, …,TNt}，無人機數量遠小于目標數。需要對每個目標Tj執行一次攻擊任務Mj，因此有Nt個任務M={M1,M2,…,MNt}。每個打擊任務需要一架或多架無人機來執行。令任務Mj需要Γ(j)≥1架無人機來執行。故M分為單打擊任務集合Md={Mj∈M|Γ(j)=1}和多打擊任務集合Mk={Mj∈M|Γ(j)>1}。每個單打擊任務只需要一架無人機攻擊相應目標；多打擊任務Mj∈Mk需要Γ(j)架無人機同時攻擊相應的目標。無人機完成任務會獲得的綜合收益由摧毀目標的價值、目標打擊時間窗口、無人機飛行航程等因素決定。每架無人機武器載荷有限，只能完成有限個數的任務，即攻擊有限個數的目標。

(1)

(2)

?c∈{2,3,…,mi}

(3)

式中：vi為無人機Ui的飛行速度;TN(·)表示執行對應任務所需時間。

同時，無人機Ui執行Δi中的單打擊任務時，無需等待，其到達時間等于任務執行時間。但當Ui執行的任務Mci是多打擊任務時，則需要等待其它執行Mci的無人機都到達同一目標點，共同執行Mci。令Θ(Mj)={Us∈U|Mj∈Δs}表示需要執行任務Mj的無人機集合，則

?c∈{2,…,mi}

(4)

(5)

式中：b1和b2分別是機會損失系數和延誤懲罰系數。

MTAP問題數學模型如下：

(6)

(7)

(8)

(9)

xij∈{0,1} ?Ui∈U,?Mj∈M

(10)

2 混合粒子群任務分配算法

提出一種用于多無人機協同攻擊地面目標的混合粒子群任務分配算法，設計粒子的編碼、解碼與修正過程。針對粒子群算法容易陷入局部收斂的缺點，提出一種基于變鄰域搜索的跳出局部收斂的策略，提高算法的性能和適應性。

2.1 標準粒子群算法

在PSO[26]中，每個粒子對應一個潛在解，多個粒子組成一個種群。在粒子種群進化過程中，粒子需要追蹤2個極值：個體極值pbest和群體極值gbest。前者是某個粒子搜索到的歷史最優解，后者是整個種群當前的最優解。所有粒子根據適應度函數更新自身的位置向量和速度向量，盡可能的向最優解靠攏。

令粒子k時刻t的位置向量和速度向量分別是和。算法迭代演化過程中，每個粒子的速度和位置根據如下公式更新：

(11)

(12)

式中：r1和r2都是分布在[0, 1]之間的隨機數；c1=c2=2分別是個體加速常數與群體加速常數；pbestk,t是粒子k當前時刻的個體極值，gbestt是當前時刻粒子種群群體極值。ω稱為慣性因子，受文獻[27]啟發，ω由下式計算：

(13)

其中：ωmax和ωmin分別為慣性權重的最大和最小參考值；Iter和Imaxter分別為當前迭代次數和最大迭代次數；Fold為過去10次迭代最優粒子適應度平均值，F(gbest)為當前迭代最優粒子適應度。這樣設置的ω能在搜索過程中自適應調整大小，特別當算法陷入局部收斂時，ω將逐步變大，提高局部探索能力。

2.2 編碼、解碼與修正

PSO算法中粒子的位置和速度是連續性變量，對應的解空間也是連續性的。而MTAP問題的任務分配解是離散的，因此需要先對粒子的位置和速度進行“離散化”編碼，進而解碼出MTAP的一個潛在解。

2.2.1 編 碼

已知Nt是任務數量，Nu是無人機數量，故粒子維數其中Γ(j)是執行打擊任務Mj需要的無人機數量。采用實數編碼方式，令粒子k的位置Pk和速度Yk都是維實數向量，每個位置元素Pk[j]限制在1跟Nu+1之間但不等于Nu+1，即Pk[j]∈[1,Nu+1)。同時，為了保證粒子的位置盡可能在[1,Nu+ 1)之間，限定粒子的速度Yk的每個元素Yk[j]∈[-Nu,Nu]。

2.2.2 解碼與修正

令In(n)為實數n的整數部分，De(n)表示n的小數部分，例如In(4.7)=4，De(4.7)=0.7?？捎昧Ｗ觡的位置元素Pk[j]表示一個任務分配解。例如對于In(Pk[j])=s，表示將任務Mj分配給了無人機Us。本文限定：對于具有相同整數部分的位置元素(將它們分給同一無人機)，其小數部分的大小順序對應該無人機執行這些任務的順序。因此從Pk可解碼出無人機Ui的一組任務序列Δi。

算例1將任務M1～M9分配給無人機U1～U3，即Nt=9且Nu=3，其中M2、M4和M6是多打擊任務，且Γ(2)=Γ(4)=Γ(6)=2，其余任務是單打擊任務。因此，=12，相應PSO算法的解空間是12維。每個粒子的位置元素限定在[1, 4)之間，速度元素限定在[-3, 3]之間。表1給出一個粒子的位置、速度以及對應位置元素的整數部分和小數部分。從中可以看出M1、M4、M6、M7和M8分配給無人機U1。同時，因為De(Pk[10])。同理可得Δ2=，Δ3= 。很顯然，對于Δ3，M2兩次分配給U3，不滿足約束式(8)。令而超過了無人機U1的任務上限，不滿足約束式(9)。

表1 一個粒子的速度、位置和對應位置分量的整數部分和小數部分

算法1 約束修正1.for(1≤t≤Nu)2. while Δt中存在重復多打擊任務Mj∈Mk3. 隨機刪除Δt中一個Mj;4. 選擇r∈[1, Nu], s.t. r ≠ t且Δr中無Mj5. 將Mj隨機插入Δr中;6. end7.end8.令Φ=?,Π=?,s=1;9.for(s≤Nt)10. if (Δs>Qmaxs)11. Φ=Φ∪{s};12. elseif(Δs

在算法1中，第1～7行對分配同一無人機的中多打擊任務進行修正，以滿足約束式(8)；第8～16行計算Φ和Π，Φ表示分配任務數超過其上限的無人機序號集合，Π表示對應任務序列還能插入任務的無人機序號集合；第17～28行是一個while循環，每次迭代中從Φ中選擇一個無人機序號i，隨機刪除任務序列Δi中的一個任務Me，并將Me隨機插入到任務集合Δj中，Δj中其余任務相應移位，其中j為隨機從Π抽取得到無人機序號，與此同時更新集合Φ和Π。最終得到的新任務序列Δ′i(i∈{1, 2, …,Nu})，滿足約束式(9)。

經算法1修正得到的任務分配解滿足約束式(8)和式(9)，但可能出現“死鎖”，即不同無人機執行多打擊任務時，出現循環等待的現象，導致任務無法繼續執行。比如，算例中任務分配解Δ經算法1修正后變成Δ′={Δ′1,Δ′2,Δ′3}，其中Δ′1=，Δ′2=，Δ′3=，Δ′可用圖1描述，灰色圓形表示單打擊任務，白色圓形表示多打擊任務。很明顯，無人機U1需等待U2到達T6后，才能執行多打擊任務M6；但U2需要先打擊目標T4(即執行任務M4)，才能到達T6；而執行任務M4又需要無人機U1先到達目標T4，這與U1的執行任務序列相矛盾。即U1和U2陷入無限循環等待，出現了死鎖[14]。

圖1 任務分配解示意圖

本文中的死鎖只與多打擊任務有關，因此采用有向圖G=來表征死鎖，其中V={j|Mj∈Mk}表示多打擊任務節點，E中的弧線(i,j)表示存在一架無人機先執行Mi再執行Mj。根據文獻[15]，G中的強連通分量(即回路)表示死鎖。比如上述修正解Δ′的有向圖G如圖2(a)表示，其中頂點4和6組成回路，因此任務M4與M6組成了死鎖，這與上述分析結果相同?？捎肈FS算法(深度優先搜索)檢測G的回路[28]。

根據文獻[16]，本文針對多打擊任務的死鎖問題，提出了一種基于多打擊任務有向圖的死鎖檢測和修復方法，如算法2所示。輸入為滿足約束式(8)和式(9)的任務分配解Δ′={Δ′k|k∈{1, 2, …,Nu}}，輸出為無死鎖可行解Δ″={Δ″k|k∈{1, 2, …,Nu}}。

圖2 多打擊任務有向圖

算法2 死鎖修正1.構建Δ'對應的有向圖G=;2.利用DFS算法檢測是否存回路,回路信息存入列表RΔ';3.while(RΔ'≠?)4. 對RΔ'中各弧線根據出現次數排序;5. 輪盤賭法選取換位弧線(i, j);6. fork∈{1, 2, …, Nu}7. if 根據Δk, Uk先執行Mi再執行Mj8. 交換Δk中Mi和Mj的位置;9. end10. end11. 更新Δ'對應的有向圖G = ;12. DFS算法檢測回路,更新列表RΔ';13. end14. 輸出無死鎖可行解{Δ″kk∈{1, 2, …, Nu}}

在算法2中，第1～2行構建有向圖，將DFS算法檢測到的回路信息保存在RΔ′中；第3～13行修正死鎖，根據RΔ′中出現的次數使用輪盤賭法選取弧線(i,j)，進行換位操作，交換一些任務序列Δ′k中多打擊任務Mi和Mj的位置。類似于文獻[16]中的分析，算法2在有限運算后輸出一個無死鎖的任務分配解。因為算法2僅調整任務序列Δ′k中一些多打擊任務的位置，不會在Δ′k中增加或者刪除任務，因此得到的無死鎖解仍然滿足式(8)和式(9)。

利用算法2對算例中的Δ′進行死鎖檢測和修復，可知RΔ′={(6, 4), (4, 6)}。選擇弧線(6, 4)，交換Δ′1中M6和M4的位置，得到新的有向圖G′，如圖2(b)所示。相應的新的無死鎖解是Δ″1= ，Δ″2= ，Δ″3= 。

2.2.3 適應度值計算

對于粒子k，首先將其位置向量解碼為1組任務分配解Δ，然后利用算法1和算法2確保Δ滿足約束條件且無死鎖。相應的適應度值F(k)由式(1)確定，即

(14)

式中，F(k)越小，從粒子k解碼出的任務分配解的質量越好。

2.3 變鄰域搜索跳出局部收斂策略

為了提高PSO算法的性能，防止算法陷入局部收斂，本文提出一種基于變鄰域搜索(Variable Neighborhood Search, VNS)算法的局部搜索策略，使算法具備跳出局部收斂的能力。

2.3.1 鄰域結構

VNS算法的基本思想是在搜索過程中改變鄰域結構集，從而拓展搜索范圍，獲得最優解[29]。

令Pk表示粒子k的位置向量，根據解碼和算法1可從Pk得到1組任務分配解，即Pk決定k對應解的質量。因此，本文采用以下3種鄰域結構，修改位置向量Pk尋找更好的鄰域解：

2) 第2鄰域結構(插入鄰域)：在Pk中隨機選擇2個位置i和j且i

算法3利用第1鄰域結構(交換鄰域)搜尋局部最優解。首先令i= rand(1,Nt)和j= rand(1,Nt)都為區間[1,Nt]的任一整數，并設當前鄰域搜索次數N為0。Nmax表示最大搜尋次數。算法的主要組成部分是while循環(第2～14行)，在每次迭代中N

算法3 第1鄰域結構1.Let i = rand(1, Nt), j = rand(1, Nt), N= 0//初始化2.while(N < Nmax)3. while(i = j)4. i = rand(1, Nt), j = rand(1, Nt)5. end6. if(Pk[i]≠Pk[j])7. P'k=(Pk, i, j) ∥將Pk[i]和Pk[j]互換,得新的位置P'k8. P'k與粒子k的速度結合得新的粒子k';9. end10. if(F(k) > F(k'))11. 將粒子k替換為k'; ∥粒子k性能差,替換為k'12. end 13. N++14. end15. 輸出粒子k';

算法4 第2鄰域結構1.Let i = rand(1, Nt), j = rand(1, Nt), N= 0;2.while(N < Nmax)3. while(i = j)4. i = rand(1, Nt), j = rand(1, Nt)5. end6. if(Pk[i]≠Pk[j])7. if(j > i)8. P'k =(Pk, i, j) ∥將Pk[j]插入位置i處得新位置P'k9. else10. P'k=(Pk, j, i)11. end12. P'k與粒子k的速度形成新的粒子k';13. end14. if(F(k) > F(k'))15. 將粒子k替換為k'; ∥粒子k性能差,替換為k'16. end17. N++;18. end19. 輸出粒子k';

算法4利用第2鄰域結構(插入鄰域)搜尋局部最優解，其算法步驟與算法3相似，主要區別在于算法4需要判斷隨機選擇的位置序號i和j的大小，將較大位置序號的元素插入較小位置序號(見第6～12行)，形成新的位置向量P′k。

算法5使用第3鄰域結構(逆轉鄰域)搜索局部最優解，將隨機選擇的序號i和j之間的片段逆轉重排(第6～12行)，直至搜索到局部最優解。

算法5 第3鄰域結構1.令 i = rand(1, Nt), j = rand(1, Nt), N = 0;2. while(N < Nmax)3. while(i = j)4. i = rand(1, Nt), j = rand(1, Nt)5. end6. if(Pk[i]≠Pk[j])7. if(j > i)8. P'k=(Pk, i, j) ∥Pk中位置i、j之間元素逆轉重排9. else10. P'k = (Pk, j, i)11. end12. P'k與粒子k的速度形成新的粒子k';13. end14. if(F(k) > F(k'))15. 將粒子k替換為k'; ∥粒子k性能差,替換為k'16. end17. N++;18. end

2.3.2 局部搜索啟動概率準則

為了綜合平衡算法跳出局部收斂能力與整體計算開銷，以概率rk啟動對粒子k的變鄰域局部搜索，rk由下式計算

(15)

啟動概率rk由當前粒子k的適應度值F(k)和全局最優值F(gbest)決定。當F(k)≤F(gbest)時，由式(15)可知rk=1，此時算法很有可能已陷入了局部收斂，因此必須要啟動變鄰域搜索過程，跳出局部收斂；當F(k)>F(gbest)時，粒子k的性能較差，距離全局最優解較遠，此時是否會啟動局部搜索由概率rk=S決定；分析可知k性能越差，越不可能陷入到局部收斂中，相應的啟動概率rk越小，同時將最小啟動概率設置為0.01。

通過此概率啟動準則，一方面對陷入局部最優的粒子進行變鄰域搜索，跳出局部收斂；另一方面，對距離全局最優解較遠的粒子，降低啟動局部搜索的概率，實現跳出局部最優與計算開銷的合理平衡。

2.3.3 跳出局部收斂的變鄰域搜索算法

利用上述3種變鄰域結構，提出一種VNS局部搜索算法，實現跳出PSO算法可能陷入的局部收斂。如算法6所示，輸入為粒子k的位置Pk，輸出為局部最優解對應的粒子k′。

在算法6中Nmax表示某一鄰域結構內最大搜索次數，本文采用了3級鄰域結構，因此最高鄰域等級Klevel_max=3。令r= rand(0,1)為0～1之間的隨機數，啟動概率rk由式(11)確定。若r≥rk，則不啟動變鄰域搜索，直接輸出原粒子k。VNS搜索過程如第3～23行所示，當鄰域搜索次數N≤Nmax時，進行第K變鄰域結構局部搜索(第6～21行)。在此過程中，若新粒子k′優于原粒子k，用k′替換k，跳出當前循環過程，并初始化N和K(第15～21行)；若搜索Nmax次后仍未找到更優粒子，則需要提升鄰域等級(第22行)；若當前鄰域等級大于Klevel_max時仍未發現更優粒子，直接輸出原粒子k。

算法6 VNS局部搜索算法1.Let Nmax= n,Klevel_max= 32.if (r = rand(0, 1) < rk)3. K = 1;4. while (K≤Klevel_max)5. N=1; ∥初始化當前鄰域搜索次數6. while (N≤Nmax)7. switchK:8. case 1: ∥啟動第一鄰域搜索9. 執行算法3,輸出粒子k'10. case 2: ∥啟動第二鄰域搜索11. 執行算法4,輸出粒子k'12. case 3: ∥啟動第三鄰域搜索13. 執行算法5,輸出粒子k'14. end15. if (F(k') < F(k)) ∥找到局部最優解16. 將粒子k替換為k';17. K = 0; ∥復位鄰域等級18. break; ∥跳出當前while循環19. end20. N = N + 1 ∥完成一次鄰域搜索21. end22. K = K + 1; ∥增加相應鄰域等級23. end24. end25. 輸出粒子k;

2.4 混合粒子群任務分配算法設計

本文提出了一種結合標準PSO算法與VNS搜索跳出局部收斂策略的協同任務分配混合粒子群算法，算法流程圖如圖3所示。具體步驟如下所示：

步驟1初始化種群，設置最大迭代次數Tmax，經過解碼和修正過程，計算當前種群的全局極值和每個粒子的個體極值。

步驟2根據式(15)計算每個粒子k的局部搜索啟動概率rk，利用算法6進行VNS搜索，用生成的更優粒子替代原粒子。

步驟3計算每個粒子k的適應度值F(k)，更新k的個體極值與全局極值。

圖3 協同任務分配混合粒子群算法流程圖

步驟4根據式(11)和式(12)更新每個粒子的位置和速度。

步驟5判斷當前迭代次數是否大于Tmax，若否，則返回步驟2。

步驟6輸出全局極值和相應的任務分配解。

2.5 基于匹配策略的局部任務重分配方法

針對新目標發現等實時事件導致的初始分配計劃失效問題，結合2.4節中的協同任務分配混合粒子群算法，提出了一種基于匹配策略的局部任務重分配方法。匹配策略思想首先定義重分配范圍(以時間窗的形式)，然后重新調度在重分配范圍內的任務，最后將得到的局部調度計劃集成到初始任務分配方案中，這樣能保證初始任務分配計劃的穩定性，還減小了計算開銷，縮短了重分配用時[18]。

考慮發現新目標場景下的任務重分配。令Tn={T1n,T2n,…,TNn}表示ts時刻新發現的Nn個目標，對應的打擊任務集合是Mn={M1n,M2n,…,MNn}。新任務Mjn需要Γ(jn)架無人機執行，對應的時間窗口[S(Mjn),C(Mjn)]。根據文獻[19]，定義重分配范圍[tstart,tend]，其中tstart=ts，tend=max{C(Mjn)|Mjn∈Mn}。需要將Mn中的新任務在時間窗[tstart,tend]內分配給各個無人機，但這樣會影響初始計劃中[tstart,tend]內的任務Mo(不包括tstart,tend點正在執行的任務)。因此，重分配的任務集合MR=Mo∪Mn。

圖4(a)表示一個任務分配方案的甘特圖，可知Δ1= ,Δ2= ,Δ3= , 假設在ts= 12發現新目標Ts，對應任務Ms的時間窗是[15, 28]，故相應的重分配范圍是[12, 28]。注意在tend時刻，M4正在執行。按照初始計劃，此時段內任務Mo= {M5,M6,M7}，因此需要重分配的任務集合是MR= {M5,M6,M7,Ms}。根據tstart之前的任務分配計劃，更新各個無人機的起始時間和地點，將MR中的任務分配給無人機，并將所得結果與原計劃tend后的方案結合起來，共同組成重分配結果。這樣的簡化調度問題減少了待分配任務數量，縮短重分配用時，保留部分原分配計劃。

圖4 任務分配甘特圖

現證明重分配任務方案Δ*是無死鎖的。假設對應的多打擊任務有向圖G*具有回路。因為MR和∪i∈{1,2,…,Nu}Δvi對應的多打擊任務有向圖都是無回路的(這由混合粒子群的死鎖修復算法決定)，則V′中肯定同時包含了MR和∪i∈{1,2,…,Nu}Δvi中的多打擊任務，且存在任務Mr∈MR∩V′以及Mv∈∪i∈{1,2,…,Nu}Δvi∩V′，使得弧線(Mv,Mr)∈E′，即有一架無人機先執行Mv再執行Mr。然而根據時間軸關系，這是不可能的。因此G*無回路，重構結果Δ*無死鎖。

3 算法實例與分析

分別用遺傳算法(Genetic Algorithm, GA)[30]、模擬退火算法(Simulated Annealing, SA)[31]、粒子群算法(PSO)[26]、粒子群與模擬退火結合的混合算法(PSO+SA)[25]和本文提出的混合PSO算法求解多無人機協同任務分配問題，并對比分析實驗結果。驗證平臺為具有Intel Core i9-9900K處理器、32 GB內存的PC機，所有算法在MATLAB R2021a平臺編譯運行。

實驗1考慮5架無人機協同攻擊20個地面目標的任務分配場景。無人機和攻擊目標的參數如表2和表3所示。為了簡化實驗場景，假設無人機起飛后均勻速飛行。每個目標具有不同打擊時間窗口和打擊用時。

設定上述5種算法的最大迭代次數均為800次，均衡考慮各受益和代價的影響，令目各項增益系數a1=a2=a3。同時設2種時間偏差的代價相同，即b1=b2=1。5種算法的任務分配結果如表4所示，括號中的數據為各無人機執行相應任務的無量綱時間，比如12(7.78)表示無人機于7.78時刻執行任務12。從表4可看出，使用本文死鎖檢測和修復算法，多架無人機在同一時刻執行同一多打擊任務，不會引發死鎖。與其他4種算法相比，提出的混合PSO適應度值最小，性能最好。

表2 無人機參數

表3 任務目標參數

圖5為5種算法適應度變化折線圖，可以看出GA算法具有較差的局部搜索能力和進化能力，所得結果與其他4種算法相比有明顯差距；SA算法在一開始優化速度較快，但很快陷入了局部收斂；PSO算法在起始階段具有較快的優化速度，但在中期陷入了局部收斂；PSO+SA算法雖具有一定的跳出局部收斂的能力，但收斂速度較慢，仍然會陷入局部收斂，所得適應度值也非最佳；本文提出的混合粒子群算法采用了局部搜索啟動概率準則，不僅在起始階段具有并不低于PSO算法的優化速度，還能不斷的跳出局部收斂，所得的結果也是最優的。

表4 任務分配結果[25,30,31]

圖5 5種算法適應度對比

實驗2為了驗證提出的概率啟動準則具有平衡跳出局部收斂與計算開銷的能力，本文對于實驗1的場景，設置3種情形：不執行跳出局部收斂策略、每次迭代執行跳出局部收斂、采用本文提出的概率啟動準則。共進行5次實驗，計算平均適應度值和平均算法運行時間。

實驗結果如表5所示，從中可知：與不執行跳出局部收斂策略的情形相比，本文的概率啟動準則跳出局部收斂策略使得解的性能提升324% (≈(182.82-43.08)/43.08)；與每次都執行跳出局部收斂策略相比，概率啟動準則在節約84% (≈(4642-732)/4642)時間的前提下，解的性能僅下降4%(≈(43.08-41.43)/41.43)。因此，本文提出的概率啟動準則實現了計算開銷與跳出局部收斂的平衡。

表5 不同跳出最優策略實驗統計結果

實驗3為了綜合驗證本文提出的混合PSO算法求解MTAP問題的能力，本文將上述5種算法用于不同規模的MTAP實驗，所得結果如圖6所示。其中，MTAP0305表示3架無人機協同打擊5個目標的任務場景。5種算法均進行5次實驗，并分別統計所得解目標值的3項指標：最小值、平均值和方差。從圖6可以看出，對于小規模問題(比如MTAP0305)，由于解空間較小，5種算法求解性能相似，均能得到最優解；隨著問題規模的增大，不同算法的表現差異也顯著增大，但本文提出的混合PSO任務分配算法在不同規模的MTAP問題中都取得了最好的解，適應性最好。

圖6 不同規模MTAP實驗對比

實驗4針對發現新目標導致初始任務分配方案失效問題，驗證本文提出的基于匹配策略的局部任務重分配算法的有效性。設初始任務分配方案Δ的甘特圖如圖7(a)所示，將10個任務M1～M10分配給了3架無人機，其中M2、M5和M8是多打擊任務。假設在ts=15時刻，發現新目標Tn={T11,T12}，新增加任務Mn={M11,M12}，它們的參數如表6所示，可知只有M12是多打擊任務。根據3.5節中的任務重分配方法，因max{C(Mjn)|Mjn∈Mn}=40，故重分配范圍為[15, 40]，相應的重分配任務集MR={M1,M4,M5,M11,M12}。注意tend時刻任務M6未完成，因此M6不屬于MR。初始任務分配方案在tend之后序列Δv1= ，Δv2= ，Δv3= 。

圖7 任務重分配實驗甘特圖

表6 新任務參數

4 結 論

針對多無人機協同任務分配問題，建立了綜合考慮飛行航程、任務收益、任務完成時間窗口的混合粒子群任務分配算法。首先設計了滿足多打擊任務約束條件的粒子編碼與解碼過程，針對可能存在的死鎖問題，設計了一種基于多打擊任務有向圖的快速死鎖檢測修復算法，實現了粒子群算法解的離散化。然后對于標準粒子群算法容易陷入局部收斂的問題，設計了一種基于變鄰域搜索算法的跳出局部收斂策略，同時提出局部搜索概率啟動準則，實現了跳出局部收斂和計算開銷的平衡。最后，將所提出的跳出局部收斂策略與粒子群算法相結合，得到適用于MTAP問題的混合粒子群算法。對于新目標發現導致的初始計劃失效問題，本文也設計了一種基于匹配策略的局部任務重分配方法。

通過設計仿真實驗，與現有其他4種智能任務分配算法相比較，本文提出的混合粒子群算法在保證優化速度的同時，還具有不斷跳出局部收斂的能力，因此會獲得較好的任務分配結果，性能表現顯著優于其他算法。