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

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

0 引言

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

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

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

1 問題描述與建模

1.1 基本描述

我方保障船于某海域釋放多艘UUV。該海域中存在多個(gè)任務(wù)點(diǎn)，每個(gè)任務(wù)點(diǎn)的任務(wù)對(duì)UUV 能力需求存差異。由于不涉及路徑規(guī)劃和跟蹤，本文不考慮UUV 動(dòng)力學(xué)模型異構(gòu)。我方保障船根據(jù)各UUV 狀態(tài)信息、任務(wù)基本信息等，在確保總?cè)蝿?wù)時(shí)間最優(yōu)情況下，降低多UUV 執(zhí)行任務(wù)的總能耗、總路程，實(shí)現(xiàn)多UUV 任務(wù)分配，生成UUV 任務(wù)序列。其中，部分任務(wù)需多艘UUV 聯(lián)合執(zhí)行，且規(guī)定多艘UUV 執(zhí)行同一任務(wù)。以最后到達(dá)任務(wù)點(diǎn)UUV 時(shí)間為任務(wù)開始時(shí)間，最后完成該任務(wù)UUV 結(jié)束時(shí)間為任務(wù)結(jié)束時(shí)間。

每艘UUV 任務(wù)序列采用有向圖表示，設(shè)Xn表示第n艘UUV 任務(wù)序列對(duì)應(yīng)鄰接矩陣，元素Mn為第n艘UUV 所執(zhí)行的任務(wù)，則

1.2 目標(biāo)函數(shù)

設(shè)任務(wù)信息為：任務(wù)區(qū)域中心坐標(biāo)點(diǎn)、預(yù)估任務(wù)耗時(shí)、預(yù)估任務(wù)能耗、預(yù)估任務(wù)所需UUV 數(shù)量、所需UUV 的能力；UUV 信息格式為：初始位置坐標(biāo)點(diǎn)、航行速度、單位距離能耗、總能量、能力、充電時(shí)間。對(duì)各UUV 任務(wù)的預(yù)分配和任務(wù)序列的生成，為多目標(biāo)多約束規(guī)劃問題。任務(wù)分配目標(biāo)為任務(wù)的總時(shí)間T、總路程C、UUV 總能耗E，表示為：

式中：α+β+γ=1且 α≥β、α≥γ，各權(quán)重由先驗(yàn)知識(shí)和指揮員對(duì)任務(wù)分配偏好確定。各變量表達(dá)式為：

1.3 約束條件

進(jìn)行任務(wù)分配時(shí)，需要滿足的約束條件分別為：

1）每個(gè)任務(wù)對(duì)于每艘UUV 最多執(zhí)行1 次。

2）每艘UUV 均由起始位置出發(fā)，執(zhí)行完成全部預(yù)分配任務(wù)時(shí)返回指定充電位置。

3）每艘UUV 預(yù)裝訂任務(wù)序列執(zhí)行完成返回指定位置的總能耗不能超過(guò)自身總能量。

4）每艘UUV 在執(zhí)行每個(gè)任務(wù)后，剩余能量Eremain需保證在完成當(dāng)前任務(wù)后可返回指定位置充電。

5）參與執(zhí)行任務(wù)的UUV 需滿足任務(wù)對(duì)UUV 能力約束，設(shè)Aj表示任務(wù)j的能力需求，表示第n艘UUV 所具有能力。

6）考慮水下弱通信環(huán)境，為保障UUV 與保障船之間的穩(wěn)定通信，設(shè)由水聲通信設(shè)備確定的有效通信距離為dsonar，保障船位置為p0，第i項(xiàng)任務(wù)任務(wù)點(diǎn)為pi。

2 改進(jìn)S-PSO 算法

在滿足約束條件下，求解使目標(biāo)取得極小值的任務(wù)序列。采用改進(jìn)的S-PSO 進(jìn)行迭代求解。傳統(tǒng)SPSO 規(guī)則簡(jiǎn)單，收斂速度快，減少任務(wù)分配環(huán)節(jié)的時(shí)間消耗，適合多UUV 協(xié)同作戰(zhàn)等具有一定時(shí)效性需求的任務(wù)分配[9]。S-PSO 在每次迭代求解過(guò)程中，均可獲得多個(gè)任務(wù)序列可行解。

在對(duì)UUV 集群進(jìn)行任務(wù)分配時(shí)，設(shè)一個(gè)粒子的位置為：

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

粒子移動(dòng)速度用可行性概率集合表示：

pij以概率形式表示執(zhí)行完成任務(wù)i后參與任務(wù)j對(duì)應(yīng)的粒子位置元素更新速度。

各個(gè)粒子速度更新公式為：

