較強海流中的低速水下機器人路徑優化

朱心科，侯 斐，孟 肯，羅建超

（自然資源部第二海洋研究所海底科學重點實驗室，浙江 杭州 310012）

以水下滑翔機為代表的低航速水下機器人由于長續航力方面的優勢，在海洋觀測中的應用越來越多。從1997年開始，美國就開始了自主海洋采樣網（Autonomous Ocean Sampling Network，AOSN）試驗，試驗中使用了17個水下滑翔機，其中12個為Slocum水下滑翔機，5個為Spray水下滑翔機，分別搭載溫鹽深（Conductivity，Temperature，Depth）、葉綠素、熒光計等傳感器對蒙特利海灣（Monterey Bay）上升流進行了40天的調查[1-4]。丹麥的卑爾根大學（University of Bergen）利用3臺水下滑翔機在格陵蘭島海域對大西洋與北歐之間的海水交換問題進行長期觀測[5]。BOSSE A等[6]利用水下滑翔機對Lofoten海盆的渦旋進行連續15個月的觀測，對其造成的海洋生態環境參數動態變化進行了記錄。然而水下滑翔機的長續航力是以犧牲滑翔速度為代價的，一般來說水下滑翔機的速度為0.5～1 kn，在較強的海流環境中，很難完成設定的觀測軌跡。SOULIGNAC M等[7]設計了SWE（Symbolic Wavefront Expansion）算法，在機器人出發時間窗內選擇最佳的出發時刻，使得完成使命的時間最短。

水下機器人（Autonomous Underwater Vehicle，AUV）路徑規劃問題一直是研究的熱點，涌現出了各種各樣的方法。傳統的AUV水下路徑規劃是以安全為主要出發點，目的是AUV在執行任務的過程中，能夠成功避開障礙物或者危險區域[8-10]。隨著AUV智能性的提升，AUV路徑規劃研究的目標除了避障之外，還要考慮任務的完成質量，例如AUV在較強的海流環境中完成指定的任務花的時間最短、走的路程最小、消耗的能量最少或者幾種的折中。ALVAREZ A等[11]以完成任務消耗的能量為優化準則，采用動態規劃的方法，在不同空間尺度的海流環境中對AUV的路徑進行優化。A*算法也常被用作AUV的路徑規劃[12-13]。

傳統的AUV路徑規劃算法中，一般假設海流為常值，不隨時間和位置發生變化，而在實際的海流場中，海流是時空變化的。KRUGER D[14]等設計了優化算法克服了快速變化的雙向潮汐流，能夠讓AUV“騎”著海流穿梭運動，克服遠大于自身速度的海流速度。對于以水下滑翔機為代表的低航速水下機器人來說，為了提高續航力必須降低功耗，一般不安裝測流速傳感器，無法實時獲得海流信息。海流預報模型輸出的數據可以用來指導水下路徑規劃。THOMPSON R等[15]依據海流預報數據，利用Wavefront算法設計了在時變海流情況下的水下滑翔機路徑規劃策略，取得了不錯的效果。

對于海洋預報來說，海流的預報時間是有時限的，只能夠提供一定時間內的海流預報，而且預報準確度隨著預報時間增長而降低[4]。對于利用海流預報數據進行水下路徑規劃來說，走完從出發位置與目標位置之間路程花費時間有可能超過單個預報周期。本文將針對較強海流場中海流的時變性以及預報周期有限的問題，以水下滑翔機為例，開展低航速水下機器人路徑規劃方法研究。

1 問題描述

一般情況下，水下滑翔機進入穩定滑翔狀態后，浮力調節系統不再發生變化。因此，滑翔速度的大小為定值，滑翔方向是可變的。假設水下滑翔機在穩態滑翔時速度為vr，海流速度為vc。

當k?2時，海流速度對水下滑翔機的運動軌跡影響微乎其微，路徑規劃可以忽略海流影響；當k＜0.5時，由于水下滑翔機的速度太小，在海流場中基本上處于隨波逐流的狀態，失去了路徑規劃的意義；當0.5≤k≤2時，海流對滑翔機的運動軌跡會有較大的影響，但通過合適的路徑規劃算法，滑翔機能夠克服、利用海流，從而獲得一條最優的觀測路徑，論文針對這種情況開展研究。

論文基于水平面內的二維海流為假設前提。在二維的離散空間，海洋環境定義在n×p個規則的網格上，空間中任意點x=（h，k）為其中的一個網格，0≤h≤n，0≤k≤p，h和k分別代表該網格的橫、縱坐標。從出發點S到目標點D的路徑P定義為一組有序點的集合Γ=S，…，xi-1，xi，…，D中相鄰兩點之間的連線。

水下滑翔機在靜水中的對地水平滑翔速度為vr，海流速度為vc（x，y，t），表示在t時刻位置（x，y）處的海流速度。以水下滑翔機以最短的時間到達目的地為路徑規劃目標如下。

2 水下滑翔機運動模型

