基于能量約束的自主水下航行器任務(wù)規(guī)劃算法

趙旭浩 王軼群 劉健 徐春暉

摘 要：多水下自主航行器（AUV）任務(wù)規(guī)劃是影響集群智能水平的關(guān)鍵技術(shù)。針對現(xiàn)有任務(wù)規(guī)劃模型只考慮同構(gòu)AUV集群和單潛次任務(wù)規(guī)劃的問題，提出了適用于AUV異構(gòu)集群的多潛次任務(wù)規(guī)劃模型。首先，該模型考慮了AUV的能量約束、AUV多次往返母船充電的工程代價(jià)、異構(gòu)集群個(gè)體間的效能差異、任務(wù)多樣性等關(guān)鍵因素;然后，為提高問題模型的求解效率，提出了一種基于離散粒子群的優(yōu)化算法，該算法引入用于描述粒子速度、位置的矩陣編碼和用于評估粒子質(zhì)量的任務(wù)損耗模型，改進(jìn)粒子更新過程，實(shí)現(xiàn)了高效的目標(biāo)尋優(yōu)。仿真實(shí)驗(yàn)表明，該算法不僅解決了異構(gòu)AUV集群的多潛次任務(wù)規(guī)劃問題，而且與采用遺傳算法的任務(wù)規(guī)劃模型相比較，任務(wù)損耗降低了11%。

關(guān)鍵詞：自主水下航行器;多AUV集群;任務(wù)規(guī)劃;離散粒子群優(yōu)化;多樣性任務(wù)

中圖分類號：TP242.6

文獻(xiàn)標(biāo)志碼：A

Task planning algorithm of multi-AUV based on energy constraint

ZHAO Xuhao1，2，3，4， WANG Yiqun1，2，3，4*， LIU Jian1，2，3， XU Chunhui1，2，3

1.Shenyang Institute of Automation， Chinese Academy of Sciences， Shenyang Liaoning 110016， China;

2.State Key Laboratory of Robotics （Shenyang Institute of Automation， Chinese Academy of Sciences）， Shenyang Liaoning 110016， China;

3.Institutes for Robotics and Intelligent Manufacturing， Chinese Academy of Sciences， Shenyang Liaoning 110016， China;

4.University of Chinese Academy of Sciences， Beijing 100049，China

Abstract：

Autonomous Underwater Vehicle （AUV） task planning is the key technology that affects the level of cluster? intelligence. In the existing task planning models， only the problem of homogeneous AUV cluster and single dive task planning are considered. Therefore， a multi-dive task planning model for AUV heterogeneous clusters was proposed. Firstly the model considered the energy constraints of AUV， the engineering cost of AUV multiple round-trip charging in mother ship， the efficiency difference between heterogeneous cluster individuals， and the diversity of tasks. Then in order to improve the efficiency of solving the problem model， an optimization algorithm based on discrete particle swarm was proposed. The algorithm introduced matrix coding for describing particle velocity and position and the task loss model for evaluating particle quality to improve the particle updating process， achieving efficient target optimization. Simulation experiments show that the algorithm not only solves the multi-dive task planning problem of heterogeneous AUV clusters， but also reduces the task loss by 11% compared with the task planning model using genetic algorithm.

Key words：

Autonomous Underwater Vehicle （AUV）; multi-AUV cluster; task planning; discrete particle swarm optimization; diverse task

0 引言

自主水下航行器（Autonomous Underwater Vehicle， AUV）是進(jìn)行海洋探索和海洋科學(xué)研究的有效工具。AUV以其智能化、靈活性、快速性成為各國爭相發(fā)展的水下利器[1-2]。隨著近年來機(jī)器人技術(shù)的快速發(fā)展，多 AUV 系統(tǒng)受到廣泛關(guān)注。與單體AUV相比，多AUV系統(tǒng)的作業(yè)范圍更廣，作業(yè)效率更高，而且能夠完成單體AUV不能完成的復(fù)雜海洋探測任務(wù)，在海洋礦產(chǎn)資源調(diào)查、海洋現(xiàn)象觀測、水下目標(biāo)搜索、海洋信息網(wǎng)絡(luò)組建[3]等諸多方面有廣闊的應(yīng)用前景。而多AUV任務(wù)規(guī)劃是多AUV系統(tǒng)協(xié)作的一個(gè)基本問題。多AUV系統(tǒng)的工作場景如圖1所示，多個(gè)不同類型的AUV在水下通信網(wǎng)絡(luò)和母船的支持下協(xié)同完成探測任務(wù)，由于AUV的布放和回收都比較困難，提高能源利用率對AUV意義重大，合理的任務(wù)規(guī)劃能夠提高能源利用率、提高系統(tǒng)的工作效率。

