無人水面艇島礁海域完全遍歷路徑規劃

鐘雨軒,葛磊,張鑫,彭艷,楊毅,李小毛

(上海大學機電工程與自動化學院,上海 200072)

無人水面艇島礁海域完全遍歷路徑規劃

鐘雨軒,葛磊,張鑫,彭艷,楊毅,李小毛

(上海大學機電工程與自動化學院,上海 200072)

針對無人水面艇(unmanned surface vehicle,USV)對島礁海域自主測繪時存在的任務計算量大、場景復雜等問題,提出了一種考慮主動方向的動態柵格法與啟發式搜索算法.該方法基于動態柵格法進行環境建模,利用優先級啟發式算法選擇進行遍歷的路徑點,并在無人水面艇陷入死鎖時通過啟發式搜索算法產生走出死鎖點的最優路徑.仿真實驗結果表明,該方法能使路徑規劃的性能得到較大的提升,且規劃出的路徑更為合理有效,滿足無人水面艇對島礁區域測繪時的路徑需求.

無人水面艇;路徑規劃;動態柵格法;優先級啟發式算法;啟發式搜索算法

隨著海洋戰略的地位不斷提升,島礁成為重要的堡壘和基站.準確測量島礁地形、地質構造數據是構建“數字海洋”的基礎工作之一[1].目前適用于淺灘、島礁海域的物探技術主要有單波束測深、多波束測深和側掃聲吶等[2].隨著海洋智能裝備的不斷完善,島礁海域的探測方法也從傳統的人工探測過渡到當前的無人水面艇(unmanned surface vehicle,USV)自主探測.

無人水面艇是指依靠遙控或自主方式在水面航行的無人化、智能化作戰平臺,具有吃水淺、機動性強、行動隱蔽等特點[3].目前,世界各國已經服役及技術成熟度已達到服役水平的無人水面艇共63型,其中軍事用途約占70%.而國內研發的海洋無人水面艇主要有上海大學“精海”系列無人水面艇、珠海云洲智能科技有限公司研發的“領航者”號海洋測繪船等,這些無人水面艇已廣泛應用于海岸線和島礁岸線的海圖測量、水下考古、海洋資源調查、內河湖泊水污染檢測等.

淺灘、島礁海域測量的主要難點在于這些區域水位較淺,遍布暗礁,且容易受岸推、岸吸等不可預測力的影響[4],使得較大型測量船只,如“張騫”號科考船(吃水深度5.65 m)等，無法對這些區域進行勘測.而傳統的測量方式為人工駕駛小型測量船進行測量,不僅效率低,危險系數大,而且人工駕駛的方式無法保證測量船的實際航線與規劃航線重合,掃測誤差較大.無人水面艇的工作方式則是先由測繪人員在海圖顯示界面上選擇期望掃測航線,然后無人水面艇按照期望掃測航線自主航行,達到在一定區域內完成海底地形地貌測量的目的.

圖1為上海大學“精海3號”無人水面艇在金塘大橋附近沿規劃航線進行測繪的實時圖形用戶界面(graphical user interface,GUI).圖中左邊是實景拍攝畫面,右邊是由測繪人員在海圖上設定的掃測航線和無人水面艇的實際航行軌跡.

圖1 無人水面艇金塘大橋測繪GUI圖Fig.1 Mapping GUI of USV in the Jintang Bridge

然而,人為選擇掃測航線的方式只能掃測航線所覆蓋的部分區域,如果要對整個島礁區域進行掃測,則人為選擇的方式顯然不能滿足要求,而只能通過完全遍歷路徑規劃算法來實現.完全遍歷路徑規劃[5]是一種在2維環境中特殊的路徑規劃方法,是在滿足某種性能指標最優或準優的前提下,尋找一條在設定區域內從始點到終點且經過所有可達點的連續路徑.隨著商用和家用機器人產業化進程的推進,相關遍歷路徑規劃的研究越來越受到關注和重視.許多移動機器被要求能進行完全遍歷路徑規劃,如清潔機器人、掃地機器人、自主吸塵器、草坪修剪機、自主收割機、自主地面礦藏探測器等.完全遍歷路徑規劃的方法有近似單元分解法(approach cellular decomposition)、精確單元分解法(exact cellular decomposition)、基于模板的模型(template based model)、神經網絡方法(neural network approach)和基于行為的方法(behaviors based approach)等[6].

