韓新潔，李欣然，范云生，孫曉界

(大連海事大學(xué) 船舶電氣工程學(xué)院，遼寧 大連 116026)

0 引 言

智能化的發(fā)展首先體現(xiàn)在水下無人機(jī)器人、無人機(jī)、無人車的出現(xiàn)，隨著智能化研究的深入無人水面艇隨之而來并飛速進(jìn)步，在軍事領(lǐng)域技術(shù)已經(jīng)較為成熟[1]。無人水面艇作為軍事領(lǐng)域的重要研究對象，其在航行過程中的路徑規(guī)劃也十分關(guān)鍵，一般可分為2種類型：一種是全局路徑規(guī)劃，另一種是局部路徑規(guī)劃[2]。二者之間的主要區(qū)別是已知信息量的范圍，全局路徑規(guī)劃是已知整個(gè)航行環(huán)境信息而局部路徑規(guī)劃則是只能根據(jù)傳感器探測得到周圍的環(huán)境信息[3]。傳統(tǒng)的路徑規(guī)劃方法主要有人工勢場法[4]、蟻群算法[5]、柵格法[6]等。智能化算法主要有模糊邏輯算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法以及混合算法等[7]。由于工作環(huán)境以及需要的不同，傳統(tǒng)算法無法滿足路徑規(guī)劃的需要因而許多研究者對算法進(jìn)行了組合和改進(jìn)。張玉奎[8]利用遺傳算法和人工勢場法對多種復(fù)雜的障礙物環(huán)境進(jìn)行規(guī)劃。王燕龍等[9]提出了一種基于航行安全權(quán)重，導(dǎo)頻量和路徑曲線平滑的改進(jìn)A*算法。曹璐[10]針對多變因素和即時(shí)重要需求約束提出了一種基于Voronoi圖和改進(jìn)遺傳算法的快速路徑規(guī)劃方法。陳超等[11]改進(jìn)人工勢場法來解決最小點(diǎn)問題。

本文在前人研究成果的基礎(chǔ)上，以無人水面艇為例提出一種混合算法優(yōu)化的全局路徑規(guī)劃方法，對環(huán)境中的可行區(qū)域使用A*算法預(yù)處理后使用遺傳算法進(jìn)行路徑規(guī)劃并對結(jié)果進(jìn)行平滑處理獲得適合快速安全行進(jìn)的路線，并給出一種評價(jià)體系對規(guī)劃結(jié)果進(jìn)行定量的避障評價(jià)，評價(jià)結(jié)果顯示通過混合優(yōu)化算法規(guī)劃出的路徑更安全和平滑。

1 問題描述

在全局路徑規(guī)劃中，無人艇航行環(huán)境已知，并且確定無人艇的位置[12]，需要根據(jù)要求如耗時(shí)短、耗能少、路線距離小等[13]搜索出一條最適合當(dāng)前要求的能夠到達(dá)目標(biāo)點(diǎn)的路徑。本文在進(jìn)行全局路徑規(guī)劃過程中選取使用的算法為能夠?qū)o態(tài)障礙物進(jìn)行全局路徑規(guī)劃的遺傳算法，但基本的遺傳算法存在著早熟、收斂速度慢等問題[14]，因此在基本的遺傳算法上進(jìn)行一定的改進(jìn)，在規(guī)劃出路線的同時(shí)進(jìn)行一定的優(yōu)化，并給出避障能力的評價(jià)指標(biāo)。

1.1 應(yīng)用平臺(tái)

“藍(lán)信”號USV作為一種具有全自主和半自主控制的多功能智能化無人水面機(jī)器人由大連海事大學(xué)自主研發(fā)[15]。

