基于混合蟻群算法的無人船航行路徑自主規劃

陳宇文，徐 照

（1. 南京工業大學 土木工程學院，江蘇 南京 210000；2. 東南大學 土木工程學院，江蘇 南京 210000）

0 引 言

無人船能在人力不可為的條件下實現水面和水下目標偵察與監視等任務[1]，是當前水面智能體的典型代表，受到各界普遍關注。在復雜工作環境下，航行路徑規劃是無人船正常工作的基礎與保障[2]。

王立鵬等[3]在研究艦船路徑規劃問題過程中，以海圖為基礎，確定航線與陸地物標的對應關系，采用遺傳算法對規劃路徑進行尋優，獲取最優規劃路徑。該方法在目標工作環境較為復雜的條件下，規劃結果精度無法保障。周怡等[4]在研究艦船路徑規劃問題過程中，以防碰撞為目的構建航行路徑規劃模型，采用優化后的DDPG 算法求解模型獲取最優路徑。該方法在實際應用過程中無法保障收斂速度與尋優性能的平衡性。

針對上述問題，提出基于混合蟻群算法的無人船航行路徑自主規劃方法，獲取最優航行路徑。

1 無人船航行路徑的自主規劃

1.1 環境建模

無人船航行路徑自主規劃之前，需先構建無人船工作環境模型，由此能在無人船工作環境中明確哪些區域是安全區域，哪些區域為障礙物區域。設定無人船工作環境中的障礙物均處于靜止狀態，由于柵格法描述簡單，易于實現，因此通過柵格法構建工作環境模型[5]，以A 和B 分別表示安全區域與障礙物區域。以方形地圖表示無人船工作環境，柵格法中包含若干個邊長為1 的小正方形，其中白色區域和黑色區域分別為安全區域和障礙物區域。

以方便后續對無人船工作環境信息的描述為目的，由上至下、由左至右的對柵格實施編號處理。在柵格間距確定過程中的主要依據為柵格點中心位置坐標，所以，可通過式（1）描述柵格號與無人船工作環境坐標(x,y)間的對應關系：

式中：ES和ceil 分別為小柵格的邊長和向上取余函數；n和MM分別為小柵格的序號和柵格的整體行數；mod為余函數。

1.2 航行路徑自主規劃數學模型

構建無人船工作環境模型后，再構建無人船航行路徑自主規劃的數學模型。無人船航行路徑自主規劃問題可描述為：在任意規劃空間內，符合相應約束條件g(γ)=0的基礎上，依照某一航行性能評價指標J，規劃確定無人船的航行路徑，也就是由起始點ES至目標點EG，同時符合相應約束條件的一系列路徑節點Γ={ES,E1,E2,···,En,EG}。

利用式（2）能夠描述無人船航行路徑自主規劃數學模型：

式中：D和 φ分別為水動力系數和水密度；v和 ρ分別為無人船航行速度和橫截面積； φ和H分別為無人船航行路徑長度和機械效率。

約束條件如下：

1）地形與威脅約束。無人船航行過程中，為保障航行安全性，需防止與障礙物產生碰撞，因此設定無人船工作環境中，障礙物與危險區域均為不可穿越的區域[6]。若以R'f表示在無人船工作區域內不可穿越區域集合，考慮無人船自身的尺寸，同時考慮規劃路徑的平滑性，需對障礙物與危險區域實施膨化處理，由此保障無人船航行的安全性。以Rf=εR'f表示通過膨化處理的集合，也就是擴大障礙物與危險區域大小，依照無人船實際尺寸可確定膨化系數。以f(x,y)表示規劃出的無人船航行路徑，由此得到約束公式描述：

2）航程上限約束。無人船內部攜帶能量對于航行距離上限Lmax產生直接影響[7]，因此在無人船航行路徑自主規劃過程中需設定相關約束條件，公式描述如下：

式中，φg和δg分別為規劃路徑長度與實際航行路徑與規劃路徑的偏差。

3）轉彎角度約束。無人船航行轉彎過程中受自身機動性能影響[8]，導致角度受到一定限制，以 ξ 和 ?i分別表示無人船允許的最大拐角與任意拐彎角，約束條件公式描述如下：

4）路徑平滑度約束。無人船航行路徑越平滑，對自身的機動性要求越低?？紤]無人船航行過程中需消耗大量能量，為路徑的平滑性能夠降低能源消耗。描述該約束條件公式為：

