多約束條件下多UUV 任務分配方法

張向鵬，黃 雙，曹 旭，呂云飛

(武漢第二船舶設計研究所，湖北 武漢 430205)

0 引言

水下無人航行器（Underwater Unmanned Vehicle,UUV）依托其無人、經濟、可大規模部署等優點，受到各國廣泛關注。在軍事領域，憑借UUV 分布式、自主化的優勢，可執行傳統載人平臺無法完成的多種復雜作戰任務，如近海全方位、長周期、體系化的無人防御警戒，目標海域清掃偵察，對敵高價值水下目標進行集群聯合打擊[1–3]等。受制于水聲通信高延遲、低帶寬問題，充分考慮載人指揮控制平臺隱蔽性安全性，在UUV 執行任務前，需對UUV 所執行作戰任務進行預分配，保證所執行任務滿足戰略戰術需求。因此，對多UUV 進行任務分配是UUV 高效執行作戰任務的必要流程，也是當前水下無人系統研究熱點。

21 世紀以來，各國紛紛開展無人系統任務分配專項研究工作，將任務分配問題與控制科學、人工智能、決策理論以及建模優化技術相融合，形成多種解決方法，如合同網法、線性規劃法、群體智能法[4]。李娟等[5]提出了一種基于改進合同網算法的異構多UUV 任務分配策略，將任務負載率指標和令牌環網概念結合起來,有效解決選擇招標者及其任務不合理的問題。范學滿等[6]假設了每個任務由單個UUV 完成，將NSGA-II 與動態規劃算法相結合，以最短路徑為基準，優化得到個固定數量UUV 各自任務序列。李建軍等[7]改進量子行為粒子群優化（Quantum-behaved Particle Swarm Optimizer，QPSO）算法，設計混沌QPSO 算法，以總時間、總收益、總代價為目標，對多個UUV 分別分配任務序列。盧騫等[8]采用MODSPO 算法引入改進SA 算法，增強對UUV 協同任務的搜索能力。上述文獻通過不同方法實現UUV 任務序列的生成，解決在UUV 任務分配過程中的部分問題，促進UUV 集群任務分配領域的發展。但實際應用場景中，UUV 與保障船需保持信息交互，以確保指揮員對態勢信息的掌握。對各UUV 進行任務分配，不僅考慮UUV 續航、功能，還需考慮與保障船交互關系。

本文在已有研究基礎上，充分考慮執行水下任務的多種約束條件，建立任務分配模型，通過改進集合粒子群優化算法（S-PSO）的慣性系數，引入遺傳算法變異操作，提高算法的局部搜索和全局探索能力。

1 問題描述與建模

1.1 基本描述

我方保障船于某海域釋放多艘UUV。該海域中存在多個任務點，每個任務點的任務對UUV 能力需求存差異。由于不涉及路徑規劃和跟蹤，本文不考慮UUV 動力學模型異構。我方保障船根據各UUV 狀態信息、任務基本信息等，在確保總任務時間最優情況下，降低多UUV 執行任務的總能耗、總路程，實現多UUV 任務分配，生成UUV 任務序列。其中，部分任務需多艘UUV 聯合執行，且規定多艘UUV 執行同一任務。以最后到達任務點UUV 時間為任務開始時間，最后完成該任務UUV 結束時間為任務結束時間。

每艘UUV 任務序列采用有向圖表示，設Xn表示第n艘UUV 任務序列對應鄰接矩陣，元素Mn為第n艘UUV 所執行的任務，則

1.2 目標函數

設任務信息為：任務區域中心坐標點、預估任務耗時、預估任務能耗、預估任務所需UUV 數量、所需UUV 的能力；UUV 信息格式為：初始位置坐標點、航行速度、單位距離能耗、總能量、能力、充電時間。對各UUV 任務的預分配和任務序列的生成，為多目標多約束規劃問題。任務分配目標為任務的總時間T、總路程C、UUV 總能耗E，表示為：