目前多AUV任務(wù)規(guī)劃的研究已經(jīng)取得了很大的進(jìn)展[4]。針對多AUV的任務(wù)規(guī)劃問題，文獻(xiàn)[5]建立了以最大收益為目標(biāo)的任務(wù)規(guī)劃模型，然后用混沌粒子群算法求解，但是所建立的模型只考慮了執(zhí)行任務(wù)的收益和時(shí)間，沒有考慮AUV和任務(wù)之間的距離信息。文獻(xiàn)[6]根據(jù)任務(wù)的位置和能耗建立了多AUV任務(wù)規(guī)劃模型，并且用蟻群算法進(jìn)行求解，但是模型中缺乏傳感器匹配機(jī)制和任務(wù)均衡策略。文獻(xiàn)[7]構(gòu)建了以每個(gè)AUV的能量耗費(fèi)與能耗均衡為約束條件的水下三維空間下的多旅行商問題模型，并且設(shè)計(jì)了考慮巡航總路徑及訪問目標(biāo)數(shù)的適應(yīng)度函數(shù)，但是這種方法沒有考慮任務(wù)的規(guī)模。文獻(xiàn)[8]用自組織神經(jīng)網(wǎng)絡(luò)求解AUV的任務(wù)規(guī)劃和路徑規(guī)劃問題，但是沒有考慮AUV的能量約束和傳感器約束。文獻(xiàn)[9]以使用最少的AUV為目標(biāo)，建立了只考慮傳感器匹配和時(shí)間限制的整數(shù)規(guī)劃模型。文獻(xiàn)[10]首先建立了每個(gè)AUV和每個(gè)任務(wù)之間的匹配矩陣，然后以多目標(biāo)元啟發(fā)式方法求解滿足約束的最優(yōu)解，實(shí)現(xiàn)了AUV和任務(wù)之間的合理匹配。文獻(xiàn)[11]用基于市場的分布式方法解決AUV的任務(wù)分配問題，這種方法能夠合理地處理各類約束，但是對通信的穩(wěn)定性要求比較高。文獻(xiàn)[12]研究了AUV和無人機(jī)的任務(wù)協(xié)同，并且提出了考慮時(shí)間窗口的任務(wù)分配模型，取得了較好的效果。

上述文獻(xiàn)在一定程度上能夠進(jìn)行多AUV的任務(wù)規(guī)劃，但是所建立的模型不能夠反映多AUV集群的實(shí)際工作過程。首先，作者都假設(shè)在一次任務(wù)規(guī)劃過程中所有的AUV有能力執(zhí)行完所有的任務(wù)，或者只分配AUV能夠承擔(dān)的任務(wù)，或者直接不考慮AUV的數(shù)量。但實(shí)際情況是，AUV一次下潛所能探測的區(qū)域遠(yuǎn)遠(yuǎn)小于所要探測的海洋區(qū)域，AUV不可能一次作業(yè)下潛就能夠執(zhí)行完所有任務(wù)，往往需要多次回母船補(bǔ)充能源，多次下潛才能夠完成任務(wù)。再者，AUV執(zhí)行任務(wù)主要依靠AUV自身所攜帶的傳感器和探測設(shè)備，而不同的任務(wù)也是根據(jù)需要的傳感器和設(shè)備來區(qū)分的，因此，考慮AUV的異構(gòu)和任務(wù)的多樣性至關(guān)重要。

因此，本文在上述文獻(xiàn)的基礎(chǔ)上建立了新的多AUV任務(wù)規(guī)劃模型，考慮了AUV回母船充電的過程，對AUV在各個(gè)任務(wù)點(diǎn)的能量變化進(jìn)行了精細(xì)建模，在滿足傳感器約束的條件下能夠?yàn)榧簝?nèi)的每條AUV規(guī)劃多次作業(yè)下潛。新模型以AUV的下潛次數(shù)和任務(wù)時(shí)長為優(yōu)化目標(biāo)，能夠在下潛次數(shù)和任務(wù)時(shí)長之間達(dá)到平衡。改進(jìn)了一種新型的離散粒子群算法對異構(gòu)多AUV任務(wù)規(guī)劃模型求解，設(shè)計(jì)了矩陣編碼的方式表示粒子位置和粒子速度，將約束的處理加入到了粒子的編碼和更新過程中。

