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

陳 茜，高軍偉，官 晟

1.青島大學(xué) 自動化學(xué)院，山東 青島266071

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

1 引言

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

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

2 算法描述

2.1 環(huán)境建模和波浪滑翔機的數(shù)學(xué)模型

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

圖1 波浪滑翔機結(jié)構(gòu)圖

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

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

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

海洋環(huán)境中除了暗礁障礙物外，波浪、風(fēng)速、洋流等因素也應(yīng)該考慮進柵格環(huán)境內(nèi)。

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

其中，ysog是波浪滑翔機的對地速度；xwht是有效波高；xwpp是波峰周期；xwdir是波浪滑翔機航向與波向的差值；xwnd是風(fēng)速在航向軸向的分量；xadcp是表層流速在航向軸向的分量；xhfr是淺層流速在航向軸向的分量[9]。因?qū)嶋H中采集到的海洋環(huán)境數(shù)據(jù)有限，僅考慮影響速度的主要因素，將速度預(yù)測模型簡化如下：

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

2.2 常規(guī)蟻群算法簡介和相關(guān)改進

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

圖3 海洋環(huán)境速度預(yù)測柵格建模

常規(guī)蟻群算法的節(jié)點選擇方式是根據(jù)節(jié)點之間的信息素濃度和啟發(fā)信息進行概率選擇的，在t時刻，螞蟻k從節(jié)點Xi轉(zhuǎn)移到節(jié)點Xj的轉(zhuǎn)移概率公式如下：

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

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

3 改進蟻群算法

3.1 改進啟發(fā)函數(shù)

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

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

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

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

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

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

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

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

其中，Dis(gi)是當(dāng)前節(jié)點gi到目標(biāo)節(jié)點的距離，mark(gi)為節(jié)點gi對應(yīng)的障礙物柵格的個數(shù)。因此，新的啟發(fā)式函數(shù)如下：

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

3.2 改進信息素更新策略

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

（1）局部信息素更新

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

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

（2）最優(yōu)最差獎懲機制全局信息素更新

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

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

3.3 動態(tài)航行速度

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

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

3.4 改進蟻群算法的流程

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

步驟2柵格建模，利用柵格法將海洋環(huán)境離散處理，并根據(jù)海洋環(huán)境數(shù)據(jù)，利用預(yù)測速度模型，將海洋環(huán)境歸一化為動態(tài)速度。

步驟3所有螞蟻開始路徑選擇，依據(jù)節(jié)點狀態(tài)轉(zhuǎn)移規(guī)則選擇下一節(jié)點，并將當(dāng)前節(jié)點加入到禁忌表tabuk中。

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

步驟5判斷是否達到最大迭代次數(shù)，若沒有繼續(xù)迭代循環(huán)，達到最大迭代次數(shù)后，輸出時間和路徑長度最優(yōu)的路線。

4 仿真驗證

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

仿真實驗結(jié)果如下：

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

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

圖7 改進算法和常規(guī)算法仿真路線對比

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

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

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

5 結(jié)論

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

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

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

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

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

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