自由運動方向下改進蟻群算法的AUV路徑規劃*

周 鑫 徐榮武，2 程 果，2 高端陽

（1.海軍工程大學振動與噪聲研究所 武漢 430033）（2.船舶振動噪聲重點實驗室 武漢 430033）（3.海軍大連艦艇學院航海系 大連 116000）

1 引言

水下自主航行器（AUV）具有機動范圍大，靈活性好、隱蔽性高等優點，使它廣泛應用于軍用、民用領域［1］。水下航行器在執行水下任務的過程中，常常會遇到各種障礙物，或不可靠近的物體，尤其是在對抗演練，搜素穿越的過程中，其關鍵問題就是路徑規劃。

蟻群算法是路徑規劃的常用方法，使用蟻群算法進行環境建模的基本思路為柵格法［2～4］，即將環境劃分為大小相同的正方形柵格，將AUV 視為一個質點，每次移動時從當前位置向臨近的柵格移動。這種方法雖然建立簡單表示方便，但卻限制了AUV 其移動角度，只能向固定的方向前進，如0°，45°，90°等；同時允許其在較短步長內改變較大的移動方向，甚至可以調轉180°，這與AUV 在水下實際運行狀況存在較大差異。

由于AUV 所處的水下環境，及其自生結構原因，其機動能力、姿態調整能力有限，傳統意義上無約束的路徑規劃方式在實際運用中具有一定的難度。針對這個問題，本文提出一種自由運動方向下基于信息素初始布置的改進蟻群算法，該方法以改進的人工勢場法規劃路徑作為初始路徑進行信息素初始布置，能夠在AUV 在轉向角度受到合理限制的情況下完成對復雜動態環境路徑規劃。

2 改進的人工勢場法路徑規劃

人工勢場法（Artificial Potential Field，APF）是由Khatib 最早引入到移動機器人的避障及路規劃領域中［5］，用它進行路徑規劃雖然簡單，但是也有著其固有的局限性，例如存在局部極小值、目標不可達，狹窄路線抖動等問題［6～8］。而在面對動態障礙物時，這些問題在應對動態障礙物環境時會被弱化，但也容易出現受迫運動的情況。為此提出有利前進方向判斷解決AUV 受迫運動的問題，同時基于可視圖法對路徑規劃進一步優化，并以該路徑為基礎作為改進蟻群算法進行初始信息素布置。

2.1 人工勢場法的有利前進方向判斷

對AUV 而言，該方法是在AUV 運動環境中建立虛擬勢場，由目標點產生的引力勢場和障礙物產生的斥力勢場組成，AUV 在引力和斥力的共同作用下，向目標點移動。

通過分析AUV 受力情況可知，在AUV 所受到的引力與斥力角度接近同向或反向時，會使AUV移動出現抖動，在引力與斥力角度完全同向或反向時，則會出現局部極小值。若任其保持在此狀態下，會使得AUV無法解脫或需要大量時間解脫。

本文結合AUV 與動態障礙物相遇的方向和位置，采用向有利于規避障礙物并靠近目標點的方向調整引力角度的方式，在脫離抖動狀態的同時，以有利方向繞過障礙物。

當AUV 規避動態障礙物時，可以根據相AUV與障礙物的相對運動方向分為正向障礙物和側向［9］。對于正面障礙物，AUV移動方向與障礙物移動方向相同或相反，AUV 可以選擇順時針方向或逆時針方向進行規避；對于側向相遇障礙物，AUV移動方向與障礙物移動方向形成一定的夾角，選擇有利于靠近目標點的方向前進，如圖1所示。

圖1 測向障礙物

2.2 基于可視圖法的動態障礙物規避路徑優化

為進一步優化AUV 規避動態障礙物的移動路徑，通過可視圖法［10］對AUV 所受引力方向進行調整，從而達到移動路徑優化的目的。

可視圖法的基本思想是在AUV 移動空間中的任意形狀的障礙物看成是由多邊形或者多面體組成的，在此基礎上，連接AUV、障礙物、目標點的所有頂點，并確保所有連接線與障礙物都沒有任何的交點。將可視圖法與人工勢場法相結合，通過可視圖法對AUV 所受引力方向進行調整，可以達到移動路徑優化的目的。根據可視圖法的基本原則，最優路徑應為AUV 所在位置到障礙物邊界點連線，對曲邊的障礙物而言即為切線。當判斷得知AUV與動態障礙物在相遇路線上時，找到一個時間點t，使得AUV 初始位置到該時刻上障礙物的切線長度，等于這段時間AUV 的運動距離。如圖2所示，即：

圖2 可視圖法角度調整示意圖

式中，l為AUV 初始位置R到切點P的距離，t0為初始時間或繞過上一個障礙物的時間點，f為移動頻率，L為移動步長。