式中：α+β+γ=1且 α≥β、α≥γ，各權重由先驗知識和指揮員對任務分配偏好確定。各變量表達式為：

1.3 約束條件

進行任務分配時，需要滿足的約束條件分別為：

1）每個任務對于每艘UUV 最多執行1 次。

2）每艘UUV 均由起始位置出發，執行完成全部預分配任務時返回指定充電位置。

3）每艘UUV 預裝訂任務序列執行完成返回指定位置的總能耗不能超過自身總能量。

4）每艘UUV 在執行每個任務后，剩余能量Eremain需保證在完成當前任務后可返回指定位置充電。

5）參與執行任務的UUV 需滿足任務對UUV 能力約束，設Aj表示任務j的能力需求，表示第n艘UUV 所具有能力。

6）考慮水下弱通信環境，為保障UUV 與保障船之間的穩定通信，設由水聲通信設備確定的有效通信距離為dsonar，保障船位置為p0，第i項任務任務點為pi。

2 改進S-PSO 算法

在滿足約束條件下，求解使目標取得極小值的任務序列。采用改進的S-PSO 進行迭代求解。傳統SPSO 規則簡單，收斂速度快，減少任務分配環節的時間消耗，適合多UUV 協同作戰等具有一定時效性需求的任務分配[9]。S-PSO 在每次迭代求解過程中，均可獲得多個任務序列可行解。

在對UUV 集群進行任務分配時，設一個粒子的位置為：

即一個粒子的位置代表一組UUV 可行任務分配序列的集合，i=1,2,3,...,Np，Np為粒子總數。

粒子移動速度用可行性概率集合表示：

pij以概率形式表示執行完成任務i后參與任務j對應的粒子位置元素更新速度。

各個粒子速度更新公式為：

式中：ω為慣性系數；系數c1和c2為給定常數；系數r1和r2為位于區間 [0,1]的隨機數；Xbest為該粒子在迭代過程中使目標函數取值最小的最優位置；Pbest為所有粒子的全局最優位置。

區別于傳統S-PSO，在迭代求解過程中，為提高迭代初期的全局搜索能力，迭代后期的局部搜索精度，慣性系數采用動態值。其表達式為：

式中：ωHigh和 ωLow為ω 最大值和最小值；k為當前迭代次數；K為總迭代次數。

此外，在傳統S-PSO 基礎上，結合遺傳算法的變異操作，設各粒子的位置矩陣中的每個元素在遍歷開始時均有pm的概率發生變異，rm為區間 [0,1]的隨機數，則

不同于遺傳算法的隨機變異，本文算法產生的變異需要滿足基本約束條件，若不滿足約束條件，則變異不成立。為避免因變異概率過大導致迭代算法退化為隨機選擇，pm值隨迭代的進行逐漸降低，直至降為0。

速度更新公式中，矩陣之間的運算不再遵循數值計算規則，采用如下運算規則：

式中：A，B為任意矩陣；c為任意常數。

綜上所述，粒子位置更新流程如圖1 所示。

通過圖1 流程更新獲得的粒子位置X′即為一可行任務分配序列。將序列代入目標函數，求得對該任務分配序列的評估值。評估值越小，表明在綜合路程、能耗、總時間等3 項目標下，該任務分配序列越優。通過迭代求解出使得目標函數取得極小值任務分配序列，以尋找最優任務分配序列。

3 仿真實驗

3.1 仿真場景設置

為驗證方案的可行性和算法的有效性，對4 艘UUV 分配10 個任務的場景進行仿真實驗。為便于分析，使圖像更直觀，假定在執行任務前，各UUV 均需前往給定任務區域某坐標點位置，從該坐標點開始執行任務；全部UUV 初始位置相同，完成自身任務序列后返回位置相同且與初始位置一致；在分配任務前，已對執行任務完成最長時間和UUV 最大耗能進行預估。

