水面無人艇路徑規(guī)劃研究綜述*

大連海事大學(xué)航海學(xué)院 陳 華 張新宇 姜長鋒 徐國瑞

水面無人艇路徑規(guī)劃研究綜述*

大連海事大學(xué)航海學(xué)院 陳 華 張新宇 姜長鋒 徐國瑞

水面無人艇近年來受到國內(nèi)外專家學(xué)者越來越多的關(guān)注。為了總結(jié)分析USV現(xiàn)有路徑規(guī)劃方法及其優(yōu)缺點，通過對USV路徑規(guī)劃研究進行分類綜述和分析，從獲取環(huán)境空間障礙物的方式，將USV路徑規(guī)劃分為基于海洋環(huán)境信息的全局路徑規(guī)劃和基于傳感器信息的局部路徑規(guī)劃?？偨Y(jié)基于各類研究方法的主要研究成果及其主要特點，剖析其存在的主要問題，闡明USV路徑規(guī)劃的研究思想和意義，提出USV路徑規(guī)劃今后可能的發(fā)展方向。

USV；路徑規(guī)劃；海上交通

隨著現(xiàn)代科學(xué)技術(shù)的飛速發(fā)展，海上智能交通已成為我國科技戰(zhàn)略的重要組成部分。發(fā)展海上智能交通主要是為了實現(xiàn)船舶的航行自動化和海上交通的智能化管理。因此，作為海上交通系統(tǒng)的主要個體船舶，對其航行路徑的研究顯得尤為重要。而近年興起的研究熱點——水面無人艇，是一種無人操作的水面艦艇，主要用于執(zhí)行危險以及不適于有人船只執(zhí)行的任務(wù)。[1]由于其具有體積小、速度快、智能化和自動化程度高的特點而吸引了廣大研究人員。它不僅可以被用于軍事領(lǐng)域的掃雷、偵察和反潛作戰(zhàn)等方面，還可以用于民用領(lǐng)域的水文氣象探測、環(huán)境監(jiān)測和海上搜救等方面。文獻［2，3］總結(jié)了無人艇的研究歷史、現(xiàn)狀以及發(fā)展趨勢。在水面無人艇研發(fā)和使用領(lǐng)域，美國和以色列一直處于領(lǐng)先地位。位于美國弗吉尼亞州的UOV公司集風(fēng)能、太陽能和回收動力作為能源而研發(fā)了理論上擁有無限續(xù)航能力的UOV，適用于海洋數(shù)據(jù)監(jiān)測和收集等。[4]以色列Elbit公司推出了Stingary號USV，它具有船型小、機動靈活、隱蔽性好和智能巡航等優(yōu)點。[5]中國對無人艇的研究起步較晚，但慶幸的是，國內(nèi)對無人艇的研究已經(jīng)越來越重視。中國氣象局與沈陽航天新光集團共同研制了我國首艘無人駕駛船“天象一號”，它由海上無人探測平臺和地面控制系統(tǒng)組成，能滿足高海況下工作需求。[6]

目前水面無人艇主要配備的系統(tǒng)包括運動控制系統(tǒng)、傳感器系統(tǒng)、通信系統(tǒng)和武裝系統(tǒng)。其中，文獻[7]將運動控制系統(tǒng)分為導(dǎo)航定位子系統(tǒng)、路徑規(guī)劃子系統(tǒng)和航跡跟蹤子系統(tǒng)。而路徑規(guī)劃作為無人艇研究的核心問題，在一定程度上代表著無人艇智能化水平的高低。近年來對無人艇路徑規(guī)劃的研究成為海上智能交通的熱點問題。本文從獲取環(huán)境空間障礙物的方式，將無人艇路徑規(guī)劃分為基于海洋環(huán)境信息的全局路徑規(guī)劃和基于傳感器信息的局部路徑規(guī)劃，分別綜述其研究方法和成果，深入分析其本質(zhì)特點和存在的不足，并對無人艇路徑規(guī)劃的發(fā)展方向提出幾點展望。

