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

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

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

1 引言

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

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

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

2 改進的人工勢場法路徑規(guī)劃

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

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

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

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

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

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

圖1 測向障礙物

2.2 基于可視圖法的動態(tài)障礙物規(guī)避路徑優(yōu)化

為進一步優(yōu)化AUV 規(guī)避動態(tài)障礙物的移動路徑，通過可視圖法［10］對AUV 所受引力方向進行調(diào)整，從而達到移動路徑優(yōu)化的目的。

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

圖2 可視圖法角度調(diào)整示意圖

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

根據(jù)有利前進方向判斷可得調(diào)整角度：

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

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

3 改進的蟻群算法路徑規(guī)劃

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

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

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

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

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

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

3.2 信息素初始布置

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

3.3 人工勢場法臨時修正

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

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

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

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

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

3.4 轉(zhuǎn)移概率

將傳統(tǒng)算法中固定在路徑中的信息素釋放到整個移動空間內(nèi)，用每個步長終點附近的信息素點作為選擇該路徑的概率計算依據(jù)，轉(zhuǎn)移概率為

3.5 不利路徑回溯與排除

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

3.6 精英螞蟻系統(tǒng)的信息素更新

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

3.7 改進的蟻群算法路徑規(guī)劃流程

如圖5所示。

圖5 改進的蟻群算法路徑規(guī)劃流程圖

4 試驗仿真

設(shè)定AUV在10*10的空間內(nèi)進行路徑規(guī)劃，在空間內(nèi)設(shè)置2000*2000 個信息素點用于儲存信息素，建立復(fù)雜的移動環(huán)境，在移動空間中設(shè)置動態(tài)障礙物3個和靜態(tài)障礙物4個，各障礙物距離較近，相關(guān)參數(shù)如表1。

表1 復(fù)雜動態(tài)環(huán)境參數(shù)設(shè)置表

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

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

表2 路徑節(jié)點分析表

圖6 不同算法繞行障礙物

圖7 簡單環(huán)境-方案一-路徑示意圖

圖8 簡單環(huán)境-方案二-路徑示意圖

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

圖9 簡單環(huán)境-方案三-路徑示意圖

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

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

表3 改進的蟻群算法參數(shù)表

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

表4 優(yōu)化模塊選擇方案表

1）簡單動態(tài)環(huán)境仿真

簡單動態(tài)環(huán)境中設(shè)置動態(tài)障礙物2 個，靜態(tài)障礙物3 個，各障礙物距離較遠，相關(guān)參數(shù)如表5所示，達到相應(yīng)的迭代次數(shù)后，各方案歷史最優(yōu)的10條路徑如圖7～圖10所示。

表5 簡單動態(tài)環(huán)境障礙物設(shè)置

圖10 簡單環(huán)境-方案四-路徑示意圖

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

2）復(fù)雜動態(tài)環(huán)境

復(fù)雜動態(tài)環(huán)境中障礙物設(shè)置與驗證勢場法時一致，如表所示。各方案在不同迭代次數(shù)后歷史最優(yōu)的10條路徑如圖11～圖14所示。

圖11 復(fù)雜環(huán)境-方案一-路徑示意圖

圖12 復(fù)雜環(huán)境-方案二-路徑示意圖

圖13 復(fù)雜環(huán)境-方案三-路徑示意圖

圖14 復(fù)雜環(huán)境-方案四-路徑示意圖

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

表7 復(fù)雜動態(tài)環(huán)境下各方案仿真數(shù)據(jù)對比

5 結(jié)語

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