1 問題描述

多個(gè)AUV組成編隊(duì)協(xié)同執(zhí)行海洋探測任務(wù)時(shí)，海洋探測任務(wù)需求不同，需要不同的AUV完成不同的任務(wù)，因此本文建立了AUV傳感器向量和任務(wù)傳感器向量，用來完成AUV和任務(wù)之間的匹配。另外，有時(shí)候任務(wù)的工作量較大，所有的AUV一次下潛并不能完成所有任務(wù)，必須將AUV回母船或者回水下基站充電的過程在任務(wù)規(guī)劃模型中體現(xiàn)出來。針對上述問題，本文在模型中用多個(gè)虛擬充電點(diǎn)來模擬AUV多次回母船充電的過程，AUV經(jīng)過一個(gè)虛擬充電時(shí)，表示AUV返回了母船一次。

執(zhí)行海洋探測任務(wù)時(shí)，AUV的操控者和海洋科學(xué)家所關(guān)心的目標(biāo)主要有兩點(diǎn)：第一是執(zhí)行任務(wù)的時(shí)間;第二是AUV的下潛次數(shù)。在多AUV的場景下，這兩個(gè)目標(biāo)是存在矛盾的，多個(gè)小型的AUV同時(shí)下潛能夠執(zhí)行完的任務(wù)對于大型AUV來說一次下潛就能夠完成，如何平衡這兩種目標(biāo)是關(guān)鍵。

問題的假設(shè)條件如下：AUV的電量有限，只存在一條母船，AUV都從母船出發(fā)，母船的位置固定不變，AUV從母船出發(fā)時(shí)都是滿電狀態(tài)，AUV都能夠順利地執(zhí)行完任務(wù)。

2 任務(wù)分配建模

多AUV任務(wù)分配模型描述如下：多樣性任務(wù)點(diǎn)的集合為T，異構(gòu)AUV的集合為R，一條母船。AUV要經(jīng)過多次回母船充電的過程然后執(zhí)行完這些任務(wù)。模型參數(shù)如表1所示。

2.1 建立模型

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

目標(biāo)函數(shù)（1）中的Z1是所有AUV的充電成本，再加上AUV在執(zhí)行任務(wù)的過程中行駛的總路程。從目前來看，首先AUV的回收和布放都是帶有危險(xiǎn)性的作業(yè)，所以應(yīng)盡量減少AUV回母船充電的次數(shù);其次，即使將來采用了水下基站的方式進(jìn)行充電，AUV和基站的對接過程依舊是耗時(shí)、耗力的工作;最后，現(xiàn)階段AUV所使用特殊電池的使用壽命和陸地電池還有差距。因此，應(yīng)該保證以最少的充電次數(shù)就能夠完成任務(wù)。同時(shí)，采用多AUV編隊(duì)的目的就是要減少任務(wù)的時(shí)長，因此AUV執(zhí)行任務(wù)的時(shí)長也應(yīng)該在目標(biāo)函數(shù)中有所體現(xiàn)，多AUV執(zhí)行任務(wù)是一個(gè)并行系統(tǒng)，其任務(wù)時(shí)長應(yīng)該用運(yùn)行時(shí)間最長的那臺AUV的運(yùn)行時(shí)間來表示。綜上，可以得到Z1和Z2兩個(gè)目標(biāo)函數(shù)，Z1是充電成本和AUV在任務(wù)點(diǎn)之間的行駛距離相加，Z2是所有AUV中最大的那個(gè)任務(wù)時(shí)長，并且使用ω1和ω2兩個(gè)參數(shù)調(diào)整它們的權(quán)重，可以根據(jù)重視程度來調(diào)整，這樣既能夠保證機(jī)器人的能源得到最大的利用，又能夠優(yōu)化機(jī)器人的運(yùn)行時(shí)間。

Min Ζ = ω1Z1+ω2Z2（1）

Z1=∑r∈R∑i∈V∑m∈MCxrim+∑r∈R∑i∈V∑j∈V″dijxrij （2）

Z2=maxr∈R∑r∈R∑i∈V∑j∈V″xrij（dij+Wi）/speedr（3）

ω1+ω2=1（4）

