基于改進人工蜂群算法的HOV 三維路徑規劃

陳帥華，趙 洋

(1. 中國科學院 沈陽自動化研究所 機器人學國家重點實驗室，遼寧 沈陽 110016；2. 中國科學院 機器人與智能制造創新研究院，遼寧 沈陽 110169；3. 遼寧省水下機器人重點實驗室，遼寧 沈陽 110169；4. 中國科學院大學，北京 100049)

0 引 言

載人潛水器作為在海洋勘察與開發中不可或缺的水下作業平臺，在深海資源勘探、海洋科學研究等工作中發揮著重要作用。我國自主研制的“奮斗者”號全海深載人潛水器，具備海底自主避碰和貼海底自動匹配地形巡航等功能[1]，提高了載人潛水器的智能程度。

然而，在載人潛水器航行的過程中，會遇到海山和深海熱液噴口等障礙，可能還會受到外界各種不確定性因素的干擾，如海洋暗流、海洋生物群落等[2]。在復雜的水下環境中，依據潛航員自身經驗，在綜合考慮路徑長度和路徑安全性等因素后，快速規劃出一條安全無碰撞的路徑有不小的難度。故而，在獲取全局環境信息后，快速地自動完成載人潛水器的全局路徑規劃，能夠輔助潛航員進行駕駛與決策，提高載人潛水器的智能程度。因此，復雜水下環境的智能路徑規劃技術是一個有意義的研究課題。

目前有多種全局路徑規劃算法，如粒子群算法、蟻群算法、A*算法、RRT 算法等。馮煒等[3]提出了基于量子行為的粒子群優化的路徑規劃方法，考慮了海流和障礙物的影響，但是其優化目標是航行時間代價，未考慮能量消耗代價。占銀[4]基于改進蟻群算法對水下機器人路徑規劃進行了研究，仿真結果表明該算法規劃的路徑更短、更平滑且收斂速度更快，但僅研究了二維平面內的路徑規劃。Garau 等[5]采用A*算法在海流環境下為AUV 規劃了運動路徑。雖然 A*算法的執行效率高，但由于A*算法是啟發式算法，無法保證所規劃路徑的全局最優性。RRT 算法可以在短時間內規劃出一條安全無碰撞的路徑[6]，Carreras 等[7]采用 RRT*算法在線進行二維 AUV 路徑搜索，但其隨機性強，往往難以得到全局最優路徑。

為此，本文針對載人潛水器三維路徑規劃問題展開研究，提出一種基于改進人工蜂群算法的三維全局路徑規劃方法。在算法初始化階段，采用混沌映射序列對蜜源進行初始化；為了跳出局部最優，采用高斯變異對部分適應度較差的個體進行擾動。最后，通過仿真證明了改進算法的有效性。

1 模型建立

1.1 三維海底模型

海洋環境模型的建立是進行路徑規劃的基礎。基于全球海陸數據庫(general bathymetric chart of the oceans，GEBCO)的開源海底地形數據對海洋環境建模。從GBECO 地圖上選定目標海域，下載后即可得目標海域范圍內海底各部分的高度數據。參照二維柵格模型的建立方法，將其推廣到三維環境中，三維海洋柵格模型示意圖如圖1 所示。

圖1 三維海洋柵格模型Fig. 1 3D ocean grid model

圖1 中，x軸和y軸代表海域的長度和寬度，z軸代表海底地形高度。從原點開始，將oxyz 空間按一定的長寬高分割為一個個小塊，然后根據獲取的海底地形高度數據值對每一個小立方體進行判斷，當立方體柵格處的高度值小于或者等于該位置所對應的海底地形高度值時，則將其視為障礙柵格，載人潛水器無法通行（見圖1 中灰色立方體），否則視為可自由航行的柵格。

1.2 海流模型

