基于ECDIS的航線自動(dòng)規(guī)劃算法設(shè)計(jì)

，,

(1.中船航?？萍加邢挢?zé)任公司,北京 100070；2.北京瑞致泰華科技有限公司,北京 100083)

長(zhǎng)期以來(lái)，航線規(guī)劃設(shè)計(jì)是根據(jù)任務(wù)需求，在紙質(zhì)或電子海圖上，人工判讀海圖內(nèi)容，評(píng)估海圖要素，手工擬定計(jì)劃航線[1]。該方法不但存在航線設(shè)計(jì)耗時(shí)長(zhǎng)、設(shè)計(jì)結(jié)果嚴(yán)重依賴個(gè)人經(jīng)驗(yàn)、自動(dòng)化程度低等問(wèn)題。而且海上環(huán)境復(fù)雜多變，設(shè)計(jì)航線時(shí)容易出錯(cuò)，尤其是在不存在歷史航線海域或缺少航行經(jīng)驗(yàn)的海域，航線設(shè)計(jì)難度很大[2]。

目前市場(chǎng)部分電子海圖系統(tǒng)已經(jīng)初具航線輔助設(shè)計(jì)能力[3]，可在手動(dòng)規(guī)劃航線后進(jìn)行航線評(píng)估，對(duì)航線及附近進(jìn)行危險(xiǎn)物檢測(cè)并給出報(bào)警[4-5]，但未有航線自動(dòng)規(guī)劃及決策功能。針對(duì)這一問(wèn)題，提出基于ECDIS的航線自動(dòng)規(guī)劃方法。利用計(jì)算機(jī)取代傳統(tǒng)的手工航線規(guī)劃，以期降低航海作業(yè)人員的工作強(qiáng)度，提高航線設(shè)計(jì)的效率和質(zhì)量，增強(qiáng)航行的安全性和經(jīng)濟(jì)性。

1 航線自動(dòng)規(guī)劃算法流程

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

圖1 自動(dòng)航線規(guī)劃流程

2 海洋環(huán)境模型搭建

2.1 礙航區(qū)提取

2.1.1 礙航區(qū)劃定

在提取礙航區(qū)數(shù)據(jù)前，需要?jiǎng)澏娮雍D中需提取的海圖數(shù)量和礙航物類別。

對(duì)于海圖數(shù)量，認(rèn)為在起始點(diǎn)和目標(biāo)點(diǎn)經(jīng)緯度下大圓連接線所經(jīng)過(guò)的所有不同比例尺海圖均為需提取的海圖。對(duì)于礙航物類別，使用IHO S-52[7]約定的強(qiáng)制礙航區(qū)和可選礙航區(qū)。其中強(qiáng)制礙航區(qū)主要包括深度范圍、疏浚區(qū)、浮船塢、報(bào)廢船、陸地區(qū)、浮碼頭、未測(cè)區(qū)、岸線結(jié)構(gòu)物等；可選礙航區(qū)主要包括通航分隔帶、近岸交通區(qū)、受限區(qū)域、警告區(qū)、海上作業(yè)區(qū)、軍事演習(xí)區(qū)、海上飛機(jī)起降區(qū)、潛水艇航道、錨泊區(qū)、海水養(yǎng)殖場(chǎng)等，需要用戶根據(jù)實(shí)際船舶及航行任務(wù)狀態(tài)事先選定。

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

2.1.2 電子海圖數(shù)據(jù)提取

礙航區(qū)數(shù)據(jù)提取。提取航線可能跨越多個(gè)海圖的所有礙航區(qū)，并將其處理為具有經(jīng)緯度坐標(biāo)、礙航屬性的點(diǎn)狀值。對(duì)于面礙航區(qū)的處理，給出周界輪廓的經(jīng)緯度坐標(biāo)，并將每點(diǎn)都標(biāo)識(shí)為特定屬性的點(diǎn)礙航物；對(duì)于點(diǎn)礙航區(qū)，給出周界多邊形緩沖區(qū)的經(jīng)緯度坐標(biāo)。

水深數(shù)據(jù)提取。為進(jìn)一步保證航行安全，除礙航區(qū)、緩沖區(qū)等船舶不可航行區(qū)域，還需提取海圖上的所有水深數(shù)據(jù)。水深數(shù)據(jù)分為兩類。第一類為位于礙航區(qū)內(nèi)的水深數(shù)據(jù)，該類數(shù)據(jù)不提取。第二類為大洋中散布的水深點(diǎn)，該類數(shù)據(jù)需要全部提取，由于海圖測(cè)繪、制作等過(guò)程，可能會(huì)出現(xiàn)部分水深點(diǎn)數(shù)據(jù)不滿足船舶吃水的要求，在航線規(guī)劃時(shí)需要作為淺水礙航區(qū)處理。

