基于生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的多AUV目標搜索?

孫奧林 曹 翔 肖 旭 徐麗雯

（淮陰師范學(xué)院物理與電子電氣工程學(xué)院 淮安 223300）

1 引言

水下機器人目標搜索是水下搜救、水下捕獲等水下任務(wù)的重要組成部分［1～2］。由于自治水下機器人（Autonomous Underwater Vehicle，AUV）自身攜帶能量有限，單個AUV很難在復(fù)雜水域完成目標搜索任務(wù)。因此，多AUV目標搜索成為了當今水下機器人研究的一個重要方向［3～4］。與陸地和天空機器人相比，水下機器人起步較晚，由于其具有相關(guān)性，陸地和天空機器人的目標搜索算法可以借鑒。對于多機器人的目標搜索算法，國內(nèi)外學(xué)者已取得了大量的研究成果。

在早期關(guān)于多機器人目標搜索問題的研究中，Ge和Fua在文獻［5］中提出一種用于動態(tài)未知連通環(huán)境的全覆蓋搜索方法，算法的思想是機器人在全覆蓋搜索的同時盡可能地搜索障礙物與已搜索區(qū)域附近一些難以到達的區(qū)域，并充分考慮如何減少重復(fù)搜索和時間花費。但在障礙物間的路徑寬度小于機器人搜索覆蓋范圍寬度的兩倍時，可能出現(xiàn)重復(fù)搜索的現(xiàn)象。

為了增加多機器人之間的協(xié)作，Yamauchi［6］提出了一種基于邊界的分布式多機器人目標搜索策略。該算法將“邊界”定義為已知開闊區(qū)域與未搜索區(qū)域之間的分界線。其使用柵格占有率的方法來表征所探索的地圖，多機器人之間分享各自的感知信息，維護獨立的全局地圖。處于搜索中的每個機器人不斷地選擇最近的邊界點對環(huán)境進行搜索，直到所有可達的區(qū)域都被搜索完畢而完成任務(wù)。由于這種策略各個機器人之間協(xié)調(diào)信息很有限，可能導(dǎo)致某些機器人駛往同一邊界造成碰撞以及重復(fù)搜索，搜索效率低下。

為了提高目標搜索的效率，市場經(jīng)濟算法常常應(yīng)用于多機器人目標搜索任務(wù)中。Zolt等在文獻［7］中提出一種基于市場經(jīng)濟機制的多機器人目標搜索算法。在該算法中各個機器人之間共享關(guān)于目標的信息，它們根據(jù)各自的局部地圖計算出到達目標的花費，并且以此作為投標價格，再按照第一價格密封標價拍賣法將目標即“標的”分配給出價最低的機器人。此種機制是分布式的，具有魯棒性、高效等特點。但機器人必須通過顯式的通信有意圖的協(xié)作，資源消耗較多，一旦通訊中斷性能將明顯下降。除此之外，但由于沒有考慮各目標之間的距離關(guān)系，所以此算法對搜索效率沒有太多提高。

對于未知環(huán)境中多機器人的目標協(xié)作搜索，Yoon和Qiao［8］提出一種基于同步的多AUV搜索算法，該算法能夠?qū)崿F(xiàn)大范圍的目標搜索。AUV通過定時的相聚完成數(shù)據(jù)的交換，實現(xiàn)對目標的協(xié)作搜索。該算法還具有冗錯能力，在部分AUV出現(xiàn)故障以后，同樣能完成搜索任務(wù)。但是該算法只研究了二維的環(huán)境且將環(huán)境理想化，沒有考慮環(huán)境中的障礙物，因此降低了該算法的實用性。Wagner等［9］提出了多機器人通過留下化學(xué)氣味軌跡的方式進行相互間的交流和協(xié)作機制，這種化學(xué)氣味能夠隨著時間變長而揮發(fā)，并且在機器人到達某一點后能夠增強其上的化學(xué)氣味。這種方法類似于Svennebring在文獻［10］所提出的一種基于蟻群優(yōu)化的目標搜索算法，其將地圖劃分為很多方形區(qū)域，并且機器人能夠在其走過路徑上留下軌跡。但是上述所有的方法都需要機器人能夠在探索環(huán)境中留下一些符號，或者使用一片集中區(qū)域（例如：共享的內(nèi)存區(qū)域）來記錄機器人的移動路徑，一旦搜索區(qū)域較大、機器人數(shù)量較多時，系統(tǒng)需要很大的存儲空間。因此不適合大范圍大規(guī)模的目標搜索任務(wù)。

