一種基于膨脹算法的 多UUV隊形生成與避障策略

何喆 劉峰 馬子飛

摘要：水下無人潛航器（Unmanned Underwater Vehicle，UUV）是一種集環境感知、動態決策與規劃、行為控制及能源適配等功能的復雜無人系統，是執行抵近海底探測、開發、搜尋任務的重要工具。本文為解決多UUV系統面臨的區域內高效探測隊形生成和動態、靜態避障問題提出了基于膨脹算法的隊形生成與避障策略，能夠高效的計算n個個體的集群在圓形區域內的均勻分布，在維持高效探測隊形的同時兼顧動態、靜態避障要求，并對膨脹算法的隊形生成與避障進行了仿真實現，驗證了基于膨脹算法的多UUV系統隊形生成與避障策略的有效性。

關鍵詞：膨脹算法;隊形生成;避障;多智能體

一、引言

本文的應用背景為基于事件驅動的多UUV編隊系統的區域均勻監測策略，所解決的問題為多UUV系統的區域保持。在當前的眾多水下任務中，UUV群更多的是執行探測任務和工作任務。但是多UUV編隊系統實際上屬于多智能體，其研究方法和方向也在向多智能體靠攏。任意UUV個體都有其水下知識庫來解決水下的運動、工作問題，其三維方向上六自由度的運動與無人機相似，多智能體系統的共性熱點問題為隊形生成與避障。

二、研究背景

水下無人潛航器（Unmanned Underwater Vehicle，以下簡稱UUV），是無人駕駛的水下自主航行的載具，最初用以代替潛水員、潛艇等進行危險區域作業，如探測、營救、排雷等。

UUV自問世以來就受到廣泛關注，其作為水下支援平臺的軍事用途更使其成為現隊海軍利器，因而UUV在軍用領域技術最為先進。隨時代和技術發展，在更復雜的環境和任務面前，單UUV已不能滿足要求，多UUV編隊系統才是應發展的方向。其在復雜環境中的內部協同機制，高容錯率為實際應用提供了諸多便利，多UUV編隊系統要進行協同，必須具有確切的等級制度或協同體系。國內對于多智能體的研究重點聚集于圍獵、隊形生成方面，并從穩定性，通信拓撲結構，也即圖論的角度來對多智能體進行研究，取得了極大的進展。

當前的多UUV系統協同控制、隊形生成相關研究已非常完備，在多智能體個體控制方面，基于避障問題有人工勢場法、柵格法等。在隊形控制和生成方面有：基于行為的方法、領隊-跟隨者方法、虛擬結構法、群體勢場法等。但以上方法對于個體數目不定或多變的多UUV系統隊形生成和避障并不高效，因此本文提出了膨脹算法來同時解決隊形生成和避障問題。

三、多UUV系統的系統結構與分布方式

多UUV系統作為一個整體來完成任務，其內部必定要有分工協作，以分層式控制體系思想來劃分，系統可以分為如下四個層次，值得注意的一點是，任何一個UUV都含有上述四個部分的功能，如圖1所示。

（一）感知層

UUV感知層來自UUV的各種傳感器和包括光學聲學在內的圖像設備，通信設備和探測設備。一個UUV所獲得的信息，不只是個體UUV獲得的自身姿態、位置、速度、方向、水流、經緯度位置、深度，還包含別的UUV和水面母艦傳遞來的各種通信信息。

（二）協調規劃層

協調層負責各UUV的組織關系，包括當前的通信拓撲結構、協調規劃模塊、任務沖突監測與消除模塊、未執行目標、任務分配分解模塊、水下知識庫。各模塊功能如下：1.通信拓撲結構：UUV的通信部分分為UUV之間的水聲通信和UUV母艦間的無線電和水聲混合通信。本文假設在較深水域進行，所以通信部分僅為UUV之間的水聲通信，其通信拓撲結構即是協調規劃層之重點。2.水下知識庫：UUV預存的以應對各種水下環境的知識。3.未執行目標：工作狀態的UUV都是有任務堆棧的，UUV會依據各任務優先性先后執行任務，任何當前任務可以被高優先級任務中斷。4.任務分解分配模塊：復雜任務必須分解為多個簡單任務來賦予多個UUV個體，毋庸置疑這將提供更高的效率。5.協調規劃模塊：任務的多樣性和水下環境的復雜多變使得UUV的任務執行機制也要根據情況不同而適時應對。6.任務沖突監測與消除模塊：多UUV執行任務將有更高的概率產生協調、分配上的沖突，這是本模塊產生的原因。

