一種混合優(yōu)化的全局路徑規(guī)劃算法

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

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

0 引 言

智能化的發(fā)展首先體現(xiàn)在水下無人機器人、無人機、無人車的出現(xiàn)，隨著智能化研究的深入無人水面艇隨之而來并飛速進(jìn)步，在軍事領(lǐng)域技術(shù)已經(jīng)較為成熟[1]。無人水面艇作為軍事領(lǐng)域的重要研究對象，其在航行過程中的路徑規(guī)劃也十分關(guān)鍵，一般可分為2種類型：一種是全局路徑規(guī)劃，另一種是局部路徑規(guī)劃[2]。二者之間的主要區(qū)別是已知信息量的范圍，全局路徑規(guī)劃是已知整個航行環(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]針對多變因素和即時重要需求約束提出了一種基于Voronoi圖和改進(jìn)遺傳算法的快速路徑規(guī)劃方法。陳超等[11]改進(jìn)人工勢場法來解決最小點問題。

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

1 問題描述

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

1.1 應(yīng)用平臺

“藍(lán)信”號USV作為一種具有全自主和半自主控制的多功能智能化無人水面機器人由大連海事大學(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ā)的自主動態(tài)避碰控制器、自主導(dǎo)航運動控制器、多信息網(wǎng)絡(luò)控制器和推進(jìn)控制器等[16]；“藍(lán)信”號USV能夠通過地面站設(shè)備操控?zé)o人船以較高的航行速度實現(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)化。本文主要以遺傳算法為主，同時使用A*算法進(jìn)行搜索范圍預(yù)處理，并對其規(guī)劃出來的路線給出適當(dāng)?shù)脑u價函數(shù)，通過評價函數(shù)更直觀的了解規(guī)劃出的路線的避障能力。

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

2.1 A＊算法

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

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

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

2.2 遺傳算法

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

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

2.3 人工勢場法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗驗證及結(jié)果分析

4.1 實驗環(huán)境搭建

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

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

4.2 仿真平臺搭建

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

4.3 實驗結(jié)果及分析

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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