相對于掃地機器人等地面移動機器人,無人水面艇有其自身特點:①受限于無人水面艇搭載的測量設備的成像要求,無人水面艇必須以掃描式軌跡航行,并盡量減少轉向次數,以便后期進行圖像處理;另外,不同于在運動過程中均可作業的掃地機器人等,無人水面艇的運動軌跡不完全等同于作業軌跡.②無人水面艇在進行測量時作業范圍大,且島礁外形復雜,故任務計算量大,場景復雜,如果用完全遍歷路徑規劃算法進行計算則要求速度快,且適用于任何復雜場景.

1 基于神經網絡模型的路徑規劃

1943年,心理學家Mcculloch和數理邏輯學家Pitts[7]在分析和總結神經元基本特性的基礎上首先提出了神經元的數學模型;1952年,Hodgkin和Huxley[8]通過大量實驗推導出能夠量化描述神經元細胞膜上電壓與電流變化過程的數學模型,稱為Hodgkin-Huxley模型(H-H模型);Stephen[9]在H-H模型的基礎上提出了一個典型的生物神經元動力學模型Shunting Model,該模型具有結構簡單、模型穩定、輸出光滑有界等特點;Yang等[10]將這種生物激勵的神經網絡模型應用于移動機器人的環境建模,得到了較好的效果.

1.1 生物激勵的神經網絡模型

在由神經網絡組成的拓撲狀態空間中,所有神經元的初始活性值均為0,根據Grossberg提出的神經動力學模型,神經元活性值的變化可表示為分流方程(shunting equation)[11-12]:

式中:xi為第i個神經元的活性值;A,B和D為非負常數,A為衰減率,B和D為神經元活性狀態的上限和下限;k為第i個神經元相鄰的神經元個數;wij=f(dij),其中dij是第i個神經元與第j個神經元在狀態空間中所處位置的歐幾里得距離.函數f(a)定義為

式中,μ和r0都為正常數.Ii為外部輸入,定義為

圖2(a)～(c)分別為機器人運動過程中的神經網絡環境模型,波峰為未遍歷區域,波谷為障礙物區域,介于波峰與波谷之間的為已遍歷區域.圖2(a)為未遍歷前的環境模型初始狀態,式(1)表示的活性傳遞方式能夠保證未遍歷區域與障礙物區域對應的活性值分別位于波峰和波谷.圖2(b),(c)分別為遍歷過程中和遍歷后的環境模型.

1.2 遍歷路徑規劃算法

Yang等[10]利用神經網絡模型進行了環境建模,并提出了一種路徑規劃算法用以實現移動機器人的完全遍歷路徑規劃:給定機器人在工作空間的前一位置pp,當前位置為pc,則下一時刻的位置pn為

圖2 基于神經網絡的環境模型Fig.2 Environmental model based on neural network

式中,c為正常數,k為當前位置鄰域內神經元的總數,

其中?θj為機器人在當前時刻與下一時刻方向角改變量的絕對大小,

從式(6)可知,yj是一個遞減函數,如果?θj值越大,則yj值越小.

移動機器人的完全遍歷路程規劃具體生成過程如下:機器人從起始點出發,判斷當前位置鄰域內神經元活性值大小,按式(4)進行選擇,如果都不大于當前神經元的活性值,則機器人位置不變,機器人由當前位置到達下一位置后,下一位置成為新的當前位置,繼續搜索路徑,直到整個環境被完全遍歷.

圖3為由該算法產生的遍歷路徑,整個地圖由15×15個柵格組成,星號(*)表示障礙物區域.機器人移動一次的步長為一個柵格的距離,初始位置為(1,15),箭頭指示機器人的移動方向,空心圓表示機器人走出死鎖位置時的路徑點.

