趙玉新， 金 娜， 劉 廠

(1.哈爾濱工程大學(xué) 自動(dòng)化學(xué)院， 哈爾濱 150000；2.空間物理重點(diǎn)實(shí)驗(yàn)室，北京 100076)

ZHAO Yuxin1, JIN Na2, LIU Chang1

基于電子海圖的AUV多約束航路規(guī)劃方法

趙玉新1， 金 娜2， 劉 廠1

(1.哈爾濱工程大學(xué) 自動(dòng)化學(xué)院， 哈爾濱 150000；2.空間物理重點(diǎn)實(shí)驗(yàn)室，北京 100076)

電子海圖涵蓋豐富的地物信息，通過對(duì)S-57標(biāo)準(zhǔn)電子海圖進(jìn)行信息提取和融合，得到接近真實(shí)航行環(huán)境的三維規(guī)劃空間。在此基礎(chǔ)上，根據(jù)三維規(guī)劃的需要擴(kuò)展二維A*算法，并結(jié)合航路規(guī)劃中常考慮的多種約束對(duì)A*規(guī)劃算法進(jìn)行改進(jìn)。試驗(yàn)結(jié)果表明：基于電子海圖的自主式水下航行器(Autonomous Underwater Vehicle,AUV)多約束航路規(guī)劃方法能模擬出較為真實(shí)的規(guī)劃空間，提出的規(guī)劃算法能規(guī)劃出符合多種規(guī)劃約束的三維路徑。

水路運(yùn)輸;S-57電子海圖；自主式水下航行器；三維航路規(guī)劃；A*算法

ZHAOYuxin1,JINNa2,LIUChang1

Abstract: The way to abstract geometric information from an S-57 electronic chart and fuse different element data is illustrated to define a 3D planning domain. The 2D A*algorithm is extended into 3D, and adapted to the constraints for path planning. The trial operation shows that the proposed method can simulate real 3D planning environment and the algorithm can produce 3D paths complying with given constraints.

Keywords: waterway transportation; S-57 electronic chart; AUV; 3D path planning; A*algorithm

隨著現(xiàn)代航海技術(shù)不斷發(fā)展，電子海圖與導(dǎo)航應(yīng)用技術(shù)的結(jié)合越來越緊密，航路規(guī)劃就是其中一種很重要的結(jié)合方式。目前有很多基于電子海圖的航路規(guī)劃方法：欒祿雨等[1]通過提取原始海圖數(shù)據(jù)，對(duì)規(guī)劃環(huán)境進(jìn)行柵格化處理，利用遺傳算法規(guī)劃航路，得到比較好的規(guī)劃效果；吳博等[2]提出一種基于電子江圖的路徑遍歷算法，該算法以分層的電子江圖為基礎(chǔ)，運(yùn)用全局路徑規(guī)劃和局部路徑規(guī)劃的方法尋找到一條近似可航路徑。

從算法設(shè)計(jì)的發(fā)展上看，越來越多的算法被應(yīng)用到航路規(guī)劃中，且都已得到很好的效果。但是，已有的規(guī)劃算法大多是二維的，其規(guī)劃的路徑不適合航行在三維空間的水下運(yùn)載器，而將其直接擴(kuò)展到三維又不能保證規(guī)劃效果。文獻(xiàn)[3]提出在二維航路規(guī)劃的基礎(chǔ)上對(duì)深度進(jìn)行解算，這種方法為三維航路規(guī)劃提供了一種思路，但靈活性較差。

從航行空間生成方法上看，目前大部分研究都把關(guān)注點(diǎn)放在航路規(guī)劃的算法設(shè)計(jì)上，忽略了規(guī)劃空間的設(shè)計(jì)和環(huán)境信息的提取，而航行環(huán)境信息的準(zhǔn)確度在航路規(guī)劃中至關(guān)重要。[4]因此，有必要設(shè)計(jì)出一種基于海圖數(shù)據(jù)的規(guī)劃空間生成方法。

這里提出一種基于電子海圖的全局規(guī)劃方法。該方法通過對(duì)S-57標(biāo)準(zhǔn)的電子海圖[5-6]進(jìn)行信息提取和數(shù)據(jù)處理，形成可用于規(guī)劃的三維航行空間。在此基礎(chǔ)上，利用A*算法進(jìn)行多約束的航路規(guī)劃，給出一條符合航行約束的三維路徑。

1 規(guī)劃空間的生成

