改進型蟻群算法的AUV三維路徑規劃

付振秋，季 光，楊 瑛

(中國航空綜合技術研究所，北京 100028)

0 引 言

隨著科學技術的發展，AUV在海洋資源開發、環境質量監測、水下作戰等領域發揮著越來越重要的作用。面對復雜多變的水域環境，三維路徑規劃是保證AUV安全完成任務的關鍵技術之一。全局路徑規劃和局部路徑規劃是復雜多變環境下的AUV根據障礙物類型進行的分類，由于全局路徑規劃主要針對環境中靜止不變且信息已知的障礙物，能夠更好地提供路徑規劃的解決方案，也因為如此近年來，AUV三維空間下的全局路徑規劃成為大家研究的熱點之一。目前，人工勢場法、A*算法、神經網絡算法、遺傳算法、人工免疫算法、模糊推理算法、粒子群算法等是最常用的路徑規劃算法。

本研究在蟻群算法的基礎上對該算法進行優化，融合了粒子群算法和人工勢場法，并在多目標環境路徑規劃中增加了路徑代價的函數，使在融合算法下得到最優路徑長度基礎上充分考慮外界環境及探測干擾和自身能源的消耗問題。

1 路徑規劃相關模型建立

1.1 環境模型建立

環境模型是AUV路徑規劃的首要環節，將三維現實環境特征進行提取和解析，并轉化為計算機模擬路徑規劃過程中的地圖模型數據。環境建模的方法很多，如可視圖法、自由空間法、柵格法等。由于柵格法的地圖創建和維護比較容易，主要內容是以柵格為基礎單位，離散化三維環境模型，所以本研究采用柵格法。設置三維空間為：水平面與XY平面重合，AUV的運動主方向定位X軸且機身頭為X軸的正方向（起點與終點分別對應對應X軸的最大值和最小值），垂直于水平面方向定位Z軸。這樣三維空間就可以分為若干基本單位柵格，以AUV開始運動的點作為空間的零點位置，其他障礙物及空位區域也就進行了相應的方位坐標確定。柵格[1]在計算時可選擇使用坐標法或是序號法，本研究為了直觀地判斷點與點的位置關系將采用坐標法。

在路徑規劃過程中對環境模型建立的要求：

1）將AUV的中心位置用質點表示，同時對障礙物的尺寸按AUV的半徑作適當擴展，以保證AUV能夠無碰撞地運動；

2）AUV每次運動只能在所有柵格的中心位置（也就是柵格體的中心），不可在邊界或是端點處；

3）AUV的下一個位置只能是相鄰的26個柵格體的自由柵格體中；

4）為避免沒有必要的局部最優，某一個柵格體的上下左右前后有5個是障礙柵格，則此柵格體就默認為障礙柵格體；

5）不考慮環境中海流、潮流等對路徑規劃的干擾。

1.2 干擾模型建立

1.2.1 障礙模型

AUV在障礙環境下進行路徑規劃，可使用人工勢場法計算AUV與障礙間的障礙代價，對AUV的運動路徑進行調整。AUV在運動過程中，始終遠離障礙代價函數值大的點運動，以實現避障。在此過程中還需要不斷朝目標點運動，因此建立目標代價函數，越趨近于目標點則目標代價函數值越小，AUV會始終尋找趨近目標代價函數值小的點運動，以實現趨向目標點的運動。

1）障礙代價函數

障礙代價函數是采用人工勢場法的思想建立，將AUV所識別的障礙物看作斥力勢場，其勢能函數為：

其中： q 為AUV的位置矢量； ρ (q,qob)為AUV到障礙物中心的距離，m； ρ0為距離障礙物中心的最小安全距離，m； k 為勢能系數； r0為障礙物的外圍半徑，m。

由上式可知當AUV越靠近障礙物時其勢能越高，其障礙代價函數值越大，令其為

2）目標代價函數

AUV在空間中運行，在其一段路徑中目標點只有一個，暫定離目標點距離越遠其目標代價函數值越大，相反當離目標點距離越近其目標代價函數值越小，從而建立目標代價函數公式為：

其中，ρ（q,qgoa）為AUV當前點到目標點中心的距離。

3）障礙總代價函數

式中， ki為權重系數（ ki＞0）， ki權重系數選取與AUV路徑規劃過程中障礙代價與目標代價那個更為重要，其中AUV路徑規劃總是趨于向總代價函數最小的點運動。

1.2.2 探測模型

AUV在水下運動過程中，除了躲避可見的障礙之外，還需要躲避來自人為因素的影響，其中最主要的是雷達的探測，其主要來自水面及水上探測雷達和水下潛艇及其他AUV的探測雷達。根據雷達回波強度與位置的關系，得到雷達探測威脅如下：

其中， Jradar為雷達探測威脅； n為威脅的數量或編號，個； li為路徑范圍內的第i 個長度值，m； di(l)為路徑上當前計算點與第i個雷達探測威脅的距離，m。

