復雜開放水域的無人船避障路線蟻群規劃算法

陳改霞，葉蕭然

（河南理工大學鶴壁工程技術學院，河南 鶴壁 458030）

0 引言

無人船的智能控制十分關鍵，其核心是避障路線規劃設計，避障路線規劃效果是判斷無人船智能航行水平的重要依據[1-2]。無人船避障路線規劃是以航行環境建模為前提，通過智能優化算法實現無人船最佳避障路線的設計[3-4]。隨著技術手段的不斷革新及智能化水平的提高，各種智能算法被引入到避障路線規劃中，實現無人船航行效率與避障能力的大幅提升。

李清亮等[5]為使無人船能夠安全航行于含有障礙物的水域環境，在障礙物區域標記的基礎上，采用最優時間控制目標函數描述無人船避障問題，通過控制參數優化和時間尺度變換對優化問題求解，再基于精確罰函數實現各狀態約束的處理，從而實現無人船航跡規劃和自動避障。但是該算法求解難度較高，優化參數的選取對無人船避障路線規劃效果影響較大。呂進鋒等[6]通過在海圖上進行節點設置與擴充，完成路徑網絡圖的建立后，采用改進和聲算法實現無人船避障路線優化，該算法會因障礙物節點位置改變而使規劃的避障路線不可行，且規劃路線無法滿足最短要求。蟻群算法是可實現全局路徑規劃的智能優化算法，通過正反饋機制指引路徑規劃問題逐步向最優解逼近，具備強大的魯棒性能。因此，本文設計復雜開放水域的無人船避障路線蟻群規劃算法，保證全局收斂效率，同時規劃出具有較少拐點、路徑最短的避障路線。

1 無人船避障路線蟻群規劃算法

1.1 復雜開放水域障礙物柵格化處理

依據無人船半徑對復雜開放水域環境中的障礙物作膨脹處理后，將障礙物所在柵格填充完整，保證無人船在復雜開放水域航行過程不發生碰撞。障礙物柵格化處理如圖1 所示。

圖1 障礙物的柵格化處理Fig.1 Grid processing of obstacles

改進蟻群算法通過對各柵格中心點進行查詢，實現無人船避障路線規劃。

1.2 蟻群算法

蟻群算法是一種智能優化算法，其設計靈感源于螞蟻覓食行為[8]，螞蟻在尋找食物時，會將一種特殊物質分泌在其食物搜索路徑中，完成一段時間搜索后，距離相對較小的搜索路徑上含有的信息素含量較高，其他螞蟻將按照信息素高的路徑繼續搜索。

螞蟻在覓食時，將搜索節點的信息素含量以及啟發信息作為依據，完成后續搜索節點的確定。對于第k只螞蟻，由節點i移動到節點j的轉移概率為：

式中：kallow為可供該螞蟻移動的所有節點集合；在t時間點下，τij(t) 為節點i與節點j的連接路徑上的信息素濃度；ρij(t) 表示啟發函數，通過 ρij(t)計算得到，dij為節點i至節點j的距離，dij與成反比例關系，當dij取最小值，可達到最大；參數 α用于描述螞蟻搜索路徑中信息素濃度的重要程度，通過參數β可實現搜索路徑中啟發信息重要程度的描述。

螞蟻覓食過程中分泌的信息素具有揮發性，蟻群中各螞蟻均執行完搜索任務后，將對各搜索路徑上的信息素濃度進行調整，公式為：

其中：λ表示揮發因子，決定了信息素的揮發速度，其值較大，信息素可易揮發，通過 λ可實現螞蟻搜索路徑信息素濃度的調節，以防止信息素持續累積；?τij表示對于搜索路徑ij，全部螞蟻在其上留下的信息素濃度大小；表示螞蟻 k在其上殘留的信息素濃度大小，可通過下式對其進行求解：

式中：Q表示對于螞蟻k，其執行一次搜索任務分泌的信息素數量，其值取常數；Lk表示搜索路徑總長。

1.3 基于改進蟻群算法的無人船避障路線規劃

1.3.1 啟發信息的改進

將無人船受到的勢場信息融入到啟發信息中，實現啟發信息的改進處理，確保螞蟻沿著合力方向執行搜索任務。勢場合力啟發信息通過下式進行描述：

其中：C為常數，其值大于0；Ftol表示勢場合力，其與螞蟻可能搜索路徑所成角度表示為θ。此種狀況下，螞蟻更傾向沿較小 θ方向進行后續搜索節點的選取。將無人船行駛環境勢場信息融入到啟發信息中，對提高無人船避障水平具有重要意義。

將 ρs(t) 與 ρij(t)相乘即可確定考慮勢場信息與距離信息的啟發信息，計算公式為：

