基于多蟻群協同搜索算法的多AUV 路徑規劃

岳 偉，席 云，關顯赫

(大連海事大學 船舶電氣工程學院，遼寧 大連，116026)

0 引言

隨著人們對海洋認識和開發力度的不斷深入，勘探、繪制地形圖、清理化學物質泄漏、排雷和探測水下目標等水下作業常常借助自主水下航行器(autonomous undersea vehicle，AUV)完成。但是，由于AUV 自身攜帶動力能源有限，已不能滿足人們的需求[1]。為了使AUV 能夠在復雜、多變、難以預測的水下環境中，在有限的時間內高效地完成任務，多AUV 技術成為AUV 研究和發展的必然趨勢[2-3]。

國內外學者對AUV 路徑規劃問題已開展了廣泛的研究，主要有自組織神經網絡算法[4]、粒子群優化算法[5]和蟻群算法[6]等。Wang 等[6]提出了一種簡單的蟻群優化元啟發式算法來解決AUV 的路徑規劃問題，尋找一條從起點到終點避開障礙物的最短路徑。朱大奇等[7]基于自組織神經網絡，引入柵格信度函數概念，提出一種改進的柵格信度自組織(belief function self-organizing map，BFSOM)算法，在已知目標確切位置的情況下對柵格信度函數賦值，每次路徑點選擇過程中需要將目標位置和AUV 位置比較，根據距離最近的原則實現對目標位置的訪問。文獻[6]和[7]需要在已知目標位置的前提下規劃安全可行的路徑，與傳統的從起點到終點生成避障路徑的規劃任務不同，搜索路徑規劃因不確定目標位置而變得復雜。Wen 等[8]將蟻群算法與自組織神經網絡相結合，提出了一種全覆蓋路徑規劃方法，但僅適用于單個AUV。為了提高目標發現概率，張跟鵬等[9]將2 個AUV 以固定的隊形，對搜索區域進行搜索直至完成對任務區域的全覆蓋，理論上只要時間足夠長，該算法一定可以發現任務區域內存在的目標，但耗時較長，同時2 個AUV 的檢測區域存在部分重疊，雖然增加了重疊區域檢測的可信度，但也浪費了有限的傳感器資源，搜索效能較低。為了減少AUV 的平均搜索時間，提高目標發現概率，Yoon 等[10]提出了一種基于初始目標信息的多AUV 分布式協同搜索策略。上述研究需要在不同水深條件下，并假設AUV 搭載合成孔徑聲吶，在同一平面實現對不同深度目標的探測。AUV 執行搜索任務時需要考慮目標發現概率和聲吶探測距離的關系，以及AUV 之間的避碰約束，上述方法并未對此進行綜合考慮，因此規劃的結果并不能很好的反映AUV 協同搜索的需求。

針對上述搜索算法效率低，優化目標單一的問題，文中假設采用合成孔徑聲吶對不同水深的目標探測，并提出基于先驗信息的多蟻群協同搜索算法。主要研究內容如下：

1) 假設搭載合成孔徑聲吶可以在某一水平面對不同深度水下目標探測，首先建立二維正態分布的目標概率圖，進一步地根據目標概率圖初始化種群信息素濃度；

2) 算法綜合考慮目標發現概率以及AUV 轉向等因素，設計路徑選擇策略和信息素更新規則，以減少對航路點的重復選擇，從而提高目標發現概率；

3) 在信息素更新時，根據搜索路徑的收益值調整信息素濃度，增加收益值高的路徑信息素濃度，加快算法收斂速度。同時限制信息素濃度范圍，避免算法過快收斂。最后，通過仿真驗證該算法的有效性。

1 問題描述

在完全未知的水下環境中，使用多個相同類型的AUV 對若干個目標執行搜索任務，AUV 上載有探測設備(合成孔徑聲吶)，聲吶最大探測寬度為R，AUV 以自主協同的方式對任務區域展開搜索，期望以最小的代價在任務區內快速發現目標，圖1給出了多AUV 協同搜索目標的場景。

