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

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

（1．上海海事大學(xué)商船學(xué)院，上海 201306；2．中遠(yuǎn)海運(yùn)集裝箱運(yùn)輸有限公司，上海 200080）

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

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

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

1 實(shí)驗(yàn)部分

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

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

圖1 坐標(biāo)轉(zhuǎn)換示意圖

1.2 Voronoi-field 算法

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

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

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

1.3 改進(jìn)A-star 算法

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

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

2 結(jié)果與討論

本文對(duì)選定的海圖區(qū)域進(jìn)行柵格化處理，劃分為500×500 的柵格，每個(gè)柵格代表25m。針對(duì)USV 的操縱性能，設(shè)定了100m、200m、300m 的安全距離約束?；诓煌踩嚯x約束并且平滑優(yōu)化后的全局路徑規(guī)劃結(jié)果如圖3所示，圖3(a)為柵格環(huán)境中規(guī)劃路徑的顯示，圖3(b)為重繪的海圖水深環(huán)境中規(guī)劃路徑的顯示。

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

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

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

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

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

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

3 結(jié)論

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