式中：ω為慣性系數(shù)；系數(shù)c1和c2為給定常數(shù)；系數(shù)r1和r2為位于區(qū)間 [0,1]的隨機(jī)數(shù)；Xbest為該粒子在迭代過(guò)程中使目標(biāo)函數(shù)取值最小的最優(yōu)位置；Pbest為所有粒子的全局最優(yōu)位置。

區(qū)別于傳統(tǒng)S-PSO，在迭代求解過(guò)程中，為提高迭代初期的全局搜索能力，迭代后期的局部搜索精度，慣性系數(shù)采用動(dòng)態(tài)值。其表達(dá)式為：

式中：ωHigh和 ωLow為ω 最大值和最小值；k為當(dāng)前迭代次數(shù)；K為總迭代次數(shù)。

此外，在傳統(tǒng)S-PSO 基礎(chǔ)上，結(jié)合遺傳算法的變異操作，設(shè)各粒子的位置矩陣中的每個(gè)元素在遍歷開始時(shí)均有pm的概率發(fā)生變異，rm為區(qū)間 [0,1]的隨機(jī)數(shù)，則

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

速度更新公式中，矩陣之間的運(yùn)算不再遵循數(shù)值計(jì)算規(guī)則，采用如下運(yùn)算規(guī)則：

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

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

通過(guò)圖1 流程更新獲得的粒子位置X′即為一可行任務(wù)分配序列。將序列代入目標(biāo)函數(shù)，求得對(duì)該任務(wù)分配序列的評(píng)估值。評(píng)估值越小，表明在綜合路程、能耗、總時(shí)間等3 項(xiàng)目標(biāo)下，該任務(wù)分配序列越優(yōu)。通過(guò)迭代求解出使得目標(biāo)函數(shù)取得極小值任務(wù)分配序列，以尋找最優(yōu)任務(wù)分配序列。

3 仿真實(shí)驗(yàn)

3.1 仿真場(chǎng)景設(shè)置

為驗(yàn)證方案的可行性和算法的有效性，對(duì)4 艘UUV 分配10 個(gè)任務(wù)的場(chǎng)景進(jìn)行仿真實(shí)驗(yàn)。為便于分析，使圖像更直觀，假定在執(zhí)行任務(wù)前，各UUV 均需前往給定任務(wù)區(qū)域某坐標(biāo)點(diǎn)位置，從該坐標(biāo)點(diǎn)開始執(zhí)行任務(wù)；全部UUV 初始位置相同，完成自身任務(wù)序列后返回位置相同且與初始位置一致；在分配任務(wù)前，已對(duì)執(zhí)行任務(wù)完成最長(zhǎng)時(shí)間和UUV 最大耗能進(jìn)行預(yù)估。

3.2 仿真結(jié)果及分析

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

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

采用改進(jìn)S-PSO 算法和傳統(tǒng)S-PSO 算法，分別經(jīng)迭代求解獲得4 艘UUV 任務(wù)序列。采用改進(jìn)的SPSO 算法求解獲得的任務(wù)序列如表3 所示，形成如圖2所示航跡圖，橫坐標(biāo)為區(qū)域坐標(biāo)。圖中每個(gè)任務(wù)點(diǎn)對(duì)應(yīng)的3 個(gè)數(shù)字分別表示任務(wù)編號(hào)、在該UUV 任務(wù)序列中的排序、UUV 編號(hào)?？芍?，UUV1 與UUV3 從保障船出發(fā)，共同執(zhí)行完成任務(wù)2 后再分別執(zhí)行其他任務(wù)。UUV2 完成任務(wù)7、任務(wù)10 后，與UUV4 匯合，聯(lián)合執(zhí)行任務(wù)9。由于UUV 能力限制，出現(xiàn)返航補(bǔ)充能量再執(zhí)行任務(wù)的情況。

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

圖2 采用改進(jìn)S-PSO 生成的UUV 任務(wù)序列圖Fig.2 UUVs task sequence with modified S-PSO

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

圖3 傳統(tǒng)S-PSO 生成的UUV 任務(wù)序列圖Fig.3 UUVs task sequence with S-PSO

圖4 評(píng)估值隨迭代次數(shù)收斂情況Fig.4 Convergence of evaluation value with the number of iterations

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

4 結(jié)語(yǔ)

本文針對(duì)多UUV 任務(wù)分配問題，建立包含任務(wù)所需UUV 數(shù)量、能力、UUV 自身功能、UUV 續(xù)航、保障船與UUV 通信距離限制等多約束條件的任務(wù)分配模型。結(jié)合遺傳算法變異操作，采用動(dòng)態(tài)慣性系數(shù)，形成改進(jìn)S-PSO 算法。實(shí)驗(yàn)結(jié)果表明，所提出的多約束多目標(biāo)任務(wù)分配方法，能獲取多UUV 的最優(yōu)任務(wù)分配，算法實(shí)現(xiàn)簡(jiǎn)單，搜索能力較好，滿足UUV 實(shí)際工程應(yīng)用的要求。