2.2 約束條件

1）每個(gè)任務(wù)只能被執(zhí)行一次。

∑r∈R∑i∈Vxrij=1; ?j∈T（5）

2）虛擬充電點(diǎn)有可能被使用，也有可能不被使用。

∑r∈R∑i∈Vxrim≤1; ?m∈M（6）

3）所有AUV都必須從起點(diǎn)出發(fā)。

∑j∈V′xrOj=1; ?r∈R（7）

4）所有AUV都不能再回到起點(diǎn)。

∑j∈VxrjO=0; ?r∈R（8）

5）所有AUV最終都必須回到終點(diǎn)。

∑j∈VxrjO′=1; ?r∈R（9）

6）所有AUV都不能從終點(diǎn)出發(fā)。

∑j∈VxrO′j=0; ?r∈R（10）

7）必須遵循流量守恒原則，AUV不能在任務(wù)點(diǎn)之間跳躍。

∑i∈Vxrij=∑i∈V″xrji;j∈V′，r∈R（11）

8）能量約束，AUV在一個(gè)任務(wù)點(diǎn)的剩余能量必須保證能到達(dá)下一個(gè)任務(wù)點(diǎn)，Ermax是松弛條件，保證沒有連接關(guān)系的任務(wù)點(diǎn)也能滿足約束。

E1jr≤E2ir-dijλrxrij+Ermax（1-xrij）; i， j∈V，r∈R（12）

9）AUV在離開起點(diǎn)時(shí)是滿電量狀態(tài)。

E2Or=Ermax; ?r∈R（13）

10）AUV在離開虛擬充點(diǎn)電時(shí)是滿電量狀態(tài)。

E2ir=Ermax∑j∈Vxrij; ?r∈R，i∈M（14）

11）離開任務(wù)點(diǎn)的能量為到達(dá)任務(wù)點(diǎn)的能量減去執(zhí)行任務(wù)消耗的能量。

E2ir=E1ir-Wi∑j∈Vxrij; ?r∈R，i∈T（15）

12）要保證在每個(gè)任務(wù)點(diǎn)執(zhí)行完任務(wù)都能回到終點(diǎn)。

E2ir≥λrdiO′; ?r∈R，i∈T（16）

13）傳感器匹配約束，對于不同的AUV來說，最大的區(qū)別就是傳感器，不同的任務(wù)之間的區(qū)別也是是否需要某種傳感器，因此本文引入了AUV傳感器向量和任務(wù)傳感器向量。sensorr和sensorj都是內(nèi)容為0和1的向量，維度相同，sensorr的每一位都要大于sensorj。

3 改進(jìn)基于集合的粒子群算法

基于集合的粒子群（Set-based Particle Swarm Optimization， S-PSO）算法[13]是一種特殊的離散粒子群算法，

相比于常見的離散粒子群算法[14]，它的特點(diǎn)在于用集合的概念來表示粒子的位置和速度，粒子的更新過程用集合運(yùn)算來代替，最大的優(yōu)點(diǎn)在于每次粒子更新都能夠得到滿足約束的解。S-PSO算法常常用來解決離散領(lǐng)域的組合優(yōu)化問題[15]。S-PSO算法的搜索空間用一個(gè)全集S表示，每個(gè)維度代表S的一個(gè)子集Si（i=1，2，…，D），即：

S=S1∪S2∪…∪SD（18）

每個(gè)粒子位置X都是全集S的一個(gè)子集，XS，X可以表示為：

X=X1∪X2∪…∪XD; XiSi（i=1，2，…，D）（19）

如果X能夠滿足所有約束，X就是一個(gè)可行解。在基于集合的粒子群算法中，速度使用一個(gè)可能性集合來表示[13]：

V={e/p（e）|e∈E}（20）

3.1 粒子編碼

按照上述思想，設(shè)計(jì)多AUV任務(wù)分配求解問題的編碼方式如下：

Xi=010001100

VELi=00.50.80.800.630.390.220

Xi是一個(gè)0-1矩陣，表示粒子的位置編碼;VELi的每一個(gè)元素值都在[0，1]區(qū)間，表示粒子的速度編碼，其中矩陣的維度也是粒子的維度，在本文的問題中，粒子的維度就代表任務(wù)的數(shù)量。

3.2 速度更新公式

S-PSO算法主要利用綜合學(xué)習(xí)公式，這樣能避免粒子早熟。

