王澳剛，智鵬飛，朱琬璐

(江蘇科技大學(xué)， 江蘇 鎮(zhèn)江 212000)

1 引言

路徑規(guī)劃是無(wú)人船能實(shí)現(xiàn)海上自主導(dǎo)航的重要組成技術(shù)之一，無(wú)人船路徑規(guī)劃通過(guò)對(duì)海洋環(huán)境信息進(jìn)行分析，規(guī)劃出一條安全且快捷的路徑。近年來(lái)，隨著無(wú)人船路徑規(guī)劃技術(shù)的不斷發(fā)展，路徑規(guī)劃的最佳路徑選取已經(jīng)不只是考慮最小航行代價(jià)，還與路徑的安全性、航跡的平滑度等諸多因素有關(guān)。目前無(wú)人船路徑規(guī)劃的算法主要有Dijkstra算法、A算法、D算法、蟻群算法、RRT算法等。Dijkstra算法采用貪心策略，適用于全局環(huán)境已知的情況。A算法采用啟發(fā)式路徑搜索，適用于全局環(huán)境信息已知的情況。D算法適用于環(huán)境未知或者環(huán)境存在動(dòng)態(tài)變化的情況。蟻群算法相比于其他啟發(fā)式算法具有較強(qiáng)的魯棒性,易于融合改進(jìn)。RRT算法適用于非完整約束的情況。

目前無(wú)人船在海上進(jìn)行路徑規(guī)劃時(shí)，普遍使用A算法來(lái)實(shí)現(xiàn)。但是傳統(tǒng)A算法進(jìn)行路徑搜索時(shí)，僅以航行代價(jià)作為考慮因素，沒(méi)有考慮路徑的安全性和存在多個(gè)最短路徑時(shí)無(wú)法保證搜索的路徑為最優(yōu)等因素。文獻(xiàn)[8]為避免無(wú)人船距離障礙物過(guò)近，對(duì)障礙物的邊界進(jìn)行了擴(kuò)張，結(jié)果顯示規(guī)劃的路徑能夠有效避免危險(xiǎn)區(qū)域；文獻(xiàn)[9]提出在柵格地圖中擴(kuò)大A算法的搜索方向，來(lái)調(diào)整搜索路徑中的冗余點(diǎn)與拐點(diǎn)。文獻(xiàn)[10]通過(guò)將可搜索鄰域拓展為無(wú)限個(gè)來(lái)獲得最短路徑；文獻(xiàn)[11]將搜索到的路徑代入三階貝塞爾公式以獲得連續(xù)的平滑路徑。

本文中，主要針對(duì)傳統(tǒng)A算法路徑不平滑，折點(diǎn)多，路徑單一的問(wèn)題，提出了風(fēng)險(xiǎn)因素影響下無(wú)人船智能路徑規(guī)劃方法。

2 改進(jìn)A*算法的無(wú)人船路徑規(guī)劃

2.1 基于柵格法的無(wú)人船航行環(huán)境模型構(gòu)建

柵格法在無(wú)人船路徑規(guī)劃的環(huán)境模型建立過(guò)程中具有數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單、便于轉(zhuǎn)化操作等優(yōu)點(diǎn)。為了能夠方便的獲取電子海圖中的航行信息，需要先將電子海圖轉(zhuǎn)化為灰度圖，灰度圖二值化后生成黑白地圖，其中黑色部分表示障礙物區(qū)域，白色部分表示可航行區(qū)域。在黑白地圖中建立柵格坐標(biāo)軸，、分別表示柵格的橫坐標(biāo)和縱坐標(biāo)，賦予柵格地圖中黑色障礙物部分狀態(tài)值為(,)=1，白色可航行部分狀態(tài)值為(,)=0。當(dāng)無(wú)人船進(jìn)行路徑規(guī)劃的路徑搜索時(shí)僅讀取柵格的狀態(tài)值就能辨別當(dāng)前位置是否為可航行區(qū)域。圖1所示為某電子海圖的柵格化環(huán)境模型。

圖1 環(huán)境模型示意圖

為了滿足無(wú)人船在海上的實(shí)時(shí)自主導(dǎo)航要求，柵格地圖中的坐標(biāo)需要與電子海圖中的經(jīng)緯度坐標(biāo)進(jìn)行對(duì)應(yīng)。將電子海圖所跨越的經(jīng)度分成份，所跨越的緯度分成份度。電子海圖跨越的經(jīng)度為最大經(jīng)度減去最小經(jīng)度，跨越的緯度為最大緯度減去最小緯度。設(shè)為無(wú)人船當(dāng)前位置的經(jīng)度坐標(biāo)，為當(dāng)前位置的緯度坐標(biāo)，則電子海圖中各經(jīng)緯度坐標(biāo)在柵格地圖中對(duì)應(yīng)的、坐標(biāo)為：

