范云生， 趙永生， 石林龍,2， 張 月

(1.大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院， 遼寧 大連 116026； 2.上海船舶運(yùn)輸科學(xué)研究所， 上海 200135)

基于電子海圖柵格化的無人水面艇全局路徑規(guī)劃

范云生1， 趙永生1， 石林龍1,2， 張 月1

(1.大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院， 遼寧 大連 116026； 2.上海船舶運(yùn)輸科學(xué)研究所， 上海 200135)

為解決無人水面艇自主避碰決策中的全局路徑規(guī)劃問題，提出一種基于電子海圖柵格化建立環(huán)境模型的遺傳算法全局路徑快速搜索方法。通過對電子海圖數(shù)據(jù)中的海洋環(huán)境信息進(jìn)行提取，采用柵格法建立路徑搜索空間的環(huán)境模型，并使用柵格標(biāo)號對路徑個體進(jìn)行編碼，利用一種隨機(jī)快速搜索產(chǎn)生初始種群的改進(jìn)遺傳算法進(jìn)行路徑搜索，提高無人水面艇全局路徑規(guī)劃的收斂速度和優(yōu)化效率。試驗(yàn)結(jié)果表明，采用改進(jìn)遺傳算法進(jìn)行基于電子海圖柵格化的無人艇全局路徑規(guī)劃具有一定的合理性和有效性。

無人水面艇；路徑規(guī)劃；電子海圖；柵格法；改進(jìn)遺傳算法

Abstract: A global path fast search method based on genetic algorithm is proposed for the Unmanned Surface Vehicle (USV) to avoid collision autonomously. The environment model is established by rasterizing electronic chart. Marine environment information in electronic chart data is extracted. Path search space is constructed. Path individual is encoded according to the code of grid. An improved genetic algorithm that adopts heuristic random initialization population method to generate initial population is used to achieve the convergence speed and optimization efficiency of USV global path planning. The effectiveness and practicality of the algorithm are verified by experiments.

Keywords: USV； path planning； electronic chart； grid model； improved genetic algorithm

無人水面艇(Unmanned Surface Vehicle, USV)作為監(jiān)測海洋環(huán)境、維護(hù)海洋權(quán)益的現(xiàn)代化裝備，具有廣闊的應(yīng)用前景，己成為國內(nèi)外智能化海洋裝備的研究熱點(diǎn)。[1]在復(fù)雜多變的海洋環(huán)境中，自主規(guī)劃出一條從起點(diǎn)到終點(diǎn)的較優(yōu)的全局路徑既是保證USN安全航行和順利完成指定任務(wù)的前提與基礎(chǔ)[2]，也是無人水面艇智能控制技術(shù)中自主避碰決策的重點(diǎn)研究內(nèi)容之一。

目前，國內(nèi)外相關(guān)學(xué)者都在對USV的全局路徑規(guī)劃方法進(jìn)行深入研究，并已取得一定的成果。文獻(xiàn)[3]采用FAA*算法,在真實(shí)的衛(wèi)星圖像中解決USV的全局路徑規(guī)劃問題。文獻(xiàn)[4]提出一種基于新BI算法的全局路徑規(guī)劃，并在電子海圖環(huán)境中對該算法進(jìn)行驗(yàn)證。文獻(xiàn)[5]在考慮海洋環(huán)境和USV最大曲率的地圖中設(shè)計基于A*算法的3-D曲率路徑規(guī)劃算法。文獻(xiàn)[6]研究一種在網(wǎng)格地圖中基于有限角速率的θ*路徑規(guī)劃算法。文獻(xiàn)[7]在柵格環(huán)境模型中應(yīng)用改進(jìn)的蟻群算法完成USV的全局路徑規(guī)劃，驗(yàn)證算法的有效性。文獻(xiàn)[8]為減少全局路徑規(guī)劃的時間，提出一種基于電子海圖的距離尋優(yōu)Dijkstra路徑規(guī)劃算法。文獻(xiàn)[9]將遺傳算法和分層模型的激活值應(yīng)用到USV全局路徑規(guī)劃中，在實(shí)際地圖中進(jìn)行驗(yàn)證。文獻(xiàn)[10]研究一種基于勢場動態(tài)柵格法的USV全局路徑規(guī)劃方法。文獻(xiàn)[11]研究一種基于進(jìn)化遺傳算法的USV全局路徑規(guī)劃算法。此外，還有一些USV全局路徑規(guī)劃算法，如基于遺傳算法的人工勢場法[12]、基于A*算法的速度避障法[13]、基于電子海圖的A*算法[14]、基于可視圖的A*算法[15]和人工魚群算法[16]等。