（三）控制決策層

控制決策層依據當前的既定策略，綜合當前感知層得到的外界信息以及多UUV系統的自身狀態信息，結合協調策略做出控制指令傳遞于執行層。控制處理層模塊包括：協調策略、控制器、任務解析模塊、行為決策。各模塊功能如下：1.協調策略：使各UUV之間協調運作。2.控制器：綜合信息得到控制結果，將指令傳遞給執行層。3.行為決策：任務分解為多個簡單行為時，決策模塊將根據各自UUV的具體情況選擇合適的行為。4.任務解析模塊：本模塊將為各任務目標提供詳細的參數，使任務可執行。

（四）執行層

作為系統的響應，類比于控制系統的執行元件。主要作用即是將控制層傳遞來的控制指令轉化為將要運動的UUV指令，如推進器的推力大小、垂直方向和水平方向的舵角，并帶有反饋。執行層主要包含以下幾個部分和功能。1.推進器：主要負責給UUV提供前進的推力。2.方向舵：垂直方向舵和水平方向舵，控制UUV的轉向以及上浮下潛。3.監控模塊：通過反饋判斷推進器和舵機是否正常運行。4.執行控制器：給出推進器、方向舵的控制量，綜合反饋數據做出適當的調整。

四、基于膨脹算法的多UUV系統的隊形生成策略

多UUV系統可認為是一個同構多智能體系統，面臨水下探測問題時均需要進行避障與隊形生成，本文提出了基于膨脹算法的多UUV系統隊形生成與避障策略。膨脹算法基于數值計算，在多個約束條件下進行趨近計算，最終形成符合多個約束條件的趨近解。在平面幾何角度可理解為多個相同大小的剛體小球在一球形區域內進行膨脹，初始狀態所有小球均隨機分布，半徑相對區域而言極小，隨時間增長，小球半徑增大，規定任意兩小球外殼相擠壓或與區域輪廓擠壓將會產生力使二者分離直至不再出現擠壓，繼續膨脹過程，直至半徑不再增大。最終小球在封閉區域內的分布即為符合膨脹極限的個體分布。

因多UUV系統面臨的絕大多數探測隊形為二維平面隊形，在此僅討論膨脹算法在二維平面的應用，

在區域內隨機部署n個點，以此n個點為圓心（此n個圓稱作n個個體），半徑為R1，R1取一較小值，使n個圓都不相切或交疊，以一低增速逐步增大半徑，當半徑取Rn時，出現圓彼此交疊或與邊界相切，圓心向交疊或相切方向的反向180°（即以反向為正90°刻標，左右各90°范圍）內任意角度移動一步，對于與多個個體圓交疊相切的情況，運動方向取其公共區間，無公共區間的個體則不可移動，與其交疊的其他可移動個體移動速度作一適應性提升，然后檢測當前是否所有個體滿足不交疊條件，否則繼續隨機移動，持續隨機移動過程直至滿足所有個體不交疊條件，繼續增大半徑，重復如上的判斷過程和隨機移動過程，直至出現部分個體相疊，且所有點不可移動的情況，以下稱為自鎖情況，出現自鎖情況則認為是最終的分布結果。以上算法的程序框圖實現如圖3所示。

進行算法實現后，設定實驗初始條件，9個個體初始位置位于直線L ：y=x上，設定圓形區域圓心為原點，半徑為5。實驗結果如圖4，圖4左為最終個體分布結果，圖4右為個體移動軌跡。試驗結果表明了膨脹算法對于多智能體隊形生成的應用是有效的。