(1)

(2)

其中：為取整運(yùn)算操作。

2.2 基于改進(jìn)A* 算法的路徑規(guī)劃

基于傳統(tǒng) A算法的無(wú)人船路徑規(guī)劃僅以航行代價(jià)作為啟發(fā)函數(shù)，不僅在存在多個(gè)最短路徑時(shí)無(wú)法保證搜索的路徑為最優(yōu)，而且規(guī)劃出的路徑不能保證無(wú)人船在復(fù)雜海洋環(huán)境中航行的安全性和連續(xù)平滑。

針對(duì)無(wú)人艇路徑規(guī)劃的單一性問(wèn)題，本文中，首先結(jié)合無(wú)人船的航行環(huán)境模型，引入障礙干擾值約束A算法的啟發(fā)函數(shù)，越靠近障礙物的可行區(qū)域，其干擾值越大，以此建立無(wú)人船安全區(qū)域模型。然后利用變向干擾值約束對(duì)A算法進(jìn)行航向優(yōu)化。再利用貝塞爾曲線使航跡更加平滑連續(xù)，最后獲得一條基于改進(jìn)A算法的優(yōu)化路徑。

障礙干擾值約束下的A啟發(fā)函數(shù)

基于上述構(gòu)建的柵格化無(wú)人船航行環(huán)境模型，采用具有障礙干擾值約束的 A算法以實(shí)現(xiàn)路徑規(guī)劃。傳統(tǒng)A算法的啟發(fā)式函數(shù)表達(dá)式如下：

()=()+()

(3)

式中：()為當(dāng)前柵格到起始柵格的航行代價(jià)；()為當(dāng)前柵格到目標(biāo)柵格的航行代價(jià)。

可知傳統(tǒng)A算法的啟發(fā)式代價(jià)函數(shù)僅為當(dāng)前單元柵格到目標(biāo)柵格的距離，沒(méi)有考慮到在復(fù)雜海面上距離障礙越近的區(qū)域無(wú)人船遇到風(fēng)險(xiǎn)的概率越大的情況，所以應(yīng)當(dāng)引入障礙干擾值來(lái)優(yōu)化A算法的啟發(fā)式代價(jià)函數(shù)。

如圖2所示，綠色區(qū)域是被賦予了障礙干擾值的區(qū)域，則當(dāng)前柵格到目標(biāo)柵格的航行代價(jià)為：

圖2 障礙干擾值約束下的柵格示意圖

()=()+()

(4)

式中：()為當(dāng)前柵格到目標(biāo)柵格的距離；()為當(dāng)前柵格被賦予的障礙干擾值。

根據(jù)式(3)和式(4)，障礙干擾值約束下各柵格的啟發(fā)函數(shù)可定義為

()=()+()+()

(5)

變向干擾值約束下的A啟發(fā)函數(shù)

傳統(tǒng)A算法下的無(wú)人船路徑規(guī)劃中路徑會(huì)出現(xiàn)不必要的變向，從而出現(xiàn)連續(xù)“顫抖”現(xiàn)象，如圖3中1處所示。但是，無(wú)人船的運(yùn)動(dòng)控制系統(tǒng)對(duì)路徑的跟隨能力不是無(wú)限的，規(guī)劃的航行路徑應(yīng)該盡量減少變向的次數(shù)。1處紅色路徑的變向不符合無(wú)人船的運(yùn)動(dòng)規(guī)則，所以應(yīng)該選擇變向更少的2處的藍(lán)色路徑。針對(duì)這一問(wèn)題，可以通過(guò)修改代價(jià)函數(shù)，來(lái)選擇變向更少的路徑。

圖3 A*搜索得到的兩條距離相等路徑示意圖

無(wú)人船的航跡先盡量減少頻繁的變向，盡可能的沿著一個(gè)方向航行。在柵格地圖上，相同航行代價(jià)下的點(diǎn)越接近起點(diǎn)或是終點(diǎn)優(yōu)先級(jí)越高。這里引入變向干擾值約束對(duì)路徑進(jìn)行選擇優(yōu)化，變向干擾值定義如下：

(6)

