基于蟻群優化算法的無人船艇航線自動生成及路徑規劃?

張海妮

（陜西交通職業技術學院基礎部 西安 710021）

1 引言

近年來，隨著人工智能的不斷發展，無人船艇的技術研發也在不斷推進，逐漸被用于代替傳統的人工作艇進行海面自主作業［1］。無人船艇的研究包括艇型設計、自動避碰避障和路徑規劃導航等方面［2］，其中，航線自動生成和路徑規劃是無人船艇研究的關鍵技術。海面環境復雜，無人船艇容易受到風浪等影響［3］，因此，展開對無人船艇航線自動生成及路徑規劃的研究具有十分重要的意義。國內外學者對無人船艇航線自動生成和路徑規劃做了大量研究，張立華等［4］提出一種基于瞬時水深模型的最短時間航線自動生成算法，能夠搜索最短時間航線和動態分析航線，與傳統算法相比，具有更強的實用性能。李雋［5］通過電子海圖與AIS系統監控船舶航行狀態相結合，實時上傳海洋及船舶信息，并使用Douglas-Peuker算法依據海洋實時信息修正航線，提高了船舶航行的安全性。吳小平等［6］運用蟻群算法結合TSP問題對無人船艇進行路徑規劃，算法通過路徑優化與路徑校核對三個無人船艇的情形進行驗證分析，發現該方法效率高、耗時短，為無人船艇路徑規劃問題提供了一個有效的方案。本文通過介紹蟻群優化算法與標準A星算法，設計無人船航線自動生成框架和基于蟻群優化算法的最佳路徑捜索流程，研究了航路轉向點辨識與連通性辨識標準，分析了航線的自動生成與考慮回轉性能、風浪阻力、氣動阻力和海流影響的路徑規劃，對無人船艇航線路徑進行更好的規劃，為相關研究提供了理論參考。

2 算法介紹

2.1 蟻群優化算法

蟻群優化算法是一種具有優良分布式、良好正反饋特性和較強魯棒性的計算機制，源于螞蟻覓食中搜索最短路徑的行為得到的一種模擬進化算法［7］，被應用于旅行商最短路徑［8］尋優問題。

假設螞蟻總數為m，航路轉向點總數為n，航路轉向點i和j在t時刻之間的信息素濃度為τij（t），則第k只螞蟻t時刻由航路轉向點i到航路轉向點j的轉移概率為

式中，α為啟發因子，體現信息素濃度的重要程度；β為期望因子，體現航路轉向點之間距離的重要程度；ηij（t）為啟發函數，表示航路轉向點i與j之間的距離，取值為1/dij；allowedk為螞蟻k能夠選擇的航路轉向點。

如果螞蟻并未選擇信息素濃度最高的路徑，則采用輪盤算法得到隨機數r，取值［0，1］，依據r的轉移概率范圍作為螞蟻航路的下一個轉向點。當完成最短路徑搜索之后，轉向點的信息素依據式（2）進行更新。

式中，τij(t)為循環中螞蟻k由航路轉向點i到j釋放信息素的增量；ρ為信息素的揮發系數。

2.2 標準A星算法

A星算法［9］根據closed鏈表和open鏈表來定位目標。假設給定終點E和起點S，步驟為：1）S添加至closed鏈表，其周圍格子添加至open鏈表；2）open鏈表中尋找最小權值F的單元格，將其命令為下一點并添加至closed鏈表；3）判斷最小權值F的單元格相鄰單位是否處在目標單元格，得到終點E，否則將相鄰單元格添加至open鏈表并返回上一步驟，假如open鏈表搜索完全而未能找到終點E，則視為無可行路徑。

3 無人船艇航線自動生成

3.1 無人船航線自動生成框架設計

無人船艇航線自動生成框架設計如圖1所示。

圖1 無人船航線自動生成的框架設計

具體步驟如下［10～11］：

步驟一：對AIS基站收集的數據進行預處理，然后通過Douglas-Peucker算法對其進行壓縮得到軌跡數據中的特征點；