規(guī)劃空間是根據(jù)規(guī)劃任務(wù)確定的一個(gè)滿足規(guī)劃要求的最小空間，該空間不僅要在空間上包含所有可能的航路點(diǎn)，而且要在環(huán)境信息上盡量準(zhǔn)確、全面地描述環(huán)境特征，從而保證規(guī)劃空間的合理性和真實(shí)性?；谏鲜鰳?biāo)準(zhǔn)，給出基于電子海圖的規(guī)劃空間生成方法。這里提出的規(guī)劃空間生成方法從電子海圖中提取水深、陸地和島嶼等數(shù)據(jù)，通過插值、疊加和融合等處理，形成一個(gè)包含水深及陸地等信息的三維空間。水深插值利用自然鄰點(diǎn)的插值方法；特征要素疊加及插值修補(bǔ)則通過緩沖區(qū)進(jìn)行判斷和賦值。特征要素疊加和插值修補(bǔ)的基本方法[7-8]如下。

1.1特征要素疊加

由于海洋中存在沉船、暗礁等很多障礙物，這些信息是以點(diǎn)、線、面要素的形式存儲(chǔ)的，而依靠水深插值生成的網(wǎng)格數(shù)據(jù)只有基本的水深數(shù)據(jù)，不包含這些障礙物信息，因此需要把海圖中的要素信息疊加到水深數(shù)據(jù)上。要素疊加的總體思想是制造要素點(diǎn)或水深點(diǎn)的緩沖區(qū)，判斷緩沖區(qū)與水深或各要素之間的重疊關(guān)系，從而進(jìn)行相應(yīng)的賦值操作。下面通過線要素疊加和面要素疊加作進(jìn)一步的說明。

1.1.1線要素的疊加

線要素的疊加分以下2步完成。

(1) 讀取線要素中的位置點(diǎn)集p={p1,p2,…,pn}，對(duì)每個(gè)位置點(diǎn)pi構(gòu)建一個(gè)水深單位網(wǎng)格大小的緩沖區(qū)pbuffer，通過計(jì)算緩沖區(qū)在水深網(wǎng)格的相對(duì)位置找到與pbuffer重合或相交的水深網(wǎng)格點(diǎn)qi；

(2) 利用pi的水深點(diǎn)對(duì)qi的水深值進(jìn)行更新。

由于受海圖信息分辨率的限制，線要素的位置點(diǎn)集在空間的分布不連續(xù)，因此要找到2個(gè)相鄰點(diǎn)pi與pi+1的連線經(jīng)過的所有網(wǎng)格，將相關(guān)網(wǎng)格的水深更改為該線要素的水深。

1.1.2面要素的疊加

讀取面要素中的位置點(diǎn)集p={p1,p2,…,pn}，連接該點(diǎn)集的所有元素形成一個(gè)封閉圖形U，對(duì)水深網(wǎng)格的每個(gè)網(wǎng)格點(diǎn)制造一個(gè)適當(dāng)大小的緩沖區(qū)pbuffer，判斷水深網(wǎng)格點(diǎn)pbuffer緩沖區(qū)與U的位置關(guān)系，表達(dá)式為

pbuffer∩U≠Θ,pi=0

(1)

式(1)中：pbuffer=(x:d(x1,pi)≤R)；R為緩沖區(qū)半徑；d為兩點(diǎn)之間的距離。

1.1.3點(diǎn)要素的疊加

點(diǎn)要素主要包括沉船、暗礁及危險(xiǎn)區(qū)等信息，點(diǎn)要素的疊加主要通過讀取點(diǎn)要素的位置信息找到水深網(wǎng)格的對(duì)應(yīng)位置，再對(duì)水深網(wǎng)格的深度進(jìn)行賦值。

1.2插值修補(bǔ)

在插值過程中，不可避免地會(huì)存在因可參考海圖水深數(shù)據(jù)較少而使插值失敗的現(xiàn)象。插值失敗的區(qū)域沒有其他陸地等要素的疊加，這就造成了規(guī)劃信息的殘缺。該問題的存在不利于路徑規(guī)劃，因此要對(duì)插值失敗的區(qū)域進(jìn)行修補(bǔ)。插值修補(bǔ)的主要思想是獲取插值失敗區(qū)域的點(diǎn)集，探測(cè)點(diǎn)集附近成功插值點(diǎn)的數(shù)據(jù)，再通過加權(quán)平均的方法獲取水深值，流程見圖1。

圖1 插值修補(bǔ)流程