2.1.3 礙航區(qū)合并

當(dāng)?shù)K航區(qū)、淺水礙航區(qū)、點(diǎn)礙航區(qū)存在相交或相互包含時(shí)，對(duì)礙航區(qū)進(jìn)行合并處理?；诎踩钥紤]，礙航區(qū)邊界給出一個(gè)緩沖半徑為d的緩沖空間。此外，船舶在實(shí)際航行中，由于風(fēng)浪的影響，總會(huì)偏離預(yù)定航線一段距離，兩側(cè)的偏離距離稱為航道寬度，這里設(shè)置航道寬度為緩沖半徑的2倍。緩沖半徑根據(jù)特定船舶的實(shí)際特性確定，如船型、滿載重量、舵的性能等，一般設(shè)定為2 km。采用閔可夫斯基和以及多邊形偏移[8-9]獲得合并后的礙航區(qū)。

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

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

(1)

對(duì)于礙航區(qū)，可能存在非凸多邊形情況。當(dāng)P、Q不是凸多邊形，則可以分解為多個(gè)子凸多邊形集合的形式，表示成

(2)

(3)

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

P⊕Q=UijSij

(4)

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

采用閔可夫斯基和對(duì)相交的礙航區(qū)進(jìn)行合并，并以緩沖半徑d的偏移進(jìn)行外擴(kuò)，則最終得到一個(gè)合理安全的礙航區(qū)。

2.2 海洋環(huán)境建模

由于水深點(diǎn)、礙航區(qū)等的數(shù)據(jù)是一系列分布不規(guī)則、散亂的數(shù)據(jù)點(diǎn)，故采用三角剖分的方式線性擬合海洋地質(zhì)環(huán)境，標(biāo)識(shí)海洋環(huán)境的主要特征。

2.2.1 自然鄰域插值

多數(shù)海圖所提供的海洋地質(zhì)環(huán)境數(shù)據(jù)較為稀疏，不能滿足航道寬度、緩沖區(qū)等航路規(guī)劃要求，故采用自然領(lǐng)域插值法將三角網(wǎng)加密[10]。自然鄰域插值方法自身帶有局部地質(zhì)特征自適應(yīng)特性，滿足任意范圍和地域的網(wǎng)格加密。該方法根據(jù)插入點(diǎn)最近的節(jié)點(diǎn)集進(jìn)行插值，離插值點(diǎn)越近的節(jié)點(diǎn)所占權(quán)重越大。根據(jù)Delaunay三角網(wǎng)的特性，插值時(shí)，在三角網(wǎng)中新增、刪除、移動(dòng)某個(gè)節(jié)點(diǎn)只會(huì)影響臨近的三角形，對(duì)其他各點(diǎn)構(gòu)成的三角形無(wú)影響，不會(huì)改變?cè)泻D中水深、礙航區(qū)等的固有特性。

2.2.2 三角網(wǎng)構(gòu)建

使用Delaunay三角構(gòu)網(wǎng)法，將所有提取的海洋地質(zhì)環(huán)境坐標(biāo)點(diǎn)以及插值得到的水深點(diǎn)進(jìn)行三角剖分，以最近的三點(diǎn)形成三角形，限制各三角形的邊皆不能相交，最后構(gòu)成一個(gè)唯一的三角網(wǎng)[11-12]。用三角網(wǎng)格模型取代規(guī)則的柵格模型，對(duì)于海洋這種復(fù)雜大面積環(huán)境，有效的減少了尋路的節(jié)點(diǎn)數(shù)，從而能夠降低尋路算法的時(shí)間復(fù)雜度。

3 航線自動(dòng)規(guī)劃算法

Delaunay三角網(wǎng)構(gòu)建海洋環(huán)境模型后，采用改進(jìn)的A*算法進(jìn)行尋路，自動(dòng)建立一條滿足航行評(píng)價(jià)標(biāo)準(zhǔn)的最優(yōu)航線。最優(yōu)航線包括航程最短、時(shí)間最少、安全最高等，這里僅考慮航程最短航線，如果要研究其他最優(yōu)航線，只需變換算法中的某些參數(shù)即可。

3.1 算法介紹

