基于人工探路蟻的波浪滑翔機路徑規劃

陳 茜，高軍偉，官 晟

1.青島大學 自動化學院，山東 青島266071

2.國家海洋局 第一海洋研究所，山東 青島266061

1 引言

波浪滑翔機是一種新型的自主海洋環境監測平臺，它的出現對海洋環境監測領域有著劃時代的意義。由于波浪滑翔機的航行動力來源于海洋波浪，海洋中無窮盡的波浪可以保證波浪滑翔機持續航行，波浪滑翔機的水面浮體上安裝有太陽能板和儲能電池，海洋中白天充足的光照可以保障波浪滑翔機上的各種儀器用電，具有超長航時、綠色無污染、自主運動等特點[1-2]。

由于波浪滑翔機的自身結構原理，海洋環境因素的變化對波浪滑翔機的航行速度和航行路徑有很大的影響，海洋環境復雜，暗流、暗礁、海風巨浪等不確定因素導致波浪滑翔機的路徑規劃一直是一個研究的難點。針對復雜的海洋環境和波浪滑翔機的結構特點，有必要設計有效的路徑規劃算法。常規的移動機器人路徑規劃工作環境較為簡單，動力速度可控，不適用于波浪滑翔機。在常規尋路算法的基礎上應考慮到波浪滑翔機的航行速度不可控，盡可能利用海洋環境。本文以柵格法劃分海洋區域，一方面方便整合海洋環境因素，將海洋環境通過速度預測模型歸一化為動態航行速度并引入到狀態轉移規則中。另一方面，海洋廣闊平坦，單位面積區域內海洋環境極為相似，柵格法的精度問題對算法性能影響較小。海洋環境復雜，常規蟻群算法極易陷入死鎖，引入人工探路蟻對可行節點情況提前探索，與文獻[3]中在轉移規則中引入上一節點數組來增加逃逸能力和文獻[4]中引入交叉算子來增加逃逸能力相比耗時更短。改進后的算法不僅優化了自身結構，提高了收斂速度，避免了局部最優解，更充分利用了海洋環境因素，使得波浪滑翔機能在復雜的海洋環境中快速、安全地航行到目標點。

2 算法描述

2.1 環境建模和波浪滑翔機的數學模型

波浪滑翔機的結構如圖1所示，分為水面浮體和水下翼板兩大部分，中間由一條4 m左右的柔性臍帶纜連接，在波浪的起伏推動下航行[5-6]。

圖1 波浪滑翔機結構圖

路徑規劃中首先要考慮的問題是環境建模，常用的環境建模方法有柵格法、可視圖法等。本文采用柵格法對波浪滑翔機的連續航行環境進行離散化處理，以二維數據的形式運算更方便高效，每個柵格可以用序號和直角系坐標表示，它們之間的換算關系如下：

在柵格環境中，波浪滑翔機可以認為是二維平面空間中的粒子，有8種運動方向，如圖2所示。由于實際中，波浪滑翔機的外觀尺寸較大，障礙物的面積應該按照波浪滑翔機的半徑大小膨化，確保波浪滑翔機沿障礙物邊緣航行時不會撞到障礙物，并且障礙物面積不滿一個柵格時應按照一個柵格計算[7]，充分保障航線的安全性。

圖2 10×10柵格建模示意圖

海洋環境中除了暗礁障礙物外，波浪、風速、洋流等因素也應該考慮進柵格環境內。

Smith等提出了線性回歸模型來預測波浪滑翔機的速度[8]。波浪滑翔機在海面航行的時候，其自身配置是恒定的。通過測量有效浪高、波峰周期、淺層流、表層流、風速和方向等海洋環境因素，線性權衡6個海洋環境因素，推導了一個波浪滑翔機速度的預測模型[9]。波浪滑翔機速度預測模型如下：

