張樹凱, 劉正江, 蔡 垚,4, 史國友, 梁偉珍2,

(1.上海海事大學(xué) 商船學(xué)院， 上海 201306； 2.招商局集團 招商蛇口郵輪事業(yè)部， 深圳 518067；3.大連海事大學(xué) 航海學(xué)院， 遼寧 大連 116026； 4.交通運輸部 政策研究室， 北京 100736)

無人船艇可承擔(dān)大范圍、長時間和低成本的海洋作業(yè)任務(wù)。2007年美國海軍就發(fā)布了《海軍無人艇計劃》。[1]2012年9月，歐盟委員會資助挪威海事技術(shù)研究所、查爾默斯大學(xué)等8家單位聯(lián)合開展名為“MUNIN”[2]的研究項目，該項目以200 m散貨船為研究對象，旨在提出無人駕駛船舶的設(shè)計概念并搭建自主航行系統(tǒng)框架。挪威航運巨頭威爾森(Wilhelmsen)和康士伯(Kongsberg)于2018年8月投入運營全球首家無人船航運公司“Massterly”，業(yè)務(wù)涵蓋設(shè)計、開發(fā)、控制系統(tǒng)、物流服務(wù)和船舶運營等方面。[3]

無人船艇在水面執(zhí)行任務(wù)時面臨著許多獨特的挑戰(zhàn)，其研究屬于多學(xué)科交叉、多領(lǐng)域融合的綜合項目，包括艇型設(shè)計、水面物標(biāo)探測識別、自動避碰避障、運動控制、路徑規(guī)劃等多個方面[4]，近年來許多專家學(xué)者取得了卓有成效的研究成果。全自主型無人船艇是其發(fā)展的終極目標(biāo)，要求其能夠自主完成任務(wù)，航線自動生成是自主作業(yè)研究中的重要組成部分和關(guān)鍵技術(shù)之一。本文先闡述國內(nèi)外無人船艇航線自動生成的研究現(xiàn)狀，然后對其中關(guān)鍵的兩個步驟分別加以小結(jié)，并在此基礎(chǔ)上，對未來的研究方向予以展望。

1 無人船艇航線自動生成研究現(xiàn)狀

傳統(tǒng)的航線設(shè)計主要依靠人工分析紙質(zhì)海圖，通過查閱《世界大洋航路》《航路設(shè)計圖》《航路指南》等航海圖書資料中的航路和航法，手工繪制航線。這種傳統(tǒng)的航線設(shè)計方法不僅效率低，且航線的質(zhì)量主要依靠航海人員的業(yè)務(wù)水平和工作態(tài)度。

隨著船舶智能化的發(fā)展，國內(nèi)外專家學(xué)者開始嘗試將智能算法應(yīng)用到航線設(shè)計中，探索航線自動生成問題，取得了卓有成效的研究成果。

無人船艇的航線自動生成是指基于任務(wù)要求，在一定的約束條件下，按照安全性、經(jīng)濟性的原則自動地規(guī)劃從起點到終點的無障礙路徑。目前，航線自動規(guī)劃的平臺一般基于電子海圖、雷達圖像以及通過衛(wèi)星等拍攝的大范圍水域照片和熱敏圖像，采用的算法包括Dijkstra算法、A*算法等啟發(fā)式搜索算法、蟻群算法、遺傳算法等仿生優(yōu)化算法，以及可視圖法、人工勢場法、模擬退火算法等。

1.1 基于電子海圖平臺的航線自動規(guī)劃

在電子海圖顯示與信息系統(tǒng)(Electronic Chart Display and Information Systern,ECDIS)已廣泛應(yīng)用的今天，ECDIS中蘊含的豐富數(shù)據(jù)成為航線自動生成研究的重要數(shù)據(jù)源之一。[5]基于ECDIS平臺的航線自動規(guī)劃首先從電子海圖中提取岸線、水深等數(shù)據(jù)，將ECDIS劃分為可航和不可航水域，其中：陸地、島嶼等為不可航水域，滿足安全水深要求的為可航水域；然后在可航水域中采用智能搜索算法搜索最短路徑。