圖1 多AUV 協同搜索場景Fig.1 Scenario of cooperative search using AUVs

1.1 環境建模

文中采用柵格法對未知位置的水下目標進行建模。將長為Lx，寬為Ly，深為hz的海域劃分為三維柵格，設每個柵格位置對應目標存在概率值為pijk。為減少在執行搜索任務過程中AUV 頻繁的上浮或下潛，這里設三維空間中每個柵格的目標存在概率pijki，將該概率向xoy平面做投影，如圖2 所示，可得橫縱坐標相同的所有柵格中目標存在的概率為pij，其中i為柵格的橫坐標，j為柵格的縱坐標。pij=pijk1+pijk2+…+pijkn(kn為z軸方向柵格數)。

圖2 目標分布示意圖Fig.2 Diagram of target distribution

1.2 目標概率圖模型

根據建立的搜索環境模型，先驗信息只要知道目標位置的橫縱坐標，就可建立目標初始概率分布。目標位置的不確定性決定了文中研究的搜索本質上是一個隨機問題，對不確定環境下的目標進行搜索，通常采用正態分布函數來描述目標的存在狀態，即每個目標具有相同的概率分布。根據先驗信息已知目標m的初始位置為()，則目標m初始位置的聯合概率密度函數可表示為

2 搜索效能指標

在多AUV 執行搜索任務過程中存在以下問題：

1) 由于AUV 間的通信能力隨著機間距離增加而嚴重衰減，因此需要AUV 間保持在通信范圍內，但同時增加了AUV 碰撞的可能性；

2) AUV 能量有限，頻繁轉向也會增加能量消耗，因此需要減少轉向帶來的能量消耗，文中引入轉向代價函數。

式中：θmnθ為AUVm第nθ次轉向時轉向角度的絕對值；Cθ為系數；Nθ為總的轉向次數。

在AUV 協同搜索問題路徑優化過程中，不可避免地會出現各AUV 間路徑重合的情況。在相同的一段時間內，各AUV 間路徑重合易造成AUV 間的碰撞，重合的航路點數目越多，則該航路的威脅代價越大，因此在AUV 航路優化過程中，避免選擇威脅代價高的航路，定義為AUVm，v的碰撞威脅代價如下

式中，lapped為不滿足安全距離約束的航路點的數目；Cc為系數。

AUVm的威脅代價表示為

AUV 協同目標搜索問題中，優化的搜索路徑應該以最小的代價盡可能以最大的概率發現目標。由此可以得出協同搜索屬于一類組合優化問題，文中建立如下搜索效能指標函數：

式中：K為系數；N為搜索路徑柵格數目；zi為目標距離水平面距離；h為AUV 距水平面距離；為AUVm的航行代價。

3 多蟻群搜索算法

由于多AUV 搜索目標與蟻群覓食行為極為相似(見表1)，文中利用多蟻群算法進行多AUV協同路徑優化設計。將螞蟻分為Nv個種群，每個子群分別對應1 個AUV，將各子群間通過信息素的傳遞完成覓食搜索的能力應用于具有通信能力的多 AUV 協同搜索目標的任務中。定義蟻群AC=｛AC j，j=1，2，…，Nv｝為AUV 對應的螞蟻種群數目，各子群定義為ACj=｛Ant l，l=1，2，…，M｝，其中M為各子群中的螞蟻個數。多蟻群算法的結構如圖3 所示。各子群中每只螞蟻都具有1 個獨立的運算單元，依據設計的搜索規則及與其他螞蟻交互信息來進行局部優化，下文將分別從信息素初始化、路徑轉移以及信息素更新分析蟻群如何為多AUV 進行協同路徑優化。

表1 多AUV 協同搜索與蟻群覓食行為關系Table 1 Relationship between multi-AUVs cooperative search and ant colony foraging behavior

