基于ECDIS的航線自動規劃算法設計

，,

(1.中船航海科技有限責任公司,北京 100070；2.北京瑞致泰華科技有限公司,北京 100083)

長期以來，航線規劃設計是根據任務需求，在紙質或電子海圖上，人工判讀海圖內容，評估海圖要素，手工擬定計劃航線[1]。該方法不但存在航線設計耗時長、設計結果嚴重依賴個人經驗、自動化程度低等問題。而且海上環境復雜多變，設計航線時容易出錯，尤其是在不存在歷史航線海域或缺少航行經驗的海域，航線設計難度很大[2]。

目前市場部分電子海圖系統已經初具航線輔助設計能力[3]，可在手動規劃航線后進行航線評估，對航線及附近進行危險物檢測并給出報警[4-5]，但未有航線自動規劃及決策功能。針對這一問題，提出基于ECDIS的航線自動規劃方法。利用計算機取代傳統的手工航線規劃，以期降低航海作業人員的工作強度，提高航線設計的效率和質量，增強航行的安全性和經濟性。

1 航線自動規劃算法流程

提出的航線自動規劃方法是指在航線規劃的工作中,航海人員只需設定出發港和目的港，該方法便可自動規劃出一條安全可行的航路。其規劃過程主要分兩步：一是進行海洋環境建模，即分析處理電子海圖中與航行安全相關的各項數據[6]，并建立航路規劃所需的統一數據要素；二是基于海洋環境模型，考慮船舶特性情況下進行最優尋路，尋找到一條航程最短路線。計算流程見圖1。

圖1 自動航線規劃流程

2 海洋環境模型搭建

2.1 礙航區提取

2.1.1 礙航區劃定

在提取礙航區數據前，需要劃定電子海圖中需提取的海圖數量和礙航物類別。

對于海圖數量，認為在起始點和目標點經緯度下大圓連接線所經過的所有不同比例尺海圖均為需提取的海圖。對于礙航物類別，使用IHO S-52[7]約定的強制礙航區和可選礙航區。其中強制礙航區主要包括深度范圍、疏浚區、浮船塢、報廢船、陸地區、浮碼頭、未測區、岸線結構物等；可選礙航區主要包括通航分隔帶、近岸交通區、受限區域、警告區、海上作業區、軍事演習區、海上飛機起降區、潛水艇航道、錨泊區、海水養殖場等，需要用戶根據實際船舶及航行任務狀態事先選定。

在電子海圖中礙航區主要分為面、點兩種。依照S-52中約定的物標范圍劃定礙航區，可以最大程度的保證航行安全。

2.1.2 電子海圖數據提取

礙航區數據提取。提取航線可能跨越多個海圖的所有礙航區，并將其處理為具有經緯度坐標、礙航屬性的點狀值。對于面礙航區的處理，給出周界輪廓的經緯度坐標，并將每點都標識為特定屬性的點礙航物；對于點礙航區，給出周界多邊形緩沖區的經緯度坐標。

水深數據提取。為進一步保證航行安全，除礙航區、緩沖區等船舶不可航行區域，還需提取海圖上的所有水深數據。水深數據分為兩類。第一類為位于礙航區內的水深數據，該類數據不提取。第二類為大洋中散布的水深點，該類數據需要全部提取，由于海圖測繪、制作等過程，可能會出現部分水深點數據不滿足船舶吃水的要求，在航線規劃時需要作為淺水礙航區處理。

2.1.3 礙航區合并

當礙航區、淺水礙航區、點礙航區存在相交或相互包含時，對礙航區進行合并處理。基于安全性考慮，礙航區邊界給出一個緩沖半徑為d的緩沖空間。此外，船舶在實際航行中，由于風浪的影響，總會偏離預定航線一段距離，兩側的偏離距離稱為航道寬度，這里設置航道寬度為緩沖半徑的2倍。緩沖半徑根據特定船舶的實際特性確定，如船型、滿載重量、舵的性能等，一般設定為2 km。采用閔可夫斯基和以及多邊形偏移[8-9]獲得合并后的礙航區。