文獻[6]采用二維柵格化模型構(gòu)建海洋環(huán)境，將海圖離散化為小型網(wǎng)格，并根據(jù)水深等條件將每個網(wǎng)格定義為可航或不可航，然后采用雙懲罰函數(shù)和距離函數(shù)對航跡長度、路徑平滑度等進行處理，提出一種基于遺傳算法的多目標(biāo)優(yōu)化路徑規(guī)劃算法。類似地，文獻[7]綜合考慮安全性約束、終點姿態(tài)約束等定義路徑規(guī)劃公式，并采用遺傳算法設(shè)計無人艇路徑規(guī)劃求解問題。文獻[8]和文獻[9]提出一種動態(tài)網(wǎng)格模型，將方格屬性分為完全可航、不完全可航和完全不可航，采用8字節(jié)表示每個方格與其鄰接的8個方格之間的連通性，然后基于二分查找法進行路徑尋優(yōu)。文獻[10]以“航行帶”寬度為單位進行海圖網(wǎng)格的劃分，以避免生成的航線穿越危險區(qū)域，然后采用蟻群算法在可航網(wǎng)格中搜索最短航線。文獻[11]根據(jù)海圖比例尺的大小確定網(wǎng)格尺寸的大小，并采用蟻群算法和遺傳算法組合的方法在可航網(wǎng)格中搜索最短航線。文獻[12]依據(jù)S-57的規(guī)定對障礙物邊緣進行擴充并采用柵格表示障礙區(qū)和可航區(qū)的環(huán)境信息。文獻[13]將分析水域網(wǎng)格化，通過疊加船舶航跡統(tǒng)計網(wǎng)格內(nèi)軌跡點頻數(shù)，然后采用A*算法規(guī)劃航線。文獻[14]和文獻[15]先采用柵格劃分海域并識別礙航物所在的方格，然后采用8鄰域邊界追蹤法提取礙航物包圍盒，之后采用Elasticity算法在由障礙物包圍盒和可航水域組成的環(huán)境模型中搜尋最短路徑，在此基礎(chǔ)上，文獻[16]和文獻[17]基于天氣和海況因素等海域模型構(gòu)建限制搜索區(qū)域，通過改進Z3-2算法快速求取多邊形凸殼建立簡化的環(huán)境模型。文獻[18]～文獻[20]依據(jù)電子海圖數(shù)據(jù)將航行環(huán)境分為礙航區(qū)、緩沖區(qū)和安全區(qū)域，然后采用繞行礙航區(qū)的航路二叉樹方法研究最短航線的生成問題。在此基礎(chǔ)上，文獻[21]和文獻[22]將海域潮位模型融入海圖靜態(tài)水深，構(gòu)建基于瞬時水深模型的礙航區(qū)動態(tài)提取方法。文獻[23]和文獻[24]考慮無人艇的操縱性和航行時的碰撞等風(fēng)險采用柵格法和Voronoi圖法進行路徑規(guī)劃。文獻[25]通過柵格動態(tài)細化電子海圖的方式建立環(huán)境模型，然后采用改進勢場法搜索最優(yōu)路徑。文獻[26]采用動態(tài)柵格法建立環(huán)境模型，采用Dijkstra算法進行路徑規(guī)劃。文獻[27]利用分層和激活值相結(jié)合、分層和遺傳算法相結(jié)合的方法進行路徑規(guī)劃。文獻[28]基于柵格化的光柵電子海圖采用迷宮算法研究航路優(yōu)化問題。文獻[29]通過增加轉(zhuǎn)向次數(shù)的懲罰因子對這一算法進行改進。

1.2 基于雷達圖像的航線自動規(guī)劃

文獻[30]～文獻[32]基于雷達圖像對無人船艇路徑規(guī)劃問題進行研究，對環(huán)境進行建模時利用自適應(yīng)閾值法和邊緣保持的去噪平滑算法對雷達圖像進行處理，從而辨識出可航水域。

文獻[30]以湖上和海上的典型雷達圖像為環(huán)境模型，通過引入距離啟發(fā)信息和限定轉(zhuǎn)角以兼顧路徑最短和無人艇的操控性能，采用改進的快速擴展隨機樹算法進行路徑規(guī)劃。文獻[31]通過雷達、水下聲吶和多攝像頭構(gòu)建立體視覺系統(tǒng)檢測水面和水下障礙物生成航行水域的障礙物地圖，并采用基于可視圖的A*算法進行路徑規(guī)劃。文獻[32]基于雷達圖像采用Dijkstra算法進行路徑規(guī)劃。

1.3 基于廣域圖像的航線自動規(guī)劃

文獻[33]～文獻[39]基于衛(wèi)星等拍攝的大范圍水域照片或熱敏圖像進行無人船艇航線自動規(guī)劃的研究，對環(huán)境進行建模時采用MATLAB等工具將衛(wèi)星照片、熱敏圖像轉(zhuǎn)換為黑白二值圖像，其中:陸地、島嶼等不可航水域轉(zhuǎn)換為“黑色”，可航水域轉(zhuǎn)換為“白色”，然后在可航水域中進行路徑規(guī)劃。