步驟二：求取相鄰特征點形成的恒向線航向和鄰特三個特征點形成夾角的角度，根據轉向闊值的設定對軌跡中的轉向點進行辨識；

步驟三：根據轉向點相似性度量標準，通過層次NBSCAN算法對不同航跡中的轉向點進行聚類并記錄其信息，依據真實航跡判斷連通性；

步驟四：采用蟻群優化算法得到設定起點與終點之間的最佳航線，然后通過對比驗證無人船航線自動生成方法的有效性。

3.2 航路轉向點辨識和連通性辨識

通過層次NBSCAN算法對不同航跡中的轉向點進行聚類得到的航路轉向點為孤立的個體，而相鄰航路轉向點的連通性一般由其軌跡轉向點的并集所決定，通常航路轉向點之間的Constitu?tion-MMSI的并集為實集。假設兩個航路轉向點分布為TN1和TN2，則兩者之間的連通性標準如下［12］。

只要滿足圖2中任意一條標準，則認為航路轉向點之間具備連通性，在連通性辨識完成之后進一步得到有向圖：

式中，L為航路轉向點之間的連通性；TN為孤立的航路轉向點。

圖2 航路轉向點辨識與連通性辨識標準

3.3 航線自動生成的實例研究

基于蟻群優化算法的無人船艇航線自動生成依據有向圖G得到起點與終點之間的最優路徑，其流程見圖3。

圖3 基于蟻群優化算法的最佳路徑捜索流程

通過基于蟻群優化算法的最佳路徑捜索流程自動生成的航線，能夠符合航線設計要求，并且生成航路轉向點均處于轉向區內；進港航道與自動生成的航線保持一致并且可以延伸至泊位，滿足船舶采用分道通航制航行的要求。

4 無人船艇航線路徑規劃

路徑規劃研究選擇無人船艇模型，通過CFD仿真計算路徑規劃中的阻力性能參數，并通過設置恰當的路徑規劃計算參數和設定正確的路徑規劃優化目標，研究了考慮回轉性能、風浪阻力和氣動阻力和海流影響的路徑規劃，確定規劃結果是否具有實際意義。

4.1 考慮回轉性能的路徑規劃

基于A星算法中通過8鄰域空間進行規劃搜索，柵格點之間的運動方向均為45°的倍數，可能導致較長的路徑與不必要的轉折點，因此，對A星算法進行回轉性能改進：保持航向角不變，選擇第i個點，進而選擇第i+2個點以及后續點，如果可以直接相連，則刪去中間點。通過表1中兩種算法對比，發現優化效果明顯，回轉次數減少大約2/3，路徑長度減少將近5%，避免了A星算法規劃路徑無法達到最短的弊端。

表1 標準A星算法與回轉性能改進算法對比

考慮回轉性能的路徑規劃如圖4所示，對真實海圖上進行考慮回轉性能的路徑規劃，發現在保證不改變航向的前提下，回轉性能改進算法對真實海圖具備有效性。

圖4 考慮回轉性能的路徑

4.2 考慮風浪阻力和氣動阻力的路徑規劃

以往的研究中，通常忽略氣動阻力對船舶的能耗，實際航行中能耗是船舶運營成本中無法忽略的。對于無人船艇而言，采取CFD方法計算無人船在不同航速下氣動阻力，并且作為輸入參數進行路徑規劃。由于風浪具有復雜性和隨機性，考慮風浪阻力的路徑規劃選擇以儲備功率研究波浪中增大的阻力、污底阻力的增值和強風導致的氣動阻力增值等，并根據各阻力間的比例關系計算風浪增阻和氣動阻力的增加系數，得到額外路徑的連接權值，如表2所示。

表2 額外路徑的連接權值

為了提高計算速率，A星算法通常采用曼哈頓距離來評估與終點的距離，路徑規劃過程中往往忽略風力阻力的影響，為了同時體現氣動阻力與風浪阻力的影響，選擇歐式距離對起點與終點距離進行評估，結果見圖5。

圖5 歐式距離下評估起點與終點距離

圖6 連接權值10倍時的規劃路徑

