,,
(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ì)性。
提出的航線自動(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.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ū)。
由于水深點(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ù)雜度。
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ù)即可。
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ù)。
改進(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)順序連線即為平滑后的路徑。
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)路徑。
為了驗(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ì)航線。
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)一步研究。