綜上所述，雖然已有許多關(guān)于多機器人目標搜索的研究，但是行為搜索策略效率較低，機器人之間基本無協(xié)作，違背了使用多機器人進行目標搜索的最初目的；基于邊界的目標搜索策略要么某些機器人駛往同一邊界造成碰撞以及重復(fù)搜索，搜索效率也不高，要么系統(tǒng)中存在有中央節(jié)點，如若損壞整個系統(tǒng)將崩潰；市場經(jīng)濟機制搜索策略由于計算量大的缺點，只適用于靜態(tài)已知環(huán)境下的小規(guī)模的多機器人系統(tǒng)；基于信息素的方法需要大量存儲空間存儲機器人運動路徑，機器人數(shù)量增加時會增加算法的負擔，不適用于大范圍大規(guī)模的搜索任務(wù)。并且，對于多AUV目標搜索的報道較少。因此，本文針對未知水下環(huán)境中目標搜索算法進行研究，引入生物啟發(fā)神經(jīng)網(wǎng)絡(luò)，提出生物啟發(fā)多AUV搜索算法。將水下柵格地圖與生物啟發(fā)神經(jīng)網(wǎng)絡(luò)相聯(lián)系，神經(jīng)網(wǎng)絡(luò)中每一個神經(jīng)元與水下柵格地圖中的位置單元一一對應(yīng)，根據(jù)該神經(jīng)網(wǎng)絡(luò)中神經(jīng)元的在線活性輸出值分布情況制定AUV的搜索路徑規(guī)劃模型。旨在提高多AUV目標搜索的效率，提高AUV之間的協(xié)作性。通過仿真實驗證明生物啟發(fā)神經(jīng)網(wǎng)絡(luò)在多AUV目標搜索中的有效性。

2 基于生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的多AUV目標搜索算法

圖1 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖

本節(jié)對多AUV目標搜索算法進行研究，提出適合多AUV目標搜索的三維神經(jīng)網(wǎng)絡(luò)模型。將生物啟發(fā)神經(jīng)網(wǎng)絡(luò)模型的神經(jīng)元在空間中排列成三維的結(jié)構(gòu)分布，如圖1所示。每個神經(jīng)元與其周邊相鄰的神經(jīng)元（最多26個）互相連接，構(gòu)成三維的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。圖1顯示了一個3×3×3的三維神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)（為直觀起見，僅顯示中心神經(jīng)元的所有連接，其他神經(jīng)元的連接省略）。

神經(jīng)網(wǎng)絡(luò)中神經(jīng)元活性變化規(guī)律如下方程表示［11］：

其中，uk為神經(jīng)網(wǎng)絡(luò)中k位置處的神經(jīng)元活性值；ul是與神經(jīng)元k相鄰（具有連接）的神經(jīng)元l的活性值；參數(shù)A，B和D為正常數(shù)，-A反映了神經(jīng)元k的活性值uk的衰減速率；B和D分別是uk的上下限值，即uk∈[-D，B]；Ik表示神經(jīng)元k的外部輸入信號，Ik＞0表示激勵信號，Ik＜0表示抑制信號。

wkl表示神經(jīng)元k與l之間的神經(jīng)元連接權(quán)系數(shù)，定義為［12］

其中，|kl|表示在三維神經(jīng)網(wǎng)絡(luò)空間中神經(jīng)元k與神經(jīng)元l之間的距離，μ為常系數(shù)，一般定義在范圍（0，1）內(nèi)。