該算法考慮遍歷最短的路徑和最少的轉彎數,規劃出的路徑能夠在避碰狀態下實現完全遍歷.當工作環境簡單、障礙物數量較少時,該算法能夠取得較好的效果;但當環境模型復雜、障礙物數量較多時,規劃出的路徑就顯得不太合理,尤其是當機器人陷入死鎖后,走出死鎖點的路徑并不是最優路徑,并且會對后續路徑點的選取造成困難,如圖3中從坐標點(15,1)至坐標點(10,12)空心圓所示路徑.此外,將基于生物激勵的神經網絡應用于移動機器人的環境建模中,雖然能夠準確地表達環境信息,并根據機器人的遍歷狀態進行實時更新,但機器人每移動一個位置整個環境模型需更新一次,計算量太大,尤其是當機器人陷入死鎖點后,為了讓目標點活性充分傳播,需要多次更新后才能產生可行路徑,因此當機器人工作區域較大、環境模型中的神經元數量較多時,該算法的運行效率急劇下降.

圖3 基于神經網絡模型的路徑規劃Fig.3 Path planning based on the neural network model

而無人水面艇的作業區域大多為島礁海域,這類區域范圍較大,障礙物數量多,且外形復雜,極易陷入死鎖,因此文獻[10]提出的完全遍歷路徑規劃方法不適用于無人水面艇在島礁海域的測繪.

2 主動方向的動態柵格法與啟發式搜索算法

本工作針對無人水面艇對島礁海域進行掃測時的難點,以及文獻[10]所提出算法的不足,提出了一種考慮主動方向的動態柵格法[13-14]與啟發式搜索算法,即在建立環境模型時融合了神經網絡方法能動態描述環境信息的特點,并優化了其活性傳遞過程,降低了計算量;結合優先級啟發式算法和A*啟發式搜索算法(A*算法)[15-16],規劃出的路徑重復率低,在陷入死鎖點時能夠快速產生走出死鎖點的最優路徑.本算法中遍歷路徑在避開障礙物的同時考慮路徑最短,規劃效率高,能夠處理的環境范圍大.通過仿真對比表明,本算法比文獻[10]提出的算法在多個性能評價指標上得到了提升.

2.1 基于動態柵格法的環境建模

根據所選待掃測區域的大小、島礁分布信息以及無人水面艇的掃測寬度,本工作基于動態柵格法將無人水面艇的工作空間分解成一系列具有屬性信息的柵格(見圖4).

當無人水面艇未掃測時,環境模型中的柵格只有2種屬性狀態:障礙物區域活性為?1,待掃測區域活性為1.無人水面艇進行掃測后,將已掃測區域的活性值賦為0.在無人水面艇的整個掃測過程中,環境模型可以描述如下:

式中,Xi為對應柵格點的活性值.

圖4 基于動態柵格法的環境模型Fig.4 Environmental model based on dynamic grids algorithm

由圖4和式(7)可知,在無人水面艇的掃測過程中,環境模型的更新只需要將無人水面艇已掃測的柵格點對應的活性值設為0,而不需要進行類似神經網絡模型的所有神經元的迭代計算,減小了計算量.同時,基于該環境模型使用文獻[10]提出的路徑點選擇方法并無太大影響,只是在陷入死鎖、走出死鎖點時需要借助A*搜索算法,使得規劃速度更快,路徑更優.

2.2 優先級啟發式算法

在完成環境建模后,需要無人水面艇通過不斷選擇下一掃測柵格的方式,形成一條完全覆蓋路徑.Yang等[10]提出的柵格節點選擇算法,在環境模型簡單的情況下能夠取得較好的遍歷效果,而對于島礁海域這類外形復雜區域則效果不佳.為了處理復雜的環境模型,本工作提出了優先級啟發式算法,以優先級作為啟發式函數,決定相鄰柵格中實施遍歷規劃的子目標.本方法簡單、直觀且有效,不僅可以降低遍歷的重復率,而且能夠很好地滿足無人水面艇對掃描式掃測路徑的要求.具體實現過程如下.

對環境模型中的某個柵格來說,可行柵格為其他鄰域內的上、下、左、右、左上、左下、右上、右下8個柵格.對于以縱向為主要掃測方向的無人水面艇來說,優先級定義依次為上柵格X t、下柵格X b、左柵格Xl,其余柵格優先級相同;當上、下、左方向的3個柵格存在屬性均小于等于0,而其余柵格存在屬性大于0時,按照式(4)進行選擇.當以水平方向為主要掃測方向時,優先級定義依次為左柵格Xl、右柵格Xr、上柵格Xt,其余柵格優先級相同.