一、基于海洋環(huán)境信息的全局路徑規(guī)劃

全局路徑規(guī)劃是基于給定的海洋環(huán)境信息（通常指電子海圖）來獲取無人艇所經(jīng)過區(qū)域的靜態(tài)障礙物信息的大范圍離線路徑規(guī)劃。為了解決全局路徑規(guī)劃問題，文獻[7]將改進勢場法與動態(tài)柵格法相結(jié)合，設(shè)計了一種勢場動態(tài)柵格法，通過將柵格動態(tài)細化的方式建立環(huán)境模型，利用改進勢場法來搜索最優(yōu)路徑，通過減少折線來減少多余的路徑點，最終達到路徑優(yōu)化的目的。該方法收斂速度快，能避免傳統(tǒng)勢場法容易陷入局部極小值問題，但沒有考慮風(fēng)、浪、流等水文氣象因素對路徑規(guī)劃的影響。文獻[8]提出一種基于電子海圖的距離尋優(yōu)Dijkstra算法來解決水面無人艇全局路徑規(guī)劃問題。為了克服傳統(tǒng)Dijkstra算法占用內(nèi)存大的問題，該算法使用動態(tài)網(wǎng)格模型來減少規(guī)劃時間，提高規(guī)劃精度。但該方法在環(huán)境模型的建立時僅僅基于電子海圖，沒有考慮風(fēng)、浪、流等水文氣象因素對航線設(shè)計的影響。文獻[9]利用遺傳算法和人工勢場法設(shè)計了水面無人艇全局路徑規(guī)劃并進行了仿真實驗，實驗表明該方法能對多種復(fù)雜的障礙物環(huán)境進行規(guī)劃，并且具有能在起點周圍三面障礙物中尋找最優(yōu)路徑的能力。但該方法只是針對簡單的幾何圖形和海岸線進行規(guī)劃，沒有引入真正意義上的電子海圖。為了尋找一條最小或者接近最小的全局最優(yōu)路徑，文獻[10，11]采用時效性好的A星算法作為路徑規(guī)劃算法，該方法也能找到最優(yōu)路徑，但局限性在于無人艇要與既定路徑非常近或處在該路徑上，這對無人艇的控制系統(tǒng)提出了更高的要求。文獻[12]針對大規(guī)模海洋環(huán)境條件復(fù)雜的特點，采用碰撞檢測技術(shù)和限制搜索區(qū)域構(gòu)建障礙物潛在碰撞集，以達到減小航線規(guī)劃搜索規(guī)模的目的。基于柵格模型簡單及其對不規(guī)則障礙物表達能力強的優(yōu)點，提取障礙物邊界信息建立緊湊、高效的環(huán)境模型，對障礙物進行離散化處理，充分利用柵格間的鄰接關(guān)系，基于 Elasticity 算法實現(xiàn)最短航線規(guī)劃。實驗結(jié)果表明，設(shè)計的方法能夠滿足船舶在復(fù)雜的海洋環(huán)境中高效地尋找出最優(yōu)路徑。但該方法沒有考慮到轉(zhuǎn)向次數(shù)問題，也沒有考慮風(fēng)、浪、流等外界環(huán)境的影響。文獻[13]提出一種基于可視圖法的A星算法用于解決無人艇全局路徑規(guī)劃問題，該方法克服了傳統(tǒng)可視圖法靈活性差的問題，可以提高規(guī)劃效率，減少規(guī)劃時間。但該算法將無人艇簡化成一個質(zhì)點，沒有考慮無人艇的機動性能，同時也沒有考慮風(fēng)、浪、流的影響。為了解決大范圍環(huán)境下的全局路徑規(guī)劃問題，文獻[14]設(shè)計了分層和激活值相結(jié)合以及分層和遺傳算法相結(jié)合的路徑規(guī)劃算法，根據(jù)分層思想的特點，結(jié)合二維環(huán)境，采用十六叉樹的環(huán)境模型建立每一層地圖，在每層地圖中建立各個區(qū)域的鄰接關(guān)系，確定子起點和子終點。但該方法只是基于真實的海圖，沒有基于真正意義上的電子海圖，也沒有考慮風(fēng)、浪、流等復(fù)雜環(huán)境因素的影響。