AUV在水下某點收到第i個雷達探測位置的影響指數為：

式中： H(x)為雷達探測影響指數可限制AUV在威脅較小的區域航行； Ki為第i 個威脅的強度； βi為乘數因子，當第 i 個威脅沒有收到預警信息時， βi=1，否則βi＞ 1。

由障礙模型中的目標代價函數可知，當AUV在路徑規劃過程中，雖然目標點確定，但是還是存在多個路線去選擇的情況，如圖1所示。

圖 1 AUV 路徑規劃目標點確定Fig. 1 Determine the AUV path planning target point

AUV在路徑規劃過程中始終需要滿足其物理性能要求和任務約束，保證其穩定安全的完成任務，多條路徑必定有長度和安全的差異，因此建立路徑代價函數為：

式中： g為路徑代價函數； hi為第i段路徑上的高度變化，km； |l|為AUV在水下環境下左右搖擺機體的位移 ；ω1，ω2， ω3， ω4為權重系數，通過調整的相對大小，可以確定AUV是在障礙間穿行或繞過障礙航行，調整的相對大小可以確定其航行路徑是在雷達探測威脅區間穿行或繞過威脅區間航行。

1.2.3 路徑規劃過程中總代價函數

在AUV的路徑規劃過程中必定優先在環境模型的基礎上進行，考慮到外界環境的干擾，AUV在航行過程中總代價函數為障礙模型和探測模型的總和，也就是其干擾模型下AUV為獲得最優路徑所作出的決策和付出的代價，公式為：

2 改進型蟻群算法的 AUV 三維路徑規劃

2.1 蟻群算法的各參數優化

在路徑規劃過程中，將AUV看作一只螞蟻，設有n 只螞蟻，螞蟻 M 在運動過程中收到來自多個路徑上的信息素濃度的“吸引”，在 t 時刻，螞蟻 M 位置為i，那么向 j 運動的轉移概率為Pij，常規公式為：

式中： τij(t)為t 時刻位置i 與位置 j之間路徑上的信息素濃度； ηij(t)為啟發函數，表示螞蟻 M 從位置i 到位置 j 的期望程度， dij為位置i 到位置j的距離；allowM為螞蟻M待訪問位置的集合。

2.1.1 信息素分布的優化

信息素濃度是衡量路徑規劃過程中路徑價值，為螞蟻的運動作引導依據。信息素只要涉及3個基本概念，分別是初始信息素、信息素更新、信息素揮發。初始信息素由螞蟻的當然位置來確定，不會有任何其他因素的影響，但是信息素的更新與揮發對信息素濃度影響最大，這也對最優路徑的選擇起到了至關重要的作用。

1）信息素更新的優化

螞蟻每移動一次稱為一次搜索，當螞蟻完成一次搜索后，就會對路徑上的信息素進行局部更新，更新公式如下：

式 中 ： ε為 局 部 信 息 素 揮 發 因 子 ；動過程中第 k 只螞蟻所構造的總代價函數值，而且Dk(t)只計算兩位置點間的總代價。

由此可見，當路徑最優時，其總代價函數越小，局部更新中信息素的增量越大，對應路徑上信息素的保留就越多，后續迭代中被選擇的幾率就高[2]。

當所有螞蟻完成一次迭代后，對路徑的全局信息素進行更新，公式如下：

式中： ρ為全局信息素揮發因子， ? τij由以下公式確定：

式中： LB為當前歷史最優路徑長度， L為本次迭代循環的最優路徑長度， σ 為根據實際路徑規劃需求與最亂路徑的偏移量來確定。

2）信息素揮發的優化

在一次搜素路徑結束后，路徑還是那個的信息素會進行一定的揮發，這樣可以使信息素不會積累過多，對于提高路徑規劃效率和全局搜索能力有一定的作用。在信息素揮發時最重要的是保留最佳路勁優勢的同時也不能影響后續算法的進行，也就是不影響后面螞蟻對路徑的選擇。

為了能有更好的最初決策，對路徑上的信息素進行不同的揮發，將以通過路徑螞蟻數量 m 和路徑長度L為參考變量，其公式為：

式中： L 為螞蟻搜索得到的路徑長度， Lb為當前周期最短路徑， s 為通過最短路徑的螞蟻數量， m 為全部的螞蟻數量， ρ為揮發權值，根據路徑長度的變化改變相應的數值。

2.1.2 啟發函數的優化

在路徑規劃相關模型建立的過程中，可以發現常規蟻群算法中，啟發因子只考慮了目標代價中即兩位置之間的距離，并沒有考慮下一點與終點和障礙代價、路徑代價這些因素的影響，優化后啟發因子的公式為：

式中： q1， q2， q3均為上述因素的相對重要程度，djE為位置 j到終點位置的距離。

2.1.3 轉移概率的優化