圖2為插值修補(bǔ)示意，其中：實(shí)心點(diǎn)為插值成功點(diǎn)；空心點(diǎn)為插值失敗點(diǎn)；圓圈區(qū)域是以插值失敗點(diǎn)為中心的緩沖區(qū)，半徑為R。這里采用一個(gè)以插值失敗點(diǎn)為中心的緩沖區(qū)來探測(cè)附近的插值成功點(diǎn)，若依靠當(dāng)前半徑的緩沖區(qū)仍找不到一定數(shù)量的插值成功點(diǎn)，則擴(kuò)大緩沖區(qū)的半徑。需指出，緩沖區(qū)的半徑應(yīng)合理地設(shè)置，既能包括足夠多的插值成功點(diǎn)，保證節(jié)點(diǎn)水深修補(bǔ)的有效性，又能保證半徑盡量小，防止緩沖區(qū)過大導(dǎo)致修補(bǔ)水深嚴(yán)重失真。

圖2 插值修補(bǔ)示意

2 多約束航路規(guī)劃方法設(shè)計(jì)

A*算法[9]是一種啟發(fā)式搜索算法，由于其對(duì)空間的探索機(jī)制非常適合于尋路，因此該算法(二維)已被廣泛應(yīng)用于路徑規(guī)劃問題的求解中。SZCZERBA[10]提出一種改進(jìn)的A*算法，稱為稀疏A*算法。該算法根據(jù)約束條件有效削減搜索空間，實(shí)現(xiàn)算法的快速有效規(guī)劃。由于水下運(yùn)載器的航行空間復(fù)雜，且實(shí)際航行時(shí)受多種約束限制，二維規(guī)劃遠(yuǎn)遠(yuǎn)達(dá)不到要求，因此這里把二維稀疏A*算法擴(kuò)展到三維，并考慮實(shí)際航行常見的幾種約束，提出一種多約束三維A*算法。該算法在三維空間中根據(jù)航路規(guī)劃約束削減算法每步擴(kuò)展出的大量子節(jié)點(diǎn)，達(dá)到快速規(guī)劃的目的。

三維A*算法是在二維A*算法的基礎(chǔ)之上建立的，主要步驟包括A*地圖的建立、啟發(fā)函數(shù)的構(gòu)建及closed表和open表的維護(hù)。對(duì)于三維A*算法，柵格地圖占用的內(nèi)存及擴(kuò)展的子節(jié)點(diǎn)數(shù)明顯增多，這使得算法計(jì)算的效率明顯降低。因此，三維A*算法要盡量平衡計(jì)算精度和計(jì)算效率，設(shè)法快速且精準(zhǔn)地計(jì)算出柵格空間數(shù)據(jù)及擴(kuò)展子節(jié)點(diǎn)是算法的關(guān)鍵。

2.1三維A*地圖的建立

三維A*地圖是由多個(gè)立方體構(gòu)成的，因此需要計(jì)算立方體的可航行性。由于三維數(shù)據(jù)的信息量巨大，對(duì)每個(gè)立方體都盡量精準(zhǔn)地計(jì)算會(huì)消耗大量的時(shí)間和內(nèi)存，因此考慮到陸地等面要素和線要素?cái)?shù)據(jù)的連續(xù)性及點(diǎn)要素的離散性，采用大面積粗算、邊緣精算和離散點(diǎn)數(shù)據(jù)疊加的方式進(jìn)行地圖構(gòu)建。具體方法如下。

1) 大面積粗算：判斷立方體的中心點(diǎn)是否在障礙物中，若是則賦值為1，否則賦值為0。

2) 邊緣精算：找到值為1且周圍存在0值的立方體，精確計(jì)算該立方體周圍值為0的立方體的可航行性。

3) 離散點(diǎn)數(shù)據(jù)疊加：由于沉船、暗礁等點(diǎn)數(shù)據(jù)障礙物的面積很小且分布分散，不具有連續(xù)性，因此獲取這些點(diǎn)數(shù)據(jù)的位置數(shù)據(jù)并將其疊加到相應(yīng)的立方體中。

2.2子節(jié)點(diǎn)的擴(kuò)展

普通二維A*算法擴(kuò)展的子節(jié)點(diǎn)方向有4個(gè)或8個(gè)，由于三維航行增加了縱向方向，因此三維A*算法擴(kuò)展的子節(jié)點(diǎn)方向應(yīng)增加到6個(gè)、18個(gè)或26個(gè)，擴(kuò)展子節(jié)點(diǎn)數(shù)越多，規(guī)劃出的路徑就越接近實(shí)際航線，相應(yīng)的計(jì)算時(shí)間就越長(zhǎng)。這里為使航路具有較高的實(shí)用性，擴(kuò)展26個(gè)子節(jié)點(diǎn)，即在三維空間中緊鄰被擴(kuò)展節(jié)點(diǎn)的柵格，通過考慮多種航行約束，達(dá)到削減子節(jié)點(diǎn)并保證滿足約束的目的。