為利用真實(shí)的海洋環(huán)境信息實(shí)現(xiàn)USV的全局路徑規(guī)劃，提出一種基于電子海圖柵格化建立環(huán)境模型的遺傳算法全局路徑快速搜索方法。通過電子海圖提供大量詳細(xì)、準(zhǔn)確的數(shù)字化海洋環(huán)境地理信息數(shù)據(jù)，對USV工作空間中包含陸地、島嶼和海岸等信息的海洋環(huán)境進(jìn)行準(zhǔn)確描述。在運(yùn)用柵格法建立環(huán)境模型的基礎(chǔ)上，利用改進(jìn)遺傳算法進(jìn)行路徑搜索，以降低全局路徑規(guī)劃的空間開銷，提高USV全局路徑規(guī)劃的收斂速度和優(yōu)化效率，為USV的自主智能避碰決策提供參考。

1 海洋環(huán)境模型的建立

對電子海圖中的海洋環(huán)境地理信息進(jìn)行統(tǒng)一描述，并采用柵格法進(jìn)行環(huán)境建模。柵格化的電子海圖一致性表述是提高路徑搜索算法效率的基礎(chǔ)。

1.1海洋環(huán)境信息的描述

在能反映真實(shí)海洋環(huán)境信息的環(huán)境模型中進(jìn)行USV自主避碰決策的準(zhǔn)確性取決于對多種海洋環(huán)境信息描述的精準(zhǔn)程度。依據(jù)S-57標(biāo)準(zhǔn)定義的電子海圖是一種便于進(jìn)行數(shù)據(jù)交換和傳輸?shù)母叨葔嚎s的數(shù)據(jù)格式，其數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜。因此，將電子海圖應(yīng)用到USV全局路徑規(guī)劃中，需按其對數(shù)據(jù)解析、讀取和存儲的標(biāo)準(zhǔn)，設(shè)計一種基于電子海圖的環(huán)境數(shù)據(jù)提取和建模方法。提取電子海圖中的海洋環(huán)境數(shù)據(jù)信息并對其進(jìn)行描述的過程見圖1。

圖1 海洋環(huán)境信息數(shù)據(jù)的描述方法

S-57標(biāo)準(zhǔn)電子海圖文件包括數(shù)據(jù)集的描述信息、特征記錄和空間記錄，利用ISO 8211 lib開源庫讀取電子海圖文件中的每條記錄，特征記錄用vector容器存儲，空間記錄用map容器存放，將包含陸地和島嶼等障礙物的海洋環(huán)境空間描述成USV能識別的海洋環(huán)境信息。

1.2柵格法建立環(huán)境模型

利用電子海圖中的海洋環(huán)境地理信息數(shù)據(jù)構(gòu)建的USV工作空間是由復(fù)雜幾何圖形組成的，使得大多路徑搜索算法都不能直接被利用，因此需解決全局路徑規(guī)劃中的環(huán)境建模問題，對海洋環(huán)境信息進(jìn)行柵格化，轉(zhuǎn)換成幾何關(guān)系簡單的環(huán)境模型，以提高路徑搜索算法的效率。采用柵格法進(jìn)行環(huán)境建模，設(shè)計適當(dāng)?shù)臇鸥翊笮?、合適的編碼方式及表示方法，用大小相等的柵格將電子海圖量化成具有可變分辨率的柵格網(wǎng)圖。在設(shè)定完柵格大小后，對組成環(huán)境模型的柵格進(jìn)行編碼，建立的柵格模型見圖2。

圖2 建立的柵格模型

圖2中:內(nèi)部含有礙航物的柵格稱為障礙柵格，用黑色表示；內(nèi)部不包含任何礙航物的柵格稱為自由柵格，用白色表示。從柵格網(wǎng)絡(luò)左上角的第1個柵格開始編號為0，按照從左到右、從上到下的順序依次為每個柵格編號，則編號將與環(huán)境空間中的柵格一一對應(yīng)。

