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

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

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

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

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

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

無人水面艇;路徑規(guī)劃;動態(tài)柵格法;優(yōu)先級啟發(fā)式算法;啟發(fā)式搜索算法

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

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

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

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

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

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

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

1 基于神經(jīng)網(wǎng)絡(luò)模型的路徑規(guī)劃

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

1.1 生物激勵的神經(jīng)網(wǎng)絡(luò)模型

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

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

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

圖2(a)～(c)分別為機器人運動過程中的神經(jīng)網(wǎng)絡(luò)環(huán)境模型,波峰為未遍歷區(qū)域,波谷為障礙物區(qū)域,介于波峰與波谷之間的為已遍歷區(qū)域.圖2(a)為未遍歷前的環(huán)境模型初始狀態(tài),式(1)表示的活性傳遞方式能夠保證未遍歷區(qū)域與障礙物區(qū)域?qū)?yīng)的活性值分別位于波峰和波谷.圖2(b),(c)分別為遍歷過程中和遍歷后的環(huán)境模型.

1.2 遍歷路徑規(guī)劃算法

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

圖2 基于神經(jīng)網(wǎng)絡(luò)的環(huán)境模型Fig.2 Environmental model based on neural network

式中,c為正常數(shù),k為當前位置鄰域內(nèi)神經(jīng)元的總數(shù),

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

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

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

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

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

圖3 基于神經(jīng)網(wǎng)絡(luò)模型的路徑規(guī)劃Fig.3 Path planning based on the neural network model

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

2 主動方向的動態(tài)柵格法與啟發(fā)式搜索算法

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

2.1 基于動態(tài)柵格法的環(huán)境建模

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

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

式中,Xi為對應(yīng)柵格點的活性值.

圖4 基于動態(tài)柵格法的環(huán)境模型Fig.4 Environmental model based on dynamic grids algorithm

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

2.2 優(yōu)先級啟發(fā)式算法

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

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

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

2.3 A*啟發(fā)式搜索算法

基于動態(tài)柵格法建立的環(huán)境模型,具有數(shù)據(jù)處理量大、易于實現(xiàn)的優(yōu)點,但同時不可避免地會出現(xiàn)路徑規(guī)劃中常見的問題——死鎖,尤其對于島礁海域這類復雜環(huán)境.本工作基于動態(tài)柵格地圖,結(jié)合A*啟發(fā)式搜索算法,較好地解決了死鎖問題.

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

(1)搜索臨時目標點.

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

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

(2)建立代價地圖.

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

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

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

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

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

2.4 性能評價指標

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

用Sw表示無人水面艇工作范圍內(nèi)的待掃測區(qū)域的面積,Sc表示無人水面艇已掃測的面積,St表示無人水面艇經(jīng)過的柵格的面積.

掃測面積百分率是指作業(yè)完成后已掃測區(qū)域與待掃測區(qū)域面積的百分比:

運動軌跡重疊率是指所有經(jīng)過但未作業(yè)面積之和與待掃測區(qū)域面積的百分比:

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

3 仿真驗證

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

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

圖7 復雜環(huán)境下的路徑規(guī)劃仿真Fig.7 Path planning simulation in complicated environments

表1 仿真結(jié)果比較Table 1 Comparisons of simulation results

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

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

4 結(jié)束語

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

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

[1]周玉坤.基于GNSS及物探方法的近海島礁勘測技術(shù)研究[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]邱雪娜,劉士榮,俞金壽,等.移動機器人的完全遍歷路徑規(guī)劃:生物激勵與啟發(fā)式模板方法[J].模式識別與人工智能,2006,19(1):122-128.

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

[13]王妹婷,齊永鋒,陸柳延,等.雙向清洗機器人玻璃幕墻完全遍歷路徑規(guī)劃[J].機械設(shè)計與制造, 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);上海市科委能力建設(shè)資助項目(14500500400)

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