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

何喆 劉峰 馬子飛

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

關(guān)鍵詞：膨脹算法;隊形生成;避障;多智能體

一、引言

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

二、研究背景

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

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

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

三、多UUV系統(tǒng)的系統(tǒng)結(jié)構(gòu)與分布方式

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

（一）感知層

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

（二）協(xié)調(diào)規(guī)劃層

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

（三）控制決策層

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

（四）執(zhí)行層

作為系統(tǒng)的響應(yīng)，類比于控制系統(tǒng)的執(zhí)行元件。主要作用即是將控制層傳遞來的控制指令轉(zhuǎn)化為將要運動的UUV指令，如推進器的推力大小、垂直方向和水平方向的舵角，并帶有反饋。執(zhí)行層主要包含以下幾個部分和功能。1.推進器：主要負(fù)責(zé)給UUV提供前進的推力。2.方向舵：垂直方向舵和水平方向舵，控制UUV的轉(zhuǎn)向以及上浮下潛。3.監(jiān)控模塊：通過反饋判斷推進器和舵機是否正常運行。4.執(zhí)行控制器：給出推進器、方向舵的控制量，綜合反饋數(shù)據(jù)做出適當(dāng)?shù)恼{(diào)整。

四、基于膨脹算法的多UUV系統(tǒng)的隊形生成策略

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

因多UUV系統(tǒng)面臨的絕大多數(shù)探測隊形為二維平面隊形，在此僅討論膨脹算法在二維平面的應(yīng)用，

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

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

五、膨脹算法對于高效探測隊形生成的應(yīng)用

UUV的主要探測功能集中在側(cè)掃聲納上，其保持位置不變，姿態(tài)可變的情況下，在三維空間的探測范圍為一以側(cè)掃聲納掃描范圍為半徑的球體，在二維平面上是一圓域。多UUV編隊系統(tǒng)實際進行區(qū)域探測時一般形成三角形編隊或一字形編隊，對區(qū)域內(nèi)進行正弦曲線的巡航來探測，其應(yīng)對大多數(shù)水下環(huán)境都是足夠的，即水下環(huán)境的實時變化并不大，較大區(qū)域內(nèi)的信息基本不變，然而隨科技進步，UUV趨于小型化，集群化，批量生產(chǎn)，應(yīng)對復(fù)雜水下環(huán)境的探測就需要大量的UUV分布在整個區(qū)域內(nèi)，各UUV在滿足通信距離情況下盡可能承擔(dān)同樣大小的探測區(qū)域?；谝陨闲枨筇岢隽烁咝綔y隊形，使其集群分布效能最優(yōu)。

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

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

首先對目標(biāo)區(qū)域作外接圓，在外接圓內(nèi)按左圖結(jié)構(gòu)擴展全覆蓋，將與目標(biāo)區(qū)域無交疊的UUV剔除，所得的剩余UUV排布即是較優(yōu)探測排布。

六、基于膨脹算法的多UUV系統(tǒng)避障策略

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

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

七、結(jié)束語

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

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

參? 考? 文? 獻

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

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

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

[4]李曄，由光鑫，龐永杰.多水下機器人視景仿真系統(tǒng)技術(shù)研究[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.