USV的工作環(huán)境空間經(jīng)柵格化后轉(zhuǎn)化為柵格地圖，柵格法的一致性和規(guī)范性使環(huán)境空間簡單化，將全局路徑規(guī)劃問題轉(zhuǎn)化為在柵格網(wǎng)中尋找2個柵格節(jié)點(diǎn)之間的最優(yōu)路徑問題。

2 路徑規(guī)劃算法的改進(jìn)及實(shí)現(xiàn)

遺傳算法是一種模擬自然界中生物的遺傳和進(jìn)化過程的優(yōu)化搜索算法，通過對路徑規(guī)劃問題解集的種群進(jìn)行編碼和模擬生物界中的優(yōu)勝劣汰、基因交叉及基因突變等過程，逐代進(jìn)化出更好的種群，使搜索過程向最優(yōu)解逼近，最終收斂于最優(yōu)路徑的近似解。

2.1初始種群的產(chǎn)生

在傳統(tǒng)的遺傳算法中，初始種群個體的生成是完全隨機(jī)的，包括很多環(huán)路和不可行的路徑，這會增加算法的運(yùn)行時間,降低搜索速度和效率。對此，采用一種啟發(fā)式隨機(jī)初始化種群方法，其路徑個體采用變長度編碼方式，具體步驟如下。

1) 采用十進(jìn)制編碼與浮點(diǎn)數(shù)編碼相結(jié)合的方法對USV柵格化后的海洋環(huán)境中的航行路徑進(jìn)行編碼，其結(jié)構(gòu)為

ni1(xi1,yi1)→…→nix(xix,yix)→…→nili(xili,yili)

(1)

式(1)中:nix(xix,yix)(x=1,2,…,li-1)為路徑上中間路徑點(diǎn)所在柵格的序號和經(jīng)緯度坐標(biāo)值，路徑長度li可變。

根據(jù)當(dāng)前路徑點(diǎn)的柵格序號nix，目標(biāo)點(diǎn)的柵格序號nili和柵格網(wǎng)絡(luò)的總列數(shù)nLine，計算當(dāng)前路徑點(diǎn)和目標(biāo)點(diǎn)在柵格網(wǎng)中的行號nLastRow和nEndRow及列號nLastLine和nEndLine，目標(biāo)點(diǎn)與當(dāng)前路徑點(diǎn)的位置關(guān)系為

(2)

2) 在柵格網(wǎng)中，相鄰2個柵格點(diǎn)的位置關(guān)系用8種方向表示，當(dāng)前柵格的序號為M，數(shù)字與上述位置關(guān)系相對應(yīng)(見圖3)。

圖3 相鄰柵格的位置關(guān)系圖

圖3中， 8個方向上的柵格作為下個路徑點(diǎn)的備選柵格，根據(jù)當(dāng)前路徑點(diǎn)與終點(diǎn)的位置關(guān)系，以正態(tài)分布概率隨機(jī)選擇一個柵格作為下個路徑點(diǎn)。

3) 判斷該方向的柵格是否為自由柵格，從而決定USV的下個可行路徑點(diǎn)，重復(fù)循環(huán)上述步驟，直至到達(dá)路徑終點(diǎn)。

這種啟發(fā)式隨機(jī)初始化種群的方法利用個體路徑的路徑點(diǎn)均為自由柵格的特點(diǎn)，因此可提高初始路徑的可行性，避免初始路徑出現(xiàn)反復(fù)和原地旋轉(zhuǎn)，加快遺傳算法搜索最優(yōu)路徑的速度。

2.2適應(yīng)度函數(shù)的選取

在全局路徑規(guī)劃過程中需選取合適的適應(yīng)度函數(shù)，即將目標(biāo)函數(shù)作為評價群體中路徑優(yōu)劣的標(biāo)準(zhǔn)和依據(jù)。設(shè)計適應(yīng)度函數(shù)時應(yīng)綜合考慮安全性(即碰撞危險度)、經(jīng)濟(jì)性(即路徑長度)和光滑性(即航向變化頻率和范圍)。

Value(P*)=min[f1(P),f2(P),f3(P)]

(3)

式(3)中：目標(biāo)函數(shù)f1(P),f2(P),f3(P)分別為USV航行路徑的經(jīng)濟(jì)性、光滑性和安全性。