圖3 基于多蟻群算法AUV 協同搜索結構圖Fig.3 Structure of cooperative search for multi-AUVs based on multi-ant colony algorithm

3.1 信息素初始化

為充分利用已有的先驗信息，使各蟻群中的螞蟻盡可能提高目標發現概率，提出如下信息素初始化函數

式中：τi0表示柵格i的信息素濃度；pi為每個柵格中的目標概率值；τ0為常數。該初始函數可有效地將信息素初值與搜索區域目標信息進行關聯。

3.2 路徑選擇策略

每只螞蟻按照狀態轉移規則從起點選擇下一個柵格，在t時刻第l只螞蟻從柵格i轉移到柵格j的狀態轉移規則設計如下

式中：UK為當前可作為下一跳的柵格集合，UK=N-Tabuk，且Tabuk 表示已訪問過的柵格集合；ηij為路徑的啟發信息，且，k1和k2為常數；φjk(t)表示其余螞蟻子群信息素在柵格j處的值；α為在柵格選擇中信息素的重要程度；β為啟發信息在螞蟻選路決策中的重要程度；γ為其他種群的信息素對航路點選擇的影響，γ越大抑制作用越強，可以避免不同AUV 之間對航路點的重復選擇。

3.3 信息素更新規則

信息素更新分為局部信息素更新和全局信息素更新2 個階段[11-12]。在局部信息素更新過程中基于排序螞蟻算法進行設計，選出每一次迭代中部分優秀的個體信息素進行增強，在引導后代螞蟻搜索的同時，保證了部分搜索較差螞蟻的生存能力，有利于搜索的多樣性，同時考慮各代螞蟻搜索路徑的優劣，采取不等量信息素增強方式，信息素的增強量和每一只螞蟻搜索效能密切相關。

3.3.1 局部信息素更新

針對傳統的信息素更新容易出現停滯的情況，提出一種改進信息素更新方式： 根據搜索路徑解的優劣情況，動態地修改信息素更新方式。一方面保證了搜索空間足夠大，以盡可能尋找最優解，另一方面有效地將當前解的信息重點放在適應值較優的個體，從而加快收斂到全局最優解[12-13]。

在每一次迭代過程中，對螞蟻經過的柵格進行信息素更新，柵格j處的信息素按下式進行更新

式中：τjk(t+1)和τjk(t)分別是更新前后網格j內第k個種群信息素的值；ρ為信息素揮發系數；Δτjk(t+1)是信息素更新值，信息素按下式更新

3.3.2 全局信息素更新

在整個蟻群完成一次迭代后，選出每個種群中本次迭代解最優的螞蟻，信息素按下式更新

式中：k*為權值；f（Jklbest）為種群k中最優搜索收益函數。

在局部信息素更新時采用不等量信息素增強方式，可加快算法的收斂速度，但同時會導致陷入局部最優，為避免這種情況的發生，將柵格內每個種群k的信息素濃度限制在［τmin，τmax］，保證算法快速收斂速度的同時增加搜索空間，綜合局部和全局的信息素更新規則

4 仿真結果與分析

為了驗證文中算法的有效性，在 Matlab 2015b 環境下建立了多AUV 協同搜索仿真環境，采用3 個AUV 對區域為20 km ×20 km海域進行搜索，聲吶的探測半徑R=1000 m，將搜索海域分成20 × 20的柵格(聲吶每次完全覆蓋一個柵格)，區域內存在10 個深度不同的目標，每個柵格同一時刻最多只存在一個目標，目標概率分布如圖4 所示。為驗證算法的有效性，將從多個角度進行仿真，并和傳統的搜索方法進行對比。

圖4 目標分布概率圖Fig.4 Diagram of target distribution probability

情景1： 給出步長為30，40，50 條件下的搜索路徑圖。3 個AUV 的初始位置分別為(1，1)，(1，16)，(20，19)，如圖5 所示。