總之，無人艇全局路徑規(guī)劃的研究思路為：從電子海圖中獲取本航次所要經(jīng)過海區(qū)的靜態(tài)障礙信息，包括岸線、島嶼、暗礁和沉船等。然后采用A星算法、距離尋優(yōu)Dijkstra算法、遺傳算法和人工勢場法等方法找出從起點到終點的無碰路徑。一般采用離線的方法，即在無人艇開航前就設(shè)定好航線。但從目前現(xiàn)有的方法來看，大都沒有考慮風(fēng)、浪、流等水文氣象因素對航線設(shè)計的影響。

二、基于傳感器信息的局部路徑規(guī)劃

局部路徑規(guī)劃是根據(jù)AIS獲取附近船舶信息或根據(jù)雷達等傳感裝置探測周圍障礙物信息的小范圍在線路徑規(guī)劃。障礙物通常是動態(tài)的船舶或者電子海圖未顯示的靜態(tài)障礙物。英國的Wasif Naeeml[15]等基于哈默斯坦和維納模型，采用遺傳算法非線性預(yù)測控制的思想來對無人艇進行實時局部路徑規(guī)劃，它是一個兩輸入單輸出的系統(tǒng)。Canny和Reif[16]證明了在平面內(nèi)限定動態(tài)障礙物速度的路徑規(guī)劃是NP問題。研究仍沒有發(fā)現(xiàn)可以得到USV需要的接近于實時計算的最優(yōu)方案。文獻[17]采用基于模糊理論改進的ND方法規(guī)避局部危險，并采用Q學(xué)習(xí)機制和同時更新相似海風(fēng)狀態(tài)的Q值來提高收斂速度。該方法主要的貢獻是打破了傳統(tǒng)忽略風(fēng)、浪、流影響的研究方法，在考慮外界因素上邁進了一步，但由于海面環(huán)境的復(fù)雜性，該方法也只是考慮了二維風(fēng)的影響，而實際的海風(fēng)是三維的，也沒有考慮海浪和海流等因素的影響。文獻[18，19]根據(jù)來船的航向和相對方位判斷兩船的會遇態(tài)勢，不同的會遇態(tài)勢生成不同的會遇安全領(lǐng)域，進而采用進化算法生成安全路徑。該方法融合了國際海上避碰規(guī)則的追越、交叉相遇和對遇條款，摒棄了傳統(tǒng)的根據(jù)兩船DCPA和TCPA判斷緊迫局面的方法，而是采用規(guī)定好的來船相對方位和航向判斷會遇態(tài)勢，智能地生成安全領(lǐng)域和航行路徑。該方法簡單易行，執(zhí)行效率高，能快速生成滿足要求的優(yōu)化路徑，但該方法將無人艇簡化為一個質(zhì)點，沒有考慮無人艇的機動性能，也沒有考慮海風(fēng)、海浪和海流的影響。為了解決無人艇同時會遇多艘船舶問題，文獻[20]提出基于國際海上避碰規(guī)則（International Regulations for Preventing Collisions at Sea，以下簡稱避碰規(guī)則）的確定性協(xié)同路徑規(guī)劃算法，該算法能使無人艇在會遇多艘船舶時成功避讓并尋找出最優(yōu)路徑，文中從不同的角度驗證了算法的一致性和有效性，但該算法也沒有考慮風(fēng)、浪、流的影響。根據(jù)動態(tài)障礙物的規(guī)避問題，文獻[21]提出基于海事規(guī)則的局部路徑規(guī)劃方法，該方法將動態(tài)障礙物在某一瞬時轉(zhuǎn)換為相對無人艇靜止的狀態(tài)，并用粒子群算法以避碰規(guī)則為約束條件進行求解。通過仿真結(jié)果發(fā)現(xiàn)，該方法能有效規(guī)避動態(tài)障礙物，得到合理的規(guī)避策略。但由于障礙物運動狀態(tài)的不確定性，預(yù)測的障礙物信息難免出現(xiàn)不準確的情況。為了解決復(fù)雜海況下的危險規(guī)避問題，文獻[22]以Sarsa在線策略強化學(xué)習(xí)算法為基礎(chǔ)，提出了USV在復(fù)雜海況下的自適應(yīng)危險規(guī)避決策模型，并以漸進貪心策略作為行為探索策略，證明了USV自適應(yīng)危險規(guī)避決策過程能夠以概率1收斂到最優(yōu)行為策略。論證結(jié)果表明，采用在線策略強化學(xué)習(xí)算法提升USV在復(fù)雜海況下的危險規(guī)避性能是可行的。