其中，ysog是波浪滑翔機的對地速度；xwht是有效波高；xwpp是波峰周期；xwdir是波浪滑翔機航向與波向的差值；xwnd是風速在航向軸向的分量；xadcp是表層流速在航向軸向的分量；xhfr是淺層流速在航向軸向的分量[9]。因實際中采集到的海洋環境數據有限，僅考慮影響速度的主要因素，將速度預測模型簡化如下：

將所有海洋環境因素歸一化為預測速度來改進柵格法，除去黑色障礙物柵格，對白色自由柵格進行不同程度的藍色填充來表示歸一化的波浪滑翔機預測速度，從而使其應用于波浪滑翔機進行海洋環境建模。海洋環境柵格建模如圖3所示。

2.2 常規蟻群算法簡介和相關改進

蟻群算法是1994年Dorigo提出的一種相對成熟的群體智能優化算法，通過模擬自然界螞蟻覓食的行為來尋求最優解。根據外界環境的變化，蟻群算法可以動態做出反應，且魯棒性能好，被廣泛應用于旅行商問題（Traveling Salesman Problem，TSP）、車輛調度問題、網絡路由問題等實際問題中[10]。

圖3 海洋環境速度預測柵格建模

常規蟻群算法的節點選擇方式是根據節點之間的信息素濃度和啟發信息進行概率選擇的，在t時刻，螞蟻k從節點Xi轉移到節點Xj的轉移概率公式如下：

其中，τij(t)為t時刻節點i到節點j的信息素濃度，α表示信息素濃度的相對重要程度；ηij(t)為t時刻節點i到節點j的實際距離的倒數，β表示啟發性因子的相對重要程度[11]。

常規蟻群算法存在收斂速度較慢，搜索范圍小且容易陷入局部最優解等缺點。為彌補常規蟻群算法的缺陷，一方面，研究者通過修改蟻群算法自身參數結構來避免局部最優解，例如修改節點轉移規則或信息素更新策略；另一方面，研究者通過蟻群算法和其他智能算法相融合來提高收斂速度，避免局部最優解，例如遺傳蟻群算法、人工免疫蟻群算法、人工勢場蟻群算法等[12-13]。

3 改進蟻群算法

3.1 改進啟發函數

海洋環境十分復雜，暗礁叢生，針對復雜航行環境，改進算法引入了障礙物復雜度mark的概念，即在一定區域范圍內，障礙物柵格的分布情況。在螞蟻進行路徑搜索時，搜索蟻從起始點S出發，以節點間的信息素和啟發信息搜索前進，在進行下一節點選擇時，派出探路蟻，為搜索蟻可能前進的方向探索障礙物分布情況，并對此方向的障礙物分布情況進行標準評分。當此方向的評分較高時，說明該方向海況良好，障礙物分布較少；當此方向評分較低時，說明障礙物分布復雜，海況情況復雜，在此方向繼續搜索前進的話，可能需要耗費更多時間，或使算法陷入死鎖[14]。探路蟻可以讓算法規避易死鎖的節點，既節約了死鎖后逃逸需要的時間，又保證了算法收斂時的穩定性，提高了算法收斂速度。

當搜索蟻進行下一節點選擇時，假定搜索蟻Mk的當前位置為Lk，設Lp1為搜索蟻Mk的一個可行柵格，則在Lp1柵格放置一只探路蟻。

第一種情況：當柵格Lp1不在邊界處時，則探路蟻沿向量LkLp1的方向移動一個柵格，到達柵格Lr1，探路蟻在以Lr1柵格為中心的（3×3）方形區域進行障礙物復雜情況探索，計算該區域的障礙物復雜度。如圖4所示，紅色圓形為搜索蟻Mk的位置，它的下一可行節點有Lp1柵格、Lp2柵格等，則對應的紅色三角形所在柵格即為對應可行節點探路蟻的位置，對紅色虛線范圍內的（3×3）柵格進行障礙物分布探索。

圖4 障礙物探索位置示意圖