式中：Sk和n分別為第k 條路徑累積轉彎角度和路徑點數量；R為無人船航行路徑的最大轉彎角度；r和Smax分別為路徑內的轉彎角度和允許的最大平滑度。

1.3 基于混合蟻群算法的模型求解

考慮蟻群算法應用過程中存在初始階段搜索效率差、有較大概率獲取局部最優結果等問題，將其與粒子群算法相結合，提出混合蟻群算法。針對式（2）無人船航行路徑自主規劃數學模型，采用混合蟻群算法進行求解。將由無人船航行路徑解集內選取最優路徑的問題描述為螞蟻搜索食物的問題，設定無人船航行路徑解集內各解以及最優解，分別為螞蟻搜索食物過程中路經的城市和目標點。

依照無人船航行路徑自主規劃的實際情況，初始化混合蟻群算法參數，設定蟻群數量與最大迭代次數分別設定為200±100 次和150±50 次，信息素揮發系數與信息素增加濃度范圍分別為0.5±0.2 和5.5±4.5，信息素初始濃度范圍與啟發因子關鍵度范圍分別為55±45和5±2，信息素關鍵度范圍為5±2。

計算螞蟻個體的適應度v，其所描述的是螞蟻種群的屬性，能夠描述螞蟻的優劣水平，公式描述如下：

式中：w和zi分別為慣性權重與第i只螞蟻的位置；c和 ε分別為螞蟻個體學習因子和范圍為[0,1]的隨機數；pi和si分別為第i 只螞蟻個體極限與速度的第d 維分量。

螞蟻依照設定的迭代次數對無人船最優航行路徑實施全局搜索，每實施一次搜索即完成一次迭代過程。螞蟻在搜索無人船最優航行路徑過程中會產生信息素，所以每次迭代過程后就需更新搜索路徑中遺留的信息素τ(t+1)，公式描述如下：

式中： ρ 和 ?分別為啟發因子關鍵度和信息素更新系數； Δτ為與收斂次數成線性相關性的函數。

為避免目標迭代過程中陷入局部最優問題，對信息素上限值實施設定，公式描述如下：

式中，τmax和H分別表示信息素上限值與混沌變量。約束不同搜索路徑上的信息素濃度，令無人船最優航行路徑搜索空間內全部路經均由被選擇的概率，通過式（9）更新的蟻群位置與信息素，確定當前蟻群位置是否為個體極值，若是個體極值，就需將當前位置與全局極值進行對比；若不是個體極值，則需返回上一過程再次確定。在滿足迭代標準后，即可終止運算過程，輸出信息濃度最高的解作為最優解，即無人船航行路徑自主規劃的最優路徑。

2 實驗結果

為驗證本文方法在路徑自主規劃中的應用效果，選取某型號的無人船為研究對象，表1 為研究對象相關參數。設定研究對象的工作環境大小為24×20 km，采用本文方法對研究對象航行路徑進行自主規劃。

表1 研究對象相關參數Tab. 1 Relevant parameters of the research object

采用本文方法獲取的研究對象最優航行路徑規劃結果，如圖1 所示。圖中，黑色方塊為研究對象工作環境中的障礙物與危險區域，白色圓形為研究對象的起始點坐標與終點坐標。

圖1 本文方法航行路徑自主規劃結果Fig. 1 The results of autonomous navigation path planning using the method presented in this article

分析圖1 可知，采用本文方法能夠有效構建研究對象工作環境模型，同時通過計算能夠有效獲取研究對象最優航行路徑，該路徑能夠有效避開全部障礙物與危險區域。

為驗證本文方法航行路徑規劃結果的優勢性，對比采用本文方法前后研究對象的航行路徑，結果如表2所示。

表2 研究對象航行路徑對比結果Tab. 2 Comparison results of navigation paths of research subjects

分析表2 可知，采用本文方法對研究對象航行路徑進行規劃后，最優路徑長度與采用本文方法前相比減少1.586 1 km，平均能耗降低6.4211 kJ，路徑規劃時間降低3.565 s。以上數據充分說明采用本文方法能夠有效保障研究對象航行路徑規劃的精度與實時性，降低研究對象航行能耗，保障研究對象航行過程中的經濟性。

3 結 語

本文研究了一種基于混合蟻群算法的無人船航行路徑自主規劃方法，在工作環境模型基礎上構建航行路徑規劃數學模型，并采用混合蟻群算法求解模型。實驗結果顯示，本文方法所構建的工作環境模型較為準確，所得最優路徑規劃結果路徑最短、能耗最低。