根據有利前進方向判斷可得調整角度：

式中，θo為t時刻下，AUV 移動方向到障礙物位置方向的角度；θr為t時刻下，障礙物位置方向與相應切線的夾角；λ為有利前進方向。

當調整角度為正時，逆時針調整角度；當調整角度為負時，順時針調整角度。當AUV 與障礙物距離較遠時，采用基于可視圖法優化的方案移動，當AUV 靠近障礙物時，在障礙物產生的斥力和抖動解除方法作用下，選擇有利前進方向繞過障礙物，繼續對下一個可能相遇的障礙物重復上述操作。

3 改進的蟻群算法路徑規劃

蟻群算法是由Dorigo.M 等在20世紀90年代提出的一種新型進化算法，由對螞蟻搜索問題的研究得出此算法。螞蟻在覓食過程中，會在通過的路徑上會留下信息素，根據路徑上信息素的大小，螞蟻會逐漸選擇信息素更大的路徑前進，信息素濃度越大，該路徑被選擇的概率就越大，在整個螞蟻系統中形成一個正反饋機制，最終找到一條從起點到終點的最優路徑［11～13］。

本文針對AUV 在水下實際運動規律，提出了AUV 在合理的可轉向范圍內自由選擇運動方向的算法模型，同時為提高路徑收斂速度，提出初始信息素布置的改進方法。

3.1 自由運動方向下的蟻群算法

傳統蟻群算法是將信息素分布在每一段可能經過的路徑上，AUV 可以到達的位置是預先設定且有限的。自由運動方向下的蟻群算法模型是將AUV 移動的空間中設置若干個信息素點，用于儲存蟻群算法中所需的信息素，這些信息素點僅用于計算每個步長附近的信息素，并不要求AUV 的每一步起點或終點落到這些信息素點上。從理論上說，AUV可以到達運動環境中的任意位置。

AUV 在移動過程中，根據上一步的移動方向和設定的最大轉角，確定在新的步長時間段內最大可轉向范圍。如圖3所示，AUV可以在此范圍內進行轉向，在轉向范圍內將可轉向角度分為若干不同路徑，對每個路徑方向終點附近的信息素點的信息素均值，作為該路徑上的信息素，最后依據輪盤賭的方式隨機選擇路徑。

圖3 自由運動方向下的算法模型示意圖

3.2 信息素初始布置

在通過改進的人工勢場法規劃出初始路徑后，基于此路徑對移動空間中的信息素點進行初始化，將AUV 移動的空間中劃分出i×j個信息素點，用于儲存蟻群算法中的信息素，當信息素點到初始路徑距離小于dL時，為該信息素點進行賦值，其信息素初始值為

3.3 人工勢場法臨時修正

為了加快路徑收斂速度，可以利用AUV 與障礙物、目標點的位置關系，基于人工勢場法受力分析，為引力方向上的信息素點的信息素數值，從而對AUV移動進行進一步引導。如圖4所示。

圖4 人工勢場法臨時信息素修正示意圖

在AUV 前進到任意位置，會受到來自目標點的引力和來自障礙物的斥力，其合力為

在合力方向的一定距離上確定為臨時目標點，對臨時目標點附件的信息素點進行修正，距離該點越近，信息素點上的信息素變得越大：

式中：kf為臨時信息素調整參數；df為勢場法對信息素的影響范圍；dijf為第i行、第j列信息素點到勢場法目標點的距離。

3.4 轉移概率

將傳統算法中固定在路徑中的信息素釋放到整個移動空間內，用每個步長終點附近的信息素點作為選擇該路徑的概率計算依據，轉移概率為

3.5 不利路徑回溯與排除

為保證路徑搜索的效率，當AUV 運行到超出信息素布置范圍，或與障礙物相遇時，使其路徑返回到上一步重新進行路徑方向選擇，若在同一位置已多次需要進行回溯，則增加路徑向前回溯長度。同時設置一個閾值，當AUV 回溯次數超過這一閾值時，則判斷該路徑搜索失敗，停止該路徑的搜索并將該路徑排除，重新進行新的路徑搜索。

3.6 精英螞蟻系統的信息素更新

在每一代蟻群搜索路徑后，對到目前為止已經規劃出的路徑進行排序，選擇所有歷史路徑中最短的一部分路徑進行信息素更新；精英螞蟻路徑信息素更新方式與初始信息素更新方式類似，但其信息素作用距離應根據實際情況進行調整。

3.7 改進的蟻群算法路徑規劃流程

如圖5所示。

圖5 改進的蟻群算法路徑規劃流程圖

4 試驗仿真