1) 路徑長度f1(P)=Length(Pi)。

(4)

式(4)中：mi為第i條路徑Pi中不可航行路段的個數(shù)；C1為適當(dāng)?shù)恼龜?shù)。

2) 路徑光滑性f2(P)=Turning(Pi)。

(5)

式(5)中：路徑點(diǎn)數(shù)li>2；aij(j=2,…,li-1)為pi(j-1)pij與pijpi(j+1)的夾角0≤aij<π；ki為aij中≥π/2的個數(shù)，即當(dāng)航向角≥π/2時，對適應(yīng)度值進(jìn)行懲罰；mi為路徑Pi中不可航行路段的個數(shù)；C2為適當(dāng)?shù)恼龜?shù)。

3) 安全性f3(P)=Danger(Pi)。

(6)

當(dāng)路徑Pi可行時，Danger(Pi)=1/di，其中di>0為無人艇航行時應(yīng)與障礙物保持一定的安全距離，該安全距離與無人艇的大小有關(guān)。當(dāng)路徑Pi不可行時，Dange(Pi)=miC3，其中:mi為路徑中路徑段與障礙物距離小于安全距離的個數(shù)；C3為適當(dāng)?shù)恼龜?shù)。

2.3種群的更新與進(jìn)化

在傳統(tǒng)的遺傳算法中，生物遺傳進(jìn)化過程中的優(yōu)勝劣汰是通過選擇適應(yīng)度高的個體模擬的，新生物個體的產(chǎn)生是通過交叉和變異算子模擬的，這3個基本遺傳算子完成種群的進(jìn)化和更新。然而,對于復(fù)雜的海洋環(huán)境，僅采用基本的算子難以規(guī)劃出較優(yōu)的無碰路徑。因此，在傳統(tǒng)的更新與進(jìn)化中加入刪除和插入算子，進(jìn)一步優(yōu)化輸出的路徑。

2.3.1選擇算子

利用傳統(tǒng)遺傳算法中的選擇操作，以種群中每條路徑的適應(yīng)度值為概率，遍歷每個個體的適應(yīng)度值，選擇概率大的第i個個體進(jìn)入下一代。

2.3.2交叉算子

采用單點(diǎn)交叉法進(jìn)行個體的交叉，如選取式(7)中的2條路徑，將按一定概率隨機(jī)選擇的種群中第i個個體的第x個路徑點(diǎn)nix(xix,yix)與第j個個體的第x個路徑點(diǎn)njy(xjy,yjy)替換，重新組合成新的路徑(見式(8))。

(7)

(8)

2.3.3變異算子

為避免過早地陷入局部收斂，按一定概率隨機(jī)選擇第i個個體上的第x個路徑點(diǎn)nix(xix,yix)進(jìn)行變異，即

ni1(xi1,yi1)…nix-1(xix-1,yix-1)…nix(xix,yix)…

nix+1(xix+1,yix+1)…nili(xili,yili)

(9)

將第x個路徑點(diǎn)nix(xix,yix)的上一個路徑點(diǎn)nix-1(xix-1,yix-1)和下一個路徑點(diǎn)nix+1(xix+1,yix+1)作為可變異范圍，采用與初始化種群生成新路徑點(diǎn)方法相同的方法，隨機(jī)搜索一個自由柵格作為變異后的新路徑點(diǎn)。

2.3.4刪除算子

刪除操作可減小個體的路徑長度，增強(qiáng)路徑的可行性，提高算法搜索效率。2種刪除算子見圖4。

a) 刪除算子1

b) 刪除算子2

在圖4a中，個體路徑中的路徑點(diǎn)所在的2條路徑段都是不可行的或其中一條路徑不可行，刪除該路徑點(diǎn)之后，連接相鄰的路徑點(diǎn)，變成可行路徑段；在圖4b中，個體路徑附近無障礙物卻出現(xiàn)轉(zhuǎn)彎的情況,刪除序號為44的路徑點(diǎn)之后，連接相鄰的路徑點(diǎn)40和74，生成新的路徑段,若其是可行的，則刪除該路徑點(diǎn)，否則不作操作。

2.3.5插入算子

當(dāng)海洋環(huán)境中的障礙物較多時，出現(xiàn)不可行路段的可能性較大，且刪除操作不能完全修復(fù)不可行路徑，插入操作可進(jìn)一步對個體中的不可行路段進(jìn)行修復(fù)，從而快速生成有效的可行路徑(見圖5)。