海流是載人潛水器航行的重要影響因素。在地球自轉運動的影響及海洋水平尺度遠大于垂直尺度的限制下，海流在水平面內的運動規模遠大于垂直面，因此對問題進行簡化，將海流的運動看作二維水平面內的運動，并假設海流在目標海域中不同點上的幅度和速度方向時不變。

通常海流運動可以由二維Navier-Stokes 方程進行判斷和預測，然而實時計算不僅復雜而且成本高，而二維Navier-Stokes 方程的近似解可以構造為粘性L a m b 渦流，水平面內的海流運動可用多個粘性Lamb 渦流疊加表示，其數學描述如下[8]：

式中：r0為 渦流中心的位置向量； δ 和Γ代表渦流半徑和渦流強度；Vx(r)和Vy(r)分別代表橫向、縱向的渦流速度分量；w(r)代表渦量。式(1)和式(2)中的參數設置如下： δ =1.0 ， Γ =10，將海流平面設置為長寬均為100 km 的二維平面，將其按照1 km×1 km 的大小進行分割，渦流中心矢量r0隨機取海流平面內的10 個點。由上述渦流方程可得海流模型如圖2 所示。

圖2 海流模型Fig. 2 Ocean current model

1.3 路徑規劃策略

給定起點和終點， 再加入若干個控制點，使用直線進行連接便可以得到一條折線路徑，這條不與障礙相碰撞的折線就是路徑規劃問題中的可行解。然而這樣一條折線路徑在實際航行過程中不夠光滑，不具有可行性，因此本文使用三次均勻B 樣條曲線來對路徑進行平滑處理。

k階B 樣條函數表達式為：

式 中：Pi(i=0,1,2,3···) 表示 控 制 點；Bi,k(u) 表示k次B 樣條基函數。目前廣泛使用的B 樣條基函數是由De-Boor[9]和 Cox[10]分別提出的遞推定義：

式中：u為節點；下標i為B 樣條的序號；k為B 樣條的冪次。

對于均勻B 樣條曲線，因節點等間距分布，對于任意i恒有：ui+1-ui=c，c 為常數。故經過推導計算可得三次均勻B 樣條基函數如下：

因此，可得三次B 樣條曲線段如下：

在給定控制點Pi后，使用式(7)便可求得一條由若干滿足三次B 樣條曲線點所組成的光滑曲線路徑。該方法把三維空間路徑規劃問題轉化為控制點搜索問題，降低了問題求解難度。

1.4 路徑的代價函數

從給定起點R0開始，經過中間路徑點R1,···,Rn-1，最終到達終點Rn，該路徑可表示如下：

對于所有可行路徑，需要建立一個路徑評價模型對路徑質量進行評估，在路徑長度的基礎上，加入地形代價和路徑能耗這2 個指標，得到路徑規劃的綜合代價函數，其表達式如下：

式中：Pc為路徑長度；Sc為地形代價；Ec為能耗代價。

1.4.1 路徑長度Pc

路徑長度Pc表示載人潛水器從起點到終點的行駛距離，使用歐幾里得距離度量，其計算過程可表示如下：

式中：

式中：Di為當前路徑點Ni和下一路徑點Ni+1之間的距離；n為路徑點總個數。

1.4.2 地形代價Sc

地形代價Sc表示載人潛水器在航行過程中來自海山等靜態障礙物的威脅，通過它，可以使載人潛水器避開航行路徑中的障礙，地形代價Sc可表示如下：

1.4.3 能耗代價Ec

能耗代價Ec表示載人潛水器沿規劃路徑的航行過程中為克服海流影響消耗的總能量，計算表達式如下：

式中，Wi為第i段路徑的能耗。為了計算這一項，首先對潛器在海流環境下的航行速度進行合成，其航行速度合成如圖3 所示[11]。

圖3 載人潛水器速度合成Fig. 3 Velocity synthesis of manned submersible