設定AUV在10*10的空間內進行路徑規劃，在空間內設置2000*2000 個信息素點用于儲存信息素，建立復雜的移動環境，在移動空間中設置動態障礙物3個和靜態障礙物4個，各障礙物距離較近，相關參數如表1。

表1 復雜動態環境參數設置表

4.1 基于可視圖法改進的人工勢場法路徑規劃仿真分析

分別采用傳統人工勢場法（算法一）、加入有利前進方向判斷的勢場法（算法二）、基于可視圖法改進的勢場法（算法三）對AUV 移動路徑進行規劃，驗證改進的人工勢場法在路徑規劃中可行性。不同算法下路徑規劃情況如圖6所示，靠近各障礙物步數及到達目標點步數分析如表2所示。

表2 路徑節點分析表

圖6 不同算法繞行障礙物

圖7 簡單環境-方案一-路徑示意圖

圖8 簡單環境-方案二-路徑示意圖

從圖9、表2 可以看出，傳統勢場法在面對動態障礙物時，會使AUV 受迫與動態障礙物一起運動，需要大量時間進行解脫；而加入有利前進方向判斷的勢場法能夠有效避免這個問題。同時，基于可視圖法改進的勢場法能夠讓AUV 更早的選擇有利前進方向繞過障礙物；傳統勢場法使AUV 在靜態障礙物3、4 的斥力和目標點的引力方向基本相反，導致其無法繼續向目標點前進；基于可視圖法改進的勢場法，相對于加入有利方向判斷的勢場法能夠提前選擇繞行障礙物的方向，提高繞過障礙物的效率，優化率為4.2%。

圖9 簡單環境-方案三-路徑示意圖

4.2 改進的蟻群算法仿真分析

分別在簡單動態環境和復雜動態環境中對改進的蟻群算法進行仿真分析，使AUV 能夠在有限制的轉向范圍內自由選擇前進方向，驗證算法的可行性。算法基本參數如表3所示。

表3 改進的蟻群算法參數表

在此參數的基礎上，每代螞蟻尋路結束后，選取歷史最優的10 條路徑對環境信息素進行更新。同時對本文采用的不同優化模塊（人工勢場法臨時修正、路徑回溯與排除、信息素初始布置）進行分析，仿真方案如表4所示。

表4 優化模塊選擇方案表

1）簡單動態環境仿真

簡單動態環境中設置動態障礙物2 個，靜態障礙物3 個，各障礙物距離較遠，相關參數如表5所示，達到相應的迭代次數后，各方案歷史最優的10條路徑如圖7～圖10所示。

表5 簡單動態環境障礙物設置

圖10 簡單環境-方案四-路徑示意圖

由圖可知，在簡單的動態環境中，方案一至方案三在一次迭代后找到的路徑都比較分散，隨著迭代次數的增加能夠逐漸收斂，并且最終都能收斂到最優路徑附近，而方案四中一次迭代后路徑收斂程度明顯優于其他方案。從表6可以看出，加入不同的優化模塊能夠有效加快迭代速度，并縮短最優路徑，其中方案四用時最短、搜索路徑最優，驗證了改進的蟻群算法在動態障礙物環境下的可行性。

2）復雜動態環境

復雜動態環境中障礙物設置與驗證勢場法時一致，如表所示。各方案在不同迭代次數后歷史最優的10條路徑如圖11～圖14所示。

圖11 復雜環境-方案一-路徑示意圖

圖12 復雜環境-方案二-路徑示意圖

圖13 復雜環境-方案三-路徑示意圖

圖14 復雜環境-方案四-路徑示意圖

由路徑圖和表7可知，方案一至方案三在一次加入勢場法修正算法和不利路徑回溯與排除算法后，能夠加快迭代速度，縮短最優路徑，但難以適應復雜動態環境中的狹窄通道，只能找到局部次優路徑。在方案四中，進行初始信息素布置后，能夠迅速找到最優路徑，驗證了改進的蟻群算法在復雜的動態環境中的可行性。

表7 復雜動態環境下各方案仿真數據對比

5 結語

本文針對AUV 在水下姿態調整能力有限的特征，提出了一種自由運動方向下基于信息素初始布置的改進蟻群算法，使AUV 能夠在合理可轉向范圍限制下完成路徑規劃。建立AUV 在合理的可轉向范圍內自由運動的算法模型，并以基于可視圖法改進的人工勢場法規劃的路徑為初始路徑，為運動環境進行信息素初始布置，再引入勢場法信息素臨時修正和不利路徑回溯與排除等優化算法，實現了對蟻群算法的改進。通過仿真實驗驗證可得，改進的人工勢場法較傳統勢場法路徑長度縮短約4.2%；改進的蟻群算法較改進的勢場法路徑長度再縮短約8.1%，并且能夠在復雜的動態環境下快速找到最優路徑。