船長7.02 m、型寬2.60 m、配備5.0 L排量191.1 kW的推進(jìn)器、該船最大載荷1 000 kg、航速最高可達(dá)35 kn、可持續(xù)航行180 n mile。艇上搭載有紅外熱成像系統(tǒng)、4G波段連續(xù)波導(dǎo)航雷達(dá)、前掃防碰撞聲納、海事衛(wèi)星鏈路終端、多路差分GPS/BDS、姿態(tài)方位組合導(dǎo)航、高清視頻和音頻、VHF通信等多種傳感器；配備自主研發(fā)的自主動(dòng)態(tài)避碰控制器、自主導(dǎo)航運(yùn)動(dòng)控制器、多信息網(wǎng)絡(luò)控制器和推進(jìn)控制器等[16]；“藍(lán)信”號USV能夠通過地面站設(shè)備操控?zé)o人船以較高的航行速度實(shí)現(xiàn)多種功能。

1.2 全局路徑規(guī)劃的快速平滑安全性問題

隨著現(xiàn)有各種算法的不斷發(fā)展，采用單一方法雖然也能夠?qū)崿F(xiàn)路徑規(guī)劃，但是每種方法也都存在著一些不足和待解決的問題，因而不斷出現(xiàn)各種改進(jìn)及優(yōu)化使得基礎(chǔ)算法不斷完善，得到更快更好的路徑規(guī)劃結(jié)果。遺傳算法以其并行性和良好的全局尋優(yōu)能力而著稱，但由于算法中早熟和收斂速度慢等不足，因此需要對其進(jìn)行改進(jìn)優(yōu)化。本文主要以遺傳算法為主，同時(shí)使用A*算法進(jìn)行搜索范圍預(yù)處理，并對其規(guī)劃出來的路線給出適當(dāng)?shù)脑u價(jià)函數(shù)，通過評價(jià)函數(shù)更直觀的了解規(guī)劃出的路線的避障能力。

2 全局路徑規(guī)劃算法介紹

2.1 A＊算法

A*算法作為智能化算法一種是典型的啟發(fā)式算法，能夠靈活方便解決問題[17]。A*算法主要是將搜索空間看作是一系列位置節(jié)點(diǎn)和連接它們的邊，針對不同邊長賦予相應(yīng)的路徑價(jià)值，通過搜索到達(dá)目標(biāo)節(jié)點(diǎn)價(jià)值最小的節(jié)點(diǎn)序列來得到最短路徑[18]。

評價(jià)函數(shù)作為算法的核心，表達(dá)式為：

式中：n為當(dāng)前搜索到的節(jié)點(diǎn)位置；f(n)為估價(jià)函數(shù)，其中估價(jià)是指從起始位置經(jīng)過節(jié)點(diǎn)n以最優(yōu)路徑到目標(biāo)位置的價(jià)值；g(n)表示從初始位置以實(shí)際的最短路徑到節(jié)點(diǎn)n的價(jià)值，如果n為起始位置，則g(n)=0；h(n)是“估算”節(jié)點(diǎn)n以最優(yōu)路徑到目標(biāo)位置的價(jià)值。

2.2 遺傳算法

遺傳算法由美國J.Holland教授在1975年提出，是一種模擬生物進(jìn)化過程尋找最優(yōu)解的智能搜索算法[19]。它以初始種群為基礎(chǔ)，其中初始種群是某一隨機(jī)產(chǎn)生的或是特定的，種群由若干經(jīng)過基因編碼的個(gè)體組成。按照適者生存和優(yōu)勝劣汰的原則經(jīng)過選擇、復(fù)制、交叉、變異等操作并根據(jù)個(gè)體的適應(yīng)度不斷迭代計(jì)算從而引導(dǎo)種群的基因向最優(yōu)解逼近[20]。迭代結(jié)束后，將最優(yōu)個(gè)體的基因經(jīng)過解碼得到最優(yōu)解或近似最優(yōu)解[21]。遺傳算法簡單易用，容易得到滿意結(jié)果，且適用于并行分布處理，在科學(xué)研究和工程領(lǐng)域得到普遍認(rèn)可[22]。

遺傳算法是基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交叉操作和變異操作，并且能夠同時(shí)處理群體中的多個(gè)個(gè)體，能夠減少陷入局部最優(yōu)解的可能，此外具有自組織、自適應(yīng)和自學(xué)習(xí)性，利用進(jìn)化過程獲得的信息自行組織搜索時(shí)適應(yīng)度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。但是遺傳算法通常的效率比其他傳統(tǒng)的優(yōu)化方法低，易過早收斂，而且對精度、可行度、計(jì)算復(fù)雜性等方面，還沒有有效的定量分析方法。