圖中，V為載人潛水器在靜態海洋中的航行速度；Voc為海流速度；Vh代表合成后載人潛水器的速度；θoc和 ψoc分別為海流速度在水平和垂直方向上的夾角；θ 和 ψ分別為Vh在水平和垂直方向上的夾角；Vh與Voc的夾角為Ф。由圖可得，Voc在3 個方向上的速度分量 (uoc,voc,woc)可表示如下：

載人潛水器航行速度在3 個方向上的速度分量(u,v,w)和夾角Ф可表示如下：

結合式(14)和式(15)，推導出合成后載人潛水器的速度Vh如下：

參照Alvarez 等[12]的研究，路徑中第i段的能量消耗Wi可表示如下：

式中：ρ為依賴于潛器尺寸和水流特性的常數；Voc為潛器的靜水速度值。結合式(13)可計算出路徑的總能耗代價Ec。

2 人工蜂群算法

2.1 基本人工蜂群算法

人工蜂群算法是一種模擬蜜蜂采蜜的群智能優化算法，由Karaboga 于2005 年提出[13]，其主要思路是通過蜜蜂不同個體的分工及個體間的信息交流協作尋找高質量的蜜源。人工蜂群算法包括蜜源、采蜜蜂、觀察蜂和偵察蜂4 個要素，以及種類轉化、放棄蜜源和搜索新蜜源3 種基本行為。人工蜂群算法示意如圖4 所示。

圖4 人工蜂群算法示意圖Fig. 4 Schematic diagram of artificial bee colony algorithm

一個蜜源代表所求問題的一個解。初始時，蜜源gi=(gi1,gi2,···,gid)可由下式隨機生成：

式中：gij表示第i個蜜源的第j維變量，j∈{1,2,···,d}，d為 問 題 維 數；i∈{1,2,···,N} ，N為 蜜 源 個 數；Uij，Lij為gij的上界和下界；r1為(0,1)內的隨機數。

初始化N個蜜源后，采蜜蜂在第i個蜜源周圍依照下式搜索產生一個新的蜜源：

式中：gnew為搜索得到的新蜜源；r2為隨機數；k∈{1,2,···,N} ，且k≠i。通過比較新舊蜜源的適應度大小，基于貪婪原則保留更優質的蜜源。在人工蜂群算法中，蜜源的適應度值計算方法如下：

式中，resi為 所求解問題的函數值。

在采蜜蜂搜索完成后，飛回蜂巢跳擺尾舞與其他蜜蜂共享蜜源信息。觀察蜂根據蜜源適應度，采用輪盤賭法選擇接下來要搜索的蜜源，按照下式計算對蜜源i的選擇概率：

在搜索過程中，如果經過t次迭代搜索到達陷入局部最優后的次數判斷閾值Jgelim后仍未找到更優質的蜜源，則會放棄該蜜源。同時與之對應的雇傭蜂會轉換為偵察蜂，偵察蜂會在搜索空間中隨機搜索產生一個新的蜜源，該過程可表示為如下：

2.2 改進人工蜂群算法

2.2.1 蜜源初始化

蜜源的初始化對求解的速度和質量有很大影響。在基本人工蜂群算法中，蜜源的位置通過隨機初始化產生，這樣會導致蜜源在整個目標空間中的位置分布不均勻。而基于混沌理論的混沌序列具有全空間遍歷性和動態性，因此使用混沌序列對人工蜂群算法的蜜源初始化進行改進以克服蜜源隨機初始化時存在的分布不均勻的不足。

采用Logistic 映射式產生混沌序列，公式如下：

式中： μ為增長率，當 μ=4時，系統處于全混沌狀態；x0為初值，xk指算法在第k次迭代時的值，根據混沌理論，當初值x0不等于0，0.25，0.5，0.75，1.0 時，序列處于混沌態，可以擴大算法的搜索范圍。

在引入混沌序列后，可對式(18) 進行改進得到下式：