以縱向為主運動方向的優先級啟發式路徑規劃示意圖如圖5所示.假定當前柵格為Xc時,則根據優先級定義,首先搜索Xt,從圖中可知Xt已被掃測;然后搜索X l,同樣可知Xl已被掃測;然后搜索Xb,若Xb未掃測,則將Xb即P1作為下一柵格節點.當P1成為當前柵格節點后,同樣按照優先級定義對周圍柵格節點進行選擇,此時上、左柵格均已掃測,下柵格為障礙物柵格,上、下、左柵格的存在屬性均小于等于0,而其余柵格存在屬性大于0,故按照式(4)進行選擇,選擇結果為將柵格P2作為下一遍歷柵格;同理,進行新一輪的路徑規劃,依次遍歷P3,P4等柵格.

2.3 A*啟發式搜索算法

基于動態柵格法建立的環境模型,具有數據處理量大、易于實現的優點,但同時不可避免地會出現路徑規劃中常見的問題——死鎖,尤其對于島礁海域這類復雜環境.本工作基于動態柵格地圖,結合A*啟發式搜索算法,較好地解決了死鎖問題.

圖5 以縱向為主運動方向的優先級啟發式路徑規劃示意圖Fig.5 Path planning diagram using priority level heuristic searching in vertical reciprocating main motion direction

(1)搜索臨時目標點.

當無人水面艇陷入死鎖點,需要通過A*算法走出死鎖點時,必須先確立一個臨時目標點.本工作采用的搜索臨時目標點的方法如下(以縱向為主要掃測方向為例):首先,從當前柵格地圖的第1列開始搜索,找到出現未掃測柵格的最左列,記為L;再對第L列進行搜索,找到位于該列最上方和最下方的未掃測柵格,分別記為P1,P2;比較P1,P2與無人水面艇當前所處柵格位置之間的距離,取距離較小的點作為臨時目標點.如圖6所示,虛線表示無人水面艇已掃測軌跡,無人水面艇在柵格P處陷入死鎖,然后搜索到最左列未掃測柵格P1,P2,經過與死鎖柵格P的距離對比后,確定將P1點作為臨時目標點.

圖6 A*算法搜索的最優路徑示意圖Fig.6 Diagram of optimal path generated by A*search algorithm

(2)建立代價地圖.

在確定臨時目標點后,還需要建立供A*算法搜索用的代價地圖.由于無人水面艇走出死鎖點時處于非工作狀態,不需要執行掃測任務,故在代價地圖中不需要區分已掃測柵格和未掃測柵格,只需區別障礙物區域和非障礙物區域,且該代價地圖只需構建一次,便可重復調用.

建立代價地圖的規則如下:對于非障礙物柵格,只考慮其與鄰域內8個柵格的距離代價,且默認相同,都為1;對于障礙物柵格,為了避免搜索時將其作為可擴展點,故設置一個較大代價值進行區分,代價值設為10 000.根據當前點、臨時目標點的位置信息,以及代價地圖,利用A*算法即可搜索得到一條從死鎖點到臨時目標點的無碰撞、最短路徑.

(3)利用A*算法搜索最短路徑.

A*算法是一種靜態路網中求解最短路徑最有效的直接搜索方法,也是常用的啟發式算法. A*算法的估價函數為式中:f(n)為經過柵格n的搜索路徑對應的總代價值;g(n)為從初始柵格到柵格n的實際代價,g(n)的值可根據代價地圖經過搜索后不斷迭代更新得到.啟發函數h(n)為從柵格n到臨時目標柵格的估計代價值.

啟發函數h(n)能夠控制A*算法的行為,如果h(n)總是小于或等于從柵格n到目標柵格的實際代價值,那么A*算法總能確保找到最短路徑,同時h(n)值越小,擴展的柵格就越多,搜索效率越低;如果h(n)的值大于實際代價值,則A*算法不能保證找到最短路徑,運行速度較快.考慮到島礁海域環境的復雜性,以及使用優先級啟發式算法陷入死鎖時的情況,本工作選取曼哈頓距離作為啟發函數,即利用A*算法搜索最優路徑的過程如圖6所示,柵格節點內的數值表示的是搜索得到的代價值f(n),從圖中可以發現,搜索得到的最終路徑為P—n3—n7—n10—P,該路徑也是無人水面艇走出當前死鎖點的最優路徑.同時觀察已搜索點與未搜索點(標記為“N”)的數量和分布可以發現,該算法搜索效率高,有利于提升完全遍歷路徑規劃的整體速度.