第二種情況：Lp1柵格位于邊界處，如圖5所示，紅色圓點為搜索蟻Mk的位置，Lp1是它的下一可行點，但Lp1位于邊界位置，不存在沿LkLp1方向的下一節點，則探路蟻的位置為紅色三角形所在的柵格，探路蟻以紅色三角形柵格為中心進行障礙物分布情況探索。

圖5 邊界情況下障礙物探索位置示意圖

第三種情況：若探路蟻最終的位置柵格在邊界的4個角落柵格（柵格序號為1、20、380、400），則該可行節點的障礙物復雜度置0。

綜上，每個可行節點gi的障礙物復雜度mark(gi)已求出，將距離啟發信息和障礙物復雜度線性權衡，最終得出該可行節點的綜合評分S(gi)如下：

其中，Dis(gi)是當前節點gi到目標節點的距離，mark(gi)為節點gi對應的障礙物柵格的個數。因此，新的啟發式函數如下：

復雜障礙物的存在，尤其是U型等陷阱類障礙物分布，不僅對算法的性能造成了影響，更對航線的安全性做出了考驗，人工探路蟻的提前規避作用，在一定程度上提高了航線的安全性。

3.2 改進信息素更新策略

常規蟻群算法只在迭代時才更新路徑上的信息素，這種更新方式不僅影響了算法的收斂速度，還較容易出現局部最優解。為避免上述的缺點，采用局部信息素更新和最優最差獎懲機制迭代信息素更新來改進蟻群算法的信息素更新策略[15]。

（1）局部信息素更新

每一代的每一只螞蟻在經過某個節點后都對該節點的信息素進行更新，更新方式如下：

其中，ρ為信息素揮發因數，在[0，1]范圍內可調；τ0為信息素初始濃度；τij為節點i到節點j路徑上的信息素。螞蟻k經過某節點后，隨時間增加，路徑上的信息素揮發了一部分，保證了信息素不會殘留太多而湮沒啟發信息，增加了螞蟻搜索未經過節點的概率，從而避免了局部最優解[16-17]。

（2）最優最差獎懲機制全局信息素更新

t代k只螞蟻都完成了路徑搜索，更新路徑的信息素濃度，選擇t代所有螞蟻經過路徑中最長的一條路徑Lworst和最短的一條路徑Lbest，對該路徑上的信息素濃度進行更新[18]。

如式（7）、（8）、（9）所示，Δτkij(t)為t代螞蟻k在路徑(i,j)上遺留的信息素。

3.3 動態航行速度

由于波浪滑翔機的航行動力全部來源于海洋環境，其中主要是海洋波浪的起伏帶動了波浪滑翔機的航行，因此，與普通機器人路徑規劃只考慮路徑長度不同，波浪滑翔機還要考慮航行時間。海洋環境隨所處區域位置和時間變化而變化，是一個動態參量。在環境建模之中，已經將環境因素通過速度預測模型歸一化為速度，為方便運算，本文以相鄰柵格之間為劃分單位，即柵格i到相鄰柵格j的速度為Vij(t)。在螞蟻進行下一節點轉移時，應考慮到當前時間當前節點與下一節點之間的速度，若路徑長度相同，應先考慮速度快的節點。

綜上，引入人工探路蟻來改進啟發函數，障礙物復雜度和距離啟發信息共同作用形成新的啟發函數Hj(t)；整合海洋環境因素，利用預測速度模型求出波浪滑翔機在當前時間地點下的航行速度Vij(t)；利用局部信息素更新和最優最差獎懲機制迭代信息素更新改進蟻群算法的信息素更新策略，得出新的路徑上的信息素濃度τij(t)。新的節點狀態轉移規則如下：

3.4 改進蟻群算法的流程

步驟1初始化海洋環境參數，包括波浪的有效波高、地下水流等環境因素；初始化蟻群算法的參數，包括螞蟻個數m、迭代次數k、初始時刻路徑上的信息素濃度、信息素強度Q、信息素揮發系數等參數。