設2個凸多邊形分別為P、Q，則閔可夫斯基和定義為

P⊕Q={p+q|p∈P,q∈Q}

(1)

對于礙航區，可能存在非凸多邊形情況。當P、Q不是凸多邊形，則可以分解為多個子凸多邊形集合的形式，表示成

(2)

(3)

則每對子凸多邊形的閔可夫斯基和為，那么對于非凸多邊形P,Q，其閔可夫斯基和如下。

P⊕Q=UijSij

(4)

對多邊形P與半徑為r，圓心在P外邊界上的圓盤Br計算閔可夫斯基和P⊕Br，則半徑r即為多邊形P的偏移。

采用閔可夫斯基和對相交的礙航區進行合并，并以緩沖半徑d的偏移進行外擴，則最終得到一個合理安全的礙航區。

2.2 海洋環境建模

由于水深點、礙航區等的數據是一系列分布不規則、散亂的數據點，故采用三角剖分的方式線性擬合海洋地質環境，標識海洋環境的主要特征。

2.2.1 自然鄰域插值

多數海圖所提供的海洋地質環境數據較為稀疏，不能滿足航道寬度、緩沖區等航路規劃要求，故采用自然領域插值法將三角網加密[10]。自然鄰域插值方法自身帶有局部地質特征自適應特性，滿足任意范圍和地域的網格加密。該方法根據插入點最近的節點集進行插值，離插值點越近的節點所占權重越大。根據Delaunay三角網的特性，插值時，在三角網中新增、刪除、移動某個節點只會影響臨近的三角形，對其他各點構成的三角形無影響，不會改變原有海圖中水深、礙航區等的固有特性。

2.2.2 三角網構建

使用Delaunay三角構網法，將所有提取的海洋地質環境坐標點以及插值得到的水深點進行三角剖分，以最近的三點形成三角形，限制各三角形的邊皆不能相交，最后構成一個唯一的三角網[11-12]。用三角網格模型取代規則的柵格模型，對于海洋這種復雜大面積環境，有效的減少了尋路的節點數，從而能夠降低尋路算法的時間復雜度。

3 航線自動規劃算法

Delaunay三角網構建海洋環境模型后，采用改進的A*算法進行尋路，自動建立一條滿足航行評價標準的最優航線。最優航線包括航程最短、時間最少、安全最高等，這里僅考慮航程最短航線，如果要研究其他最優航線，只需變換算法中的某些參數即可。

3.1 算法介紹

A*算法[13]基本思想是設定合適的啟發函數，評估每個節點到目標點的代價，沿著代價小的點繼續擴展直到找到目標點。A*算法也存在著一些不足：在大規模尋路節點多的環境下，A*算法搜索速率大大降低；尋到的最終路徑不夠光滑，轉折點較多。考慮到在海洋環境中，海洋環境遼闊，復雜多變，而船舶在行進時，過多的轉向次數會增加船舶操作上的不便。針對海洋環境、船舶航行特點，在三角網格中進行A*算法尋路，在尋路的同時對搜索到的路徑進行平滑處理，以減少船舶轉彎次數、船舶航行節點數。

3.2 改進的A*算法

改進的A*算法評估函數如下。

F(n)=G(n)+H(n)+λna

(5)

式中：H(n)為啟發式函數，為節點n到目標點的代價，這里采用歐式距離公式；G(n)不再是起始點到第n個節點的距離和，而是每次尋路后同時對路徑進行平滑處理，為起始點到第n個節點的實際最短距離；評估函數最后加入一個懲罰項na，na為尋路時轉向點個數，懲罰因子λ，當轉向節點個數增多時，加大對評估函數的懲罰力度，懲罰因子λ的值由實驗設定，本文取λ=25。

三角網路徑平滑處理算法。

步驟1。初始化i=1，起始航路點S，三角網個數為len。

步驟2。S與第i+1個三角網共同邊的2個節點構成一個掃描扇面α。

步驟3。設第i+1個三角網的第3個節點為P，判斷P點是否在扇面α內。

1)如果P在α內，則移動掃描扇面的一側到P點與第i+2個三角網構成新的掃描扇面，令i=i+1，重復第3步。