A*算法[13]基本思想是設(shè)定合適的啟發(fā)函數(shù)，評(píng)估每個(gè)節(jié)點(diǎn)到目標(biāo)點(diǎn)的代價(jià)，沿著代價(jià)小的點(diǎn)繼續(xù)擴(kuò)展直到找到目標(biāo)點(diǎn)。A*算法也存在著一些不足：在大規(guī)模尋路節(jié)點(diǎn)多的環(huán)境下，A*算法搜索速率大大降低；尋到的最終路徑不夠光滑，轉(zhuǎn)折點(diǎn)較多?？紤]到在海洋環(huán)境中，海洋環(huán)境遼闊，復(fù)雜多變，而船舶在行進(jìn)時(shí)，過(guò)多的轉(zhuǎn)向次數(shù)會(huì)增加船舶操作上的不便。針對(duì)海洋環(huán)境、船舶航行特點(diǎn)，在三角網(wǎng)格中進(jìn)行A*算法尋路，在尋路的同時(shí)對(duì)搜索到的路徑進(jìn)行平滑處理，以減少船舶轉(zhuǎn)彎次數(shù)、船舶航行節(jié)點(diǎn)數(shù)。

3.2 改進(jìn)的A*算法

改進(jìn)的A*算法評(píng)估函數(shù)如下。

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

(5)

式中：H(n)為啟發(fā)式函數(shù)，為節(jié)點(diǎn)n到目標(biāo)點(diǎn)的代價(jià)，這里采用歐式距離公式；G(n)不再是起始點(diǎn)到第n個(gè)節(jié)點(diǎn)的距離和，而是每次尋路后同時(shí)對(duì)路徑進(jìn)行平滑處理，為起始點(diǎn)到第n個(gè)節(jié)點(diǎn)的實(shí)際最短距離；評(píng)估函數(shù)最后加入一個(gè)懲罰項(xiàng)na，na為尋路時(shí)轉(zhuǎn)向點(diǎn)個(gè)數(shù)，懲罰因子λ，當(dāng)轉(zhuǎn)向節(jié)點(diǎn)個(gè)數(shù)增多時(shí)，加大對(duì)評(píng)估函數(shù)的懲罰力度，懲罰因子λ的值由實(shí)驗(yàn)設(shè)定，本文取λ=25。

三角網(wǎng)路徑平滑處理算法。

步驟1。初始化i=1，起始航路點(diǎn)S，三角網(wǎng)個(gè)數(shù)為len。

步驟2。S與第i+1個(gè)三角網(wǎng)共同邊的2個(gè)節(jié)點(diǎn)構(gòu)成一個(gè)掃描扇面α。

步驟3。設(shè)第i+1個(gè)三角網(wǎng)的第3個(gè)節(jié)點(diǎn)為P，判斷P點(diǎn)是否在扇面α內(nèi)。

1)如果P在α內(nèi)，則移動(dòng)掃描扇面的一側(cè)到P點(diǎn)與第i+2個(gè)三角網(wǎng)構(gòu)成新的掃描扇面，令i=i+1，重復(fù)第3步。

2)如果P不在α內(nèi)，則將距離P點(diǎn)近的節(jié)點(diǎn)設(shè)為S并標(biāo)記，令i=i+1，返回到第2步。

步驟4。當(dāng)i=len時(shí)處理結(jié)束，將標(biāo)記過(guò)S的節(jié)點(diǎn)順序連線即為平滑后的路徑。

3.3 航線自動(dòng)搜索算法

1)將起始點(diǎn)所在的三角網(wǎng)放在openlist中。

2)重復(fù)以下步驟。

①在openlist中查找F值最小的三角網(wǎng)，作為當(dāng)前三角網(wǎng)。

②把當(dāng)前三角網(wǎng)移到closelist中。

③對(duì)當(dāng)前三角網(wǎng)相鄰的三角網(wǎng)進(jìn)行以下步驟。

如果該相鄰三角網(wǎng)已經(jīng)在closelist中，則繼續(xù)檢查下一個(gè)相鄰三角網(wǎng)。

如果不在openlist中，則添加到表里，調(diào)用三角網(wǎng)路徑平滑處理算法，計(jì)算該三角網(wǎng)的G值，保存G值和H值，將該三角網(wǎng)的父節(jié)點(diǎn)設(shè)為當(dāng)前三角網(wǎng)。

如果在openlist中，則判斷經(jīng)由當(dāng)前三角網(wǎng)到達(dá)該相鄰三角網(wǎng)的G值是否小于原來(lái)保存的G值，若小于，則設(shè)置三角網(wǎng)的父節(jié)點(diǎn)為當(dāng)前三角網(wǎng)，并重新設(shè)置該三角網(wǎng)的G值和H值。

④循環(huán)結(jié)束條件。當(dāng)目標(biāo)三角網(wǎng)被加入到openlist或者作為待檢驗(yàn)節(jié)點(diǎn)時(shí)，表示路徑被找到，循環(huán)結(jié)束。

3)從目標(biāo)點(diǎn)開始沿父節(jié)點(diǎn)遍歷，遍歷所得的節(jié)點(diǎn)就是最后得到的最優(yōu)路徑。

4 算法驗(yàn)證與分析

