無人船集群隊形重構(gòu)的目標任務(wù)分配

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

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

0 引 言

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

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

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

1 無人船隊形重構(gòu)任務(wù)分配問題描述

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

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

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

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

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

2 基于拍賣法的無人船任務(wù)分配

2.1 拍賣過程描述

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

1）投標階段。

假設(shè)分配S中未被分配的無人船構(gòu)成的集合為I。對任意無人船i∈I：

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

并計算其對應(yīng)的最大收益值ν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相關(guān)的二元對，并將新的二元對(ij，j)加入指派S中，其中ij是P(j)中出價最高的無人船。

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

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

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

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

2.2 基于拍賣法的任務(wù)分配機制設(shè)計

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

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

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

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

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

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

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

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

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

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

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

3 無人船任務(wù)分配仿真分析

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

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

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

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

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

4 結(jié) 語

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