2.3 人工勢場法

Khatib[23]針對配置空間提出了勢場的概念。人工勢場是將被控對象看作一個(gè)質(zhì)點(diǎn)，其所在環(huán)境為二維歐式空間，對環(huán)境空間模擬潛在的引力場和斥力場，其中目標(biāo)位置周圍為吸引力場，障礙物周圍為排斥力場[24]，環(huán)境中被控對象的運(yùn)動(dòng)虛擬為在受力場中的運(yùn)動(dòng)，障礙物產(chǎn)生斥力，目標(biāo)則為引力，2種力產(chǎn)生的合力控制運(yùn)動(dòng)方向[25]。

3 全局路徑規(guī)劃的混合優(yōu)化

3.1 全局路徑規(guī)劃的優(yōu)化

遺傳算法之所以能被大量使用是因其并行性和良好的全局尋優(yōu)能力等，但也飽受早熟和收斂速度慢等問題的困擾。收斂速度慢的原因有很多，例如隨著搜索范圍的不斷擴(kuò)大，生成的隨機(jī)初始種群的可能性也越來越多，有些位置可能會(huì)出現(xiàn)在初始種群中，但在路徑規(guī)劃時(shí)，這些位置最終不會(huì)出現(xiàn)在可行路徑，排除這些可行區(qū)域中的不通行區(qū)域，能夠減少不必要的計(jì)算量。

選擇A*算法進(jìn)行預(yù)處理是因?yàn)锳*算法從當(dāng)前節(jié)點(diǎn)出發(fā)向周圍8個(gè)方向進(jìn)行節(jié)點(diǎn)擴(kuò)展，如圖1所示。

圖1 A*算法擴(kuò)展節(jié)點(diǎn)方向圖Fig.1 A* algorithm extended node pattern

8個(gè)節(jié)點(diǎn)選取“估算”價(jià)值最小的節(jié)點(diǎn)作為路徑節(jié)點(diǎn)序列中第2個(gè)節(jié)點(diǎn)，然后對第2個(gè)節(jié)點(diǎn)進(jìn)行相同操作直到目標(biāo)節(jié)點(diǎn)，搜索出最短路徑[26]。A*算法在規(guī)劃過程中會(huì)有許多可行點(diǎn)作為規(guī)劃結(jié)果而導(dǎo)致最終路徑過于冗余，也會(huì)出現(xiàn)一些大角度的轉(zhuǎn)折，因此在使用A*算法作為路徑規(guī)劃算法時(shí)需要對其進(jìn)行改進(jìn)優(yōu)化，綜上考慮選取A*算法作為預(yù)處理方法保證非全覆蓋搜索后搜索到的可行柵格內(nèi)包含最優(yōu)路徑。

A*算法對海圖進(jìn)行預(yù)處理主要是對給定的海圖以及起始點(diǎn)和目標(biāo)點(diǎn)進(jìn)行搜索區(qū)域計(jì)算，柵格大小選取為海圖的一個(gè)像素點(diǎn)，通過預(yù)處理縮小可行區(qū)域范圍，并將搜索區(qū)域的范圍讀取出來作為遺傳算法的初始種群范圍。圖2是以天津港的海圖作為無人艇的航行環(huán)境，給定的起始點(diǎn)和目標(biāo)點(diǎn)位置在圖中以綠色點(diǎn)的形式顯示，使用A*算法對環(huán)境進(jìn)行預(yù)處理，紅色區(qū)域?yàn)槭褂肁*算法預(yù)處理后得到的可行區(qū)域范圍，其中經(jīng)過預(yù)處理后的可行區(qū)域約占整個(gè)海圖可行區(qū)域的40%，減少了遺傳算法的規(guī)劃范圍，提高了遺傳算法全局路徑規(guī)劃效率。

