無人船集群隊形重構的目標任務分配

呂光顥，彭周華，王丹，竇偉滔

大連海事大學 船舶電氣工程學院，遼寧 大連 116026

0 引 言

伴隨著“工業4.0”概念的提出，人工智能、無人駕駛技術得到快速發展，無人船成為船舶智能化發展的趨勢。無人船因其具備自主性高、裝配簡單、使用靈活、成本低等優勢［1］，在軍事與民用領域都得到了廣泛應用，例如利用無人船來執行軍事偵察、搜尋救助、水文勘察、海洋環境監測等任務。為了擴大任務執行范圍，提高任務執行效率，無人船集群通常以編隊的形式協同完成某項任務。在無人船集群以編隊形式協同執行任務時，由于所處水域的復雜程度和任務的臨時變換，無人船集群的隊形重構不可避免，隊形重構中，需要將構成預設隊形的目標任務點分配給集群中的無人船。目標任務點的分配效率對無人船集群隊形重構以及協同任務執行效率有著重要影響。

關于目標任務分配問題，Mcgrew等［2］用近似動態規劃技術求解指定速度一對一作戰機動問題；Sujit等［3］通過博弈論的方法，解決了雙智能體的未知區域協同搜索問題；Manathara等［4］采用啟發式算法，針對多異構無人機的資源分配問題設計了分配策略；Kim等［5］基于響應閾值模型，提出了區域搜索任務分配方法；Wei等［6］基于粒子群算法設計出雙級任務分配方法，使得任務完成精度與可靠性得到了提高；謝宗仁、朱曉軍等［7-8］分別利用突變級數法與遺傳算法對艦船編隊的部署作戰能力進行分析，以達到資源的優化分配；Chopra等［9］針對經典匈牙利法無法處理大規模集群任務分配的問題，將匈牙利法改進成了一種并行運行的分配方法。除以上所提任務分配方法外，近年來，一種基于拍賣機制［10-11］的資源分配方法因其計算量小且運行方式靈活，得到了各國學者的廣泛關注。雖然目前針對多無人機系統的目標任務分配問題已有相關研究，但有關無人船集群自主決策任務分配以及無人船隊形重構方面的研究應用還較少。

本文將主要研究無人船集群隊形重構中目標任務點的分配問題，基于拍賣理論設計出一種無人船集群隊形重構的目標分配方法，集群中各無人船自主決策選擇興趣目標點進行競拍。同時，針對傳統拍賣算法在隊形重構的目標分配中可能存在的無可行解問題，提出基于最大迭代次數的拍賣終止機制。然后對其進行仿真，并與匈牙利法相比較。

1 無人船隊形重構任務分配問題描述

如圖1所示，本節將研究由無人船集群中的n艘無人船（黃圈）到隊形中的n個目標點（藍圈）的分配問題，并使分配后的收益z最大，行程最短，如式（1）所示。

式中：aij為本次任務的收益矩陣，無人船i距離目標點j的距離越短，則收益越大；xij為任務分配的結果，當xij=1時，目標點j分配給無人船i。任務分配完成后，無人船將與目標點形成一一對應的關系，如式（2）所示。

式中，A為分配中所有可能配對的集合。

假設目標點j的競標價格為pj，那么無人船i競拍得到目標點的凈值為aij-pj。每艘無人船都希望競拍到能獲得最大凈值的目標點ji，即

對于一個給定的指派S，假若存在二元對(i，j)∈S，則說明無人船i或者目標點j被分配，反之，則稱無人船i或目標點j未被分配。假若這個指派S包括n組二元對，而且每艘無人船和目標點都已一一對應分配，那么這個指派可以稱為可行指派或完全指派，否則，該指派被稱為部分指派。對于所有二元對(i，j)∈S，如果目標點j都是無人船i在ε范圍內的最優指派，即，則稱分配S和價格向量p滿足互補松弛（ε—CS）條件。

2 基于拍賣法的無人船任務分配

2.1 拍賣過程描述