2.4 性能評價指標

評價無人水面艇工作效率的性能指標[17]與清潔機器人類似,主要有掃測面積百分率、運動軌跡重疊率等.

用Sw表示無人水面艇工作范圍內的待掃測區域的面積,Sc表示無人水面艇已掃測的面積,St表示無人水面艇經過的柵格的面積.

掃測面積百分率是指作業完成后已掃測區域與待掃測區域面積的百分比:

運動軌跡重疊率是指所有經過但未作業面積之和與待掃測區域面積的百分比:

本工作主要結合遍歷路徑長度、轉彎數、掃測面積百分率和運動軌跡重疊率等指標綜合評價完全遍歷路徑規劃算法.如果轉彎數越少、掃測面積百分率越高、運動軌跡重疊率越低,則作業效果越好、效率越高.

3 仿真驗證

本工作將遍歷路徑規劃算法應用于無人水面艇的路徑規劃,并且模擬了具有較為典型的島礁障礙物特征的環境信息,用于比較本算法與文獻[10]所提算法的各個性能指標,以驗證本工作提出算法的有效性.

圖7(a)和(b)分別為文獻[10]算法和本算法對同一環境情形規劃出的路徑.整個柵格地圖大小為30×30,標有“O”形標識的為障礙物區域;無人水面艇的初始位置為“S”標識處,坐標為(1,1),終點位置為“F”標識處,坐標為(30,21);箭頭指示無人水面艇的移動方向,空心圓表示無人水面艇重復經過的路徑點.表1為對這組仿真數據的各個性能指標的綜合對比,性能指標包括遍歷路徑長度、轉彎數、掃測面積百分率和運動軌跡重疊率等.

圖7 復雜環境下的路徑規劃仿真Fig.7 Path planning simulation in complicated environments

表1 仿真結果比較Table 1 Comparisons of simulation results

由表1可知,兩種算法規劃后的掃測面積百分率均為100%,說明兩種算法均能完全遍歷所有的可行區域;但是本算法相對文獻[10]所提算法在遍歷路徑長度、轉彎數、運動軌跡重疊率等性能指標方面均有提升,尤其是轉彎數,減少了55.6%.在環境地圖相同的情況下,遍歷路徑長度與運動軌跡重疊率是兩個相關變量,遍歷路徑越長,運動軌跡重疊率就越高.從圖7中可以看出,文獻[10]所提算法中這兩個性能指標較高的原因主要在于走出死鎖點(30,1)的路徑并非最優路徑,而本算法搜索出的路徑即為最優路徑.轉彎數這一性能指標能反映出規劃路徑的有序性,在圖7中也能體現,本算法規劃出的路徑明顯更合理、有序,滿足無人水面艇對島礁區域掃測時的路徑需求,有利于測繪圖像的后期處理.

仿真實驗證明,本算法在遍歷路徑長度、轉彎數、運動軌跡重疊率等性能指標上明顯優于文獻[10]所提算法,且規劃出的路徑更為合理有效.

4 結束語

本工作以無人水面艇對島礁海域地形地貌的測繪為背景,引出了對島礁海域自主測繪時存在的任務計算量大、場景復雜等難點.經過實驗及分析發現,文獻[10]中的基于神經網絡模型的遍歷路徑規劃方法并不能解決島礁海域自主測繪時存在的這些問題.因此,本工作提出了一種考慮主動方向的動態柵格法與啟發式搜索算法,本算法在復雜環境情況下能完全遍歷任務區域,且算法計算量小,規劃出的路徑重復率低,在陷入死鎖時能夠快速搜索出走出死鎖點的最優路徑.

與文獻[10]所提算法進行仿真比較,結果表明本算法在多個性能指標上均優于文獻[10]所提算方法,且規劃出的路徑更為合理有效,滿足無人水面艇對島礁區域進行測繪時的路徑需求.

[1]周玉坤.基于GNSS及物探方法的近海島礁勘測技術研究[D].沈陽:東北大學,2014.

