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

蔣驍?shù)希饰难?/p>

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

1 引言

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

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

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

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

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

圖1 二維柵格地圖

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

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

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

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

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

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

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

4.1 基于“位置分配”的圍捕占位點(diǎn)分配算法

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

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

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

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

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

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

圖4 “位置分配”流程圖

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

圖5 “位置分配法”后的占位點(diǎn)分配情況

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

在上一節(jié)中確定圍捕AUV與圍捕占位點(diǎn)之間的分配關(guān)系后，接著需要解決圍捕AUV如何到達(dá)圍捕占位點(diǎn)的問(wèn)題。針對(duì)該路徑規(guī)劃問(wèn)題，本節(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ì)算神經(jīng)網(wǎng)絡(luò)的活性值，與BNN所采用的微分方程相比，能夠有效降低算法計(jì)算量，提升算法運(yùn)算速度。

4.2.1 GBNN算法原理

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

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

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

(1)

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

(2)

(3)

(4)

式中，γ為正常數(shù)，|i-j|表示的是第i個(gè)神經(jīng)元到第j個(gè)神經(jīng)元之間的歐幾里得距離，代表每個(gè)神經(jīng)元僅與其周圍8個(gè)神經(jīng)元存在側(cè)連接關(guān)系。由于神經(jīng)元之間的連接關(guān)系不具有方向，所以連接權(quán)系數(shù)Wij具有對(duì)稱特性，即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)變化實(shí)時(shí)更新。由于水下環(huán)境建模時(shí)，水下地圖已經(jīng)被離散化柵格地圖，所以這里將神經(jīng)網(wǎng)絡(luò)與離散化柵格地圖意義對(duì)應(yīng)起來(lái)，就可以使得神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元活性值根據(jù)水下環(huán)境變化而變化。圖7展示了將圖1中的柵格地圖(圖7(a))對(duì)應(yīng)到二維神經(jīng)網(wǎng)絡(luò)中(圖7(b))。

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

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

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

(6)

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

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

5 仿真結(jié)果

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

圖9 BNN同速圍捕完成圖

圖10 GBNN同速圍捕完成圖

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

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

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

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

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

表2 兩種方法的比較

6 小結(jié)

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