假設水下滑翔機在靜水中的水平滑翔速度為vr，大小為定值，方向可變；海流速度為vc（x，y，t）（在不致混淆情況下，用vc，表示），那么水下滑翔機的對地速度v如下。

海流方向為θc，水下滑翔機靜水中的速度方向為θr，對地速度方向為θ。假設二維空間中每個網格中海流速度是定值，如果從一個網格運動到另一個網格，水下滑翔機有8個方向可選，如圖1所示。因此，水下滑翔機的對地速度可以寫為

圖1 可移動方向

由于水下滑翔機速度方向是可變的，可以是任意值。通過式（4）和式（5）消去θr可得關于對地速度的方程如下。

由式（6）表示的方程可以判斷滑翔機能否從一個網格運動到另一個網格。若方程有一個正數解，表示水下滑翔機能夠從當前網格運動到下一個網格；如果方程的解為有負數或者復數，表示水下滑翔機無法抵制強海流從當前網格運動到下一個網格。如果有兩個正數解，選擇較大的v作為水下滑翔機的合速度。

3 路徑規劃算法

對于離散空間中的路徑規劃問題，Wavefront算法和A*搜索是較常用算法，分別應用這兩種算法對水下滑翔機進行路徑規劃，并對結果進行比較。

3.1 Wavefront算法

傳統的Wavefront算法[6]主要分為兩個部分，首先，從出發點開始向相鄰節點擴展，一直擴展到目標節點為止，在擴展的過程中，記錄每個被擴展到的節點需要的代價；然后，從目標節點開始，根據記錄的每個被擴展到節點的代價，利用爬山法反向構建最優路徑。在這里，進行兩個方面的改變：①代價最小的節點優先向前擴展。②每個節點指定一個唯一的父節點。通過修改擴展規則，可以大幅度減小節點的擴展數量，同時有利于反向構造最優路徑，提升算法速度。Wavefront算法的擴展過程如下。

（1）A→B，其中A為父節點，B為子節點，表示為P（A，B）。每個節點前向擴展過程中可以有多個子節點，但只能有一個父節點；

（2）T（A，B）表示從水下滑翔機節點A運動到節點B花費的時間；T（B）表示從水下滑翔機出發點運動到節點B花費的總時間；

（3）如果B的父節點為A，即P（A，B），如果滿足T（B）＞T（C）+T（C，B），則B的父節點由A改變為C，即P（C，B），并且從出發點運動到B點的花費的總時間更新成T（B）=T（C）+T（C，B）；

（4）每次前向擴展總是從min{T（x）}的節點開始，直至到達目標節點；

（5）從目標點開始，按照代價最低原則反向尋找自己的父節點，直至到達出發點為止。

利用Wavefront算法進行路徑規劃時，只要從出發點到目標點的路徑存在，就一定能夠找到一條全局最優路徑。但是，由于Wavefront算法無啟發式搜索，搜索的過程中擴展的節點較多，因此搜索時間較長。

3.2 A*算法

A*算法與Wavefront算法最大不同之處是代價評價函數中加入了啟發函數。啟發函數體現了當前節點與目標節點的關系，因此能夠加速朝著目標節點方向進行搜索。

A*算法的評價函數定義如下。

式中，T（n）為出發點運動到當前節點的代價；h（n）為當前節點運動到目標節點代價的估計值。

式中，s（d，n）為當前節點到目標節點的歐氏距離；vmax為水下滑翔機的最大速度。當h（n）≤h*（n）（h*（n）為當前節點到目標節點代價的真值）時，h（n）稱作可采納啟發函數。在這種情況下，只要從出發點到目標點的路徑存在，那么A*算法就一定能搜索到全局最優解。

與Wavefront算法相比，由于A*算法具有啟發性，評價函數中體現了當前節點與目標節點之間的關系，只要保證啟發函數是可采納啟發，那么在節點的擴展過程中，只需要朝著當前評價函數最小的節點擴展而無需擴展當前節點所有的相鄰節點，就能夠搜索到全局最優解，從而提升了搜索效率。

3.3 算法仿真

3.3.1 海流模型

以流函數描述的周期性變化的雙曲流為例驗證路徑規劃算法[4]。雙曲流定義如下。

其中，

海流的速度場如下。

圖2 雙曲海流

3.3.2 仿真結果

假設在路徑規劃過程中，已經通過海洋預報獲得了海流信息。路徑規劃的出發點為s（10，20），目標點為d（80，30），分別利用Wavefront算法和A*算法在對水下滑翔機在海流環境中進行路徑規劃，結果如圖3所示。

圖3 路徑規劃結果

圖3 （a）中，棕色網格表示Wavefront算法在搜索過程中父節點沒有發生過改變，黃綠色網格表示該節點的父節點發生過改變，二者共同表示在算法搜索過程中擴展到的節點。圖3（b）中，棕色網格表示A*算法在搜索過程中該節點沒有被反復搜索過，黃綠色網格表示該節點被重復搜索過。從圖3可以看出，A*算法搜索過程擴展的節點個數明顯小于Wavefront算法，從而搜索速度相對較快。在本仿真實例中，A*算法的搜索速度是Wavefront算法的3倍。由于A*算法的啟發函數是可采納的，因此和Wavefront算法搜索到的路徑完全一樣，都是最優的。