通過對現(xiàn)有文獻的綜述發(fā)現(xiàn)，無人艇局部路徑規(guī)劃可以分為融合避碰規(guī)則和不考慮避碰規(guī)則兩類。融合避碰規(guī)則的局部路徑規(guī)劃中，大都采用速度避障法，該方法對來船能成功避讓，但對于未知障礙為靜態(tài)障礙并不適用。在不考慮避碰規(guī)則的局部路徑規(guī)劃中，將來船視為其他動態(tài)障礙，即無論來船的航向和航速如何，無人艇都對其進行避讓，這會使無人艇在海上航行時，當需要來船采取避讓行動的時候，無人艇也采取了避讓行動，這會使兩船行為不協(xié)調(diào)，容易引起碰撞事故。

三、無人艇路徑規(guī)劃的發(fā)展方向

為深入研究無人艇路徑規(guī)劃中的建模問題，筆者認為以下可能的發(fā)展方向應(yīng)該受到重視:

（1）針對無人艇路徑規(guī)劃中的環(huán)境建模問題，應(yīng)考慮加入風(fēng)、浪和流等外界因素的干擾。通過模擬、實測和咨詢專家等方式獲取比較可靠的數(shù)據(jù)，將獲得的數(shù)據(jù)對模型進行驗證。

（2）在無人艇會遇他船采取避讓行動時應(yīng)考慮無人艇碰撞危險度問題。目前并無權(quán)威的無人艇碰撞危險度模型，因此可以參考現(xiàn)有船舶的碰撞危險度，根據(jù)無人艇的實際情況，構(gòu)建無人艇碰撞危險度。

（3）人工智能方法具有快速尋優(yōu)的優(yōu)點，已在建模、數(shù)字信號和圖像處理等方面得到了廣泛的應(yīng)用，但在無人艇路徑規(guī)劃中，基于智能技術(shù)的路徑規(guī)劃遠未發(fā)揮現(xiàn)有智能信息處理技術(shù)的優(yōu)勢，還需深入研究。

四、結(jié)語

水面無人艇無論在民用領(lǐng)域還是軍事領(lǐng)域都發(fā)揮著不可估量的重要作用，是一個國家大力發(fā)展海洋強國戰(zhàn)略不可或缺的有力武器。為推動無人艇路徑規(guī)劃的深入研究和廣泛應(yīng)用，本文從獲得障礙物信息方式的角度，對現(xiàn)有路徑規(guī)劃方法進行分類綜述和分析，總結(jié)出各類研究方法的現(xiàn)有成果和主要優(yōu)缺點，剖析存在的問題。在此基礎(chǔ)上，提出無人艇路徑規(guī)劃具有重要理論意義和實際應(yīng)用價值的發(fā)展方向。

[1]熊亞洲,張曉杰,馮海濤,等.一種面向多任務(wù)應(yīng)用的無人水面艇[J].船舶工程,2012(1):16-19.

[2]MANELY J E.Unmanned Surface Vehicles,15 Years of Development[C]//Proc.Oceans 2008 MTS/IEEE Quebec Conference Exhibition,Quebec City:Ocean’08,2008:1-4.

