一種新型多AUV水下圍捕路徑規(guī)劃算法

蔣驍?shù)?，甘文?/p>

(上海海事大學(xué)智能海事搜救與水下機(jī)器人上海工程技術(shù)研究中心，上海 201306)

1 引言

近年來，由于陸地資源的逐漸消耗，人類逐漸將目光放到了具有豐富資源的海洋，借助各種科學(xué)技術(shù)開發(fā)和利用海洋。AUV作為人類探索海洋的有力工具，無論在軍事領(lǐng)域還是民用領(lǐng)域，都有著無可比擬的地位。由于水下環(huán)境的復(fù)雜性以及AUV本身所能攜帶的能源有限，對于較復(fù)雜的作業(yè)任務(wù)或者AUV出現(xiàn)故障時，單個AUV可能會出現(xiàn)執(zhí)行任務(wù)失敗的情況。因此具有更好容錯性的多AUV系統(tǒng)[1]對于大型水下任務(wù)的執(zhí)行來說是個不錯的選擇。近年來，多AUV系統(tǒng)相關(guān)的研究工作也是吸引到眾多國內(nèi)外學(xué)者投身于此，取得了一系列的成果，相關(guān)研究內(nèi)容包括聯(lián)合搜索[2]，編隊算法[3]，地圖構(gòu)建[4]，多目標(biāo)任務(wù)分配[5]以及協(xié)作圍捕[6]等等。其中多AUV協(xié)作圍捕研究作為多AUV系統(tǒng)技術(shù)的一個重要分支，在海洋軍事領(lǐng)域有著重要應(yīng)用，所以對其進(jìn)行研究就顯得極為迫切。

二維環(huán)境下的多AUV協(xié)作圍捕與多移動機(jī)器人圍捕類似，具體是指通過多個智能體的協(xié)作圍捕到一個或多個目標(biāo)。對于多機(jī)器人圍捕研究方法主要有以下幾種：強(qiáng)化學(xué)習(xí)算法[7]；基于合同網(wǎng)協(xié)議算法[8]；基于勢點圍捕方法[9]；編隊算法[10]等等。這些算法都有著其優(yōu)點，適用于多機(jī)器人圍捕，但同時也存在著一些缺點，例如強(qiáng)化學(xué)習(xí)算法計算量大，學(xué)習(xí)時間較長，不能夠適應(yīng)復(fù)雜多變的環(huán)境；基于合同網(wǎng)協(xié)議算法需要大量的通信開銷，要求機(jī)器人之間有著較高的通信能力及計算能力；基于勢點圍捕方法不能夠處理某個機(jī)器人故障時的情況，容錯性能較差；編隊算法易受環(huán)境影響。

以上多機(jī)器人圍捕的方法在協(xié)調(diào)、魯棒性方面存在一定的局限性，使得其不能很好地適用于水下環(huán)境中的多AUV協(xié)作圍捕問題中。針對多AUV圍捕問題，李宏達(dá)[11]設(shè)計了基于優(yōu)化的狼群算法的多AUV協(xié)同圍捕策略，將圍捕分為三個階段：搜索、召喚奔襲和圍攻，在二維無障礙物環(huán)境下對靜態(tài)逃逸目標(biāo)和動態(tài)逃逸目標(biāo)進(jìn)行仿真，仿真結(jié)果表明針對靜態(tài)逃逸目標(biāo)的圍捕效果較好，但對于動態(tài)逃逸目標(biāo)的圍捕成功率則大大降低。Zhang等人[12]針對多AUV協(xié)作圍捕問題，提出改進(jìn)拍賣算法作為多AUV的決策方法，用來選定圍捕者，將自組織的獅群算法用于多AUV行為協(xié)同控制中，完善多AUV圍捕時的行為協(xié)同機(jī)制，但圍捕成功的前提必須是圍捕AUV的速度要大于逃逸AUV的速度，在兩者同速的情況下，不能成功執(zhí)行圍捕任務(wù)。

