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

鐘雨軒,葛磊,張?chǎng)?彭艷,楊毅,李小毛

(上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院,上海 200072)

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

鐘雨軒,葛磊,張?chǎng)?彭艷,楊毅,李小毛

(上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院,上海 200072)

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

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

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

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

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

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

圖1 無(wú)人水面艇金塘大橋測(cè)繪GUI圖Fig.1 Mapping GUI of USV in the Jintang Bridge

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

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

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

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

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

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

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

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

圖2(a)～(c)分別為機(jī)器人運(yùn)動(dòng)過(guò)程中的神經(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)分別為遍歷過(guò)程中和遍歷后的環(huán)境模型.

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

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

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

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

其中?θj為機(jī)器人在當(dāng)前時(shí)刻與下一時(shí)刻方向角改變量的絕對(duì)大小,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對(duì)環(huán)境模型中的某個(gè)柵格來(lái)說(shuō),可行柵格為其他鄰域內(nèi)的上、下、左、右、左上、左下、右上、右下8個(gè)柵格.對(duì)于以縱向?yàn)橹饕獟邷y(cè)方向的無(wú)人水面艇來(lái)說(shuō),優(yōu)先級(jí)定義依次為上柵格X t、下柵格X b、左柵格Xl,其余柵格優(yōu)先級(jí)相同;當(dāng)上、下、左方向的3個(gè)柵格存在屬性均小于等于0,而其余柵格存在屬性大于0時(shí),按照式(4)進(jìn)行選擇.當(dāng)以水平方向?yàn)橹饕獟邷y(cè)方向時(shí),優(yōu)先級(jí)定義依次為左柵格Xl、右柵格Xr、上柵格Xt,其余柵格優(yōu)先級(jí)相同.

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

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

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

圖5 以縱向?yàn)橹鬟\(yùn)動(dòng)方向的優(yōu)先級(jí)啟發(fā)式路徑規(guī)劃示意圖Fig.5 Path planning diagram using priority level heuristic searching in vertical reciprocating main motion direction

(1)搜索臨時(shí)目標(biāo)點(diǎn).

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

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

(2)建立代價(jià)地圖.

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

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

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

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

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

2.4 性能評(píng)價(jià)指標(biāo)

評(píng)價(jià)無(wú)人水面艇工作效率的性能指標(biāo)[17]與清潔機(jī)器人類似,主要有掃測(cè)面積百分率、運(yùn)動(dòng)軌跡重疊率等.

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

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

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

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

3 仿真驗(yàn)證

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

[13]王妹婷,齊永鋒,陸柳延,等.雙向清洗機(jī)器人玻璃幕墻完全遍歷路徑規(guī)劃[J].機(jī)械設(shè)計(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61403245,51675318,61673254);上海市科委能力建設(shè)資助項(xiàng)目(14500500400)

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