式 中：i∈{1,2,...,N} ，N為蜜源 個 數；Ui，Li為gi的 上界和下界；xi為迭代過一定次數后的d維混度序列。

2.2.2 蜜源搜索機制

為了提高人工蜂群算法的局部搜索能力，引入高斯變異機制，在每次迭代后對蜜源的適應度函數值進行排序，選擇最差的n×η個蜜源，進行高斯變異，其中n是蜜源個數， η為變異的比例，依據經驗， η取為1/12； μ 為 均值，σ 為標準差。

最差的n×η個蜜源進行高斯變異后，新蜜源產生公式如下：

式中，git和gnewt分別為變異前和變異后的蜂群位置。

改進人工蜂群算法流程如圖5 所示。

圖5 改進人工蜂群算法流程圖Fig. 5 Flow chart of modified artificial bee colony algorithm

3 仿真及結果分析

3.1 試驗環境及算法參數設置

將式(9)作為優化目標為潛器搜索全局最優路徑。采用的仿真平臺為Matlab 2021a。基于GEBCO數據庫，選取14.7601°N～15.8°N，158.4009°E～159.4428°E 作為試驗的目標海域建立三維海底地形模型，目標海域大小為100 km×100 km。取海域中最深為Z=0 的點，其余部分的高度值根據該值確定。起點為(1,1,50)，終點為(100,100,80)。

選取基本人工蜂群算法、遺傳算法和粒子群算法與改進人工蜂群算法進行對比。這4 種算法均采用相同的最大迭代次數IterMax=100, 這些算法的其余參數如表1 所示。

表1 四種算法參數設置Tab. 1 Parameter settings for four algorithms

3.2 試驗結果

使用改進人工蜂群算法、基本人工蜂群算法、遺傳算法和粒子群算法進行三維路徑規劃，最終規劃得到的路徑如圖6～圖8 所示。

圖6 不同算法規劃的三維路徑對比Fig. 6 Comparison of three-dimensional paths between different algorithms

圖7 不同算法規劃的三維路徑俯視圖Fig. 7 Top view of three-dimensional paths

圖8 渦流環境下三維路徑俯視圖Fig. 8 Top view of three-dimensional paths in ocean current environment

可以看出，采用這4 種算法為潛器所規劃的路徑均能避開環境中的障礙物，并成功到達終點。使用上述4 種算法均分別迭代100 次后，所規劃的路徑長度見表2，所得到的適應度函數值隨著迭代次數變化曲線如圖9 所示。

表2 不同算法所規劃實際路徑長度Tab. 2 Actual path lengths planned by different algorithms

圖9 適應度函數值迭代曲線Fig. 9 Iterative curves of fitness function values

從表2 可以看出，改進人工蜂群算法相比于其他3 種算法能夠規劃出一條更短的全局最優路徑。從圖9可以看出，改進人工蜂群算法、人工蜂群算法和粒子群算法均能較快速地收斂，而遺傳算法的收斂速度則相對較慢。隨著迭代次數的增加，相比于其他3 種算法，改進人工蜂群算法能夠不斷跳出局部最優解，最終收斂在一個更小的適應度函數值。相比之下，改進人工蜂群算法的路徑規劃效果最好。

4 結 語

本文提出一種基于改進人工蜂群算法的載人潛水器路徑規劃方法，使用三維柵格模型為海洋環境建模，綜合考慮了路徑長度、地形代價和能耗代價三方面因素建立了路徑評價模型。基于Logistic 混沌映射在算法的初始化階段對蜜源進行初始化，使用高斯變異對每次路徑搜索中適應度較差的一部分個體進行擾動，提高了其局部搜索能力，并采用三次 B 樣條曲線對路徑進行平滑處理。仿真試驗表明，相比于其他群智能算法，本文提出的改進算法收斂較快，跳出局部最優的能力更強，可以高效地為載人潛水器規劃出一條滿足性能要求的最優路徑。