本文針對二維水下障礙物環(huán)境，提出一種包含基于位置分配圍捕占位和基于改進(jìn)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃的圍捕策略，使圍捕AUV能夠在與逃逸目標(biāo)AUV速度相同的情況下，高效完成圍捕任務(wù)。該圍捕策略執(zhí)行的前提有兩點：1)逃逸目標(biāo)AUV已經(jīng)被搜索到；2)圍捕團(tuán)隊中的圍捕AUV已經(jīng)進(jìn)行任務(wù)分配操作。本文的圍捕策略主要針對多個圍捕AUV圍捕一個逃逸目標(biāo)AUV的情況。該圍捕策略主要包含兩個部分：1)占位點分配：利用“位置分配”方法將逃逸目標(biāo)AUV附近的幾個占位點分配給圍捕AUV；2)利用改進(jìn)的生物啟發(fā)神經(jīng)網(wǎng)絡(luò)算法規(guī)劃圍捕AUV到占位點的路徑，同時能夠避開障礙物，在逃逸目標(biāo)AUV與圍捕AUV同速的情況下最終完成圍捕任務(wù)。

2 二維水下環(huán)境建模

圖1 二維柵格地圖

對二維環(huán)境的建模方法有很多，本文采用柵格地圖法。柵格地圖法是將二維水下環(huán)境離散成柵格空間，如圖1所示，其中黑色柵格表示障礙物，白色柵格表示自由空間，即AUV可達(dá)的空間。

3 二維水下環(huán)境中圍捕問題描述

在逃逸目標(biāo)AUV被發(fā)現(xiàn)、圍捕團(tuán)隊形成之后，即在二維環(huán)境中確定了4個圍捕AUV(AUV1-4)從上下左右方向圍捕一個逃逸目標(biāo)AUV(T-AUV)，圍捕初始狀態(tài)如圖2所示。

圖2 圍捕初始狀態(tài)

逃逸目標(biāo)AUV在圍捕過程中也是一直移動的，所以在整個圍捕過程中，圍捕AUV需要組成圍捕團(tuán)隊想逃逸目標(biāo)AUV移動，追蹤具有智能逃逸能力的逃逸目標(biāo)AUV。當(dāng)圍捕AUV包圍住逃逸目標(biāo)AUV且包圍圈足夠小，同時在逃逸目標(biāo)AUV周圍均勻分布時，表示圍捕任務(wù)完成，最終完成圖如圖3所示。

圖3 圍捕成功狀態(tài)

4 二維水下環(huán)境中的圍捕策略

4.1 基于“位置分配”的圍捕占位點分配算法

圍捕過程中逃逸目標(biāo)AUV周圍的圍捕占位點隨著其位置的移動而實時更新。因此各個圍捕AUV分配獲得的圍捕點位置也是不斷更新的，為此本文提出一種動態(tài)“位置分配”算法，根據(jù)圍捕AUV最短行駛總距離進(jìn)行圍捕點分配。

該動態(tài)“位置分配”算法步驟如下：

1)圍捕AUV與圍捕占位點隨機(jī)匹配，計算出該情況下圍捕AUV到圍捕占位點的總距離d并賦值給dmin。

2)計算其它情況下圍捕AUV到圍捕占位點的總距離d，若d小于dmin，則將d的值賦給dmin；否則保留原dmin。

3)比較所有情況后得出整體最小總距離dmin，確定最終分配方案。

流程圖如圖4所示，該方法通過圍捕AUV的最短航行總距離分配圍捕點，使得每個圍捕AUV都能夠分配到整體而言的最優(yōu)圍捕占位點，同時由于圍捕占位點分配的開始就確定了圍捕AUV與圍捕占位點的一一對應(yīng)關(guān)系，從源頭上解決了圍捕占位點的“路徑?jīng)_突”問題。圖5是二維環(huán)境下圍捕占位點分配情況的示例，其結(jié)果是根據(jù)“位置分配”策略得到的最優(yōu)圍捕占位點分配結(jié)果，在這種情況下，4個圍捕AUV所航行的總路徑是最短的。

圖4 “位置分配”流程圖

提出基于總體航行距離最短的圍捕占位點分配算法，優(yōu)化了圍捕占位點分配，不僅從總體上更好的節(jié)約能源，且能夠在更短時間內(nèi)完成包圍圈，避免出現(xiàn)圍捕AUV由于路徑?jīng)_突無法及時合圍，圍捕任務(wù)失敗的情況，提升了圍捕的效率和成功率。

圖5 “位置分配法”后的占位點分配情況

4.2 基于GBNN的圍捕路徑規(guī)劃算法