2.3多約束的處理

由于水下運(yùn)載器的運(yùn)動(dòng)受下潛深度、自身尺寸及靈活性的限制，因此只有充分考慮這些約束條件才能使規(guī)劃出的航路具有較強(qiáng)的實(shí)用性。此外，通過約束處理，也可達(dá)到消減規(guī)劃過程中的子節(jié)點(diǎn)的目的，以提高計(jì)算的效率。針對(duì)上述問題，給出深度和安全距離及最大轉(zhuǎn)向角、俯仰角的約束處理方法。

2.3.1深度約束的處理

水下運(yùn)載器的工作深度由自身特性決定，包括最小深度和最大深度，超過該深度范圍，運(yùn)載器將無法正常工作。因此，在構(gòu)建A*柵格地圖時(shí)根據(jù)最小深度和最大深度對(duì)網(wǎng)格節(jié)點(diǎn)進(jìn)行判斷，表達(dá)式為

(2)

這樣不僅能保證規(guī)劃出的航路始終在一個(gè)安全的深度范圍內(nèi)，而且可減少算法需要遍歷的空間節(jié)點(diǎn)。

2.3.2安全距離約束的處理

對(duì)于安全距離，為簡(jiǎn)化問題,對(duì)障礙物進(jìn)行“膨脹”處理，即將障礙物向外擴(kuò)展一定的距離，以滿足安全距離的要求。從空間分析的角度來說，障礙物的膨脹處理相當(dāng)于以一定的半徑對(duì)障礙物建立緩沖區(qū)。對(duì)于三維緩沖區(qū)的建立，通用的方法是計(jì)算A*地圖節(jié)點(diǎn)與規(guī)劃空間中障礙物的歐氏距離，若該距離小于安全距離，則認(rèn)為該節(jié)點(diǎn)是不可航的。具體方法如下。

(1) 找到A*地圖節(jié)點(diǎn)的經(jīng)緯度位置對(duì)應(yīng)的障礙物局部區(qū)域；

(2) 計(jì)算地圖節(jié)點(diǎn)到障礙物單位平面的歐氏距離θ；

(3) 判斷θ與安全距離dsafe的大小關(guān)系，若不滿足安全距離要求，則設(shè)置該節(jié)點(diǎn)為不可航點(diǎn)。

2.3.3轉(zhuǎn)角約束的處理

如“2.2”節(jié)所述，在三維A*算法中可擴(kuò)展出26個(gè)子節(jié)點(diǎn)，因此轉(zhuǎn)角也對(duì)應(yīng)26種情況。在處理最大轉(zhuǎn)向角和最大俯仰角時(shí)，首先判斷子節(jié)點(diǎn)的擴(kuò)展方向，若是向上方或下方擴(kuò)展的,則對(duì)應(yīng)最大俯仰角;若是在同一水平面內(nèi)擴(kuò)展的,則對(duì)應(yīng)最大轉(zhuǎn)向角。接著計(jì)算夾角θ，并判斷θ與角度約束的大小關(guān)系，若不滿足角度約束,則該子節(jié)點(diǎn)被刪除。這樣的處理方法不僅能滿足角度約束，同時(shí)可減輕open表的存儲(chǔ)負(fù)擔(dān)，有利于快速規(guī)劃出符合要求的路徑。

3 仿真驗(yàn)證及試驗(yàn)結(jié)果

3.1規(guī)劃空間生成方法的測(cè)試

從電子海圖中選擇一個(gè)特定的區(qū)域，該區(qū)域含有4塊陸地和若干個(gè)島嶼，水深從左至右逐漸加深。圖3為規(guī)劃空間對(duì)應(yīng)的電子海圖，其中：A位置為暗礁；B位置和C位置為危險(xiǎn)區(qū)。

為驗(yàn)證規(guī)劃空間生成方法的有效性和正確性，把生成的空間數(shù)據(jù)導(dǎo)入到Surfer中繪制成二維和三維地形(見圖4和圖5)。

圖3 規(guī)劃空間對(duì)應(yīng)的電子海圖

圖4 規(guī)劃空間的漸變地形圖

圖5 規(guī)劃空間的三維效果圖

從圖4和圖5中可看出，利用所提出的規(guī)劃空間生成方法得到的地形圖與圖3的特征基本吻合。由此可知，提出的面要素和線要素的疊加方法是正確的。

此外，通過對(duì)比圖3～圖5中的點(diǎn)要素A，B，C的位置可看出，要素A，B，C均被處理成障礙物，符合路徑規(guī)劃的要求。