文獻[33]基于衛(wèi)星照片采用Dijkstra算法在可航水域中搜尋最短路徑。文獻[34]考慮無人艇動力學(xué)和回轉(zhuǎn)性能方面的限制，提出角度限制下的快速步進方格算法。文獻[35]～文獻[37]同樣采用改進的快速步進方格算法對無人艇的路徑規(guī)劃進行試驗。文獻[38]也考慮了無人艇回轉(zhuǎn)性能的限制，為使規(guī)劃的路徑平滑，提出有限角A*算法并基于衛(wèi)星熱敏圖像進行路徑規(guī)劃試驗。類似地，文獻[39]考慮無人艇轉(zhuǎn)向時的角速率限制提出一種改進的Theta*算法并基于衛(wèi)星照片進行路徑規(guī)劃試驗。

1.4 基于模擬環(huán)境的航線自動規(guī)劃

文獻[40]～文獻[44]在模擬環(huán)境下對無人船艇航線自動規(guī)劃問題進行研究。文獻[40]采用廣義Voronoi圖在模擬環(huán)境下進行航線自動規(guī)劃，并與采用A*算法規(guī)劃的路徑進行性能比較；文獻[41]采用柵格圖模擬無人艇航行環(huán)境，采用蟻群算法搜尋最短路徑；文獻[43]利用遺傳算法和人工勢場法在柵格化的模擬環(huán)境中設(shè)計無人艇路徑規(guī)劃方法；文獻[42]針對人工勢場法存在的目標(biāo)不可達和局部極小值點問題提出一種改進人工勢場算法并在隨機生成障礙物的模擬環(huán)境下進行路徑規(guī)劃試驗，文獻[44]也做了類似研究。

1.5 局部路徑規(guī)劃研究

無人船艇的局部路徑規(guī)劃是指無人船艇在航行過程中遇到其他船舶、漂浮物等障礙物時，通過采取適當(dāng)?shù)谋芘鲂袆玉傠x原規(guī)劃路徑避免危險而實時規(guī)劃的路徑。文獻[45]～文獻[48]等對無人艇的局部路徑規(guī)劃問題進行研究，由于無人船艇的局部路徑規(guī)劃問題屬于智能避碰的研究范疇，因此不對此進行詳細綜述。

2 環(huán)境建模方法

通過對國內(nèi)外無人船艇航線自動生成研究現(xiàn)狀綜述可看出，無論基于何種平臺，航線自動生成方法大致遵循兩個基本步驟：

1) 建立航行水域環(huán)境模型。

2) 搭建好的環(huán)境模型中依據(jù)優(yōu)化目標(biāo)根據(jù)設(shè)置的起點和終點搜尋最短路徑。

第1步建立環(huán)境模型的主要目的是將真實的航行環(huán)境通過適當(dāng)?shù)姆绞睫D(zhuǎn)化為適用于航線規(guī)劃的簡化模型，一般是從圖形學(xué)角度出發(fā)，其中最重要的是障礙物的表示方法。根據(jù)障礙物表示方法的不同可分為基于柵格化模型的建模方法和基于障礙物包圍盒模型的建模方法兩類。

(1) 基于柵格化模型的環(huán)境建模方法將ECDIS、雷達圖像、衛(wèi)星熱敏圖像等進行細粒度的網(wǎng)格劃分，從而將空間分割成可航行的自由空間和不可航行的障礙物空間。例如，文獻[6]～文獻[13]采用正方形的網(wǎng)格對電子海圖進行柵格化。針對網(wǎng)格大小的問題，文獻[10]以“航行帶”寬度為單位，文獻[11]根據(jù)海圖比例尺的大小確定網(wǎng)格尺寸的大小，文獻[12]在采用柵格表示環(huán)境信息時對障礙物區(qū)域的邊緣進行擴充并息。

