基于改進型A＊-蟻群混合算法的USV 航跡規劃

孫海文，肖玉杰，王生玉

(1.中國人民解放軍91054 部隊，北京 102442；2.海軍航空大學，山東 青島 266000)

0 引言

航跡規劃[1]是USV 研究領域中最主要的研究方向之一。USV 航跡規劃指規劃出一條安全快速到達目標位置的路徑。

航跡規劃主要研究避障問題。目前，傳統的航跡規劃算法有模擬退火算法[2]、禁忌搜索算法[3]、A*算法[4]、人工視場法[5–6]等。隨著智能仿生學算法的發展和應用，逐漸將遺傳算法[7]、粒子群算法[8]以及蟻群算法[9]等用于航跡規劃。其中，A*算法具有較強的全局搜索能力，在低密度避障環境中能夠快速高效地規劃出到達目標點的合理路徑，但當避障環境密度較高時，A*算法容易陷入局部死區。蟻群算法具有較強的魯棒性，在高密度環境下亦能找到合理路徑，但其收斂速度較慢。因此本文將水面環境進行分割，在高密度環境中設置過度目標點，在低密度環境下采用A*算法進行航路規劃，當目標到達過度目標點，則采用蟻群算法進行搜索規劃航路。從而提高了USV 全局和局部航路規劃能力。

1 航行環境模型

柵格（grid）法[1]，即用編碼的柵格來表示地圖，把包含障礙物的柵格標記為障礙柵格，反之則為自由柵格，以此為基礎作路徑搜索。柵格法是目前研究最為廣泛的空間規劃方法。構建路徑規劃環境，令障礙物的柵格狀態為1，自由柵格狀態為0。環境矩陣為：

模擬空間環境如圖1 所示。

圖1 模擬的空間環境Fig.1 Simulated space environment

無人航行器節點的位置移動方式如圖2 所示。

圖2 位置移動模式Fig.2 Position movement mode

2 改進型A*-蟻群混合算法

2.1 啟發式A＊算法

A*算法[4]的估價函數為：

式中：f(n)為當前USV 所處的節點n的總代價；g(n,s)為節點n到起始節點s的實際代價函數；h(n,e)為節點n到目標節點e的預估代價函數。

2.2 改進型蟻群算法

在傳統的蟻群算法[10–11]中，當所有螞蟻完成一次迭代后，對路徑上(i,j)上的信息量進行調整，調整公式：

式中：τij(t+n)表示t+n時刻路徑 (i,j)上的信息濃度；ρ表示信息素揮發系數；1-ρ 表示信息素殘留因子；Δτij(t)表示本次循環中所有螞蟻在路徑 (i,j)上釋放的信息素濃度之和；Q為一常數；Lk表示第k只螞蟻在本次循環中所走的總路徑長度。

為增強蟻群算法的快速性和有效性，本次改進了信息素的更新模型，增強了可行路徑中最優路徑的信息濃度，減弱了最差路徑的信息濃度，并通過調整信息素濃度總和比例，增強算法的尋優能力。

式中：Lmin表示第k只螞蟻在所經歷的迭代中可行路徑的最小值；Lmax表示第k只螞蟻在所經歷的迭代中可行路徑的最大值。

2.3 改進型A＊-蟻群混合算法

USV的航路規劃分為全局規劃和局部規劃。算法首先利用A*算法進行全局規劃，當遇到高密度環境，則采用蟻群算法，通過蟻群信息素搜索原理，進行障礙的規避。

根據環境柵格圖的特點在高密度局部圖中設置過渡節點，過渡節點的總代價函數要小于USV 所處節點的代價。目標先采用A*算法朝向目標節點進行全局規劃，到達過渡節點時采用蟻群搜索算法進行局部規劃。在USV的全局航行過程中，不斷采用蟻群算法進行局部高密度避障在，可有效地提高航行器在復雜環境中的航路規劃能力，避免陷入局部死鎖。算法流程如圖3 所示。

圖3 改進的A*-螞蟻混合算法流程圖Fig.3 Flow chart of improved A * -ant hybrid algorithm

3 仿真實驗

為了驗證本文所提改進型A*-蟻群混合算法的有效性和優勢性，進行仿真實驗比較。

3.1 低密度簡單環境下的仿真比較分析

本仿真試驗選取22 km×22 km的正方形水域，采用柵格法劃分該區域為22×22的網格，各網格表示1 km×1 km 區域。黑色表示障礙物區或禁航區，白色表示自由航行區。分別采用傳統A*算法、蟻群算法、改進型蟻群算法、改進型A*-蟻群混合算法進行航路規劃。蟻群規模為M=50，最大迭代次數為N=100；信息素重要程度因子α=1；啟發函數重要程度因子β=5；常系數Q=2 000；信息素揮發因子為ρ=0.7；單位柵格邊長為1 km。仿真結果如圖4 所示。

圖4 四種算法的仿真結果Fig.4 Simulation results of four algorithms

圖4 中的路線規劃路徑長度和運行時間統計如表1所示。

表1 四種算法的數據統計Tab.1 Data statistics of four algorithms

根據圖4 和表1 比較分析，4 種方法的路徑長度比較為改進型蟻群算法<本文算法

3.2 高密度復雜環境下仿真比較分析

為了進一步證明該算法的優越性和有效性。選取面積為45 km×45 km的正方形水域，采用柵格法將面積劃分為45×45 個網格，每個網格代表1 km×1 km的面積。分別采用傳統A*算法、蟻群算法、改進型蟻群算法、改進型A*-蟻群混合算法進行航路規劃。仿真參數不變，增加了障礙的復雜性。仿真結果如圖5 所示。

圖5 中的路線規劃路徑長度和運行時間統計如表2所示。

根據圖5 和表2的比較分析，4 種方法的路徑長度比較為：本文算法<改進型蟻群算法<傳統蟻群算法

圖5 四種算法的仿真結果Fig.5 Simulation results of four algorithms

表2 四種算法的數據統計Tab.2 Data statistics of four algorithms

仿真結果表明，A*算法在低密度、小規模環境下具有較強的路徑規劃能力和較短的運行時間。然而，在高密度、復雜的環境中，A*算法容易陷入死區。與傳統蟻群算法和A*算法相比，本文提出的算法大大提高了路徑規劃的質量和效率，能夠快速有效地完成OSV的路徑規劃。

4 結語

針對高密度復雜環境下的無人水面航行器（USV）航跡規劃問題，本算法有效地增強USV 航跡規劃能力，解決了傳統蟻群算法和A*算法各自使用不能兼顧全局和局部規劃的問題。通過仿真比較分析，本算法能夠有效地平衡全局和局部規劃，提高在復雜環境下的USV 航跡規劃能力。本文方法將為USV 大規模復雜的環境任務提供研究依據。