趙玉新， 金 娜， 劉 廠

(1.哈爾濱工程大學 自動化學院， 哈爾濱 150000；2.空間物理重點實驗室，北京 100076)

ZHAO Yuxin1, JIN Na2, LIU Chang1

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

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

(1.哈爾濱工程大學 自動化學院， 哈爾濱 150000；2.空間物理重點實驗室，北京 100076)

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

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

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

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

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

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

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

1.1特征要素疊加

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

1.1.1線要素的疊加

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

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

(2) 利用pi的水深點對qi的水深值進行更新。

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

1.1.2面要素的疊加

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

pbuffer∩U≠Θ,pi=0

(1)

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

1.1.3點要素的疊加

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

1.2插值修補

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

圖1 插值修補流程

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

圖2 插值修補示意

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

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

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

2.1三維A*地圖的建立

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

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

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

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

2.2子節(jié)點的擴展

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

2.3多約束的處理

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

2.3.1深度約束的處理

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

(2)

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

2.3.2安全距離約束的處理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2多約束三維A*算法的測試

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

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

表1 航行約束設置

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

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

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

4 結(jié)束語

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

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

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

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

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

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

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

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

[8] 王勝正，黃玉貴，施朝健.基于區(qū)域?qū)哟渭毠?jié)繪制的 3D ECDIS實現(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—)，男，黑龍江哈爾濱人，教授，研究方向為現(xiàn)代艦船綜合導航系統(tǒng)及無人海洋運載器導航技術(shù)。 E-mail: zhaoyuxin@hrbeu.edu.cn 金 娜(1989—),女，遼寧鐵嶺人，碩士生，研究方向為智能算法和航路規(guī)劃。E-mail：jinna8899@163.com

1000-4653(2016)02-0011-04