圖6為正常氣動阻力連接權值的10倍得到的路徑規劃結果，對比圖6與圖5發現，選擇不同的氣動阻力連接權值，路徑規劃結果差異極大。圖6中路徑規劃航線長度極大增加，原因在于順風航行時，氣動阻力、能耗影響和連接權值均表現為負值，當連接權值選擇錯誤時，導致單元格間的路徑影響小于氣動影響，相鄰柵格間總連接權值為負值，致使路徑規劃錯誤。路徑規劃過程中考慮能耗，柵格間連接權值不大于0更接近實際，但是參數設置不恰當，則會產生不正確的連接路徑。通過CFD方法獲得的參數準確無誤，因此，利用CFD仿真無人船在不同風向和不同風速下氣動阻力權值具有十分重要的意義。圖7為同時考慮風浪增阻、氣動阻力和回轉性能影響的仿真結果，路徑規劃合理，基本實現順風航行。

圖7 考慮風浪增阻、氣動阻力和回轉性能的路徑規劃

4.3 考慮海流影響的路徑規劃

通常情況下，無人船航速較低，并且需要儲備較大功率用于保持低航速的穩定狀態，考慮海流影響的路徑規劃，主要研究海流對航線控制難度和無人船能耗的影響。頂海流方向行駛，無人船需要消耗額外能量；順海流方向行駛，無人船能量節約能耗，側海流方向行駛，不僅會增加控制難度，而且需要消耗額外能量，因此，原則上認為側流航行最差、頂流一般、順流最佳。通過CFD仿真模擬海流和無人船在不同航向、不同航速下的函數關系，假設海流方向為正北，考慮海流影響的連接權值如表3所示。

表3 考慮海流影響的連接權值

考慮海流影響的路徑規劃結果見圖8。

圖8 考慮海流影響的路徑規劃

由圖8可知，初步的點狀航線規劃優先選擇順海流方向行駛，并且可以保持航線的穩定性。航線連接權值的總和為能耗，點狀航線轉向4次，航線長度為336，能耗為299，經過優化之后，航線轉向3次，航線長度為324，能耗為272，由此可見，經過優化考慮船舶回轉性能夠有效減小轉向次數和航線長度，并且能耗也有所降低，這是因為航線規劃盡可能選擇順海，節約無人船能量的部分損耗。航線規劃的主要影響因素為輸入參數的準確程度，提高順流參數的精準程度可以進一步優化路徑規劃。

5 結語

為了對無人船艇航線路徑進行更好的規劃，首先介紹了蟻群優化算法與標準A星算法，設計了無人船航線自動生成框架和基于蟻群優化算法的最佳路徑捜索流程，研究了航路轉向點辨識與連通性辨識標準，分析了航線的自動生成與考慮回轉性能、風浪阻力和氣動阻力和海流影響的路徑規劃，主要得出以下結論：

1）通過層次NBSCAN算法對不同航跡中的轉向點進行聚類，進而對聚類形成的簇狀集合進行連通性辨識并得到有向圖為G=（TN，L），基于蟻群優化算法的最佳路徑捜索流程自動生成的航線，能夠符合航線設計要求，進港航道與自動生成的航線保持一致并且延伸至泊位，滿足船舶采用分道通航制航行的要求。

2）通過對A星算法進行回轉性能改進，可以避免A星算法規劃路徑無法達到最短的弊端，對真實海圖上進行考慮回轉性能的路徑規劃，在保證不改變航向的前提下，回轉性能改進算法對真實海圖具備有效性。

3）不同的氣動阻力連接權值對路徑規劃結果影響極大。考慮能耗的路徑規劃，柵格間連接權值小于0更接近實際，參數設置不恰當，會產生錯位的連接路徑。CFD方法得到的參數準確無誤，通過CFD仿真無人船在不同風向和不同風速下氣動阻力權值具有十分重要的意義。

4）通過CFD仿真計算路徑規劃中的阻力性能參數，設置恰當的路徑規劃計算參數和設定正確的路徑規劃優化目標，并在考慮海洋風浪流環境、船舶運動性能的情況下進行驗證，表明該方法具有一定的實際意義，可以用于掃海作業中區域間移動的路徑規劃。