在上一節(jié)中確定圍捕AUV與圍捕占位點之間的分配關(guān)系后，接著需要解決圍捕AUV如何到達(dá)圍捕占位點的問題。針對該路徑規(guī)劃問題，本節(jié)采用GBNN(Glasius Bio-inspired Neural Network)算法規(guī)劃路徑，比傳統(tǒng)的生物啟發(fā)神經(jīng)網(wǎng)絡(luò)算法[13](Bio-inspired Neural Network，BNN)相比較，GBNN算法[14]采用差分方程計算神經(jīng)網(wǎng)絡(luò)的活性值，與BNN所采用的微分方程相比，能夠有效降低算法計算量，提升算法運算速度。

4.2.1 GBNN算法原理

GBNN是一種離散時間Hopfield神經(jīng)網(wǎng)絡(luò)，其對應(yīng)的神經(jīng)網(wǎng)絡(luò)模型如圖6所示。其中，每個圓代表一個神經(jīng)元，每個神經(jīng)元都與周圍其它神經(jīng)元相連接，神經(jīng)元活性值通過神經(jīng)元之間的連接傳遞。

圖6 二維神經(jīng)網(wǎng)絡(luò)模型

其中，其神經(jīng)元的活性值的表達(dá)式為

(1)

式中傳遞函數(shù)表達(dá)式為

(2)

(3)

(4)

式中，γ為正常數(shù)，|i-j|表示的是第i個神經(jīng)元到第j個神經(jīng)元之間的歐幾里得距離，代表每個神經(jīng)元僅與其周圍8個神經(jīng)元存在側(cè)連接關(guān)系。由于神經(jīng)元之間的連接關(guān)系不具有方向，所以連接權(quán)系數(shù)Wij具有對稱特性，即Wij=Wji。Ii為神經(jīng)網(wǎng)絡(luò)中神經(jīng)元i的外部輸入，具體定義如下

(5)

式中，E為正常數(shù)。

4.2.2 多AUV協(xié)作圍捕的GBNN路徑規(guī)劃算法

將GBNN算法應(yīng)用到AUV的圍捕路徑規(guī)劃中，需將神經(jīng)網(wǎng)絡(luò)與水下環(huán)境緊密結(jié)合，使神經(jīng)元活性值能夠隨著水下環(huán)境狀態(tài)變化實時更新。由于水下環(huán)境建模時，水下地圖已經(jīng)被離散化柵格地圖，所以這里將神經(jīng)網(wǎng)絡(luò)與離散化柵格地圖意義對應(yīng)起來，就可以使得神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元活性值根據(jù)水下環(huán)境變化而變化。圖7展示了將圖1中的柵格地圖(圖7(a))對應(yīng)到二維神經(jīng)網(wǎng)絡(luò)中(圖7(b))。

圖7 二維水下環(huán)境與神經(jīng)網(wǎng)絡(luò)的對應(yīng)

根據(jù)柵格地圖建立相對應(yīng)的神經(jīng)網(wǎng)絡(luò)模型，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元與地圖中的柵格一一對應(yīng)，即黑色神經(jīng)元對應(yīng)柵格地圖中的障礙物，白色神經(jīng)元對應(yīng)柵格中的自由空間。例如，圖7(b)中白色神經(jīng)元i對應(yīng)的即是圖7(a)中的第i個自由空間柵格。

地圖中各個柵格的狀態(tài)決定對應(yīng)神經(jīng)元的外部輸入，從而直接影響神經(jīng)網(wǎng)絡(luò)的活性值。AUV進(jìn)行路徑規(guī)劃時，柵格地圖中的各個柵格表示障礙物或自由區(qū)域，因此式(5)所給的外部輸入 應(yīng)該重新定義，具體如下式所示

(6)

圖8 圍捕路徑規(guī)劃策略

在柵格賦活性值的基礎(chǔ)上，給出路徑規(guī)劃策略。以圖8為例，左側(cè)圖Pc為圍捕AUV當(dāng)前的位置，假設(shè)分配給它的圍捕點在正上方即柵格8，那么可以得到右側(cè)的柵格活性值圖，柵格6為障礙物，所以柵格6的活性值為-1；柵格1-5和7為自由區(qū)域，所以對應(yīng)的活性值為0；而柵格8同時為自由區(qū)域和圍捕點所在位置，所以它的活性值為1。在圍捕AUV周圍柵格活性值給定的情況下，路徑規(guī)劃策略是選取活性值最大的柵格作為下一步航行位置，所以在圖8的情況中，圍捕AUV選取活性值最大的柵格8作為下一步航行位置，完成到達(dá)圍捕點的路徑規(guī)劃任務(wù)。對于其它圍捕AUV同步采取同樣的路徑規(guī)劃策略，進(jìn)而完成多AUV協(xié)作圍捕任務(wù)。

