基于海圖環(huán)境的無人艇全局路徑規(guī)劃

馬欣，楊兵，邱斌彬，王勝正，趙建森

（1．上海海事大學商船學院，上海 201306；2．中遠海運集裝箱運輸有限公司，上海 200080）

近年來，由于全球氣候變暖、陸地資源緊缺、環(huán)境污染日益加劇，世界各國對海洋資源的開發(fā)更加重視，也因此帶動了水面無人艇（Unmanned Surface Vehicle，USV）和水下機器人等海上高端設備的快速發(fā)展。作為一種海上智能機器人，USV 能夠在無人干預的狀況下獨立執(zhí)行任務，是一種具有體量小、高速智能、隱蔽性強等優(yōu)點的水面作業(yè)任務平臺，主要被用于執(zhí)行具有危險性以及不適合有人船舶執(zhí)行的任務。無人艇在環(huán)境監(jiān)測、水文探測、近海巡邏、海上搜尋救助、遠程偵察等民用及軍事領域中都發(fā)揮了重大的作用。

Singh等使用可以設置安全距離的A*算法在衛(wèi)星圖上生成了一條沿岸的安全路徑，該方法更適用于近岸航行。Candeloro等利用維諾圖（Voronoi Diagram，VD）方法對新加坡海峽的航行空間進行分割，分割邊界上的路徑是環(huán)境中最安全的路徑，但利用費馬螺線方法平滑后的路徑與初始規(guī)劃路徑偏差較大。Niu等利用維諾圖算法和Dijsktra 算法進行全局路徑搜索，在重構的新加坡海峽環(huán)境下得到了一條距離所有障礙物最遠的路徑但卻不夠平滑。Zhang等將遺傳算法和模擬退火法混合，在柵格化的海圖環(huán)境上進行了實驗，解決了傳統(tǒng)遺傳算法搜索能力不足和時間消耗問題。以上研究雖然考慮了路徑的安全性，但對實驗環(huán)境中障礙物的建模以及路徑的經(jīng)濟性考慮不足。

為了無人艇在自主航行過程中能夠規(guī)劃出一條安全、經(jīng)濟的路徑，本文通過Web 海圖構建基于5m 等深線的實驗環(huán)境，確定全局路徑規(guī)劃的安全性優(yōu)化目標，建立全局路徑規(guī)劃子模型。

1 實驗部分

1.1 海圖數(shù)據(jù)處理

首先，對于海圖中渲染了不同顏色的面數(shù)據(jù)，用像素閾值分割技術進行處理。其中，滿足水深約束條件的處理為可航區(qū)域，其他為障礙物區(qū)域。其次，篩選實驗區(qū)域內(nèi)礙航的點、線數(shù)據(jù)繪制在實驗環(huán)境模型中。最后，將海圖數(shù)據(jù)構建為柵格化環(huán)境模型。

圖1 坐標轉換示意圖

1.2 Voronoi-field 算法

維諾場是Dolgov等提出的在維諾圖區(qū)域邊界與障礙物之間按比例添加的危險勢場，路徑越靠近VE，則維諾場值越接近于0，越安全；路徑越靠近障礙物，則維諾場值越接近于1，越危險。維諾場定義如下所示：

式(2)中,d(x,y)為當前節(jié)點到障礙物的距離；d(x,y)為當前節(jié)點到維諾邊界的距離；a>0 是控制勢場衰減率的常數(shù)；d>0 是控制勢場最大作用范圍的常量。

該公式適用于當勢場值為0 時；因此，若將公式中的d設置為d=D，根據(jù)公式可知，維諾場值為0 的航行區(qū)域與障礙物之間的距離均大于USV 需要保持的安全距離D。無人艇航行在維諾場值為0 的區(qū)域能夠降低碰撞風險。

1.3 改進A-star 算法

A-star 算法作為一種常用的啟發(fā)式路徑搜索算法，被廣泛應用在全局路徑規(guī)劃領域。它的搜索方式有4 連通區(qū)域搜索和8 連通區(qū)域搜索兩種，考慮到USV 在海洋中的運動特性，文中采用八連通區(qū)域的搜索方式對可航水域進行搜索。本文將危險度函數(shù)作為評價函數(shù)的一部分進行路徑規(guī)劃，改進后A-star 算法的啟發(fā)式函數(shù)f(n)定義如下：

式(3)中，g(n)為起始點到當前節(jié)點的實際距離代價，h(n)為估算當前節(jié)點到目標節(jié)點的距離代價。D(n)為利用維諾場為柵格添加危險度的危險度函數(shù)。D(n)的定義如下：

2 結果與討論

本文對選定的海圖區(qū)域進行柵格化處理，劃分為500×500 的柵格，每個柵格代表25m。針對USV 的操縱性能，設定了100m、200m、300m 的安全距離約束。基于不同安全距離約束并且平滑優(yōu)化后的全局路徑規(guī)劃結果如圖3所示，圖3(a)為柵格環(huán)境中規(guī)劃路徑的顯示，圖3(b)為重繪的海圖水深環(huán)境中規(guī)劃路徑的顯示。

圖2 不同安全距離約束下的全局路徑規(guī)劃結果

圖3 不同安全距離約束下路徑平滑效果對比

圖2為傳統(tǒng)A-star 算法與不同安全距離約束條件下A-star 算法的實驗結果的對比。其中，藍色實線為沒有添加安全距離約束的A-star 算法全局路徑規(guī)劃的結果，可以看出規(guī)劃的路徑在障礙物附近貼近障礙物，這無疑會增加無人艇與障礙物之間的碰撞風險。紅色、青色與洋紅色分別為是保持100m、200m、300m 安全距離約束的路徑規(guī)劃結果，可以看出隨著距離約束的增加，規(guī)劃出的路徑在靠近障礙物時能夠保持距離約束并且安全距離越大的路徑與障礙物的距離越遠，所提的方法能夠保證安全水深的約束。

圖3為部分規(guī)劃路徑平滑優(yōu)化前后的對比。圖3(a)為平滑優(yōu)化前的路徑，路徑轉折次數(shù)多、不平滑，不符合航海實際與無人艇性能要求；圖3(b)為平滑優(yōu)化后的路徑，路徑轉折次數(shù)少、平滑性高，具有較高的指導意義。

圖4為三種不同安全距離下路徑節(jié)點與障礙物之間的距離，從圖中設置的黑色橫向虛線可以看出，路徑節(jié)點均與障礙物保持了設定的安全距離，能夠提高無人艇航行過程中的安全系數(shù)。

圖4 不同安全距離下路徑節(jié)點與障礙物的距離

3 結論

本文針對無人艇全局路徑規(guī)劃展開研究，提出了基于海圖環(huán)境的全局路徑規(guī)劃方法，在研究中著重考慮水深及安全距離的約束。首先，利用海圖水深環(huán)境進行滿足水深約束的環(huán)境建模；其次，利用Voronoi Field 算法進行安全距離約束設置并結合A*算法實現(xiàn)了在100m、200m、300m 不同安全距離下的路徑規(guī)劃；最后，利用路徑規(guī)劃中采集的數(shù)據(jù)可視化，分析了算法合理性和可行性。