VELid=ω×VELid+c×rd×（Pid-Xid）（21）

但是S-PSO算法重新定義了式（21）的各個(gè)運(yùn)算符，將上述的運(yùn)算符操作改為了概率之間的運(yùn)算和集合之間的運(yùn)算。式（22）～（25）中的i代表粒子編號，d代表維度，在本文的問題中，第d維元素就是所有和任務(wù)d有連接關(guān)系的任務(wù)?！磚，v〉就代表著這種連接關(guān)系， p（u，v）表示這種連接關(guān)系對應(yīng)的概率。

假設(shè)當(dāng)前粒子位置如Xi所示，粒子速度如VELi所示，而目前的最優(yōu)粒子為：

Pi=001100010

如果要計(jì)算維度2的粒子速度更新結(jié)果，那么：

Xi2={〈1，2〉，〈2，3〉}

Pi2={〈3，2〉，〈2，1〉}

U2={〈3，2〉，〈2，1〉}

假設(shè)c=0.5

c×Ud={〈3，2〉/0.5，〈2，1〉/0.5}

c×VELi2={〈1，2〉/0.25，〈2，1〉/0.4，〈2，3〉/0.315，〈3，2〉/0.11}

那么

c×VELi2+c×Ud={〈1，2〉/0.25，〈2，1〉/0.5，〈2，3〉/0.315，〈3，2〉/0.5}

就得到了更新之后的速度值，同時(shí)可以看到有關(guān)維度2的概率值得到了更新，并且概率值得到了提升，表示從最優(yōu)粒子中學(xué)到了知識。

3.3 位置更新

原始的粒子群算法的位置更新公式為：

Xi-new=Xi+Vi（26）

而S-PSO算法將式（26）中的加法運(yùn)算符改成了如算法1所示的集合運(yùn)算操作。在文獻(xiàn)[15]中，作者將S-PSO應(yīng)用到了多車輛路徑問題上，但是本文的問題和多車輛路徑問題有一定差異。因?yàn)槎嘬囕v問題不考慮車輛的異構(gòu)性，不考慮車輛的數(shù)量，而AUV的異構(gòu)性是本文的主要關(guān)注點(diǎn)，因此，本文在原有的粒子位置更新算法中加入了隨機(jī)選擇AUV的過程和傳感器匹配的過程，改進(jìn)后的粒子更新過程如算法1所示。

算法1 粒子位子更新過程。

輸入：速度，原有粒子;

輸出：新粒子。

有序號的程序——————————Shift+Alt+Y

程序前

Pv為速度編碼矩陣;Px為當(dāng)前位置矩陣;PE為所有位置都為1的矩陣。P′X為保存新粒子，i為當(dāng)前已分配的任務(wù)， j為下一個(gè)任務(wù)。

1）

Convert（Pv）//將小于0.5的概率值置0

2）

While（還有任務(wù)沒有被分配）

3）

If存在Pv（i， j）>0且滿足約束

4）

從滿足條件的集合中以距離最短的標(biāo)準(zhǔn)從Pv中選擇j

5）

end if

6）

If在Pv中沒有找到滿足約束的任務(wù)

7）

從Px中尋找滿足條件的j

8）

end if

9）

If在Px、Pv中都沒有找到

從PE中尋找滿足約束的任務(wù)

10）

end if

11）

If從上述3個(gè)集合中都沒找到合適的任務(wù)

12）

說明當(dāng)前機(jī)器人不合適，以隨機(jī)選擇的方式更換AUV并且記錄當(dāng)前的i和AUV，讓當(dāng)前AUV回到終點(diǎn)，即P′X（i，1）=1

13）

end if

14）

i=j;將j加入到已分配任務(wù)序列中

15）

end while

16）

return P′X

程序后

上述算法模擬的過程是：按照AUV的編號隨機(jī)選擇一個(gè)AUV，給AUV分配滿足約束的任務(wù)，直到AUV達(dá)到電池容量約束或者再沒有合適的任務(wù)可以執(zhí)行，然后讓該AUV回到母船充電，再次隨機(jī)選擇新的AUV，直到所有任務(wù)分配完畢。該算法在更新粒子的過程中能夠保證上述模型中的約束都能夠得到滿足，因此，一次循環(huán)之后得到的一定是一個(gè)可行解。

3.4 粒子評估