圖5 插入算子示意

在圖5中，當(dāng)有路徑段穿過障礙物時，選擇一個自由柵格作為新的路徑點(diǎn)插入后,可使路徑變成可行路徑，從而修復(fù)該路徑。

3 試驗(yàn)驗(yàn)證及結(jié)果分析

3.1構(gòu)建海洋環(huán)境

在VS 2010和SQL SERVER 2008環(huán)境下完成基于電子海圖柵格化的USV全局路徑規(guī)劃算法驗(yàn)證試驗(yàn)。海圖中的物標(biāo)數(shù)據(jù)信息由以下2個電子海圖文件中的數(shù)據(jù)共同組成。

1) C1100103.000海圖的經(jīng)度范圍為116.5°W～133.0°E,緯度范圍為21.5°S～41.5°N，編圖比例尺為1∶2 300 000，坐標(biāo)乘數(shù)因子為10 000 000，水深乘數(shù)因子為10。

2) CN110011.000海圖的經(jīng)度范圍為117.000 413°W～127.150 630°E,緯度范圍為35.300 066°S～41.000 202°N，編圖比例尺為1∶1 000 000，坐標(biāo)乘數(shù)因子為100 000，水深乘數(shù)因子為10。緯度范圍35.846 786°N～39.846 786°N和經(jīng)度范圍117.474 388°E～125.474 388°E所包含的區(qū)域設(shè)為海洋環(huán)境建模空間，涵蓋陸地、島嶼、海床和等深線等基本的礙航物信息。根據(jù)USV工作空間范圍建立基于電子海圖柵格化的海洋環(huán)境模型(見圖6)。

在圖6中，等深面范圍為-10～10 m，等深線范圍為10 m，安全距離為10 m，USV工作空間的范圍設(shè)定為從起點(diǎn)(120.171 013°E，38.621 632°N)到終點(diǎn)(123.532 463°E，37.019 115°N)的數(shù)據(jù)信息，搜索數(shù)據(jù)庫生成以該起點(diǎn)和終點(diǎn)為中心點(diǎn)、經(jīng)度范圍為4°(120.187 309°E～124.187 309°E)、緯度范圍為2°(38.219 494°N～40.219 494°N)的海洋環(huán)境(如圖6a所示)，選擇柵格為100×200，柵格化后建立的海洋環(huán)境模型如圖6b所示。

a) 電子海圖海洋環(huán)境

b) 柵格化后的海洋環(huán)境

3.2試驗(yàn)驗(yàn)證方法

利用軟件VS 2010編程實(shí)現(xiàn)基于電子海圖的無人艇全局路徑規(guī)劃軟件程序流程(見圖7)。試驗(yàn)中實(shí)現(xiàn)的主要功能有：設(shè)置無人艇和電子海圖顯示的環(huán)境信息；根據(jù)無人艇的參數(shù)信息獲取并顯示電子海圖數(shù)據(jù)庫中礙航物的物標(biāo)空間幾何信息，生成無人艇航行的海洋環(huán)境空間；完成海洋環(huán)境模型的建立，設(shè)置柵格大小，柵格化電子海圖；啟動遺傳算法程序，完成路徑規(guī)劃任務(wù)。

圖7 全局路徑規(guī)劃程序流程圖

圖7中，進(jìn)行具體的無人水面艇全局路徑規(guī)劃的步驟為：

1) 設(shè)置無人艇起始點(diǎn)和目標(biāo)點(diǎn)等相關(guān)信息及電子海圖顯示參數(shù)等。

2) 搜索電子海圖數(shù)據(jù)庫，查詢礙航物數(shù)據(jù)表，生成無人艇航行的海洋環(huán)境信息并顯示。

3) 設(shè)置柵格大小，對電子海圖進(jìn)行柵格化處理，生成電子海圖柵格圖。

4) 設(shè)置遺傳算法的初始化參數(shù)，包括迭代次數(shù)、種群規(guī)模、交叉概率Pc和變異概率Pm等。

5) 初始化種群，產(chǎn)生初始路徑，進(jìn)入遺傳算法迭代循環(huán)。