4 分段路徑規劃

4.1 分段路徑規劃算法

數值海洋預報根據預報的范圍和空間分辨率不同，預報的時效也不同，從數小時到幾十個小時不等。當出發點與目標點間的距離相對較近時，完成觀測任務需要的時間相對較短，根據單個周期的海洋預報提供的海流信息，利用Wavefront算法或者A*算法均可搜索到最優路徑，稱之為完整路徑規劃；當兩個點距離較遠，單個預報周期提供的海流信息不足以完成觀測任務的路徑規劃時，就需要根據預報周期分段進行路徑規劃，稱之為分段路徑規劃[4]。

Wavefront算法不適合分段路徑規劃，因為只能得到出發點到目標點之間的最優路徑，無法得到中間值。對于A*算法來說，算法具有啟發性，能夠評價中間點和目標點之間的相互關系，因此，適合用來進行分段路徑規劃。

當觀測時間超過海流預報周期時，可以利用A*算法先找到單個預報周期內最優的路徑，然后再以這條最優路徑的終點作為下一段路徑優化的起點進行路徑規劃，直至到達目標點為止。算法偽代碼如表1所示。

表1 分段路徑規劃偽代碼

4.2 仿真結果

路徑規劃算法的海流環境仿真參數同3.1節中的參數，水下滑翔機的出發點為S（170，60），目標點為D（10，20），分別用完整路徑規劃算法和分段路徑規劃算法兩種方式進行。進行分段路徑規劃時，假設海流的預報周期為1個時間單位，即10個時間步長的海流預報，仿真結果如圖4所示。

圖4 完整路徑規劃與分段路徑規劃比較

結果顯示，無論是利用完整還是分段路徑規劃算法，水下滑翔機都能克服海流從出發點順利到達目標點，二者的差別主要體現在走完該段路徑用時不同。完整路徑規劃得到的路徑長度為2.19個距離單位，從出發點到目標點用時5.25個時間單位；分段路徑規劃得到的路徑長度為2.25個距離單位，用時5.73個時間單位。對比發現，分段路徑規劃獲得路徑長度僅比最優路徑多了2.7%，而用時卻多了9%。這是由于基于A*算法的分段路徑規劃算法是“貪婪”式搜索，當啟發函數是可采納的情況下，每段的路徑都是最優的，但是組合起來后就不一定是全局最優；同時，由于兩種算法規劃出來的路徑不同造成滑翔機遭遇到的海流速度（方向和大小）也不同，因此增加的耗時與路徑長度并不一定成正比。但總的看來，走完分段路徑規劃得到路徑需要的時間僅僅超過最優路徑需要時間的9%，這個偏差結果在可接受的范圍之內，表明基于A*算法的分段路徑規劃算法能夠滿足時變海流中的低航速水下機器人的路徑規劃。

5 結論與展望

5.1 結論

針對以水下滑翔機為代表的低航速水下機器人航跡易受海流的影響問題，研究了在較強海流下路徑規劃方法。

（1）當海流預報周期小于滑翔機水下觀測時間時，Wavefront算法和A*算法均能夠克服較強海流對滑翔機觀測路徑的影響，獲得最優的觀測路徑。

（2）當海流預報周期超出滑翔機水下觀測時間時，Wavefront算法只能得到出發點與目標點之間的最優路徑，而無法得到中間值，無法進行路徑規劃。

（3）設計了分段式A*路徑規劃算法，解決了觀測時間超出海洋預報周期問題。

仿真結果顯示，分段式A*路徑規劃算法獲得較為合理的觀測路徑。該方法可為水下滑翔機為代表的低航速水下機器人在海洋觀測中的應用提供理論指導。

5.2 展望

分段路徑規劃的本質是“貪婪”式規劃，每一段都選擇當前的局部最優。局部最優組合起來的完整路徑往往與全局最優路徑會有一定的差距，未來將會考慮用拉格朗日相干結構（Lagrangian Coherent Structures，LCS）指導路徑規劃。LCS描述了流體的平均運動，與變化較快的海流場相比，LCS具有長期的穩定性，而且能將海流場明顯地分為不同的區域，水下機器人沿著LCS能夠較容易地從一個區域到達另外一個區域。同時，水下機器人沿著LCS運動一方面能夠節省能量，另一方面也能夠提高對地速度，是一條比較理想的軌跡，在最大程度上減小與全局最優解的偏差。基于LCS的路徑規劃算法對被動式海洋觀測設備，如Argo浮標、表面漂流浮標的投放位置、間距的選擇也有一定的指導作用，可以避免設備在海流作用下過早地漂到近岸或者聚集在一起，失去大范圍觀測的意義。