(2) 基于障礙物包圍盒模型的環(huán)境建模方法將航行環(huán)境中由復(fù)雜多邊形表示的障礙物簡化為可包圍該障礙物的包圍盒，例如包圍圓、包圍凸多邊形等。在簡化的過程中，為后續(xù)路徑尋優(yōu)的方便，一般將船舶簡化為一個質(zhì)點，同時將障航物的邊界依據(jù)船舶參數(shù)進行膨脹處理。簡化后的障礙物在方便求取切線的同時減少碰撞檢測次數(shù)，有效提高路徑尋優(yōu)效率。文獻[49]和文獻[50]將島礁、沉船等障礙物采用最大包含圓形表示。文獻[51]采用最小凸多邊形包圍盒表示障礙物，創(chuàng)新之處在于通過限定搜索區(qū)域減少障礙物數(shù)量。文獻[52]也通過建立安全區(qū)的方法減小搜索范圍、提高效率，然后采用最小包圍圓表示礙航物。除考慮陸地、島礁等固定障礙物外，文獻[16]和文獻[17]綜合考慮天氣和海況因素等海域模型提取潛在的礙航區(qū)，構(gòu)建由多邊形凸殼表示的環(huán)境模型。文獻[21]和文獻[22]綜合考慮海圖水深和潮位模型，構(gòu)建基于瞬時水深模型的礙航區(qū)動態(tài)提取方法。

3 最短路徑搜索算法

無人船艇航線自動生成主要步驟中的第2步是在搭建好的環(huán)境模型中，依據(jù)優(yōu)化目標(biāo)，采用啟發(fā)式搜索算法、仿生優(yōu)化算法等搜尋最短路徑。

在基于柵格化環(huán)境建模的研究中，文獻[28]和文獻[29]通過改進的迷宮算法進行最優(yōu)航線的搜索，但是由于該搜索算法基于單位格點進行逐步搜索，因此航線可能不是最短的。文獻[8]～文獻[13]采用Dijkstra算法、A*算法、二分法、蟻群算法、遺傳算法等進行最短航線搜索，但隨著海域的增大，一是網(wǎng)格的數(shù)量以平方級迅速增長，計算量迅速增大，二是隨著海域的增大和復(fù)雜化，岸線的邊緣檢測與方格可航性的判定計算量也隨之增大，效率明顯下降。

在基于障礙物包圍盒方法進行環(huán)境建模的研究中，文獻[14]～文獻[22],文獻[49]～文獻[54]通過求取礙航物包圍盒之間的公切線，然后采用Dijkstra算法、蟻群算法、遺傳算法等在所有公切線中搜索最短航線；或者通過求取繞行礙航物多邊形區(qū)的左、右子結(jié)點建立航路子二叉樹，然后通過遍歷航路二叉樹的方法搜索最短航線。這兩種方法在小范圍海域時，由于礙航物的數(shù)量較少，礙航物的包圍盒及其公切線、航路二叉樹的求取工作量相對較少，具有較好的適用性；但當(dāng)面向全球大范圍水域的航線自動生成時，隨著礙航物數(shù)量的增加和形狀的復(fù)雜化，求取礙航物包圍盒和其公切線、航路二叉樹的計算量急劇增大，算法的效率也隨之下降。

4 研究總結(jié)與展望

現(xiàn)階段的航線自動生成方法研究模式可大致概括為：將電子海圖或從雷達、衛(wèi)星獲取的圖像進行柵格化或二值化閾值處理，將處理后的電子海圖或圖像分為可航和不可航水域，然后在可航水域中采用智能搜索算法(如Dijkstra、A*算法等)、航路二叉樹法、人工勢場法、可視圖法等搜索從指定起點到終點的最短路徑。

隨著太陽能、風(fēng)能等清潔能源作為無人船艇的動力驅(qū)動源，無人船艇的續(xù)航能力大大增強，且隨著船舶智能化水平的不斷提高，大型無人駕駛船舶也逐步有了實現(xiàn)的可能。因此，從宏觀角度出發(fā)面向大范圍水域且符合航海實際的航線自動生成方法是亟待研究的一個重要問題，現(xiàn)有的技術(shù)和手段仍需關(guān)注以下問題：

1) 傳統(tǒng)的面向小范圍水域的航線自動生成方法具有一定的局限性，需補充從宏觀角度出發(fā)面向大范圍水域的航線自動生成方法。傳統(tǒng)的航線自動生成方法在進行可行性驗證時都是面向小范圍的水域，但是，隨著海域的增大，在面向全球海域范圍時，將電子海圖、衛(wèi)星熱敏圖像等進行柵格化方法的網(wǎng)格數(shù)量以平方級迅速增長且岸線的邊緣檢測與方格可航性的判定計算量也隨之增大，效率明顯下降；通過求取障礙物包圍盒和包圍盒公切線、航路二叉樹的方法，隨著礙航物數(shù)量的增加和形狀的復(fù)雜化，計算量也急劇增大，算法的效率也隨之下降。

隨著無人船艇研發(fā)技術(shù)的不斷提升，船舶的尺度更大、續(xù)航能力更強和安全性要求更高的無人駕駛船舶正逐步成為可能。因此，從提高算法效率和符合無人駕駛船舶發(fā)展趨勢的角度出發(fā)，必須要探索一種從宏觀角度出發(fā)適用于全球海域范圍的高效航線自動生成方法。