粒子評估采用上文中建立的多目標(biāo)函數(shù)，目標(biāo)函數(shù)的值代表著執(zhí)行任務(wù)總的損耗，這個(gè)損耗既有電池能量上的損耗也包括時(shí)間上的損耗，任務(wù)損耗的值越小，表明粒子的適應(yīng)度越好。

3.5 粒子解碼

假設(shè)有一個(gè)起點(diǎn)（終點(diǎn)和起點(diǎn)相同）和3個(gè)待分配任務(wù)的問題，那么這個(gè)粒子位置的一種可能性如下：

P=0101100010000010

從這個(gè)矩陣中可以得到P（1，2）=1，P（2，1）=1，P（1，4）=1，P（4，3）=1，P（3，1）=1。那么這3個(gè)任務(wù)就是依靠AUV的兩次下潛來完成的，執(zhí)行任務(wù)的順序分別是1-2-1和1-4-3-1。雖然得到了兩次下潛執(zhí)行任務(wù)的順序，但是不知道由哪個(gè)AUV執(zhí)行的任務(wù)。好在在粒子更新的過程中記錄了每個(gè)粒子在更新AUV時(shí)，前一個(gè)AUV執(zhí)行的最后一個(gè)任務(wù)編號以及AUV型號，這樣就能到解碼得到每個(gè) AUV所要執(zhí)行的任務(wù)。

3.6 S-PSO算法總流程

S-PSO算法的工作流程和原始粒子群算法的流程沒有區(qū)別，流程如圖2所示。

4 仿真分析

本文的實(shí)驗(yàn)環(huán)境為I5-6300HQ，8GB RAM，實(shí)驗(yàn)軟件為Matlab R2016a。仿真實(shí)驗(yàn)的基本參數(shù)為：粒子種群數(shù)量為20，慣性參數(shù)為2，加速度系數(shù)為0.7，目標(biāo)函數(shù)中的ω1=0.5，ω2 = 0.5，總的任務(wù)數(shù)量為30個(gè)。表2展示的是30個(gè)任務(wù)的信息，任務(wù)信息中分別有4個(gè)數(shù)字，這4個(gè)數(shù)字的含義分別是（任務(wù)橫坐標(biāo)/km，任務(wù)縱坐標(biāo)/km，任務(wù)代價(jià)/（kW·h），任務(wù)所需傳感器向量）。編號1屬于母船，母船的位置是（35，35）。

仿真實(shí)驗(yàn)設(shè)定有4條AUV，每條AUV的參數(shù)設(shè)置如表3所示，其中電池表示AUV的電池容量，可以看到4條AUV所擁有的傳感器都不一樣。其中AUV2和AUV3能夠執(zhí)行執(zhí)行所有的任務(wù)，而AUV1和AUV4只能夠執(zhí)行部分任務(wù)。這樣的參數(shù)設(shè)置能夠最大限度地保證AUV之間的異構(gòu)性，也能夠有效地測試算法的有效性。AUV行駛單位距離所用的電量都設(shè)為λr=1。充電成本設(shè)為100。

首先，對待分配的任務(wù)量小于多AUV系統(tǒng)一次下潛的工作量的情況進(jìn)行仿真。從上述30個(gè)任務(wù)中抽取前10個(gè)任務(wù)，分配給4個(gè)AUV。粒子群算法迭代200次，結(jié)果如圖3（a）所示，可以看到AUV1-AUV3分配得到了任務(wù)，而AUV4沒有分配到任務(wù)。因?yàn)榍?0個(gè)任務(wù)都需要傳感器S2，AUV4沒有這個(gè)傳感器，所以AUV4沒有分配到任務(wù);再者，能夠執(zhí)行任務(wù)的AUV都被分配到了任務(wù)，沒有單個(gè)AUV負(fù)載過重的情況，而且AUV3的電池容量最大，它承擔(dān)的任務(wù)也最多，帶來了最少的下潛次數(shù)，任務(wù)分配的結(jié)果完全符合目標(biāo)函數(shù)的設(shè)定。

