馬 碩，馬亞平

(1.國防大學(xué) 研究生院，北京 100091；2.國防大學(xué) 軍事管理學(xué)院，北京 100091)

0 引 言

無人水下航行器（UUV）能夠有效降低海上作業(yè)風(fēng)險、提高作業(yè)效率，已廣泛應(yīng)用于水下目標(biāo)搜索和海洋環(huán)境調(diào)查[1]。為了進(jìn)一步提高水下搜索的工作效率、可靠性和靈活性，采用多種類型UUV組成異構(gòu)集群協(xié)作系統(tǒng)是未來主要發(fā)展趨勢。在執(zhí)行水下探測任務(wù)的集群UUV系統(tǒng)中，根據(jù)功能定位不同，可以分為探測型UUV（SVs）、識別型UUV（CVs）、導(dǎo)航型UUV（NVs）等。SVs搭載側(cè)掃聲吶、前視聲吶、合成孔徑聲吶等對水下目標(biāo)進(jìn)行快速大范圍搜索、定位，基于已獲取的水下圖像，通過目標(biāo)輔助檢測/識別技術(shù)（CAD/CAC）自動實(shí)現(xiàn)圖像中疑似目標(biāo)（OI）的標(biāo)示[2]，并將OI信息發(fā)送給系統(tǒng)中各CV。CVs根據(jù)OI位置分布情況進(jìn)行實(shí)時在線分配，使用高分辨率識別聲吶、水下光學(xué)攝像機(jī)等近距離對MLO進(jìn)行識別，確認(rèn)是否為搜尋目標(biāo)。集群UUV系統(tǒng)多目標(biāo)任務(wù)分配的主要目的是將SV發(fā)現(xiàn)的目標(biāo)分配給CVs，使得識別目標(biāo)的總代價（航程、時間等）最小。

目前無人系統(tǒng)任務(wù)分配方法可分為分布式和集中式2種。分布式任務(wù)分配方法主要采用基于市場的協(xié)商拍賣機(jī)制[3]。如果待分配的目標(biāo)任務(wù)只有一個，可以使用傳統(tǒng)的合同網(wǎng)由無人系統(tǒng)根據(jù)各自局部信息對目標(biāo)分別投標(biāo)競爭擇優(yōu)；但對于多個目標(biāo)的情況，由于目標(biāo)和無人系統(tǒng)之間存在復(fù)雜的組合關(guān)系（對n個目標(biāo)，每個無人系統(tǒng)都存在種組合投標(biāo)方案），對集群UUV系統(tǒng)通信速率、容量和可靠性的要求很高，在復(fù)雜多變的水聲信道中，難以實(shí)現(xiàn)。針對這個問題，目前一種解決思路是降低系統(tǒng)通信負(fù)載量[4]，由1艘UUV集中收集系統(tǒng)其他UUV的相關(guān)信息，對各UUV執(zhí)行各種組合方案的代價計(jì)算選優(yōu)，存在的問題是計(jì)算量大，目標(biāo)數(shù)量較多的情況下無法滿足實(shí)時性；另一種解決思路是使用聚類方法對目標(biāo)分組以縮減組合空間，Saha等[5]提出基于k-均值的聚類拍賣分配以及多目標(biāo)優(yōu)化方法，Murugappan等[6]提出了考慮任務(wù)負(fù)載均衡因素的k-均值聚類分配方法，存在主要的問題是k-均值聚類需要指定聚類的數(shù)量，聚類結(jié)果對初值敏感，影響對目標(biāo)分組效果以及最終優(yōu)化目標(biāo)，此外沒有考慮無人系統(tǒng)原有的任務(wù)序列以及剩余能源可行性的因素。集中式任務(wù)分配方法由指定的無人系統(tǒng)進(jìn)行全局規(guī)劃，將得到的分配方案指派給相關(guān)無人系統(tǒng)執(zhí)行，可以歸結(jié)為多倉庫開放式多旅行商問題模型（multiple depot Open Multiple traveling salesmen problem，MDOMTSP）[7-8]，存在的主要問題是計(jì)算量大，對通信可靠性要求高，難以綜合考慮旅行商數(shù)量的選擇、旅行商任務(wù)執(zhí)行的可行性以及任務(wù)負(fù)載量的權(quán)衡等多方面因素。