3.2多約束三維A*算法的測(cè)試

為驗(yàn)證航路規(guī)劃算法的有效性，基于規(guī)劃空間生成的三維空間設(shè)計(jì)多約束三維A*算法性能驗(yàn)證試驗(yàn)，試驗(yàn)參數(shù)見表1。

程序仍用C++編寫，計(jì)算結(jié)果顯示在二維海圖上。為驗(yàn)證算法規(guī)劃的路徑滿足航路約束，統(tǒng)計(jì)所有路徑段中深度、轉(zhuǎn)角和俯仰角的最大值，判斷與障礙物的距離是否小于安全距離。給出的規(guī)劃結(jié)果見圖6，結(jié)果統(tǒng)計(jì)見表2。

表1 航行約束設(shè)置

圖6 電子海圖路徑結(jié)果圖

表2 規(guī)劃路徑約束統(tǒng)計(jì)結(jié)果

圖6中：S為起點(diǎn)；D為終點(diǎn)。由圖6和表2可知，該算法成功規(guī)劃出了一條三維無碰路徑，且該路徑符合航路規(guī)劃約束的要求。

4 結(jié)束語

給出基于S-57標(biāo)準(zhǔn)電子海圖的規(guī)劃空間生成方法，保證規(guī)劃空間的真實(shí)性；基于規(guī)劃空間并結(jié)合實(shí)際規(guī)劃需求，設(shè)計(jì)多種規(guī)劃約束的處理方法，提出多約束的三維A*規(guī)劃算法，提高規(guī)劃算法的實(shí)用性。仿真結(jié)果表明：所提出的方法能生成接近真實(shí)航行環(huán)境的規(guī)劃空間，并能規(guī)劃出一條符合多個(gè)約束要求的三維無碰路徑。

[1] 欒祿雨，朱海.基于改進(jìn)遺傳算法的潛艇隱蔽航路規(guī)劃[J].武器裝備自動(dòng)化，2005,25(9):3-4.

[2] 吳博，文元橋，肖長(zhǎng)詩.一種內(nèi)河海事無人艇路徑規(guī)劃算法設(shè)計(jì)與仿真[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(14):241-246.

[3] 欒祿雨，朱海，蔡鵬.艦艇航路規(guī)劃系統(tǒng)研究[J].中國航海，2008,31(4)：392-404.

[4] 張欣景，胡訓(xùn)強(qiáng)，謝國新，等.航路規(guī)劃中數(shù)字地圖綜合處理技術(shù)[J].火力與指揮控制，2012,37(1):95-98.

[5] 孟嬋媛，翟京生，陸毅.S-57數(shù)據(jù)的組織與實(shí)現(xiàn)[J].測(cè)繪學(xué)院學(xué)報(bào),2003,20(4):275-278.

[6] 扈震,楊之江,馬振強(qiáng).基于S-57標(biāo)準(zhǔn)的電子海圖三維可視化[J].地球科學(xué)——中國地質(zhì)大學(xué)學(xué)報(bào)，2010,35(3)：471-474.

[7] 王輝.海底地形三維可視化技術(shù)研究[D].哈爾濱：哈爾濱工程大學(xué),2013:31-32.

[8] 王勝正，黃玉貴，施朝健.基于區(qū)域?qū)哟渭?xì)節(jié)繪制的 3D ECDIS實(shí)現(xiàn)方法[J].中國造船，2014,55(3)：175-184.

[9] MITCHELL J S B, KEIRNEY D M. Planning Strategic Path Through Variable Terrain Data[C]//Proceedings of the Applications of Artificial Intelligence. USA: SPIE Press, 1984:172-179.

[10] SZCZERBA R J. Robust Algorithm for Real Time Route Planning[J]. IEEE Transaction on Aerospace and Electronic System, 2000, 36(3): 869-878.

Multi-ConstraintPathPlanningforAUVwithElectronicChart

(1.College of Automation，Harbin Engineering University, Harbin 150000, China； 2. Science and Technology on Space Physics Laboratory, Beijing 100076, China)

U612.1

A

2016-01-11

趙玉新(1980—)，男，黑龍江哈爾濱人，教授，研究方向?yàn)楝F(xiàn)代艦船綜合導(dǎo)航系統(tǒng)及無人海洋運(yùn)載器導(dǎo)航技術(shù)。 E-mail: zhaoyuxin@hrbeu.edu.cn 金 娜(1989—),女，遼寧鐵嶺人，碩士生，研究方向?yàn)橹悄芩惴ê秃铰芬?guī)劃。E-mail：jinna8899@163.com

1000-4653(2016)02-0011-04