步驟2柵格建模，利用柵格法將海洋環境離散處理，并根據海洋環境數據，利用預測速度模型，將海洋環境歸一化為動態速度。

步驟3所有螞蟻開始路徑選擇，依據節點狀態轉移規則選擇下一節點，并將當前節點加入到禁忌表tabuk中。

步驟4判斷螞蟻是否到達終點，若某只螞蟻到達終點，則局部信息素更新；某代所有螞蟻完成從起點到終點的搜索后，選出最優局部路徑和最差局部路徑，全局更新路徑上的信息素濃度。

步驟5判斷是否達到最大迭代次數，若沒有繼續迭代循環，達到最大迭代次數后，輸出時間和路徑長度最優的路線。

4 仿真驗證

采用Matlab2014a編程平臺進行實驗仿真，仿真環境為20 km×20 km的海洋區域，障礙物分布已知。算法中的參數初始化為螞蟻個數M=50，最大迭代次數K=80，其他參數根據實際仿真效果動態調整[19]。

仿真實驗結果如下：

由于改進蟻群算法引入了人工探路蟻，提前對無效或容易使路徑陷入死鎖的節點進行屏蔽，有效提高了算法的收斂速度。圖6為改進算法和常規算法的收斂曲線對比，圖7為改進算法和常規算法的仿真路線對比，可以看出，改進算法在第15代左右就收斂并趨于穩定，較常規蟻群算法的25代左右趨于穩定有明顯的提升。

圖6 改進算法和常規算法的收斂曲線對比

圖7 改進算法和常規算法仿真路線對比

圖8 常規算法和改進算法仿真路線對比（增加障礙物）

（1）更換仿真環境，增加障礙物分布的復雜情況。在新的靜態環境中進行仿真實驗，如圖8所示，在圖7仿真環境的基礎上增加了障礙物的復雜情況。常規蟻群算法在遇到障礙物阻擋前進方向時，繞障礙物移動，沒有提前探索到障礙物，這增加了路徑的長度[20]。而改進蟻群算法提前探索到了障礙物的分布，提前舍棄該節點躲避了障礙物，相較于常規蟻群，路徑長度較短，安全性更高。

（2）由于單次算法運行結果有偶然性，為驗證改進后算法的有效性，選取兩種新的仿真環境，多次運行取平均值。另外，由于節點之間的航行速度不同，且在路徑節點選擇時已經將速度考慮進去，航行時間和航行路徑長度應該都是衡量算法優劣的性能指標。如表1所示，在改進算法和常規算法規劃出來的路徑長度相近時，改進算法的航行時間更短。改進蟻群算法的總體性能較常規蟻群算法有了明顯的提升。

5 結論

本文針對波浪滑翔機的路徑規劃問題，提出一種改進的蟻群算法。

表1 改進蟻群算法和常規蟻群算法的性能對比

（1）考慮到海洋環境障礙物分布復雜，引入了人工探路蟻，對可行節點方向的障礙物分布情況提前探索，充分避免了算法易陷入死鎖的問題，減少了收斂振蕩，提高了收斂速度，也提高了航線的安全性。

（2）針對波浪滑翔機的動力特點，將海洋環境因素依據波浪滑翔機環境預測模型歸一化為預測速度，并將此因素加入蟻群算法的狀態轉移規則中，在考慮航線長度的同時兼顧航行速度。

（3）針對蟻群算法信息素更新策略的缺點，增加了局部信息素更新方式，利用最優最差獎懲機制改進了迭代信息素更新策略，增加了螞蟻的尋優能力，增大螞蟻搜索范圍，避免了局部最優解。

經仿真驗證，改進后的蟻群算法完全勝任波浪滑翔機的路徑規劃任務，即使在復雜的海洋環境中，也可以快速地規劃出一條距離短、安全性高的航線。