基于生物啟發神經網絡的多AUV目標搜索?

孫奧林 曹 翔 肖 旭 徐麗雯

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

1 引言

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

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

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

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

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

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

2 基于生物啟發神經網絡的多AUV目標搜索算法

圖1 神經網絡結構圖

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

神經網絡中神經元活性變化規律如下方程表示［11］：

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

wkl表示神經元k與l之間的神經元連接權系數，定義為［12］

其中，|kl|表示在三維神經網絡空間中神經元k與神經元l之間的距離，μ為常系數，一般定義在范圍（0，1）內。

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

在三維生物啟發神經網絡結構中，外部輸入信號包括激勵信號和抑制信號。其中目標作為激勵信號吸引搜索AUV向其靠近，而障礙物作為抑制信號排斥AUV使其不能靠近，避免發生碰撞。在神經網絡中外部信號對應神經元的活性定義為

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

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

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

3 三維水下環境中多AUV目標搜索仿真及分析

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

表1 控制參數表

3.1 三維環境中未知靜態目標搜索

圖2 三維環境中未知靜態目標搜索仿真

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

3.2 三維環境中未知動態目標搜索

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

如圖3顯示了AUV搜索到未知動態目標的過程。圖3（a）顯示了第一個動態目標被發現時的搜索過程。圖3（b）顯示了第二個動態目標被發現時各個AUV的搜索軌跡。從圖中可見不管目標怎么運動，AUV的搜索路徑總能隨之作出調整，向著目標的方向搜索。可見本文提及的算法不僅能夠搜索到未知的靜態目標，同樣對未知動態目標的搜索也是非常有效。

3.3 三維環境中部分AUV出現故障情況下的未知目標搜索

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

圖3 三維環境中未知動態目標搜索仿真

圖4一個AUV出現故障的未知目標搜索仿真

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

圖5 兩個AUV出現故障的未知目標搜索仿真

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

4 結語

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