式中：為當(dāng)前柵格橫坐標(biāo)；為起點(diǎn)柵格橫坐標(biāo)；為目的地柵格橫坐標(biāo)；為當(dāng)前柵格縱坐標(biāo)；為目的地柵格縱坐標(biāo)；為目的地柵格縱坐標(biāo)；(-)為水平距離(-)為垂直距離。

結(jié)合式(3)和式(6)，引入變向干擾值約束后，各柵格對(duì)應(yīng)的啟發(fā)式代價(jià)函數(shù)為：

()=()+*()+()

(7)

利用變向干擾值約束下的A算法進(jìn)行路徑搜索，得到如圖4所示。

圖4 變向干擾值優(yōu)化的路徑示意圖

路徑平滑優(yōu)化

在引入變向干擾值約束后，可以獲得變向較少的路徑，但是此時(shí)獲得的路徑中還存在一些變向角度過(guò)大的拐點(diǎn)，并不符合無(wú)人船的運(yùn)動(dòng)規(guī)則。需要將這些拐點(diǎn)擬合成一條平滑的曲線。這里用貝塞爾曲線進(jìn)行路徑平滑優(yōu)化，貝塞爾曲線公式如下：

(8)

(9)

(10)

假設(shè)一條路徑有+1個(gè)節(jié)點(diǎn)，，…,，利用階貝塞爾曲線優(yōu)化得到如圖5所示的平滑曲線。

圖5 貝塞爾曲線優(yōu)化的平滑曲線

3 多路徑搜索算法

經(jīng)過(guò)基于改進(jìn)A算法的路徑搜索后，便得到一條優(yōu)化路徑，但是由于A算法不能保證一次搜索得到的路徑就是最優(yōu)路徑。為了能夠獲得多條平衡了路徑相似度和路徑航行代價(jià)的優(yōu)化路徑，提出一種多路徑搜索算法。

首先利用改進(jìn)A算法進(jìn)行路徑規(guī)劃搜索出一條優(yōu)化路徑，將該路徑上的所有節(jié)點(diǎn)坐標(biāo)和航行代價(jià)存儲(chǔ)起來(lái)，并提高其移動(dòng)到終點(diǎn)的估算成本，結(jié)合式(7)，新的代價(jià)函數(shù)為

()=()+*′()+()

(11)

當(dāng)為存儲(chǔ)節(jié)點(diǎn)時(shí)，′()=()。為新節(jié)點(diǎn)時(shí)，′()=()，為成本倍數(shù)系數(shù)。

再次利用改進(jìn)A算法進(jìn)行搜尋，由于搜索過(guò)的路徑上的節(jié)點(diǎn)到終點(diǎn)的估算成本提高，再次搜索得到的路徑便是平衡了路徑相似度和路徑航行代價(jià)的優(yōu)化路徑。

多路徑規(guī)劃算法流程如圖6所示。

圖6 多路徑搜索算法流程框圖

設(shè)置=15，=2時(shí)，可以得到兩條優(yōu)化路徑，如圖7所示。

圖7 多路徑搜索優(yōu)化路徑示意圖

多路徑優(yōu)化算法通過(guò)對(duì)已搜索路徑的航行代價(jià)加權(quán)搜索新路徑，相比于傳統(tǒng)A算法，縮小了搜索范圍，提高了搜索效率。傳統(tǒng)A算法搜索范圍如圖8中橙色區(qū)域所示，基于人工勢(shì)場(chǎng)的改進(jìn)A算法搜索范圍如圖9中橙色區(qū)域所示，優(yōu)化算法搜索范圍如圖10中橙色區(qū)域所示。

圖8 傳統(tǒng)A*算法搜索范圍示意圖

圖9 基于人工勢(shì)場(chǎng)的改進(jìn)A*算法搜索范圍示意圖

圖10 優(yōu)化算法搜索范圍示意圖

4 風(fēng)險(xiǎn)評(píng)估函數(shù)

無(wú)人船的實(shí)時(shí)傳感器難以檢測(cè)到被遮擋視野的障礙物。如圖11所示，無(wú)人船在柵格地圖中有2種風(fēng)險(xiǎn)區(qū)域，綠色區(qū)域?yàn)榭拷系K物的風(fēng)險(xiǎn)區(qū)域。紅色圓圈區(qū)域?yàn)榇嬖陔p重碰撞幾率的高風(fēng)險(xiǎn)區(qū)域，這里視野受到遮擋，環(huán)境復(fù)雜，碰撞風(fēng)險(xiǎn)大。

圖11 風(fēng)險(xiǎn)區(qū)域示意圖