UUV通常采用電池作為能源[9]，航程相對較短，與任務(wù)分配的均衡性相比，能源消耗是否滿足任務(wù)需要，是實(shí)際使用中更為關(guān)注的因素；此外，已有研究工作主要是在固定條件下靜態(tài)分析，沒有考慮系統(tǒng)異常、能源不足等實(shí)際條件動態(tài)變化的問題。根據(jù)水下目標(biāo)搜索任務(wù)的特點(diǎn)，提出一種基于分層聚類拍賣的集群UUV系統(tǒng)多目標(biāo)任務(wù)分配方法（Hierarchical clustering auction-based multiple objects allocation approach，HCAMOA），采用基于最小生成樹（Minimum Spanning Tree，MST）的層次化目標(biāo)分組聚類方法，改進(jìn)k-均值聚類分組存在的問題，提出2種水下目標(biāo)任務(wù)分配模式模型，研究了相應(yīng)的任務(wù)分配方法；針對故障或能源不足等異常情況，提出了任務(wù)調(diào)整機(jī)制。

1 基于聚類拍賣的集群UUV系統(tǒng)多目標(biāo)任務(wù)分配方法

1.1 任務(wù)描述及模型

SVs對海區(qū)搜索，由n艘CVs組成的UUV集群V={V1，···，Vn}對探測到的 OI進(jìn)行識別。CV 當(dāng)前需要執(zhí)行的任務(wù)集合稱為任務(wù)序列（符號TV），第c艘CV長度為k的當(dāng)前任務(wù)序列表示為TVc={tvc1，···，tvck}（tvci∩tvcj=?，i，j∈{1，···，k},i≠j，c∈{1，···，n}）。當(dāng) SVs檢測到m個新目標(biāo) NT= {t1，···，tm}后，向CVs廣播。CVs接到任務(wù)，各自從當(dāng)前位置P={P1，···，Pn}出發(fā)依次訪問任務(wù)序列中的OI位置。任務(wù)分配的目標(biāo)是滿足規(guī)定的約束條件下，使CVs的總航程最短。水下多目標(biāo)識別任務(wù)分配有2種模式：

1）異步分配模式（Asynchronous Allocation Mode，AAM）

當(dāng)SV發(fā)布目標(biāo)信息時，CVs各自的任務(wù)序列TVc與新目標(biāo)NT一起構(gòu)成任務(wù)集合T=TV1∪...∪TVn∪NT。該模式需將系統(tǒng)所有待識別的OI重新分配給CVs，優(yōu)點(diǎn)是可以實(shí)現(xiàn)全局優(yōu)化，但計(jì)算量相對較大。為避免頻繁的重新分配任務(wù)，SVs應(yīng)在完成一定海域面積的探測任務(wù)工作后發(fā)布目標(biāo)信息。異步分配模式數(shù)學(xué)模型為：

式中：i和j為位置下標(biāo)，表示UUV或目標(biāo)位置；cij表示從位置i到位置j的航程；xij為0-1變量，1表示從位置i到j(luò)存在路徑，0表示沒有；TC表示總航程。

式（2）表示對任意一個目標(biāo)t∈T，都有且只有一次訪問。式（3）表示CV不能同時訪問多個目標(biāo)。式（4）表示訪問路徑是無環(huán)的。

2）同步分配模式（Synchronous Allocation Mode，SAM）