在三維柵格地圖中，當一只螞蟻從當前位置向下移位置運動過程中可能都是遍歷過的柵格體時，它將無法選擇下一位置進行運動轉移，此時，它可能陷入死循環或死鎖狀態[3]。因此，在計算轉移概率時在考慮距離和信息素濃度的同時也需要考慮柵格體區域的安全性。在一個柵格體的周圍障礙體占大多數，那么在運動到這個柵格體后，其運動方向的可能性會變得很小，也就是其柵格體區域內附件的安全性相對較差。那么，優化后的公式為：

式中： Bgrid為與當前柵格體相鄰柵格體中障礙柵格體所占的比例， A Bgrid為與當前柵格體相鄰的柵格體中障礙柵格體的數量， Agrid為與當前柵格體相鄰的柵格體的數量。

在轉移概率公式中加入區域安全信因素后的公式為：

其中， μ為安全信息的權重值。注意：盡管在這個柵格體周圍障礙占多數，但這個柵格體依然屬于可通過性高且有時又是路徑的必經之路，所以其值不能過高。

2.2 粒子群算法

粒子群算法是一種群體的迭代算法，通過群體性性能在解空間進行結果的優化計算[5]。其公式為：

由公式可以看出，粒子群算法在每次迭代過程中通過粒子跟蹤2個最優解來更新自己。

式中： wmax為慣性權重的最大值， wmin為慣性權重的最小值，為最大迭代次數， λ為當前迭代次數。

2.3 改進型蟻群——粒子群融合算法

蟻群算法是啟發式優化算法中比較常用和經典的算法，具有較強的魯棒性與正反饋機制，但是由于其初期信息素信息匱乏，搜索比較盲目容易陷入局部最優和過早收斂，為了追求搜索精度使其整個算法的搜索速度慢。而粒子群算法雖然其搜索精度不高，但卻具有較強的全局搜索能力和較快的搜索速度。將蟻群算法和粒子群算法進行融合，先利用粒子群算法較強的全局搜索能力和搜索速度對整個區域空間進行路徑搜索得到最優解或是次優解。接下來，將得到的最優解或是次優解轉化為蟻群算法中的初始信息素，并進行重新分布，利用優化后的蟻群算法的正反饋機制對次優解進行精確搜索，得到當前路徑信息素豐富的最優解。這樣不僅解決了蟻群算法容易陷入局部最優、搜索盲目的缺點，也通過粒子群算法加快了路徑規劃搜索的速度。

改進型蟻群—粒子群融合算法中2種算法的銜接點為利用粒子群算法產生蟻群算法的初始信息素分布，也就是利用蟻群算法中根據外界環境信息等確定的信息素的初始值 τ，利用粒子群算法求得的次優或是最優路徑轉化為信息素的增量，最終得到蟻群算法中各路徑上的信息素的初始值為 τij，其公式為

算法流程框架圖如圖2所示。

3 仿真與實驗驗證分析

在Matlab環境下編程對AUV三維路徑規劃進行仿真實驗，實驗環境在跨度為21×21 km的一片海域中搜索從起點到目標終點并且避開所有障礙物及干擾的路徑。為了方便問題的求解，取該片區域內最深的點的高度為0，其他高度根據最深點來確定。起點坐標為（1，0，800），目標終點坐標為（21，4，100）。粒子群算法參數設置為： c1與 c2都為2， wmax為0.9，wmin為0.6，最大迭代次數為100；蟻群算法參數設置為： q1， q2， q3都設置為1，為0.9，全局信息素揮發因子 ρ為0.2；分別采用未融合、融合前未優化及優化并融合的蟻群——粒子群融合算法對AUV路徑規劃進行仿真，結果如圖3所示。

可以看出融合后的算法在路徑規劃時適應度值較小，且響應時間較快，而且在優化后的融合算法中效果更加明顯。

圖 2 算法流程框架圖Fig. 2 Framework of the algorithm flow

圖 3 未采用融合優化算法的路徑規劃；Fig. 3 The path planning without fusion optimization algorithm

4 結 語

圖 4 未采用融合優化算法的蟻群路徑規劃Fig. 4 The path planning with fusion optimization algorithm

圖 5 采用優化后的蟻群——粒子群融合算法路徑規劃Fig. 5 The path planning with improved ant colony optimization and particle swarm optimization

本文提出了基于改進型蟻群—粒子群融合算法對AUV在水下三維空間的路徑規劃進行研究。首先利用粒子群算法較強的全局搜索能力和搜索速度對整個區域空間進行路徑搜索得到最優解或是次優解，然后再利用蟻群算法的正反饋機制對次優解進行精確搜索，得到當前路徑信息素豐富的最優解。根據仿真結果顯示分析可知，改進型蟻群—粒子群融合算法獲得的最終結果優于單一以蟻群算法或粒子群算法以及傳統蟻群—粒子群融合算法進行路徑規劃尋優的結果。該算法對于AUV路徑規劃的應用研究以及多AUV水下環境協調路徑規劃方法的研究具有一定的參考意義。