五、膨脹算法對于高效探測隊形生成的應用

UUV的主要探測功能集中在側掃聲納上，其保持位置不變，姿態可變的情況下，在三維空間的探測范圍為一以側掃聲納掃描范圍為半徑的球體，在二維平面上是一圓域。多UUV編隊系統實際進行區域探測時一般形成三角形編隊或一字形編隊，對區域內進行正弦曲線的巡航來探測，其應對大多數水下環境都是足夠的，即水下環境的實時變化并不大，較大區域內的信息基本不變，然而隨科技進步，UUV趨于小型化，集群化，批量生產，應對復雜水下環境的探測就需要大量的UUV分布在整個區域內，各UUV在滿足通信距離情況下盡可能承擔同樣大小的探測區域。基于以上需求提出了高效探測隊形，使其集群分布效能最優。

多UUV系統的高效探測隊形計算就成了n個固定大小球體對一圓形區域的覆蓋分布。此處直接引入蜂巢原理，即蜂巢的正六邊形結構排布是無空隙，且最節省邊界的結構，其優點有多篇文獻說明。在此直接使用，承認正六邊形的外接圓結構是重疊率最小的排布結構，并給出如下的探測多UUV系統最優解。如圖5所示。

對于虛線圓域內任意區域都是完全探測的，由此，給出了多UUV系統對任意形狀封閉區域完全探測的最少UUV排布計算方法。

首先對目標區域作外接圓，在外接圓內按左圖結構擴展全覆蓋，將與目標區域無交疊的UUV剔除，所得的剩余UUV排布即是較優探測排布。

六、基于膨脹算法的多UUV系統避障策略

多UUV系統在執行行進避障或躲避動態障礙物時，為保持隊形的相對松散與一致，需進行同時進行避障與隊形變換，應對策略應盡可能符合總體能耗最低原則。對于上述情況提出了基于膨脹算法的多UUV系統避障策略。即將障礙物視作僅能進行固定方向移動的個體，執行逆膨脹算法。算法策略如下：

有一外界圓球狀障礙物沿直線L ：y=x穿越區域，包含安全距離的碰撞域即為圖5所示的紅色障礙物。設定其僅能沿直線L ：y=x單向移動，任意時刻，如果動態障礙物不可移動，則縮小所有個體圓半徑，可使障礙物移動，依據膨脹算法內的調整機制障礙物只沿直線L ：y=x單向移動，各UUV個體則做避讓運動，同時維持隊形的相對松散，其最終結果，將是動態障礙物由左下方離開圓域，然后圓域內的多UUV系統重新膨脹至高效探測隊形。

七、結束語

本文針對多UUV系統的水下探測需求，提出了基于膨脹算法的多UUV隊形生成和避障策略。并進行了多UUV系統的隊形生成與避障的相關仿真，驗證了所設計的策略在高效探測隊形生成方面的有效性，可用于任意數目的同構智能體集群生成松散均勻隊形，具有較好的參考價值。本文針對多UUV編隊系統的區域保持問題，使用膨脹算法進行了控制律層面的隊形控制，避障研究，并針對區域保持的評價體系提出了區域均勻規劃。

作者單位：何喆? ? ?劉峰? ? 馬子飛? ? 航空工業西安航空計算技術研究所

參? 考? 文? 獻

[1]鄧超.AUV三維軌跡跟蹤控制方法研究[D].哈爾濱：哈爾濱工程大學，2011.

[2]王國英.欠驅動水面艇運動控制建模及三維仿真實現研究多水下機器人編隊控制方法研究[D].哈爾濱：哈爾濱工程大學，2011.

[3]王愛兵，嚴浙平.不同優先級的多水下機器人避碰技術研究[J].微計算機信息，2007，（14）：232-233，253.

[4]李曄，由光鑫，龐永杰.多水下機器人視景仿真系統技術研究[J].計算機仿真，2005，（06）：161-163，217.

[5] Fahimi F.Sliding-mode formation control for underactuated surface vessels.IEEE Transactions on Robotics，2007，23（3）：617-622.