基于分層聚類拍賣的集群UUV多目標分配方法

馬 碩，馬亞平

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

0 引 言

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

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

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

1 基于聚類拍賣的集群UUV系統多目標任務分配方法

1.1 任務描述及模型

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

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

當SV發布目標信息時，CVs各自的任務序列TVc與新目標NT一起構成任務集合T=TV1∪...∪TVn∪NT。該模式需將系統所有待識別的OI重新分配給CVs，優點是可以實現全局優化，但計算量相對較大。為避免頻繁的重新分配任務，SVs應在完成一定海域面積的探測任務工作后發布目標信息。異步分配模式數學模型為：

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

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

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

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

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

1.2 HCAMOA方法流程

1.2.1 工作流程

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

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

1.2.2 分層聚類分組

分層聚類將所有目標點自底而上逐層分類，算法1分為聚類和分組2個步驟。

1）聚類

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

定義1：2個目標點集合T1、T2之間距離D，為以T1∪T2為節點所構成連通圖的MST權值，即D=MST（T1∪T2）。

聚類過程示例如圖2所示。圖中左半部分為目標點分布，右半部分為對應的聚類過程，將6個目標劃為 5 種分類：{t1，···，t6}，{t1，t3}，{t2，t4}，{t5，t6}，{t1，t2，t3，t4}，最終形成二叉樹結構的聚類樹。

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

2）分組

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

1.2.3 CVs投標

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

1.2.4 中標

SV接收到CVs的投標信息后，根據NC的大小，對TP進行擇優中標操作。從TP樹形結構最底層的葉子節點開始，自底而上逐層比較。

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

1.2.5 系統異常情況的任務處理機制

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

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

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

2 仿真實驗

1）異步分配模式

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

表1 目標點的分布情況Tab.1 Distribution of target locations

表2 CVs當前位置以及初始任務位置分布情況Tab.2 Distribution of CVs and their initial tasks locations

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

12個目標共分為2檔20個任務包。CVs對各任務包最小MST代價投標結果如表3所示（任務包編號為樹形結構自底而上順序排列）。

根據算法3，最終中標結果如表4所示。

2）同步分配模式

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

4個目標共分為2檔10個任務包。CVs對各任務包最小TSP代價投標結果如表7所示。

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

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

表4 中標結果Tab.4 The bidding results

表5 目標點的分布情況Tab.5 Distribution of target locations

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

最終中標結果如表8所示。

表6 CVs當前位置以及初始任務位置分布情況Tab.6 Distribution of CVs and their initial tasks locations

表7 各任務包最小TSP代價投標結果Tab.7 The minimum TSP cost of each task package and bidding results

表8 中標結果Tab.8 The bidding results

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

3 結 語

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