因此，通過(guò)多路徑搜索算法得到的多條路徑雖然航行代價(jià)相似卻存在不同的風(fēng)險(xiǎn)，需要評(píng)估路徑的安全性，以獲得平衡了航行代價(jià)和安全性的全局最優(yōu)路徑。風(fēng)險(xiǎn)評(píng)估函數(shù)定義為

為風(fēng)險(xiǎn)系數(shù)，為節(jié)點(diǎn)到不同障礙物的距離，風(fēng)險(xiǎn)等級(jí)的范圍是(0,),為周圍障礙物的數(shù)量，障礙物越密集的地方，其風(fēng)險(xiǎn)等級(jí)也越高。

當(dāng)=1，>時(shí)，<1,為障礙干擾值的覆蓋寬度。表示該區(qū)域遠(yuǎn)離障礙物，風(fēng)險(xiǎn)等級(jí)較低。

當(dāng)>1,>1時(shí)，表示該區(qū)域?yàn)楦唢L(fēng)險(xiǎn)區(qū)域，障礙物密集。

利用風(fēng)險(xiǎn)評(píng)估函數(shù)對(duì)搜索到的所有優(yōu)化路徑進(jìn)行風(fēng)險(xiǎn)區(qū)域檢測(cè)，通過(guò)比較路徑經(jīng)過(guò)高風(fēng)險(xiǎn)等級(jí)區(qū)域的數(shù)量，便可以獲得全局最優(yōu)路徑。

5 仿真結(jié)果

在 Python 3.7環(huán)境下，為驗(yàn)證風(fēng)險(xiǎn)因素影響下無(wú)人船智能路徑規(guī)劃方法的可行性，對(duì)某海域的電子海圖進(jìn)行柵格化處理，設(shè)置每個(gè)柵格代表的橫向與縱向?qū)嶋H距離均為 20 m，處理結(jié)果如圖1所示。然后利用改進(jìn)A算法進(jìn)行路徑規(guī)劃搜索出一條優(yōu)化路徑，如圖5所示。設(shè)置=15，=2，得到優(yōu)化路徑1和優(yōu)化路徑2，如圖12所示。

圖12 傳統(tǒng)A*路徑和優(yōu)化路徑示意圖

對(duì)比傳統(tǒng)A算法搜索的路徑，和利用多路徑搜索獲得的兩條改進(jìn)A算法的優(yōu)化路徑，所得結(jié)果如表1所示。

表1 本文中方法與傳統(tǒng)方法路徑規(guī)劃結(jié)果Table 1 Comparison of path planning performance between this method and traditional method

對(duì)比傳統(tǒng)A算法、基于人工勢(shì)場(chǎng)的改進(jìn)A算法和本文中的優(yōu)化算法的搜索效率，所得結(jié)果如表2所示。

表2 搜索效率Table 2 Comparison of search efficiency

表1可知：本文中的優(yōu)化算法比傳統(tǒng)A算法規(guī)劃的總航程略長(zhǎng)，A算法變向很頻繁，本文中的優(yōu)化算法轉(zhuǎn)向次數(shù)比傳統(tǒng)A算法明顯減少。傳統(tǒng)A算法規(guī)劃的路徑一直貼著危險(xiǎn)區(qū)域，路徑1和路徑2途徑的危險(xiǎn)區(qū)域明顯減少，路徑1途徑的危險(xiǎn)區(qū)域最少。表2可知：本文中的優(yōu)化算法搜索范圍比傳統(tǒng)A算法和基于人工勢(shì)場(chǎng)的改進(jìn)A算法的小，從相同的起點(diǎn)搜索到終點(diǎn)本文中的優(yōu)化算法搜索效率最高。

綜合考慮規(guī)劃總航程，變向次數(shù)和途徑風(fēng)險(xiǎn)區(qū)域的數(shù)量，路徑1是全局最優(yōu)路徑。

6 結(jié)論

通過(guò)改進(jìn)基于A算法的無(wú)人船路徑規(guī)劃，提升了無(wú)人船路徑規(guī)劃的實(shí)用性和安全性。利用多路徑搜索算法可以獲得多條協(xié)調(diào)了航行代價(jià)和路徑相似度的優(yōu)化路徑。

所提出的風(fēng)險(xiǎn)因素影響下無(wú)人船智能路徑規(guī)劃方法可獲得平滑度更好、更安全的全局最優(yōu)路徑，非常適用于無(wú)人船在復(fù)雜海洋環(huán)境下的路徑規(guī)劃。