通過用拍賣算法的迭代循環執行競買過程，直至最后的分配為最優指派。在每次迭代開始前，需要一個符合ε—CS條件的價格向量p。將滿足ε—CS度的指派和對應的價格pj作為初始選擇的輸入，來篩選出對無人船有吸引力的目標點，通過拍賣競價，以使二者可以始終滿足ε—CS條件。整個拍賣過程由投標階段和分派階段2個階段組成。

1）投標階段。

假設分配S中未被分配的無人船構成的集合為I。對任意無人船i∈I：

（1）尋找最大收益目標點ji，使得

并計算其對應的最大收益值νi，即

然后，尋找ji之外的其他目標點提供的最佳值ωi，即

如果ji是唯一目標點，也就是說A(i)中只有一個點，那么定義ωi=-∞，為便于計算，取一個遠小于νi的值賦值給ωi。

（2）計算無人船i對目標點ji投標pji與目標點ji收到無人船i的標價pij：

2）分派階段。

對于每個目標點j都能夠收到若干無人船在投標階段的投標，記這些無人船的集合為P(j)。若P(j)非空，記下最高標價pj，即

如果目標點j被分配給無人船i，則從指派S去掉所有與無人船i和目標點j相關的二元對，并將新的二元對(ij，j)加入指派S中，其中ij是P(j)中出價最高的無人船。

在拍賣過程中，目標點只有在被競拍時價格才會抬高，每次競拍價格至少增加ε。而未被競拍的目標點的價格則一直保持在初始值。例如，若無人船i要競拍目標點j，則競標費用piji為

拍賣結束后，會出現一個新分配。在這個新分配里，將之前分配過的目標點與無人船編號去除，因此，被指派過的無人船和目標點不再參與后續拍賣過程。

3）無可行解的拍賣終止機制。

上述拍賣算法將會在產生一個可行分配時終止，若該分配問題沒有可行解，拍賣過程將無限循環。為了打破這種循環，必須為上述拍賣算法補充一個拍賣終止機制。假設存在可行解，那么拍賣的迭代次數是有限的，如式（10）所示，即存在一個最大迭代次數上限D。若不存在可行解，即由于最后不能一一分配滿足互補松弛條件的目標點，拍賣將會一直進行且迭代次數會超過最大迭代次數。當拍賣次數達到最大迭代次數時，為了兼顧拍賣的運行時間，停止對此目標點進行拍賣，并將此目標點分配給下標較小的無人船。

2.2 基于拍賣法的任務分配機制設計

如圖2所示，由n艘無人船組成的系統動態網絡有集成的網絡通信能力，其中無人船所擔任的角色可以分為任務管理與任務執行2類。任務管理船的主要功能是將任務需求及分配發送至各執行船。任務執行船是一種能夠執行任務的單元，通常是帶各種負載的無人船，其主要功能是執行由任務管理船發送的各個任務請求。本文中，任務管理船將預設隊形中目標點的信息并發送給集群中任務執行船，各個任務執行船根據目標點的信息自主決策，選擇興趣目標點進行出價競拍，并將競價發送給任務管理船，然后任務管理船通過競價高低來分配目標任務點，最終目標任務點能夠分配到各個任務執行船，執行船前往各自所分配到的目標點位置構成預設隊形。

2.3 基于拍賣法的無人船任務分配流程

本文所提算法在任務執行船中運行，在拍賣過程中競價信息都將發送并儲存在任務管理船中，每艘任務執行船都能接受到目標點的當前競價信息。設置構成預設隊形的目標任務點χf，任務管理船將目標點的信息發送給任務執行船，各個執行船根據目標點的信息在本地計算出自己對每個目標點的距離，從而生成收益aij，將競標價格初始化為0，然后開始拍賣過程，算法流程圖如圖3所示，分以下5個步驟進行：

1）更新目前未分配的無人船的數量N，每艘無人船本地算出對所有目標點的凈收益bi(j)，自主尋找最大凈收益值vi并記錄其對應的目標點ji，找出無人船凈收益第2大值wi。此時引入一個增量ε以保證競價始終在增加，根據式（7）進行出價并將競價信息發送給任務管理船。

2）任務管理船開始記錄對任務s競拍的船數以及最高出價并作為當前所有執行船對任務s的下次競標價格。