該模式只分配新發(fā)現(xiàn)的目標(biāo)集合NT，因此任務(wù)分配的計(jì)算量相對較小。對于任一Vc∈V，其任務(wù)序列TVc與分配給Vc的新目標(biāo)集NTc（NTc∈NT，NT1∪···∪NTn=NT，NTi∩NTj=?，i，j∈{1，···，k},i≠j）組合成新的任務(wù)序列ntvc。相對異步分配模式，雖然不能實(shí)現(xiàn)全局優(yōu)化，但實(shí)時性相對較好，在任務(wù)過程中，SVs能夠不斷的將新發(fā)現(xiàn)的目標(biāo)分配給CVs識別，適用于小數(shù)量多批次分配目標(biāo)的場合。同步分配模式數(shù)學(xué)模型為：

式中：pathc為第c艘UUV的訪問路徑航程，其余符號定義和公式意義參見上文中的相關(guān)說明。

1.2 HCAMOA方法流程

1.2.1 工作流程

HCAMOA方法采用基于市場的拍賣機(jī)制，基本流程見圖1所示。在AAM模式下，SV首先收集所有CVs的位置和任務(wù)信息，生成目標(biāo)集合T；在SAM/AAM模式下，對T進(jìn)行分層聚類分組，將T分成d個任務(wù)包，任務(wù)包集合為TP={tp1，···，tpd}（對任一tpi∈TP，tpi?T）。分組完成后，SV發(fā)布TP拍賣信息，CVs根據(jù)任務(wù)分配模式對TP各任務(wù)包計(jì)算執(zhí)行代價NC，進(jìn)行投標(biāo)。SV收到投標(biāo)信息后，計(jì)算最優(yōu)的任務(wù)組合方式，通知CVs中標(biāo)情況以及相應(yīng)的任務(wù)包。最后CVs接收中標(biāo)信息并確認(rèn)。

圖1 HCAMOA方法處理流程Fig.1 Procedure of HCAMOA method

1.2.2 分層聚類分組

分層聚類將所有目標(biāo)點(diǎn)自底而上逐層分類，算法1分為聚類和分組2個步驟。

1）聚類

最小生成樹能夠構(gòu)建目標(biāo)集合中連接各點(diǎn)的極小連通子圖，是求解旅行商問題一種啟發(fā)式方法[10]，因此基于MST對水下目標(biāo)點(diǎn)集合進(jìn)行聚類分組。

定義1：2個目標(biāo)點(diǎn)集合T1、T2之間距離D，為以T1∪T2為節(jié)點(diǎn)所構(gòu)成連通圖的MST權(quán)值，即D=MST（T1∪T2）。

聚類過程示例如圖2所示。圖中左半部分為目標(biāo)點(diǎn)分布，右半部分為對應(yīng)的聚類過程，將6個目標(biāo)劃為 5 種分類：{t1，···，t6}，{t1，t3}，{t2，t4}，{t5，t6}，{t1，t2，t3，t4}，最終形成二叉樹結(jié)構(gòu)的聚類樹。

圖2 基于最小生成樹的聚類過程示例Fig.2 Demonstration of clustering process based on minimum spanning tree

2）分組

設(shè)定若干門限值，根據(jù)聚類結(jié)果將目標(biāo)集分組為任務(wù)包TP，每個門限值決定一個分組的層級。門限值的設(shè)定可以根據(jù)分類情況，按最大MST權(quán)值（即MST（T）值）的比例確定（如分為50%，25%兩個檔）。對16個目標(biāo)分組過程示例如圖4所示，圖中左半部分為目標(biāo)點(diǎn)平面分布，右半部分為聚類樹以及對應(yīng)的任務(wù)包分組情況，聚類樹中的虛線分別表示2個MST權(quán)值門限，按不同的門限對聚類結(jié)果進(jìn)行分組，第1個門限1 195將11個分類劃為5組，第2個門限2 391將11個分類劃為3組，加上16個目標(biāo)，以及所有目標(biāo)組成的任務(wù)包，共計(jì)25個任務(wù)包（圖中右半部分圈內(nèi)所示）。TP之間組成樹形結(jié)構(gòu)。