由于采用不同的海圖以及設(shè)置的起始點(diǎn)和目標(biāo)點(diǎn)存在差異，因此預(yù)處理過程搜索出的可行區(qū)域相對于原環(huán)境的海圖來說能夠減少一定的可行區(qū)域面積，但是具體減少的面積比例要根據(jù)實(shí)驗(yàn)環(huán)境中的可行區(qū)域以及對起始點(diǎn)和目標(biāo)點(diǎn)的設(shè)定的不同而存在差異。

圖2 A*預(yù)處理結(jié)果Fig.2 A* preprocessing results

遺傳算法中著重考慮的是適應(yīng)度函數(shù)，在本文中選取的是最小路徑代價(jià)、平均拐角值代價(jià)和碰撞威脅代價(jià)得到綜合最小解[27,28]。綜合最小解Value(P*)為Value(P*)=min[f1(P),f2(P),f3(P)]，其中，目標(biāo)函數(shù)f1(P),f2(P),f3(P)代表無人艇路徑的平滑性、經(jīng)濟(jì)性和安全性。路徑光滑性平均拐角值代價(jià)(li-2)+mi×C2；經(jīng)濟(jì)性主要考慮的是路徑長度及最小路徑代價(jià)，其中路徑長度f2(P)為{Length(Pi)}，最小路徑代價(jià)Length(Pi)為：Length(Pi)=安全性{danger(Pi)}，其中danger(di)=1/di。

由于無人艇實(shí)際航行軌跡應(yīng)為一條連續(xù)平滑的曲線，而進(jìn)化遺傳算法得到的可行路徑是由浮點(diǎn)數(shù)所連接而成的折線段組成，因此要對結(jié)果進(jìn)行平滑處理使其能夠作為無人艇的航行路線。通過采用貝塞爾數(shù)學(xué)優(yōu)化方法，可以將折線路徑進(jìn)行曲線優(yōu)化[29]。

貝塞爾曲線普遍應(yīng)用為矢量曲線，一般化的n階貝塞爾曲線表達(dá)式為:

其中，B(t)表示由點(diǎn)P0，P1，···，Pn所決定的貝塞爾曲線，t∈(0,1]。

路徑優(yōu)化采用高階貝塞爾曲線，階數(shù)選取依據(jù)可行路徑的浮點(diǎn)個(gè)數(shù)，從而得到光滑的連續(xù)路徑。

本文提出的混合優(yōu)化算法主要是對遺傳算法的初始種群進(jìn)行優(yōu)化，對生成初始種群的范圍進(jìn)行縮小，在不影響最終路線的情況下，縮小搜索范圍，使得混合優(yōu)化后的算法能夠快速有效的規(guī)劃出適合無人水面艇安全航行的全局路線。

3.2 評價(jià)函數(shù)的優(yōu)化

本文提出一種對避障能力進(jìn)行評價(jià)的方法，利用人工勢場法的思想，將無人艇行進(jìn)過程中的陸地島嶼等不可行區(qū)域看作斥力影響，目標(biāo)點(diǎn)則看作引力影響，給出引力和斥力對無人艇的影響函數(shù)，最終得到評價(jià)函數(shù)。其中無人艇受到的斥力由當(dāng)前行進(jìn)的位置點(diǎn)到左右兩側(cè)的最近障礙點(diǎn)的斥力值之差來確定，斥力值需要分別計(jì)算左右兩側(cè)，通過下式計(jì)算得到：

式中：h為行駛到當(dāng)前規(guī)劃路線時(shí)所在點(diǎn)(x0,y0)與最近障礙點(diǎn)(xb,yb)的距離

最終該位置點(diǎn)的斥力fr由式（3）分別計(jì)算出左側(cè)障礙物的斥力值frel和右側(cè)障礙物的斥力值frer，取兩者之差的絕對值作為該點(diǎn)的斥力

無人艇受到的引力主要是目標(biāo)點(diǎn)對當(dāng)前行進(jìn)的位置點(diǎn)的吸引，當(dāng)前位置點(diǎn)離目標(biāo)點(diǎn)越近，受到的引力值越大，受到的引力fa通過下式計(jì)算得到：

式中：H為行駛到當(dāng)前規(guī)劃路線時(shí)所在點(diǎn)(x0,y0)到目標(biāo)點(diǎn)(xa,ya)的距離。