2)如果P不在α內，則將距離P點近的節點設為S并標記，令i=i+1，返回到第2步。

步驟4。當i=len時處理結束，將標記過S的節點順序連線即為平滑后的路徑。

3.3 航線自動搜索算法

1)將起始點所在的三角網放在openlist中。

2)重復以下步驟。

①在openlist中查找F值最小的三角網，作為當前三角網。

②把當前三角網移到closelist中。

③對當前三角網相鄰的三角網進行以下步驟。

如果該相鄰三角網已經在closelist中，則繼續檢查下一個相鄰三角網。

如果不在openlist中，則添加到表里，調用三角網路徑平滑處理算法，計算該三角網的G值，保存G值和H值，將該三角網的父節點設為當前三角網。

如果在openlist中，則判斷經由當前三角網到達該相鄰三角網的G值是否小于原來保存的G值，若小于，則設置三角網的父節點為當前三角網，并重新設置該三角網的G值和H值。

④循環結束條件。當目標三角網被加入到openlist或者作為待檢驗節點時，表示路徑被找到，循環結束。

3)從目標點開始沿父節點遍歷，遍歷所得的節點就是最后得到的最優路徑。

4 算法驗證與分析

為了驗證航線自動生成算法的有效性，進行仿真并給出仿真實驗結果。實驗基于真實的海洋數據，開發環境為Visual Studio 2010，運行于PC機，windows系統下。基于德國SevenCs公司開發的EC2007 ECDIS Kernel進行二次開發，其中該ECDIS系統自帶航線輔助功能，可根據經驗航路交通網組合出一條新的航線。

實驗1的仿真結果見圖2，完成起始點位置坐標(16.155 26,113.440 2)到目標點位置坐標(-1.691 93,98.420 02)的航線規劃，該區域由海南省出發，目的地為明打威群島，途徑南海、爪哇海，海洋環境復雜，障礙物較多且分布集中。

圖2 實驗1仿真結果

海圖中，圓圈叉形圖標為獨立礙航點，方形點狀圖標為海上平臺。粗的虛線表示本文的算法自動規劃的一條航線，細的實線表示EC2007 ECDIS中根據歷史經驗航路組合的航線。航路點的坐標表示為緯度、經度，其中負號表示南緯或者西經。

表1為經典航線各航路點坐標，表2為規劃航線各航路點坐標。

表1 實驗1經典航線航路點坐標

表2 實驗1規劃航線航路點坐標

圖3為實驗2仿真結果，起始點位置坐標(41.518 09,143.118 7)到目標點位置坐標(28.023 28,-115.995)的航線規劃，該區域為由日本出發，目的地為墨西哥西北部，途徑菲律賓海、太平洋的大洋航線。該航線航程較長，海洋環境簡單，障礙物稀少。

圖3 實驗2仿真結果

表3為經典航線各航路點坐標，表4為規劃航線各航路點坐標。

表3 實驗2經典航線航路點坐標

表4 實驗2規劃航線航路點坐標

表5為在2種不同的海洋環境下，本算法規劃的航線與EC2007 ECDIS中根據經驗航路交通網組合的航線的比較。

表5 規劃航路與經典航路比較

通過表5可以看出，在航路點個數上，本文提出的算法搜索的航路點更少，尤其是在障礙物少，海洋環境簡單的情況下；在總航程上，本文搜索到的航路要比經典航路總航程短，尤其是在海洋環境復雜，不存在歷史航線，或者航行經驗不足的情況下，本文提出的航線規劃算法可自動規劃出一條安全經濟航線。

5 結論

1)航線自動規劃算法能夠在復雜缺少航行經驗海域規劃出一條安全經濟航線，在航海中具有一定的實用性；并且只需對評估函數的參數進行變換，便可得到其他評價標準的最優航線，具有一定的靈活性。

2)Delaunay三角網模擬海洋環境，準確的構建海洋環境模型是航路自動規劃算法的基礎。

3)本方法用不規則三角網模擬靜態海洋環境，對動態的海洋環境如潮汐、風、海流的影響適應性需進一步研究。