1.2.3 CVs投標(biāo)

CVs分別對各任務(wù)包計(jì)算執(zhí)行代價NC（即航程，第i艘CV的NCcvi={NCtp1，...，NCtpd}）。NC有2種計(jì)算方法：基于MST的快速啟發(fā)式算法（Fast Heuristic Algorithm Based on MST，H-MST）和基于遺傳算法的開放式單旅行商求解模型（Open Traveling Salesman Problem based on GA，GA-OTSP）[11]。H-MST 以MST權(quán)值替代航程作為執(zhí)行代價的估計(jì)值，計(jì)算速度相對較快；GA-OTSP以CV當(dāng)前位置點(diǎn)為起點(diǎn)，計(jì)算遍歷任務(wù)包中各目標(biāo)位置的最小航程，且不返回起點(diǎn)，使用遺傳算法不一定能得到最優(yōu)解，但有限時間內(nèi)可以獲得相對較優(yōu)的方案。在2種任務(wù)分配模式下，計(jì)算執(zhí)行代價的位置點(diǎn)集合有所不同：SAM模式時，位置點(diǎn)集合為任務(wù)包、CV任務(wù)序列和CV當(dāng)前位置點(diǎn)的并集；而AAM模式時，位置點(diǎn)集合不包括CV的任務(wù)序列。GA-OTSP方法可以準(zhǔn)確計(jì)算航程，當(dāng)CV剩余航程不足以完成某個任務(wù)包tpi時，則在投標(biāo)信息中加入tpi的投標(biāo)失敗標(biāo)識，不參與tpi的投標(biāo)。

1.2.4 中標(biāo)

SV接收到CVs的投標(biāo)信息后，根據(jù)NC的大小，對TP進(jìn)行擇優(yōu)中標(biāo)操作。從TP樹形結(jié)構(gòu)最底層的葉子節(jié)點(diǎn)開始，自底而上逐層比較。

圖3 聚類分組過程示例Fig.3 Demonstration of clustering process

1.2.5 系統(tǒng)異常情況的任務(wù)處理機(jī)制

引發(fā)異常情況問題的主要原因包括：受環(huán)境等條件影響，導(dǎo)致CV實(shí)際能耗大于預(yù)計(jì)值，如避障、逆流航行等情況，導(dǎo)致剩余能源不足以完成所分配的任務(wù)；CV系統(tǒng)發(fā)生故障退出，無法完成其后續(xù)的任務(wù)；快速啟發(fā)式方法H-MST只是實(shí)現(xiàn)了對執(zhí)行代價的估計(jì)值，與實(shí)際航程有一定出入，可能發(fā)生剩余能源不足的問題。發(fā)生異常情況導(dǎo)致后續(xù)任務(wù)執(zhí)行失敗，需對任務(wù)進(jìn)行再分配。任務(wù)再分配可以等效為集群UUV系統(tǒng)處理新的目標(biāo)識別任務(wù)，因此任務(wù)分配過程同HCAMOA流程，只是發(fā)起者為能源不足的CV。采用AAM模式時，CVs的所有任務(wù)均參與重新分配；SAM模式時，只對CVs任務(wù)序列進(jìn)行局部調(diào)整。按異常事件的性質(zhì)，分為2種情況。

情況1：CV不能完成后續(xù)任務(wù)。CV發(fā)生故障或剩余能源不足退出任務(wù)時，需要將所擔(dān)負(fù)的所有后續(xù)任務(wù)分配給其他CVs。

情況2：CV剩余能源能完成部分后續(xù)任務(wù)。將不能完成的任務(wù)分配給其他CVs。

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

1）異步分配模式

3艘CV，10個目標(biāo)，采用MST作為執(zhí)行代價。初始條件如表1和表2所示。

表1 目標(biāo)點(diǎn)的分布情況Tab.1 Distribution of target locations

