基于蟻群優(yōu)化算法的無人船艇航線自動生成及路徑規(guī)劃?

張海妮

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

1 引言

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

2 算法介紹

2.1 蟻群優(yōu)化算法

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

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

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

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

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

2.2 標準A星算法

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

3 無人船艇航線自動生成

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

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

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

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

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

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

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

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

3.2 航路轉(zhuǎn)向點辨識和連通性辨識

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

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

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

圖2 航路轉(zhuǎn)向點辨識與連通性辨識標準

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

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

圖3 基于蟻群優(yōu)化算法的最佳路徑捜索流程

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

4 無人船艇航線路徑規(guī)劃

路徑規(guī)劃研究選擇無人船艇模型，通過CFD仿真計算路徑規(guī)劃中的阻力性能參數(shù)，并通過設置恰當?shù)穆窂揭?guī)劃計算參數(shù)和設定正確的路徑規(guī)劃優(yōu)化目標，研究了考慮回轉(zhuǎn)性能、風浪阻力和氣動阻力和海流影響的路徑規(guī)劃，確定規(guī)劃結(jié)果是否具有實際意義。

4.1 考慮回轉(zhuǎn)性能的路徑規(guī)劃

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

表1 標準A星算法與回轉(zhuǎn)性能改進算法對比

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

圖4 考慮回轉(zhuǎn)性能的路徑

4.2 考慮風浪阻力和氣動阻力的路徑規(guī)劃

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

表2 額外路徑的連接權(quán)值

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

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

圖6 連接權(quán)值10倍時的規(guī)劃路徑

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

圖7 考慮風浪增阻、氣動阻力和回轉(zhuǎn)性能的路徑規(guī)劃

4.3 考慮海流影響的路徑規(guī)劃

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

表3 考慮海流影響的連接權(quán)值

考慮海流影響的路徑規(guī)劃結(jié)果見圖8。

圖8 考慮海流影響的路徑規(guī)劃

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

5 結(jié)語

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

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

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

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

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