評價(jià)函數(shù)作為無人艇受到的合力值，是整個(gè)規(guī)劃的路線中每一個(gè)位置點(diǎn)的引力和斥力值之和后取平均值，而斥力在評價(jià)函數(shù)中是作為負(fù)值出現(xiàn)的，因此引入的評價(jià)函數(shù)為：

其中：n為規(guī)劃出的路線上所有點(diǎn)的個(gè)數(shù)。

評價(jià)函數(shù)評價(jià)的路徑為經(jīng)過混合算法得到的路徑點(diǎn)使用貝塞爾曲線平滑處理后的路徑，若經(jīng)過平滑處理后的路線經(jīng)過障礙物及其他不可行區(qū)域則重新進(jìn)行全局路徑規(guī)劃。評價(jià)函數(shù)的值越高，說明經(jīng)過平滑處理得到的可行路徑能夠保證在整個(gè)行進(jìn)的過程中無人艇距離周圍陸地及暗礁島嶼的距離都很充裕，能夠較好地使用算法獲得最優(yōu)路徑。

4 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境搭建

本文在Matlab環(huán)境中基于天津港的海圖針對無人艇進(jìn)行了全局路徑規(guī)劃。首先對獲取的電子海圖進(jìn)行加載，用Matlab讀取電子海圖的像素點(diǎn)信息，將彩色的海圖進(jìn)行圖像處理，分離障礙物與可行進(jìn)區(qū)域，設(shè)置起始點(diǎn)和目標(biāo)點(diǎn)的位置，使用A*算法對規(guī)劃路線區(qū)域進(jìn)行預(yù)處理，縮小生成初始種群的范圍。對縮小后的可行區(qū)域范圍使用遺傳算法進(jìn)行路徑規(guī)劃并對規(guī)劃后的路線進(jìn)行平滑處理從而使規(guī)劃出來的路線更符合船舶運(yùn)動(dòng)特性。最后對規(guī)劃出來的路線進(jìn)行避障評價(jià)，采用基于人工勢場法的評價(jià)函數(shù)對規(guī)劃路線的避障能力予以評價(jià)分析，以便更加顯著地看出使用混合算法優(yōu)化的路線具有更好地避障能力，具體流程如圖3所示。

圖3 混合算法流程圖Fig.3 Hybrid algorithm flowchart

4.2 仿真平臺(tái)搭建

本文在Matlab上使用混合算法進(jìn)行路徑規(guī)劃的同時(shí)，搭建了能夠加載海圖顯示相關(guān)參數(shù)的QT平臺(tái)。該平臺(tái)能夠加載典型航行區(qū)域的電子海圖，并可以針對每個(gè)加載的海圖設(shè)置相應(yīng)的起點(diǎn)和終點(diǎn)經(jīng)緯度，選擇相應(yīng)的算法進(jìn)行路徑規(guī)劃。

4.3 實(shí)驗(yàn)結(jié)果及分析

本文在Matlab上對天津港的海圖進(jìn)行了模擬仿

真，仿真主要是以天津港為背景，結(jié)合天津港周圍的海況以及暗礁島嶼繪制出天津港的環(huán)境，通過對周圍的島嶼及陸地等無人艇不可能行駛的區(qū)域進(jìn)行提取后，

分別使用A*算法和混合算法對無人艇進(jìn)行路徑規(guī)劃，使無人艇能夠避開障礙物從設(shè)定的起始點(diǎn)到達(dá)目標(biāo)點(diǎn)。本文首先使用了路徑規(guī)劃較為廣泛的A*算法對天津港的周圍區(qū)域進(jìn)行全局路徑規(guī)劃，設(shè)定起始位置和目標(biāo)位置后使用A*算法進(jìn)行規(guī)劃并對規(guī)劃出來的折線結(jié)果進(jìn)行相同的貝塞爾曲線平滑處理，對最終的路徑點(diǎn)進(jìn)行避障結(jié)果評價(jià)。在進(jìn)行平滑處理后得到的曲線會(huì)穿過障礙物致使無人艇無法航行，使用A*算法規(guī)劃并進(jìn)行平滑處理后得到的仿真結(jié)果如圖4所示。