為了驗(yàn)證航線自動(dòng)生成算法的有效性，進(jìn)行仿真并給出仿真實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)基于真實(shí)的海洋數(shù)據(jù)，開發(fā)環(huán)境為Visual Studio 2010，運(yùn)行于PC機(jī)，windows系統(tǒng)下?；诘聡?guó)SevenCs公司開發(fā)的EC2007 ECDIS Kernel進(jìn)行二次開發(fā)，其中該ECDIS系統(tǒng)自帶航線輔助功能，可根據(jù)經(jīng)驗(yàn)航路交通網(wǎng)組合出一條新的航線。

實(shí)驗(yàn)1的仿真結(jié)果見圖2，完成起始點(diǎn)位置坐標(biāo)(16.155 26,113.440 2)到目標(biāo)點(diǎn)位置坐標(biāo)(-1.691 93,98.420 02)的航線規(guī)劃，該區(qū)域由海南省出發(fā)，目的地為明打威群島，途徑南海、爪哇海，海洋環(huán)境復(fù)雜，障礙物較多且分布集中。

圖2 實(shí)驗(yàn)1仿真結(jié)果

海圖中，圓圈叉形圖標(biāo)為獨(dú)立礙航點(diǎn)，方形點(diǎn)狀圖標(biāo)為海上平臺(tái)。粗的虛線表示本文的算法自動(dòng)規(guī)劃的一條航線，細(xì)的實(shí)線表示EC2007 ECDIS中根據(jù)歷史經(jīng)驗(yàn)航路組合的航線。航路點(diǎn)的坐標(biāo)表示為緯度、經(jīng)度，其中負(fù)號(hào)表示南緯或者西經(jīng)。

表1為經(jīng)典航線各航路點(diǎn)坐標(biāo)，表2為規(guī)劃航線各航路點(diǎn)坐標(biāo)。

表1 實(shí)驗(yàn)1經(jīng)典航線航路點(diǎn)坐標(biāo)

表2 實(shí)驗(yàn)1規(guī)劃航線航路點(diǎn)坐標(biāo)

圖3為實(shí)驗(yàn)2仿真結(jié)果，起始點(diǎn)位置坐標(biāo)(41.518 09,143.118 7)到目標(biāo)點(diǎn)位置坐標(biāo)(28.023 28,-115.995)的航線規(guī)劃，該區(qū)域?yàn)橛扇毡境霭l(fā)，目的地為墨西哥西北部，途徑菲律賓海、太平洋的大洋航線。該航線航程較長(zhǎng)，海洋環(huán)境簡(jiǎn)單，障礙物稀少。

圖3 實(shí)驗(yàn)2仿真結(jié)果

表3為經(jīng)典航線各航路點(diǎn)坐標(biāo)，表4為規(guī)劃航線各航路點(diǎn)坐標(biāo)。

表3 實(shí)驗(yàn)2經(jīng)典航線航路點(diǎn)坐標(biāo)

表4 實(shí)驗(yàn)2規(guī)劃航線航路點(diǎn)坐標(biāo)

表5為在2種不同的海洋環(huán)境下，本算法規(guī)劃的航線與EC2007 ECDIS中根據(jù)經(jīng)驗(yàn)航路交通網(wǎng)組合的航線的比較。

表5 規(guī)劃航路與經(jīng)典航路比較

通過(guò)表5可以看出，在航路點(diǎn)個(gè)數(shù)上，本文提出的算法搜索的航路點(diǎn)更少，尤其是在障礙物少，海洋環(huán)境簡(jiǎn)單的情況下；在總航程上，本文搜索到的航路要比經(jīng)典航路總航程短，尤其是在海洋環(huán)境復(fù)雜，不存在歷史航線，或者航行經(jīng)驗(yàn)不足的情況下，本文提出的航線規(guī)劃算法可自動(dòng)規(guī)劃出一條安全經(jīng)濟(jì)航線。

5 結(jié)論

1)航線自動(dòng)規(guī)劃算法能夠在復(fù)雜缺少航行經(jīng)驗(yàn)海域規(guī)劃出一條安全經(jīng)濟(jì)航線，在航海中具有一定的實(shí)用性；并且只需對(duì)評(píng)估函數(shù)的參數(shù)進(jìn)行變換，便可得到其他評(píng)價(jià)標(biāo)準(zhǔn)的最優(yōu)航線，具有一定的靈活性。

2)Delaunay三角網(wǎng)模擬海洋環(huán)境，準(zhǔn)確的構(gòu)建海洋環(huán)境模型是航路自動(dòng)規(guī)劃算法的基礎(chǔ)。

3)本方法用不規(guī)則三角網(wǎng)模擬靜態(tài)海洋環(huán)境，對(duì)動(dòng)態(tài)的海洋環(huán)境如潮汐、風(fēng)、海流的影響適應(yīng)性需進(jìn)一步研究。