圖5 多蟻群算法搜索路徑Fig.5 Search path of multi-ant colony algorithm

圖5 中，3 種步長情況下AUV 分別發現5 個，6 個和7 個目標，增加步長可以提高目標的發現概率，但需要浪費更多的算力，以及更長的搜索時間。

情景2： 并行搜索、貪婪搜索和未改進蟻群算法的搜索路徑如圖6 所示。從圖中可以看出，步長40 條件下，文中搜索方法明顯優于并行(發現3 個目標)和貪婪算法(發現5 個目標)，未改進的蟻群算法雖然也發現了6 個目標，但是AUV 之間存在較高碰撞概率，且存在大量重復搜索路徑和頻繁的轉向，搜索效能較低。

圖6 其他算法搜索路徑對比Fig.6 Comparison of search paths of other algorithms

情景3： 相同數目的AUV 在不同搜索方式下的目標發現概率(若對同一柵格重復搜索，目標發現概率只算一次)。在計算目標發現概率時考慮聲吶探測距離與目標的相對距離。以步長60 為例，在20 km ×20 km的搜索區域內3 個AUV 發現概率隨搜索時間的變化。從圖7 可知，前50 步并行算法效率最低，隨著搜索時間的增加，并行算法超過了貪婪算法，發現貪婪算法和文中方法目標發現概率幾乎相同，并行搜索發現概率較低；當搜索步長大約40 時，貪婪算法目標發現概率增加緩慢，主要原因是隨著搜索步長的增加，貪婪搜索路徑重疊嚴重；在搜索步長到50 時，并行搜索發現概率超過貪婪搜索；步長為60 時，文中算法目標發現概率約為75%，因種群間缺乏交流機制，未改進的蟻群算法目標發現概率約為69%，且始終低于改進多蟻群算法。

圖7 不同算法目標發現概率比較Fig.7 Comparison of search probabilities of different algorithms

情景4： 50 次仿真不同算法搜索到的目標數目。表2 是3 個AUV 在20 km×20 km 區域，搜索隨機分布的10 個目標，50 次仿真所得4 種方法不同步長搜索到的目標平均數目。

表2 不同方法下搜索目標數目比較Table 2 Numbers of search targets by different methods

文中方法在步長為20 時，平均發現目標3.3個；步長為60 時，平均發現目標8.3 個?？梢钥闯?，文中方法搜索目標數目遠高于其余3 種算法。

情景5： 在搜索步長為40 時，經過200 次迭代搜索效能的變化。傳統蟻群算法和改進后的蟻群算法搜索效能和迭代次數比較如圖8 所示。圖中：a是在傳統蟻群算法信息素的更新方式下，按照螞蟻經過次數等量的增加每條路徑的信息素濃度，經過約110 次迭代，最佳搜索效能為17.3；c是在傳統蟻群算法基礎上加快收斂速度的結果，約經過40 次迭代，搜索效能為16；b是對收斂速度和避免過快收斂折衷處理后的結果，經過60 次迭代，最佳搜索效能約為17?？梢姡倪M的信息素方式在加快收斂速度的同時，還能保證解的質量。

圖8 搜索效能對比曲線Fig.8 Comparison curves of search effectiveness

5 結束語

文中基于搜索目標隨機分布的概率圖特點，建立多個指標(包括搜索率、轉彎次數、避碰和重復路徑等)，提出一種改進的多蟻群優化算法，充分考慮目標存在概率和轉向的影響，各種群之間通過信息素的排斥，減少對其他種群選擇過的航路點的重復選擇。仿真結果表明，該算法實現AUV 協同目標搜索，有效減少航路重合，以較大概率發現目標。下一步研究中將進一步考慮AUV協同搜索時存在通信受限、涌浪干擾、可見度低等問題，以期得到更符合實際的搜索方法。