三維搜索路徑規(guī)劃模型是將AUV的搜索路徑規(guī)劃問題演變?yōu)閷ふ页鯝UV的下一個航行位置，只有準確找出了該位置，才能使AUV能夠快速地發(fā)現(xiàn)未知目標，且不會與障礙物發(fā)生碰撞。對此，必須把具體的動態(tài)環(huán)境和AUV前后時刻的航行位置聯(lián)系起來綜合決策出AUV的下一個航行位置。用建立的三維生物啟發(fā)神經(jīng)網(wǎng)絡(luò)模型來表示AUV的三維工作環(huán)境，并且神經(jīng)網(wǎng)絡(luò)中的每一個神經(jīng)元與柵格地圖中的位置單元一一對應(yīng)，就可以根據(jù)神經(jīng)網(wǎng)絡(luò)中每一個神經(jīng)元的活性輸出值分布情況來規(guī)劃AUV的搜索路徑。由此把AUV搜索路徑規(guī)劃的研究轉(zhuǎn)換為對神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中神經(jīng)元活性輸出值的研究，通過神經(jīng)元活性輸出值的分布情況來決策出AUV下一時刻的航行位置。首先計算出所有與當前神經(jīng)元相鄰的神經(jīng)元的活性輸出值，然后找出最大活性值的神經(jīng)元，最后AUV向著最大活性輸出值對應(yīng)的位置航行。當出現(xiàn)多個相鄰節(jié)點神經(jīng)元活性值為最大值的情況時，AUV會隨機選取其中一個神經(jīng)元的位置作為它的下一步航行的位置，這樣的路徑?jīng)Q策并不會影響整個搜索路徑規(guī)劃的過程。

在三維生物啟發(fā)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中，外部輸入信號包括激勵信號和抑制信號。其中目標作為激勵信號吸引搜索AUV向其靠近，而障礙物作為抑制信號排斥AUV使其不能靠近，避免發(fā)生碰撞。在神經(jīng)網(wǎng)絡(luò)中外部信號對應(yīng)神經(jīng)元的活性定義為

將外部信號的值代入式（1），計算輸出神經(jīng)網(wǎng)絡(luò)中每個神經(jīng)元的活性值。AUV根據(jù)神經(jīng)元的活性值選擇下一個航行位置Pn，其具體搜索路徑規(guī)劃模型為［13］

式中，Path是AUV的路經(jīng)集合；Pc，Pp，Pn分別表示AUV的當前位置、前一時刻位置和下一時刻位置；uk是當前神經(jīng)元的活性值；ul是周邊神經(jīng)元的活性值；|kl|是當前神經(jīng)元與周邊神經(jīng)元之間的歐氏距離。

式（4）表明，當AUV開始尋找下一時刻的航行路徑時，會將當前所處神經(jīng)元周邊的神經(jīng)元的活性值進行比較，選取活性值最大的神經(jīng)元所在的位置作為下一步的航行位置，此過程不斷地重復(fù)，直到AUV發(fā)現(xiàn)未知目標。因為目標所在的神經(jīng)元具有最大的活性值，起著激勵作用，一直引領(lǐng)AUV不斷靠近直至被發(fā)現(xiàn)；而障礙物所在的神經(jīng)元具有最小的活性值，起著抑制作用，因此AUV不會選擇此處神經(jīng)元所在的位置作為下一步的路徑，由此成功地規(guī)避障礙物。

3 三維水下環(huán)境中多AUV目標搜索仿真及分析

本節(jié)將驗證該算法的有效性，對靜態(tài)和動態(tài)情況下的三維多AUV目標搜索進行仿真研究，仿真在Matlab R2011a上實現(xiàn)。仿真實驗設(shè)置水下工作空間的大小為100×100×100，其中隨機的分布著各種形狀的障礙物。每個AUV和目標都視為質(zhì)點，不考慮其形狀。同時假設(shè)AUV是可以全方位運動的，它的觀察范圍為3×3×3。通過搜索靜態(tài)和動態(tài)未知目標的仿真實驗，考察本文提及的算法是否能夠快速地完成搜索任務(wù)，是否能自動避開障礙物。另外通過和其他算法的比較，考察本文所提及算法的性能。本節(jié)中算法的控制參數(shù)設(shè)置如表1所示。

表1 控制參數(shù)表

3.1 三維環(huán)境中未知靜態(tài)目標搜索

