王澳剛，智鵬飛，朱琬璐

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

1 引言

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

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

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

2 改進A*算法的無人船路徑規(guī)劃

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

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

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

為了滿足無人船在海上的實時自主導航要求，柵格地圖中的坐標需要與電子海圖中的經緯度坐標進行對應。將電子海圖所跨越的經度分成份，所跨越的緯度分成份度。電子海圖跨越的經度為最大經度減去最小經度，跨越的緯度為最大緯度減去最小緯度。設為無人船當前位置的經度坐標，為當前位置的緯度坐標，則電子海圖中各經緯度坐標在柵格地圖中對應的、坐標為：

(1)

(2)

其中：為取整運算操作。

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

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

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

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

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

()=()+()

(3)

式中：()為當前柵格到起始柵格的航行代價；()為當前柵格到目標柵格的航行代價。

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

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

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

()=()+()

(4)

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

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

()=()+()+()

(5)

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

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

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

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

(6)

式中：為當前柵格橫坐標；為起點柵格橫坐標；為目的地柵格橫坐標；為當前柵格縱坐標；為目的地柵格縱坐標；為目的地柵格縱坐標；(-)為水平距離(-)為垂直距離。

結合式(3)和式(6)，引入變向干擾值約束后，各柵格對應的啟發(fā)式代價函數為：

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

(7)

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

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

路徑平滑優(yōu)化

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

(8)

(9)

(10)

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

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

3 多路徑搜索算法

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

首先利用改進A算法進行路徑規(guī)劃搜索出一條優(yōu)化路徑，將該路徑上的所有節(jié)點坐標和航行代價存儲起來，并提高其移動到終點的估算成本，結合式(7)，新的代價函數為

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

(11)

當為存儲節(jié)點時，′()=()。為新節(jié)點時，′()=()，為成本倍數系數。

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

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

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

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

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

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

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

圖9 基于人工勢場的改進A*算法搜索范圍示意圖

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

4 風險評估函數

無人船的實時傳感器難以檢測到被遮擋視野的障礙物。如圖11所示，無人船在柵格地圖中有2種風險區(qū)域，綠色區(qū)域為靠近障礙物的風險區(qū)域。紅色圓圈區(qū)域為存在雙重碰撞幾率的高風險區(qū)域，這里視野受到遮擋，環(huán)境復雜，碰撞風險大。

圖11 風險區(qū)域示意圖

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

為風險系數，為節(jié)點到不同障礙物的距離，風險等級的范圍是(0,),為周圍障礙物的數量，障礙物越密集的地方，其風險等級也越高。

當=1，>時，<1,為障礙干擾值的覆蓋寬度。表示該區(qū)域遠離障礙物，風險等級較低。

當>1,>1時，表示該區(qū)域為高風險區(qū)域，障礙物密集。

利用風險評估函數對搜索到的所有優(yōu)化路徑進行風險區(qū)域檢測，通過比較路徑經過高風險等級區(qū)域的數量，便可以獲得全局最優(yōu)路徑。

5 仿真結果

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

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

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

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

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

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

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

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

6 結論

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

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