在人工勢場法中，當目標節點引力與障礙物斥力相同時，勢場合力將等于0，將獲得一個局部最小值，為避免無人船避障路線規劃陷入局部最小問題，將勢場力融入到蟻群算法自身啟發信息中，可確保無人船在勢場合力等于0 時，也能實現最優避障路線規劃。

1.3.2 信息素濃度增量優化

對各搜索路徑上的信息素濃度進行優化處理，提高無人船避障路線規劃效果，其計算公式為：

其中，信息素濃度的高低通過Q?反映。

通過設計的信息素濃度增量優化，可對螞蟻搜索路徑上的信息素濃度高低進行自主更新，以提高無人船全局最佳避障路線收斂效率。δ>ε條件下，信息素濃度隨著 δ值的增大而提高，這有利于提升無人船避障路線規劃效率；δ ≤ε 條件下，Ln,k與Lmin之差越小，信息素揮發性越高，可防止無人船避障路線規劃陷入局部最優解。

1.3.3 狀態轉移概率的改進

應用蟻群算法對無人船避障路線進行規劃時，容易陷入局部最優困局，這是由于螞蟻在后續移動節點選取時，一旦其處于凹型障礙環境或無新節點可選，就會停在原處不動。本文對狀態轉移概率進行優化處理，通過引入穩定因子S j，避免無人船避障路線規劃陷入局部最優困局。優化后的狀態轉移概率公式為：

式中：對于節點j，Tj為與其鄰近的柵格總量；Oj為其附近障礙物柵格總量；γ為穩定因子參數。

2 實驗分析

以航行于復雜開放水域的某無人船為實驗對象，對無人船航行環境進行建模，獲得30×30 柵格地圖，航行環境中的障礙物用灰色柵格標記。在上述環境采用本文算法對無人船避障路線進行規劃，分析本文算法的避障性能。無人船航行環境建模結果如圖2 所示。

圖2 復雜開放水域航行環境建模結果Fig.2 Modeling results of complex open water navigation environment

蟻群算法性能的優劣直接影響無人船避障路線規劃效果，啟發參數 α反映了搜索路徑上信息素濃度對螞蟻路徑選擇的影響，參數 β體現了啟發函數對螞蟻路徑選擇的重要性。采用本文算法對復雜開放水域環境下的無人船避障路線進行規劃，并將算法改進前路線規劃結果作為對比，通過分析不同 α、β取值下的最優路徑長度差異，驗證本文算法的避障效果，實驗結果如圖3 和圖4 所示。

圖3 啟發參數 α對無人船避障路線規劃效果影響Fig.3 Influence of heuristic parameters on the planning effect of ship obstacle avoidance routes

圖4 啟發參數 β對無人船避障路線規劃效果影響Fig.4 Influence of heuristic parameters on the planning effect of ship obstacle avoidance routes

可知，啟發參數 α、β的取值對無人船避障路線規劃效果具有直接影響，隨著參數 α、β的不斷增大，無人船避障路線長度大體呈先減小后微弱增大趨勢變化，當α=1、β=4時，本文算法確定的無人船避障路線最短；改進前算法在 α=1.2、β=5.5時可獲得最短避障路線，但避障路線長度始終高于改進后。實驗結果表明，將勢場信息引入到啟發信息中，實現蟻群算法的改進，可有效提升無人船避障路線規劃效果，獲得更短規劃路徑。

在圖2 航行環境下，無人船航行初始點為A，航行目標點為B，將本文算法應用到無人船避障路線規劃中，通過對算法改進前后的避障路線規劃結果以及收斂曲線進行對比分析，驗證本文算法的應用性，實驗結果如圖5 和圖6 所示。

圖5 算法改進前后避障路線規劃結果對比分析Fig.5 Comparative analysis of obstacle avoidance route planning results before and after algorithm improvement

圖6 改進前后算法性能對比分析Fig.6 Comparative analysis of algorithm performance before and after improvement

可知，隨著迭代次數的不斷增加，算法改進前后的收斂曲線均呈現出不斷降低的發展趨勢，本文算法經過50 次迭代即可實現最佳路徑長度曲線的快速收斂，改進前算法需要100 次迭代方能達到穩定狀態，且迭代前期曲線波動起伏較大，曲線平滑性差。改進前算法的避障路線規劃結果中存在更多的拐點，路線曲折、避障路線更長。采用本文算法規劃設計的無人船避障路線平整度高、避障路線長度降低了40.39%，拐點數降低了60%。

3 結語

以航行于復雜開放水域的無人船為實驗對象，在分析蟻群算法性能影響因素的基礎上，通過對比分析改進前后無人船避障路線規劃結果研究本文算法的優越性。實驗結果表明：

1）蟻群規模為80，啟發參數 α、β分別為1 和4 時，設計的無人船避障路線最短。

2）本文算法可實現無人船避障路線規劃，設計的避障路線長度比改進前降低了40.39%、拐點數減少60%。