圖2 三維環(huán)境中未知靜態(tài)目標搜索仿真

首先測試本文提及算法在三維環(huán)境中對多個靜態(tài)目標搜索的能力。仿真實驗的初始位置如圖2（a）所示，搜索空間大小為一個100×100×100的立方體空間，空間中隨機的分布著4個AUV，4個位置未知的靜態(tài)目標，還有一些形狀各異的障礙物。而AUV 初始位置坐標分別為（10，80，20），（60，100，90），（90，10，50）和（90，90，10）。AUV對區(qū)域中目標搜索采用生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的方式。根據(jù)算法的原理，針對柵格地圖構(gòu)建100×100×100的拓撲神經(jīng)網(wǎng)絡(luò)。目標作為激勵輸入在神經(jīng)網(wǎng)絡(luò)中對應(yīng)神經(jīng)元的活性值為1，而障礙物作為抑制輸入在神經(jīng)網(wǎng)絡(luò)中對應(yīng)的神經(jīng)元活性值為-1。搜索任務(wù)開始以后，根據(jù)搜索路徑的規(guī)劃模型，AUV比較相鄰柵格的神經(jīng)元活性值，選擇神經(jīng)元活性值最大的柵格作為下一步的航行位置。所以AUV總是向著神經(jīng)元活性值最大的位置搜索，對應(yīng)到地圖上就是向著目標的位置航行。同時在搜索過程中障礙物對應(yīng)的神經(jīng)元活性值是最低的，所以根據(jù)算法原理AUV能夠自動的躲避障礙物。當目標進入任何一個AUV的觀察范圍以后，目標被發(fā)現(xiàn)。所有的目標都被發(fā)現(xiàn)以后搜索任務(wù)結(jié)束。圖2（b）顯示4個未知靜態(tài)目標被發(fā)現(xiàn)時各個AUV的最終搜索軌跡，靜態(tài)目標T1，T2，T3和 T4分別被AUV R1，R3，R4和R2發(fā)現(xiàn)。從圖中可見AUV不僅搜索到了目標，而且在搜索過程中自動躲避障礙物，沒有對已搜索區(qū)域重復(fù)搜索?？梢姳疚奶峒暗乃惴▽ξ粗o態(tài)目標的搜索是非常有效的。

3.2 三維環(huán)境中未知動態(tài)目標搜索

在實際的搜索任務(wù)中，時常需要對位置未知的動態(tài)目標進行搜索。這無疑增加了搜索的難度。但是本文提及的算法能夠克服這個困難。根據(jù)算法的定義，目標為激勵輸入對應(yīng)的神經(jīng)元活性值是最大的，AUV搜索路徑規(guī)劃策略是始終向著神經(jīng)元活性值大的位置搜索。根據(jù)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的傳遞性，當目標運動以后，AUV相鄰神經(jīng)元的活性值將隨之發(fā)生變化。因此移動目標運動的位置信息將通過神經(jīng)網(wǎng)絡(luò)傳遞給每一個AUV。AUV根據(jù)實時獲取的神經(jīng)活性值信息調(diào)整搜索的路徑，到達對未知動態(tài)目標搜索的目的。

如圖3顯示了AUV搜索到未知動態(tài)目標的過程。圖3（a）顯示了第一個動態(tài)目標被發(fā)現(xiàn)時的搜索過程。圖3（b）顯示了第二個動態(tài)目標被發(fā)現(xiàn)時各個AUV的搜索軌跡。從圖中可見不管目標怎么運動，AUV的搜索路徑總能隨之作出調(diào)整，向著目標的方向搜索?？梢姳疚奶峒暗乃惴ú粌H能夠搜索到未知的靜態(tài)目標，同樣對未知動態(tài)目標的搜索也是非常有效。

3.3 三維環(huán)境中部分AUV出現(xiàn)故障情況下的未知目標搜索

如果在搜索過程中部分AUV出現(xiàn)故障，將對多AUV系統(tǒng)的容錯性是一個極大的考驗。本節(jié)將檢驗本文提及的多AUV系統(tǒng)的容錯能力，對系統(tǒng)中部分AUV出現(xiàn)故障的情況進行仿真。首先對一個AUV出現(xiàn)故障的情況進行仿真，實驗中4個AUV對4個未知靜態(tài)目標進行搜索。

