何喆 劉峰 馬子飛

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

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

一、引言

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

二、研究背景

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

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

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

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

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

（一）感知層

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

（二）協(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)測(cè)與消除模塊、未執(zhí)行目標(biāo)、任務(wù)分配分解模塊、水下知識(shí)庫(kù)。各模塊功能如下：1.通信拓?fù)浣Y(jié)構(gòu)：UUV的通信部分分為UUV之間的水聲通信和UUV母艦間的無(wú)線電和水聲混合通信。本文假設(shè)在較深水域進(jìn)行，所以通信部分僅為UUV之間的水聲通信，其通信拓?fù)浣Y(jié)構(gòu)即是協(xié)調(diào)規(guī)劃層之重點(diǎn)。2.水下知識(shí)庫(kù)：UUV預(yù)存的以應(yīng)對(duì)各種水下環(huán)境的知識(shí)。3.未執(zhí)行目標(biāo)：工作狀態(tài)的UUV都是有任務(wù)堆棧的，UUV會(huì)依據(jù)各任務(wù)優(yōu)先性先后執(zhí)行任務(wù)，任何當(dāng)前任務(wù)可以被高優(yōu)先級(jí)任務(wù)中斷。4.任務(wù)分解分配模塊：復(fù)雜任務(wù)必須分解為多個(gè)簡(jiǎn)單任務(wù)來(lái)賦予多個(gè)UUV個(gè)體，毋庸置疑這將提供更高的效率。5.協(xié)調(diào)規(guī)劃模塊：任務(wù)的多樣性和水下環(huán)境的復(fù)雜多變使得UUV的任務(wù)執(zhí)行機(jī)制也要根據(jù)情況不同而適時(shí)應(yīng)對(duì)。6.任務(wù)沖突監(jiān)測(cè)與消除模塊：多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)運(yùn)作。2.控制器：綜合信息得到控制結(jié)果，將指令傳遞給執(zhí)行層。3.行為決策：任務(wù)分解為多個(gè)簡(jiǎn)單行為時(shí)，決策模塊將根據(jù)各自UUV的具體情況選擇合適的行為。4.任務(wù)解析模塊：本模塊將為各任務(wù)目標(biāo)提供詳細(xì)的參數(shù)，使任務(wù)可執(zhí)行。

（四）執(zhí)行層

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

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

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

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

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

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

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

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

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

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

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

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

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

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

七、結(jié)束語(yǔ)

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

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

參? 考? 文? 獻(xiàn)

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

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

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

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