無人船艇航線自動生成研究現狀及展望

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

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

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

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

1 無人船艇航線自動生成研究現狀

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

隨著船舶智能化的發展，國內外專家學者開始嘗試將智能算法應用到航線設計中，探索航線自動生成問題，取得了卓有成效的研究成果。

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

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

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

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

1.2 基于雷達圖像的航線自動規劃

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

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

1.3 基于廣域圖像的航線自動規劃

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

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

1.4 基于模擬環境的航線自動規劃

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

1.5 局部路徑規劃研究

無人船艇的局部路徑規劃是指無人船艇在航行過程中遇到其他船舶、漂浮物等障礙物時，通過采取適當的避碰行動駛離原規劃路徑避免危險而實時規劃的路徑。文獻[45]～文獻[48]等對無人艇的局部路徑規劃問題進行研究，由于無人船艇的局部路徑規劃問題屬于智能避碰的研究范疇，因此不對此進行詳細綜述。

2 環境建模方法

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

1) 建立航行水域環境模型。

2) 搭建好的環境模型中依據優化目標根據設置的起點和終點搜尋最短路徑。

第1步建立環境模型的主要目的是將真實的航行環境通過適當的方式轉化為適用于航線規劃的簡化模型，一般是從圖形學角度出發，其中最重要的是障礙物的表示方法。根據障礙物表示方法的不同可分為基于柵格化模型的建模方法和基于障礙物包圍盒模型的建模方法兩類。

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

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

3 最短路徑搜索算法

無人船艇航線自動生成主要步驟中的第2步是在搭建好的環境模型中，依據優化目標，采用啟發式搜索算法、仿生優化算法等搜尋最短路徑。

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

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

4 研究總結與展望

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

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

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

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

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

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

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

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

5 結束語

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