圖3 三維環(huán)境中未知動態(tài)目標搜索仿真

圖4一個AUV出現(xiàn)故障的未知目標搜索仿真

目標和AUV的初始位置和3.1節(jié)未知靜態(tài)目標搜索實驗相同。開始搜索的初期，4個AUV都是正常工作的。搜索了一段時間，R4出現(xiàn)了故障不能繼續(xù)工作，其余的機器人繼續(xù)搜索目標（如圖4（a）所示）。由于多AUV系統(tǒng)采用分布式的體系結(jié)構(gòu)，一個AUV出現(xiàn)故障不會使整個系統(tǒng)發(fā)生癱瘓。剩余正常的AUV將繼續(xù)搜索工作。當R3發(fā)現(xiàn)目標T3后，由于目標T4的吸引，R3繼續(xù)向著目標T4搜索。圖4（b）所示R3最終發(fā)現(xiàn)了目標T4，搜索任務(wù)結(jié)束。通過上述仿真實驗可見即使有AUV出現(xiàn)故障，本文提及的算法仍然能完成搜索任務(wù)，證明該算法有很強的容錯能力和多AUV的協(xié)作能力。

圖5 兩個AUV出現(xiàn)故障的未知目標搜索仿真

仿真實驗進一步驗證當不止一個AUV出現(xiàn)故障時，本文提及的算法是否還能完成搜索任務(wù)。圖5顯示了2個AUV出現(xiàn)故障時的目標搜索仿真結(jié)果。仿真實驗是4個AUV對2個未知靜態(tài)目標進行搜索。開始搜索的初期4個AUV都能正常工作。經(jīng)過10s的搜索后，AUV R4出現(xiàn)故障，停止搜索（如圖5（a）所示），其他的AUV繼續(xù)搜索。當搜索進行了20s時，另一個機器人R1又出現(xiàn)故障（如圖5（b）所示）。由于系統(tǒng)采用分布式的結(jié)構(gòu)體系，剩余的兩個AUV繼續(xù)搜索目標。最終AUV R2和R3發(fā)現(xiàn)了目標T1和T2（如圖5（c）所示）。雖然在搜索過程中兩個AUV出現(xiàn)了故障，但是在沒有對算法做任何參數(shù)修改的情況下剩余的AUV仍然完成了搜索任務(wù)，可見本文的算法有很好的容錯性，并且對于不同的工作環(huán)境不需要對算法的參數(shù)進行修改，證明該算法有很強的適應(yīng)性。

4 結(jié)語

本文對三維水下環(huán)境中的多AUV目標搜索算法進行了研究。針對水下環(huán)境中未知目標搜索，將生物啟發(fā)神經(jīng)網(wǎng)絡(luò)應(yīng)用到搜索算法中，分別選擇目標和障礙物作為生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的激勵輸入和抑制輸入，通過神經(jīng)元活性函數(shù)計算出神經(jīng)網(wǎng)絡(luò)中每個神經(jīng)元的活性值，AUV比較鄰近神經(jīng)元活性值大小確定下一步搜索的位置，從而規(guī)劃出一條有效的搜索路徑。從不同情況下的多AUV目標搜索仿真實驗可知，在三維的水下環(huán)境中本文提及的算法都能成功搜索到未知的靜態(tài)和動態(tài)目標。同時還通過實驗證明了多AUV系統(tǒng)中有部分AUV出現(xiàn)故障時仍然能完成搜索任務(wù)。本文最后對不同目標搜索算法進行了比較，從比較結(jié)果可知本文提及的算法縮短了搜索時間，降低了搜索路徑的重復(fù)率。雖然本文提及的算法有上述優(yōu)點，但是仍然存在一些不足，如環(huán)境模型較為簡單，并未考慮水流對目標搜索的影響；另外，將AUV假設(shè)為一個質(zhì)點，未考慮AUV的動力學(xué)和運動學(xué)模型，這些不足將在進一步的研究中解決。