表2 CVs當(dāng)前位置以及初始任務(wù)位置分布情況Tab.2 Distribution of CVs and their initial tasks locations

在初始階段，每艘CV任務(wù)序列中各有一個待完成的目標(biāo)識別任務(wù)。在AAM模式下，上述目標(biāo)均參與分組，共計(jì)13個目標(biāo)，如圖4所示。聚類和分組結(jié)果如圖5所示。

12個目標(biāo)共分為2檔20個任務(wù)包。CVs對各任務(wù)包最小MST代價投標(biāo)結(jié)果如表3所示（任務(wù)包編號為樹形結(jié)構(gòu)自底而上順序排列）。

根據(jù)算法3，最終中標(biāo)結(jié)果如表4所示。

2）同步分配模式

3艘CV，4個目標(biāo)，采用TSP作為執(zhí)行代價。初始條件如表5和表6所示。

4個目標(biāo)共分為2檔10個任務(wù)包。CVs對各任務(wù)包最小TSP代價投標(biāo)結(jié)果如表7所示。

圖4 目標(biāo)及CVs初始位置分布Fig.4 Distribution of target and CVs initial locations

表3 各任務(wù)包最小代價Tab.3 The minimum cost for each task package

表4 中標(biāo)結(jié)果Tab.4 The bidding results

表5 目標(biāo)點(diǎn)的分布情況Tab.5 Distribution of target locations

圖5 聚類和分組結(jié)果Fig.5 Results of clustering and grouping

最終中標(biāo)結(jié)果如表8所示。

表6 CVs當(dāng)前位置以及初始任務(wù)位置分布情況Tab.6 Distribution of CVs and their initial tasks locations

表7 各任務(wù)包最小TSP代價投標(biāo)結(jié)果Tab.7 The minimum TSP cost of each task package and bidding results

表8 中標(biāo)結(jié)果Tab.8 The bidding results

發(fā)生異常情況時，需將不能完成的任務(wù)進(jìn)行再分配，分配的基本流程和方法同上。上述2個仿真實(shí)例運(yùn)行時間分別為0.89 s和87.8 s（仿真平臺Matlab2016b，運(yùn)行環(huán)境為Intel core i5 1.6 GHz，8G RAM）。盡管實(shí)例2分配的目標(biāo)數(shù)量較少，但采用計(jì)算量較大的TSP算法，運(yùn)行時間大幅增加。因此，在對實(shí)時性要求較高，或目標(biāo)較多的情況下，適合使用快速啟發(fā)式HMST算法。

3 結(jié) 語

作業(yè)效率和可靠性是集群UUV協(xié)同執(zhí)行任務(wù)關(guān)注的主要問題。針對水下多目標(biāo)識別任務(wù)的特點(diǎn)，提出了2種任務(wù)分配模式，AAM模式本質(zhì)上是全局任務(wù)重分配方法，適合大量目標(biāo)分階段分配，而SAM模式是對CVs任務(wù)進(jìn)行局部增量式的調(diào)整，適合少量目標(biāo)的多批次任務(wù)分配情況。提出2種任務(wù)模式的優(yōu)化模型及拍賣分配方法，能夠在保證系統(tǒng)可靠運(yùn)行的條件下，提高運(yùn)行效率（總航程最短）。針對現(xiàn)有多任務(wù)分組研究工作的不足，提出了基于分層聚類的分組方法，改進(jìn)了K均值聚類分組方法存在的問題。仿真結(jié)果表明，HCAMOA方法能夠有效解決集群UUV水下多目標(biāo)任務(wù)分配問題。該方法也可應(yīng)用于其他無人系統(tǒng)同類型任務(wù)分配領(lǐng)域。后續(xù)主要工作是進(jìn)一步開展同時考慮任務(wù)時間、航程、任務(wù)負(fù)載率等多目標(biāo)優(yōu)化問題。