5 仿真結(jié)果

為了驗證所提圍捕算法的有效性，本節(jié)主要利用基于改進(jìn)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)和位置分配策略的多AUV圍捕算法在二維障礙物環(huán)境中進(jìn)行了仿真。仿真環(huán)境是MATLAB仿真平臺，針對障礙物環(huán)境下，圍捕AUV與目標(biāo)AUV在速度比始終為1：1的情況下，進(jìn)行圍捕占位點分配與圍捕路徑規(guī)劃仿真。

圖9 BNN同速圍捕完成圖

圖10 GBNN同速圍捕完成圖

二維環(huán)境下的多AUV圍捕仿真中，所設(shè)柵格地圖為20×20的離散柵格地圖，黑色柵格代表水下靜態(tài)障礙物，白色柵格代表自由區(qū)域。圍捕團(tuán)隊中共有4個AUV，它們具有同等智能性，且可以進(jìn)行互相通信；逃逸目標(biāo)AUV有一個，也具有智能性，在檢測到圍捕AUV后向空曠區(qū)域逃跑，逃逸目標(biāo)AUV與圍捕AUV速度均設(shè)為1步/次。

BNN位置分配算法得到的同速圍捕完成圖如圖9所示，GBNN位置分配算法得到的同速圍捕完成圖如圖10所示，其中黃色星型圖標(biāo)代表逃逸目標(biāo)AUV，其余為圍捕AUV，所有AUV速度相同。逃逸目標(biāo)AUV初始位置為(11，11)，四個圍捕AUV分別以(21，21)，(21，2)，(2，20)和(2，2)坐標(biāo)為初始位置向逃逸目標(biāo)AUV航行。圖9中，逃逸目標(biāo)AUV在(21，15)處被圍?。粓D10中，逃逸目標(biāo)AUV在(8，4)處被圍住。

表1為BNN位置分配算法中AUV5在第25步陷入死區(qū)(圖9)，即到達(dá)柵格(18，8)之后的運動軌跡。由表1可以看出，AUV5在柵格(18，8)處停留，陷入死區(qū)。原因是傳統(tǒng)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)中，神經(jīng)元活性值來自周邊神經(jīng)元所傳遞的激勵和。當(dāng)AUV進(jìn)入死區(qū)，在死區(qū)神經(jīng)元活性值衰減到小于周邊神經(jīng)元之前，AUV將重復(fù)訪問活性值最大的死區(qū)柵格，逃離死區(qū)時間較長。當(dāng)采用GBNN算法進(jìn)行路徑規(guī)劃，則不會出現(xiàn)無法逃離死區(qū)的問題。在多次測試中，使用GBNN算法的AUV都會從死區(qū)邊緣繞路圍捕。由此可見，GBNN算法在逃離死區(qū)的問題中更有優(yōu)勢。

表1 BNN位置分配算法中：AUV5第24到30步坐標(biāo)

表2對使用位置分配的二維BNN算法和使用位置分配的二維GBNN算法兩種方法進(jìn)行對比。從表2可看出，兩種方法均能完成圍捕任務(wù)。其中，GBNN算法比BNN算法圍捕步數(shù)更少。所以綜上所述，使用位置分配的GBNN算法在圍捕占位點分配和路徑規(guī)劃問題中更具優(yōu)勢。

表2 兩種方法的比較

6 小結(jié)

本文針對二維水下圍捕的路徑?jīng)_突問題，提出了一種基于最優(yōu)總體行駛距離的“位置分配”圍捕算法，同時引入GBNN算法來進(jìn)行圍捕路徑規(guī)劃。在圍捕AUV與逃逸目標(biāo)AUV同速的情況下，該算法不僅能高效地完成圍捕任務(wù)，而且使得圍捕AUV協(xié)作系統(tǒng)總體行駛距離更短，效率更高，更好地節(jié)約了能源。本文只考慮了靜態(tài)障礙物環(huán)境，下一步可以將動態(tài)障礙物以及海流因素引入其中，考慮更加復(fù)雜環(huán)境下的多AUV協(xié)作圍捕任務(wù)。