[3]VEERS J,BERTRAM V.Development of the USV Multi-mission Surface Vehicle III[C]//5th Int.Computer and IT Application in the Maritime Industries,COMPIT.2006:345-355.

[4]VEERS J,BERTRAM V.Development of the USV multi-mission surface vehicle III[C]//5th International Conference on Computer Applications and Information Technology in the Maritime Industries. Delft,2006.

[5]YAN R,PANG S,SUN H,et al.Development and missions of unmanned surface vehicle[J].Journal of Marine Science and Application,2010(4):451-457.

[6]柳晨光,初秀民,吳青,等.USV發(fā)展現(xiàn)狀及展望[J].中國造船, 2014(4):194-205.

[7]劉建.水面無人艇路徑規(guī)劃技術(shù)的研究[D].南京:江蘇科技大學(xué),2014.

[8]莊佳園,萬磊,廖煜雷,等.基于電子海圖的水面無人艇全局路徑規(guī)劃研究[J].計算機科學(xué),2011(9):211-219.

[9]張玉奎.水面無人艇路徑規(guī)劃技術(shù)研究[D].哈爾濱:哈爾濱工程大學(xué),2008.

[10]盧艷爽.水面無人艇路徑規(guī)劃算法研究[D].哈爾濱:哈爾濱工程大學(xué),2010.

[11]王錦川.自主式水面航行器導(dǎo)航與制導(dǎo)算法的研究[D].大連:大連海事大學(xué),2014.

[12]湯青慧.基于電子海圖的航線規(guī)劃方法研究[D].青島:中國海洋大學(xué),2011.

[13]陳超,唐堅.基于可視圖法的水面無人艇路徑規(guī)劃設(shè)計[J].中國造船,2013(1):129-135.

[14]饒森.水面無人艇的全局路徑規(guī)劃技術(shù)研究[D].哈爾濱:哈爾濱工程大學(xué),2007.

[15]NAEEML W,SUTTON R,CHUDLEY J.Modeling and control of unmanned surface vehicle for environment monitoring [J].Robotic Ocean Vehicles for Marine Science Applications,2006(1):409-415.

[16]CANNY J,REIF J.New lower bound techniques for robot motion planning problem[C].Proceedings of 28th Annual IEEE Symp on Foundation of Computer Science,Los Angeles:CA,1987:49-60

[17]王敏捷.USV自適應(yīng)局部危險規(guī)避方法研究[D].哈爾濱:哈爾濱工程大學(xué),2012.

[18]TAM C K,BUCKNALL R.Collision risk assessment for ships [J].Journal of Marine Science and Technology,2010,15:257-270.

[19]TAM C K,BUCKNALL R.Path planning algorithm for ships in close range encounters[J].Journal of Marine Science and Technology,2010,15:395-470.

[20]TAM C K,BUCKNALL R.Cooperative path planning algorithm for marine surface vessels[J].Ocean Engineering,2013,57:25-33.

[21]杜開君,茅云生,向祖權(quán),等.基于海事規(guī)則的水面無人艇動態(tài)障礙規(guī)避方法[J].船舶工程,2015(3):119-124.

[22]張汝波,唐平鵬,楊歌,等.水面無人艇自適應(yīng)危險規(guī)避決策過程收斂性分析[J].計算機研究與發(fā)展,2014(12):2644-2652.

10.16176/j.cnki.21-1284.2015.11.008

國家自然科學(xué)基金項目（51309043）；交通運輸部應(yīng)用基礎(chǔ)研究項目（2014329225020）；中國博士后科學(xué)基金項目（2014M551095）；遼寧省自然科學(xué)基金項目（2014025005）；遼寧省高校杰出青年學(xué)者成長計劃（LJQ2014052）；中央高校基本科研業(yè)務(wù)費專項資金資助項目（3132014202）；遼寧省教育廳重點實驗室基礎(chǔ)研究項目（LZ2015009）