3）如若對任務s的出價數量唯一，則說明任務只有一艘執行船在競標并且滿足互補松弛條件。因此，分配任務s給出價的執行船。若對任務s的出價數量有重復，則counti加1。

4）若counti超出設置的最大迭代次數D，說明有若干艘無人船一直在重復競標且對任務s具有相同的興趣，出價一直相同。此時，把任務s分配給下標較小的執行船。同時，刪除任務s以及對應的執行船來提高運算速度。

5）判斷未分配任務的執行船的數量lj，若lj=0，說明任務已全部分配，此時跳出循環，分配結束。若lj=1，則說明還有一艘執行船和一個目標點未分配，此時，無需競價直接分配即可，同時跳出循環分配結束。在該算法中，任務執行船不需要知道其初始位置信息，任務管理船將目標點的信息發送至各任務執行船，各任務執行船本地計算各自收益，自主決策選擇興趣目標點進行競拍，從而分散計算量，最終完成分配任務。

在此過程中，會存在以下2個問題：

1）在無人船i變化時，其對應的最大凈收益所對應的下標集合ji會隨之變化，即在算法迭代過程中ji的維數是會改變的。因此，在實際編寫程序時，要特別注意聲明ji數組的大小。

2）為了貼合實際市場中的拍賣過程，減小分配時間，在本文算法中，每有一對無人船i與目標點j匹配完成，就把與無人船i和任務j相關的所有數據刪除不再參與以后的競拍過程。那么在步驟3）與步驟5）進行任務分配記錄時，xi中第1個元素對應的并不是第1艘無人船，而是目前尚未分配的無人船中下標最小的無人船。同樣的，χf中儲存的第1個元素是未被分配的目標點中下標最小的目標點。

3 無人船任務分配仿真分析

本文假設某一水域存在由39艘無人船組成的集群需要進行隊形重構，針對構成預設隊形的39個目標任務點分配問題進行仿真。如圖4所示，將39艘隨機分布在水域中的無人船分派到構成DMU隊形的39個目標任務點，形成DMU編隊隊形。

上述分配方案中的增量參數ε對分配收益有重要影響，因此，首先針對不同ε取值時的分配收益進行仿真分析。圖5所示為增量參數ε對分配后收益的影響?？傮w上分配收益隨增量參數ε的增加呈下降趨勢。尤其是當增量參數ε的取值為0.02～0.03時，分配收益下降幅度大。在ε＞0.1時，分配收益的下降趨于平緩，此時，分配收益值達到最優分配收益值的93%左右。

其次，本文將選取的ε=1/39時的分配結果與匈牙利法的最優分配結果進行比較驗證。分配結果如圖6所示，DMU隊形中39個目標任務點被分配，無人船所分配到的目標點基本在附近范圍之內。2種分配方法所得分配結果相似，驗證了本文所述分配方案的合理性。

最后，為了進一步對比本文所述算法與經典匈牙利法，針對不同規模的無人船集群進行隊形任務點的分配。此時，ε的取值均為1/n，最大迭代次數D的設置如式（10）所示。由表1可以看出，本文分配方法和匈牙利法相對比，收益最大差值在2%左右；但隨著集群規模的增大，拍賣分配求解時間較匈牙利法有所縮短，即用匈牙利法分配目標點的分配收益大于拍賣分配目標點的收益，但拍賣分配計算量分散，分配時間有所縮短。

表1 算法分配結果對比Table 1 Comparisons of the results of two assignment algorithms

4 結 語

本文基于“拍賣理論”提出了一種對無人船編隊隊形重構中目標任務點的分配算法，集群中無人船本地計算，自主決策選擇興趣目標點競拍，完成預設隊形中目標點的分配。與匈牙利法的比較結果驗證了采用本文所提方法當補增量ε的取值在1/n附近時能快速得出相對優化的分配方案。本文中的分配方法還可以針對無人船集群多節點通信問題做進一步研究，這樣不僅可以減少對處理器的依賴，也可解決無人船通信帶寬不足的問題，從而提高大規模無人船集群動態隊形重構的魯棒性。