圖3（b）和表4展示的是把30個(gè)任務(wù)分配給4個(gè)AUV的結(jié)果，粒子群算法迭代1000次。30個(gè)任務(wù)的工作量明顯超過了多AUV系統(tǒng)一次下潛的工作量，因此AUV2和AUV3都下潛了兩次，而AUV4單次下潛執(zhí)行的任務(wù)最多，這種情況非常符合所設(shè)計(jì)的目標(biāo)函數(shù)。首先，目標(biāo)函數(shù)中的Z1是最小化下潛次數(shù)，AUV4的電池容量最大，它基本上執(zhí)行了它所能執(zhí)行的所有任務(wù)，AUV2和AUV3的能力最強(qiáng)，能執(zhí)行所有任務(wù)，所以這兩個(gè)AUV執(zhí)行的任務(wù)也多，符合目標(biāo)函數(shù)的設(shè)定。如果只看Z1，最優(yōu)的情況應(yīng)該是AUV3和AUV4執(zhí)行完所有的任務(wù)，只有這樣分配任務(wù)才能得到最少的下潛次數(shù)，但是這樣會造成任務(wù)執(zhí)行時(shí)間過長，失去了部署多AUV執(zhí)行任務(wù)的意義。所以，本文在目標(biāo)函數(shù)中加入了Z2，同時(shí)實(shí)驗(yàn)結(jié)果也體現(xiàn)了目標(biāo)函數(shù)一和目標(biāo)函數(shù)二之間的均衡，AUV1號和AUV2分擔(dān)了一部分任務(wù)，將任務(wù)時(shí)長降低，如果在AUV3執(zhí)行任務(wù)期間多次派遣AUV1執(zhí)行任務(wù)，確實(shí)可以進(jìn)一步減少任務(wù)執(zhí)行時(shí)間，但是這樣又會造成下潛次數(shù)增加，給保障工作帶來負(fù)擔(dān)。

[9]GRAY G， MAHMUT K， LOVELL S D， et al. Automated mission parallelization for a group of UUVs [C]// Proceedings of the 15th International Symposium on Unmanned Untethered Submersible Technology. Durham： Durham NH， 2007： 28-40.

GIGER G， KANDEMIR M， Dan LOVELL S， et al. Automated mission parallelization for a group of UUVs [C]// Proceedings of the 15th International Symposium on Unmanned Untethered Submersible Technology. Durham： Durham NH， 2007： 28-40.

GIGER G， KANDEMIR M， Dan LOVELL S， et al. Automated mission parallelization for a group of UUVs [EB/OL]. [2019-01-12]. https：//www.researchgate.net/publication/228900865_Automated_Mission_Parallelization_for_a_Group_of_UUVs.

[10]LANDA-TORRES I， MANJARRES D， BILBAO S， et al. Underwater robot task planning using multi-objective meta-heuristics [J]. Sensors， 2017， 17（4）： Ariticle No. 762.

[11]DENG Y， BEAUJEAN P P J， AN E， et al. Task allocation and path planning for collaborative autonomous underwater vehicles operating through an underwater acoustic network [J]. Journal of Robotics， 2013（10）： 1-9.

[12]WILDE J， DIBIASO D， NERVEGNA M. Team planning for unmanned vehicles in the risk-aware mixed-initiative dynamic replanning system [C]// Proceedings of the OCEANS 2007. Piscataway， NJ： IEEE， 2007： 1-8.

[13]CHEN W， ZHANG J， CHUNG H S H， et al. A novel set-based particle swarm optimization method for discrete optimization problems [J]. IEEE Transactions on Evolutionary Computation， 2010， 14（2）： 278-300.

[14]程畢蕓，魯海燕，徐向平，等.求解旅行商問題的改進(jìn)局部搜索混沌離散粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2016，36（1）：138-142.（CHEN B Y， LU H Y， XU X P，et al. Improved local-search-based chaotic discrete particle swarm optimization algorithm for solving traveling salesman problem [J]. Journal of Computer Applications， 2016， 36（1）： 138-142.）

[15]GONG Y， ZHANG J， LIU O， et al. Optimizing the vehicle routing problem with time windows： a discrete particle swarm optimization approach [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C （Applications and Reviews）， 2012， 42（2）： 254-267.

This work is partially supported by the National Key Research and Development Program of China（2017YFC0306800）.

ZHAO Xuhao， born in 1994， M. S. candidate. His research interests include task planning of multi-AUV.

WANG Yiqun， born in 1985， M. S.， associate research fellow. His research interests include navigation methods and path planning algorithms of underwater AUVs.

LIU Jian， born in 1962， M. S.， research fellow. His research interests include navigation methods and control algorithms of underwater AUVs.

XU Chunhui， born in1982， M. S.， associate research fellow. His research interests include control algorithms of underwater AUVs.