2) 傳統(tǒng)的航線自動生成方法忽視了在航海實踐中必須遵守的航線設(shè)計原則和航行規(guī)則，需探索基于海量船舶歷史軌跡數(shù)據(jù)和數(shù)據(jù)驅(qū)動技術(shù)的航線自動生成方法。傳統(tǒng)的航線自動生成方法主要基于電子海圖平臺、遙感圖像等，通過柵格化方法或提取障礙物包圍盒的方法識別出可航水域和不可航區(qū)域，然后在可航水域中采用智能搜索算法尋找出從指定起點到終點的最短航線。在該模式下生成的“最佳航線”僅是計算機圖形學(xué)角度下的最佳航線，但理論分析的結(jié)果和實際應(yīng)用之間還存在一定差距。例如，采用智能搜索算法提取的航線無法智能識別分道通航水域和推薦交通流方向等國際海事組織規(guī)定的需要特別注意的航路或航道，從而造成在這些地區(qū)無法按照規(guī)則行駛。

船舶軌跡數(shù)據(jù)中存儲豐富的航行相關(guān)信息是真實航行情況的客觀反應(yīng)，如果能夠充分地分析、挖掘這些信息，從已被實際航行證實可行的歷史軌跡數(shù)據(jù)中提取出航路相關(guān)信息，則可為航線自動生成提供重要的借鑒和參考，同時，這也符合航線設(shè)計時“參考他船具體航行經(jīng)驗”的思想。因此，在軌跡數(shù)據(jù)呈現(xiàn)出爆炸性增長趨勢且全球聯(lián)網(wǎng)的船舶軌跡數(shù)據(jù)庫已建立的今天，在數(shù)據(jù)科學(xué)崛起的大背景下，借鑒大數(shù)據(jù)策略和管理分析模式，采用軌跡分析與處理技術(shù)，提出基于數(shù)據(jù)驅(qū)動技術(shù)和海量船舶歷史軌跡數(shù)據(jù)、且符合航海實際的航線自動生成方法勢在必行。

3) 傳統(tǒng)的航線自動生成方法忽略了航線安全檢測環(huán)節(jié)，需綜合考慮宏觀交通流特征、船舶運動參數(shù)以及風(fēng)浪流作用下的船舶漂移量，建立具有一定寬度的“航線領(lǐng)域”模型，并基于電子海圖數(shù)據(jù)對航線所在領(lǐng)域自動進行安全檢測。文獻[55]～文獻[61]基于船舶自動識別系統(tǒng)(Automatic Indentification System，AIS)數(shù)據(jù)對船舶定線制、船舶習(xí)慣航路等問題進行研究，然而，船舶在實際航行中并非嚴(yán)格按照生成的航線行駛，而是會有一定的偏移量，特別是在轉(zhuǎn)彎的時候需要一定的旋回水域，傳統(tǒng)的航線自動生成方法忽略了這一點。

因此，需要綜合考慮航跡帶寬度、交通流特征參數(shù)、船舶自身運動參數(shù)、風(fēng)浪流作用下的漂移量以及偏航極限和航道安全富余寬度等建立“航線領(lǐng)域”模型，然后根據(jù)國際海事組織(International Maritime Organization，IMO)對航線安全檢測的要求，基于國際航道組織(International Hydrographic Organization，IHO) S-63標(biāo)準(zhǔn)的策略結(jié)構(gòu)和工作流程對ECDIS數(shù)據(jù)進行解析，通過提取“航線領(lǐng)域”內(nèi)的水深、障礙物等點、線、面海圖要素進行航線安全檢測，確保自動生成航線的安全性。

5 結(jié)束語

本文對無人船艇航線自動生成方面的國內(nèi)外研究現(xiàn)狀進行系統(tǒng)的梳理與總結(jié)，介紹基于不同平臺的無人船艇航線自動規(guī)劃研究現(xiàn)狀，闡述并分析航線自動生成中的主要步驟。本文還通過總結(jié)現(xiàn)有航線自動生成技術(shù)的研究模式，分析現(xiàn)有方法的不足之處，并對未來的研究方向進行展望，對可行的研究思路提出建議。隨著船舶智能化水平的逐步提高，無人船艇的研發(fā)也在不斷加快，航線自動生成相關(guān)理論和技術(shù)也將逐步提高、完善，為工業(yè)化應(yīng)用奠定基礎(chǔ)。