6) 從無人艇的安全性、路徑的光滑度和路徑長度等3個方面綜合評價種群個體的適應(yīng)度，計算適應(yīng)度函數(shù)值。

7) 對種群中的路徑進(jìn)行選擇、交叉、變異、刪除和插入等進(jìn)化操作，優(yōu)化種群。

8) 迭代完成，輸出全局路徑規(guī)劃的結(jié)果。

3.3試驗(yàn)結(jié)果分析

在試驗(yàn)中，設(shè)置USV的起點(diǎn)位置為(123.131 073°E，39.236 572°N)，終點(diǎn)位置為(121.243 544°E，39.202 417°N)，USV的初始航向?yàn)?50°，航速為8 kn，遺傳算法初始化種群選用20個個體，終止條件為迭代100代，個體編碼采用變長度編碼方式初始種群，個體路徑段數(shù)不固定，交叉概率為0.7，變異概率為0.3，以安全、光滑和路徑最短為尋優(yōu)目標(biāo)，采用拐點(diǎn)盡量少的原則對路徑進(jìn)行優(yōu)化，完成參數(shù)設(shè)定。

基于柵格法建立的海洋環(huán)境模型見圖8，規(guī)劃的路徑點(diǎn)坐標(biāo)見表1。

圖8 基于柵格法建立的海洋環(huán)境模型

路徑節(jié)點(diǎn)節(jié)點(diǎn)柵格序號經(jīng)度/(°)E緯度/(°)N開始節(jié)點(diǎn)09947123．13107339．236572節(jié)點(diǎn)112940122．99730738．929493節(jié)點(diǎn)216061121．41731338．609493節(jié)點(diǎn)316042121．03730838．609493節(jié)點(diǎn)413433120．85730738．869495節(jié)點(diǎn)511834120．87731239．029495終止節(jié)點(diǎn)610052121．24354639．202415

表2為圖8中的路徑在算法進(jìn)化過程中種群適應(yīng)度函數(shù)值的變化。當(dāng)進(jìn)化代數(shù)接近100代時，種群路徑的平均適應(yīng)度函數(shù)值和最優(yōu)路徑的適應(yīng)度函數(shù)值幾乎不再變化，且隨著進(jìn)化代數(shù)的增加，種群的平均適應(yīng)度函數(shù)值越來越趨于最優(yōu)值。

表2 適應(yīng)度函數(shù)值變化

由試驗(yàn)結(jié)果可知，在實(shí)際的海洋環(huán)境下，即使是在礙航物較多的工作空間中，通過使用柵格法將電子海圖轉(zhuǎn)化為柵格地圖，可簡化USV的工作環(huán)境，利用改進(jìn)遺傳算法進(jìn)行路徑搜索，最終輸出的路徑也能準(zhǔn)確地避開海洋環(huán)境中的礙航物，保證無人艇航行時的安全性；同時，在沒有礙航物的可航行區(qū)域，規(guī)劃出的無人艇航行路徑呈直線形狀，滿足路徑最短的要求。此外，規(guī)劃出的路徑的拐點(diǎn)較少且拐角均為鈍角，保證了路徑的光滑性。最終的試驗(yàn)結(jié)果驗(yàn)證了算法的可行性和有效性。

4 結(jié)束語

本文將電子海圖數(shù)據(jù)與智能避碰決策方法相結(jié)合，提出一種基于電子海圖柵格化的改進(jìn)遺傳算法無人艇全局路徑規(guī)劃方法。

1) 利用電子海圖提供的數(shù)字化海洋環(huán)境地理信息數(shù)據(jù)對USV工作空間中的海洋環(huán)境進(jìn)行準(zhǔn)確描述，并以大小相等的柵格將環(huán)境信息量化成具有一定分辨率的柵格網(wǎng)，建立USV工作空間的環(huán)境模型，減小全局路徑規(guī)劃中的環(huán)境模型空間開銷。

2) 在能反映真實(shí)海洋環(huán)境信息的電子海圖柵格化的環(huán)境模型中設(shè)計一種啟發(fā)式隨機(jī)初始化種群方法，根據(jù)自主、安全航行等要求，將經(jīng)濟(jì)性、安全性和光滑性等3個評價因子加入到適應(yīng)度函數(shù)中，并在選擇、交叉和變異等傳統(tǒng)進(jìn)化操作的基礎(chǔ)上結(jié)合插入操作及刪除操作對種群進(jìn)行優(yōu)化。