3.2 仿真結果及分析

設置求解算法的參數 ωHigh為1.6；參數 ωLow為0.4；系數c1和c2均取1；粒子個數為10；最大迭代次數為1 500。迭代過程中，目標函數各項變量均歸一化處理。10 項待分配任務的信息如表1 所示，表中第0 號任務為設定緊急返航能量補充點，用以保證某UUV 能量不足以支撐任何任務執行時返航補充能量。UUV 信息如表2 所示，假定所有UUV 均從給定原點出發。設仿真實驗采用的UUV 返航位置、初始位置、緊急返航充電位置均相同。待分配任務信息中所需UUV 能力與UUV 信息中UUV 所具有能力采用二進制編碼，每一位代表一種能力。假設任意一個任務能否執行，需檢查所有參與任務的UUV 能力是否均滿足任務UUV 能力需求。如任務1 的UUV 能力需求為11，UUV1 能力為01，UUV2 能力為11，僅UUV2 能滿足任務需求。由于任務1 只需1 艘UUV 即可執行，若UUV1 承接該任務且滿足各項約束條件，則任務1 由UUV1 執行，任務1 為可執行任務。

表1 待分配任務信息Tab.1 Task information to be assigned

采用改進S-PSO 算法和傳統S-PSO 算法，分別經迭代求解獲得4 艘UUV 任務序列。采用改進的SPSO 算法求解獲得的任務序列如表3 所示，形成如圖2所示航跡圖，橫坐標為區域坐標。圖中每個任務點對應的3 個數字分別表示任務編號、在該UUV 任務序列中的排序、UUV 編號。可知，UUV1 與UUV3 從保障船出發，共同執行完成任務2 后再分別執行其他任務。UUV2 完成任務7、任務10 后，與UUV4 匯合，聯合執行任務9。由于UUV 能力限制，出現返航補充能量再執行任務的情況。

表3 仿真生成的UUV 任務序列Tab.3 UUV task sequence generated by simulation

圖2 采用改進S-PSO 生成的UUV 任務序列圖Fig.2 UUVs task sequence with modified S-PSO

傳統S-PSO 求解的任務序列如圖3 所示，UUV1 的任務序列明顯長于采用改進S-PSO 生成的任務序列。由于任務完成的總體時間受到完成任務用時最長的UUV 影響，對其他UUV 約束不強，使得在迭代求解過程中，陷入局部最優解，這促使能力較差的UUV1而不是能力較強的UUV3 執行過多任務。盡管改變粒子群的初始值和粒子數量可能會出現圖2 基于改進SPSO 算法獲取的解，但改變初始值和增多粒子數量的方式存在偶然性，其效率相對于改進S-PSO 算法較低。

圖3 傳統S-PSO 生成的UUV 任務序列圖Fig.3 UUVs task sequence with S-PSO

圖4 評估值隨迭代次數收斂情況Fig.4 Convergence of evaluation value with the number of iterations

為進一步比較本文算法與傳統S-PSO 的搜索性能和收斂性，選取在迭代過程中獲得的目標評估值進行分析，評估值越小，表明越逼近最優解。由評估值可知，傳統S-PSO 盡管在迭代早期收斂速度較快，但過早陷入局部最優解；改進S-PSO 降低部分收斂速度情況下，提高全局搜索與局部搜索能力，使結果更趨近全局最優解。

4 結語

本文針對多UUV 任務分配問題，建立包含任務所需UUV 數量、能力、UUV 自身功能、UUV 續航、保障船與UUV 通信距離限制等多約束條件的任務分配模型。結合遺傳算法變異操作，采用動態慣性系數，形成改進S-PSO 算法。實驗結果表明，所提出的多約束多目標任務分配方法，能獲取多UUV 的最優任務分配，算法實現簡單，搜索能力較好，滿足UUV 實際工程應用的要求。