圖4 使用A*算法仿真圖Fig.4 Simulation diagram using A* algorithm

在使用A*算法進(jìn)行路徑規(guī)劃的同時(shí)，本文也使用了混合優(yōu)化算法對天津港附近海域進(jìn)行了同樣的路徑規(guī)劃，設(shè)定相同的起始點(diǎn)和目標(biāo)點(diǎn)，得到的仿真結(jié)果如圖5所示。由于起點(diǎn)和終點(diǎn)都位于不可行區(qū)域附近，結(jié)合仿真結(jié)果和評價(jià)值，說明規(guī)劃出的路徑能夠正確避開障礙物及不可行區(qū)域抵達(dá)目標(biāo)點(diǎn)。

圖5 使用混合算法仿真圖Fig.5 Simulation diagram using a hybrid algorithm

A*算法和混合算法都能夠?qū)㈦娮雍D給出的附近區(qū)域中的障礙物和可行區(qū)域信息提取出來，在設(shè)定起始點(diǎn)和目標(biāo)點(diǎn)之后通過算法得到一條無碰撞航線，但是經(jīng)過貝塞爾曲線平滑處理后，2種算法得到的路線有一些不同之處，依據(jù)避障評價(jià)函數(shù)對2種算法進(jìn)行評價(jià)的結(jié)果如表1所示。其中安全距離為無人艇與周圍障礙物之間的最小距離，避障評價(jià)為衡量算法規(guī)劃出的路徑對于無人艇平穩(wěn)安全通過的能力。

表1 A＊算法與混合算法的對比Tab.1 Comparison of A* algorithm and hybrid algorithm

通過評價(jià)結(jié)果可以看到當(dāng)確定無人艇航行環(huán)境以及起始點(diǎn)和目標(biāo)點(diǎn)時(shí)，A*算法的規(guī)劃路徑穿越障礙物區(qū)域，這種路徑是不能被采用的，本文所提出的混合算法可以規(guī)劃出一條足夠安全的路徑。同時(shí)本文通過所提出的評價(jià)函數(shù)對不同算法規(guī)劃出來的路線進(jìn)行避障能力的評價(jià)，用數(shù)值直觀地給出評價(jià)結(jié)果。通過以上仿真及評價(jià)函數(shù)的結(jié)果可以顯著地看出使用混合優(yōu)化算法比用A*算法規(guī)劃的路線具有更好的避障能力，其生成的路徑能夠與周圍障礙物保持相對較遠(yuǎn)的安全距離，使得船只能夠更安全的通過障礙物區(qū)域抵達(dá)目標(biāo)點(diǎn)。

5 結(jié) 語

本文將A*算法應(yīng)用到遺傳算法中提出混合路徑規(guī)劃算法，首先A*算法預(yù)處理從起點(diǎn)到目標(biāo)點(diǎn)進(jìn)行大致范圍搜索，減少遺傳算法中計(jì)算的范圍，然后使用遺傳算法對起點(diǎn)到目標(biāo)點(diǎn)的路線進(jìn)行規(guī)劃生成能夠行進(jìn)的路線，最后引入評價(jià)函數(shù)對規(guī)劃出來的路線進(jìn)行評價(jià)，評價(jià)函數(shù)的值越高，該路線的避障能力越強(qiáng)，最后選擇最為合適的路線作為最優(yōu)路線。在仿真過程中，使用能夠提供周圍障礙的圖像并給出起始點(diǎn)和目標(biāo)點(diǎn)，使用Matlab進(jìn)行路徑規(guī)劃，并對規(guī)劃出的路線進(jìn)行評價(jià)，最終得到較為合適且便捷的行進(jìn)路線。同時(shí)使用QT搭建界面顯示的平臺(tái)，加載相應(yīng)的環(huán)境進(jìn)行路徑的設(shè)置和顯示。在接下來的研究中路徑規(guī)劃算法不僅需要考慮行駛的天氣性因素，還要對行駛中的其他各種干擾情況進(jìn)行考慮。