3) 在VC 2010平臺上編寫全局路徑規(guī)劃算法的程序。

試驗(yàn)結(jié)果表明，基于電子海圖柵格化的改進(jìn)遺傳算法USV全局路徑規(guī)劃方法能加快路徑規(guī)劃的收斂速度，提高路徑優(yōu)化的效率，是一種合理、有效的USV路徑搜索算法。

[1] YAN Rujian, PANG Shuo, SUN Hanbing, et al. Development and Missions of Unmanned Surface Vehicle[J]. Journal of Marine Science and Application, 2010,9(4):451-457.

[2] CAMPBELL S, NAEEM W, IRWIN GW. A Review on Improving the Autonomy of Unmanned Surface Vehicles Through Intelligent Collision Avoidance Manoeuvres[J]. Annual Reviews in Control, 2012,36(2):267-283.

[3] YANG JM, TSENG CM, TSENG PS. Path Planning on Satellite Images for Unmanned Surface Vehicles[J]. International Journal of Naval Architecture and Ocean Engineering, 2015,7(1):87-99.

[4] SONG L. Path Planning Research of Unmanned Surface Vehicle Based on Electronic Chart[J]. Journal of Information and Computational Science, 2014,11(17): 6245-6254.

[5] KIM H, PARK B, MYUNG H. Curvature Path Planning with High Resolution Graph for Unmanned Surface Vehicle[M]. Berlin: Springer Berlin Heidelberg, 2013：147-154.

[6] KIM H, KIM D, SHIN JU, et al. Angular Rate-Constrained Path Planning Algorithm for Unmanned Surface Vehicles[J]. Ocean Engineering, 2014,84(4):37-44.

[7] SONG CH. Global Path Planning Method for USV System Based on Improved Ant Colony Algorithm[J]. Applied Mechanics and Materials, 2014,568:785-788.

[8] 莊佳園, 萬磊, 廖煜雷, 等. 基于電子海圖的水面無人艇全局路徑規(guī)劃研究[J]. 計算機(jī)科學(xué), 2011,38(9):211-214.

[9] 饒森. 水面無人艇的全局路徑規(guī)劃技術(shù)研究[D]. 哈爾濱:哈爾濱工程大學(xué), 2007.

[10] 劉建. 水面無人艇路徑規(guī)劃技術(shù)的研究[D]. 鎮(zhèn)江:江蘇科技大學(xué), 2014.

[11] 劉佳男. 基于進(jìn)化遺傳算法的無人艇避碰系統(tǒng)研究[D]. 大連:大連海事大學(xué), 2015.

[12] 張玉奎. 水面無人艇路徑規(guī)劃技術(shù)研究[D]. 哈爾濱:哈爾濱工程大學(xué), 2008.

[13] 盧艷爽. 水面無人艇路徑規(guī)劃算法研究[D]. 哈爾濱:哈爾濱工程大學(xué), 2010.

[14] 王錦川. 自主式水面航行器導(dǎo)航與制導(dǎo)算法的研究[D]. 大連:大連海事大學(xué), 2014.

[15] 陳超, 唐堅. 基于可視圖法的水面無人艇路徑規(guī)劃設(shè)計[J]. 中國造船, 2013(1):129-135.

[16] 馬文耀, 吳兆麟, 楊家軒, 等. 人工魚群算法的避碰路徑規(guī)劃決策支持[J]. 中國航海, 2014,37(3):63-67.

GlobalPathPlanningforUnmannedSurfaceVehicleBasedonGridModelofElectronicChart

FANYunsheng1，ZHAOYongsheng1，SHILinlong1,2，ZHANGYue1

(1. School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China; 2. Shanghai Ship & Shipping Research Institute, Shanghai 200135, China)

U664.82

A

2016-11-24

國家自然科學(xué)基金(61374114,51609033);遼寧省自然科學(xué)基金(2015020022);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資金(3132016022)

范云生(1981—)，男，遼寧丹東人，講師，碩士生導(dǎo)師，博士，從事船舶智能控制理論與應(yīng)用、無人系統(tǒng)測控技術(shù)等研究。 E-mail:yunsheng@dlmu.edu.cn

1000-4653(2017)01-0047-06