一種混合優化的全局路徑規劃算法

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

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

0 引 言

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

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

1 問題描述

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

1.1 應用平臺

“藍信”號USV作為一種具有全自主和半自主控制的多功能智能化無人水面機器人由大連海事大學自主研發[15]。

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

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

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

2 全局路徑規劃算法介紹

2.1 A＊算法

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

評價函數作為算法的核心，表達式為：

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

2.2 遺傳算法

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

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

2.3 人工勢場法

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

3 全局路徑規劃的混合優化

3.1 全局路徑規劃的優化

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

選擇A*算法進行預處理是因為A*算法從當前節點出發向周圍8個方向進行節點擴展，如圖1所示。

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

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

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

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

圖2 A*預處理結果Fig.2 A* preprocessing results

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

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

貝塞爾曲線普遍應用為矢量曲線，一般化的n階貝塞爾曲線表達式為:

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

路徑優化采用高階貝塞爾曲線，階數選取依據可行路徑的浮點個數，從而得到光滑的連續路徑。

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

3.2 評價函數的優化

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

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

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

無人艇受到的引力主要是目標點對當前行進的位置點的吸引，當前位置點離目標點越近，受到的引力值越大，受到的引力fa通過下式計算得到：

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

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

其中：n為規劃出的路線上所有點的個數。

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

4 實驗驗證及結果分析

4.1 實驗環境搭建

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

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

4.2 仿真平臺搭建

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

4.3 實驗結果及分析

本文在Matlab上對天津港的海圖進行了模擬仿

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

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

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

在使用A*算法進行路徑規劃的同時，本文也使用了混合優化算法對天津港附近海域進行了同樣的路徑規劃，設定相同的起始點和目標點，得到的仿真結果如圖5所示。由于起點和終點都位于不可行區域附近，結合仿真結果和評價值，說明規劃出的路徑能夠正確避開障礙物及不可行區域抵達目標點。

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

A*算法和混合算法都能夠將電子海圖給出的附近區域中的障礙物和可行區域信息提取出來，在設定起始點和目標點之后通過算法得到一條無碰撞航線，但是經過貝塞爾曲線平滑處理后，2種算法得到的路線有一些不同之處，依據避障評價函數對2種算法進行評價的結果如表1所示。其中安全距離為無人艇與周圍障礙物之間的最小距離，避障評價為衡量算法規劃出的路徑對于無人艇平穩安全通過的能力。

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

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

5 結 語

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