[2]PETILLOT Y R,REED S R,BELL J M.Real time AUV pipeline detection and tracking using side scan sonar and multi-beam echo-sounder[C]//Oceans.2002:217-222.

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

[4]YAN M Z,ZHu D Q.An algorithm of complete coverage path planning for autonomous underwater vehicles[J].Key Engineering Materials,2011,467/468/469:1377-1385.

[5]DECARVALHO R N,VIDAL H A,VIEIRA P,et al.Complete coverage path planning and guidance for cleaning robots[C]//IEEE International Symposium on Industrial Electronics.1998:677-682.

[6]Wu J H,QIN T D,CHEN J,et al.Complete coverage path planning and obstacle avoidance strategy of the robot[J].Advanced Materials Research,2014,756/757/758/759:497-503.

[7]MCCuLLOCH W S,PITTs W.A logical calculus of the ideas immanent in nervous activity[M]. Cambridge:The MIT Press,1943:115-133.

[8]HODGKIN A L,HuXLEY A F.A quantitative description of membrane current and its application to conduction and excitation in nerve[J].Bulletin of Mathematical Biology,1990,117(1):500-544.

[9]STEPHEN G.Nonlinear neural networks:principles,mechanisms,and architectures[J].Neural Networks,1988,1(1):17-61.

[10]YANG S X,LuO C.A neural network approach to complete coverage path planning[J].IEEE Transactions on Systems Man&Cybernetics Part B Cybernetics A,2004,34(1):718-725.

[11]邱雪娜,劉士榮,俞金壽,等.移動機器人的完全遍歷路徑規劃:生物激勵與啟發式模板方法[J].模式識別與人工智能,2006,19(1):122-128.

[12]邱雪娜,劉士榮,宋加濤,等.不確定動態環境下移動機器人的完全遍歷路徑規劃[J].機器人,2006, 28(6):586-592.

[13]王妹婷,齊永鋒,陸柳延,等.雙向清洗機器人玻璃幕墻完全遍歷路徑規劃[J].機械設計與制造, 2013(11):211-213.

[14]LIu X,QIN N,XIA H.Fast dynamic grid deformation based on Delaunay graph mapping[J]. Journal of Computational Physics,2006,211(2):405-423.

[15]RICHARDs N,SHARMA M,WARD D.A hybrid A*/automaton approach to on-line path planning with obstacle avoidance[C]//AIAA 1st,Intelligent Systems Technical Conference.2004:6629.

[16]CANNY J.The complexity of robot motion planning[M].Cambridge:The Mit Press,1987: 27-32.

[17]CHOsET H.Coverage for robotics—a survey of recent results[J].Annals of Mathematics and Artifcial Intelligence,2001,31(1):113-126.

Complete coverage path planning of USV used for mapping round island

ZHONG Yuxuan,GE Lei,ZHANG Xin,PENG Yan,YANG Yi,LI Xiaomao
(School of Mechatronic Engineering and Automation,Shanghai University,Shanghai 200072,China)

When mapping the seabed around islands independently,there are difculties like large amount of calculation and complex task scene for mapping with an unmanned surface vehicle(USV).To solve the problems,an algorithm composed of a dynamic grids algorithm for main motion direction and a heuristic search algorithm is proposed.This algorithm establishes an environmental model based on the dynamic grids algorithm.The heuristic algorithm based on priority is used to choose an appropriate path point to travel. When the USV getting into a deadlock,an optimal path is generated with the heuristic search algorithm to get out.Simulation results show that performance of path planning is improved with the proposed algorithm.The planned path is more reasonable and efective to meet the needs when using USV to map the seabed around an island.

unmanned surface vehicle(USV);path planning;dynamic grids algorithm; heuristic algorithm based on priority;heuristic search algorithm

TP 242.6

A

1007-2861(2017)01-0017-10

10.3969/j.issn.1007-2861.2016.07.020

2017-01-04

國家自然科學基金資助項目(61403245,51675318,61673254);上海市科委能力建設資助項目(14500500400)

李小毛(1981—),男,研究員,研究方向為圖像處理、雷達數據處理、無人艇環境感知、導航和控制及其總體技術.E-mail:lixiaomao@shu.edu.cn