金 震 黃衛(wèi)華 李傳奇 何佳樂(lè)

(*武漢科技大學(xué)機(jī)器人與智能系統(tǒng)研究院 武漢430081）

(**武漢科技大學(xué)冶金自動(dòng)化與檢測(cè)技術(shù)教育部工程研究中心 武漢430081）

(***武漢科技大學(xué)信息科學(xué)與工程學(xué)院 武漢430081）

0 引言

移動(dòng)機(jī)器人的路徑規(guī)劃是指機(jī)器人遵循一些優(yōu)化指標(biāo)(比如時(shí)間最短、路程最優(yōu)和能耗最低等),在具有障礙物的環(huán)境中尋找一條從起始狀態(tài)到目標(biāo)狀態(tài)的無(wú)碰撞路徑[1]。在圖搜索類全局路徑搜索算法中,A*算法是一種較為穩(wěn)定的啟發(fā)式路徑算法,已廣泛應(yīng)用于路徑規(guī)劃領(lǐng)域。然而,A*算法在每步評(píng)價(jià)過(guò)程中,均會(huì)查詢open 列表和close 列表中節(jié)點(diǎn)的狀態(tài),導(dǎo)致A*算法搜索效率較低,尤其是當(dāng)環(huán)境存在對(duì)稱路徑時(shí),A*算法耗費(fèi)代價(jià)大,影響路徑規(guī)劃的實(shí)時(shí)性。2011 年,文獻(xiàn)[2]提出了跳點(diǎn)搜索(jump point search,JPS)算法。在路徑搜索中,JPS 算法刪減大量的對(duì)稱性中間節(jié)點(diǎn)和無(wú)用節(jié)點(diǎn),保留了具有代表性的跳點(diǎn),從而減少不必要的搜索路徑,由此改善A*算法小步移動(dòng)的缺點(diǎn),有效提高了路徑搜索效率[3]。

在應(yīng)用過(guò)程中,JPS 算法簡(jiǎn)單且高效,但其適用于具有一定規(guī)律、大開(kāi)放區(qū)域的地圖進(jìn)行路徑規(guī)劃,也就是通過(guò)在矩形區(qū)域內(nèi)跳過(guò)大量對(duì)稱路徑,尋找關(guān)鍵跳點(diǎn)作為路徑搜索的節(jié)點(diǎn)。為進(jìn)一步提高JPS算法的性能,學(xué)者們提出了改進(jìn)方法。文獻(xiàn)[4]針對(duì)移動(dòng)機(jī)器人在復(fù)雜環(huán)境下對(duì)智能性、高效性和可靠性的要求,提出了一種“塊”操作方法以加快搜索跳點(diǎn)的速度,并刪減了一部分僅代表路徑方向發(fā)生改變的中間轉(zhuǎn)折節(jié)點(diǎn)。文獻(xiàn)[5]針對(duì)JPS 算法規(guī)劃的路徑可能存在碰撞的問(wèn)題,將跳點(diǎn)進(jìn)行危險(xiǎn)度評(píng)估,改進(jìn)了跳點(diǎn)的篩選方式,并且對(duì)障礙物進(jìn)行膨化處理,從而降低了平均危險(xiǎn)碰撞度。文獻(xiàn)[6]改進(jìn)了JPS 的搜索規(guī)則,以得到更多具有價(jià)值的路徑并使用多段高階多項(xiàng)式對(duì)所得路徑進(jìn)行軌跡優(yōu)化。文獻(xiàn)[7]針對(duì)JPS 算法存在路徑搜索時(shí)間長(zhǎng)等問(wèn)題,提出了一種雙向跳點(diǎn)搜索算法,從正、反兩個(gè)方向采用改進(jìn)的JPS 算法交替進(jìn)行路徑搜索。綜合上述研究,JPS 算法主要是通過(guò)改進(jìn)修剪規(guī)則和跳躍規(guī)則體現(xiàn)其優(yōu)于A*算法的路徑搜索效率。然而,相比于A*算法,JPS 算法在圖裁剪的過(guò)程中往往需要評(píng)估更多的障礙物,尤其是當(dāng)其所規(guī)劃的路徑過(guò)于靠近障礙物,常規(guī)對(duì)角線的跳躍方式極易發(fā)生碰撞,搜索到的路徑存在一定的安全隱患;此外,當(dāng)?shù)貓D規(guī)模較大或?qū)ΨQ性路徑較少的時(shí)候,JPS 算法存在搜索到的跳點(diǎn)多且混亂的問(wèn)題,一定程度上影響了路徑搜索的效率。

考慮JPS 算法和A*算法的特點(diǎn),本文提出了一種基于改進(jìn)JPS 算法和A*算法的組合規(guī)劃算法。首先,針對(duì)JPS 算法的跳點(diǎn)篩選規(guī)則進(jìn)行改進(jìn)并刪除冗余的中間跳點(diǎn),同時(shí)禁止機(jī)器人對(duì)角線穿越障礙物,并通過(guò)所設(shè)計(jì)的安全性評(píng)估模型保證搜索路徑的安全性。然后,考慮到環(huán)境地圖中具有對(duì)稱性和非對(duì)稱性路徑規(guī)劃的問(wèn)題,設(shè)計(jì)了跳點(diǎn)閾值函數(shù),構(gòu)成基于改進(jìn)JPS 和A*的組合路徑規(guī)劃算法。最后,仿真實(shí)驗(yàn)結(jié)果證明了本文所設(shè)計(jì)組合路徑規(guī)劃算法的可行性和有效性。

1 JPS 算法簡(jiǎn)介

JPS 算法是一種啟發(fā)式路徑規(guī)劃算法,它保留了A*算法的基本結(jié)構(gòu),其不同點(diǎn)在于搜索路徑過(guò)程中對(duì)后繼節(jié)點(diǎn)拓展策略。相比于A*算法,JPS算法并非直接獲取當(dāng)前節(jié)點(diǎn)的所有非關(guān)閉的可達(dá)鄰居節(jié)點(diǎn)作為后繼節(jié)點(diǎn),而是根據(jù)當(dāng)前節(jié)點(diǎn)的方向和強(qiáng)迫鄰居修剪規(guī)則確定后繼節(jié)點(diǎn)的拓展策略,通過(guò)裁減無(wú)意義的節(jié)點(diǎn)及保留特殊節(jié)點(diǎn),提高全局路徑搜索的效率。

1.1 跳點(diǎn)篩選規(guī)則

根據(jù)節(jié)點(diǎn)周?chē)欠翊嬖谡系K物,JPS 算法的跳點(diǎn)篩選規(guī)則分為兩種情況:自然鄰居篩選規(guī)則和強(qiáng)制鄰居篩選規(guī)則。

1.1.1 自然鄰居篩選規(guī)則

在圖1 所示的柵格地圖中,灰色柵格表示可裁減節(jié)點(diǎn)。假設(shè)路徑搜索到了節(jié)點(diǎn)x處,該節(jié)點(diǎn)的父節(jié)點(diǎn)為p(x),p(x) 到x的方向?yàn)閿U(kuò)展節(jié)點(diǎn)的當(dāng)前方向。圖1 為自然鄰居的篩選規(guī)則,主要有直線方向和對(duì)角線方向的篩選方式。

圖1 自然鄰居篩選規(guī)則

如圖1(a)所示,父節(jié)點(diǎn)p(x) 到x為水平方向,故此時(shí)x的擴(kuò)展方向?yàn)橹本€方向。若p(x) 要到達(dá)節(jié)點(diǎn)n,虛線和實(shí)線的路徑代價(jià)相同,即p(x) 可以不經(jīng)過(guò)節(jié)點(diǎn)x到達(dá)節(jié)點(diǎn)n且代價(jià)不會(huì)增加,則稱n為可裁減節(jié)點(diǎn)。根據(jù)以上規(guī)則,除了白色節(jié)點(diǎn)q之外的其他節(jié)點(diǎn)均可被裁減,則稱節(jié)點(diǎn)q為節(jié)點(diǎn)x的自然鄰居。

如圖1(b)所示,x的擴(kuò)展方向?yàn)閷?duì)角線方向,p(x) 不經(jīng)過(guò)節(jié)點(diǎn)x到達(dá)n的路徑最短(圖中虛線所示為最短路徑)。同樣的,白色節(jié)點(diǎn)為自然鄰居,其他節(jié)點(diǎn)均可被裁減。

1.1.2 強(qiáng)制鄰居篩選規(guī)則

強(qiáng)制鄰居篩選規(guī)則如圖2 所示,黑色柵格為障礙物,其他均為可行走節(jié)點(diǎn)。不管當(dāng)前方向?yàn)橹本€方向還是對(duì)角線方向,均不存在任何一條路徑使得p(x) 到n不經(jīng)過(guò)節(jié)點(diǎn)x為最短路徑,即圖中的實(shí)線為最短路徑,則定義n為x的強(qiáng)制鄰居,x為n的跳點(diǎn)。

圖2 強(qiáng)制鄰居篩選規(guī)則

1.2 評(píng)價(jià)函數(shù)

JPS 算法尋路時(shí),對(duì)每一個(gè)加入open 列表中的跳點(diǎn)進(jìn)行評(píng)估,選擇代價(jià)最小的跳點(diǎn)作為下一父節(jié)點(diǎn),通過(guò)不斷地迭代直到擴(kuò)展到目標(biāo)點(diǎn)。JPS 算法的評(píng)價(jià)函數(shù)如式(1)所示。

式中,f(n) 為從起始節(jié)點(diǎn)經(jīng)過(guò)當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的評(píng)價(jià)函數(shù),g(n) 是起始節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)函數(shù),h(n) 為當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最小代價(jià)函數(shù)。

在二維空間中,一般采用歐式距離計(jì)算g(n),即:

式中,(X(n),Y(n)) 為當(dāng)前跳點(diǎn)n的位置,(X(n-1),Y(n -1)) 為上一跳點(diǎn)的位置。

對(duì)于h(n) 而言,常見(jiàn)最小代價(jià)函數(shù)的計(jì)算方式有曼哈頓距離、切比雪夫距離和歐式距離[8],本文采取歐氏距離計(jì)算h(n),即:

式中,(X(n +1),Y(n +1)) 為目標(biāo)節(jié)點(diǎn)的位置。

1.3 JPS 算法尋路

圖3 為JPS 算法的尋路過(guò)程,其中S為起始點(diǎn),D為目標(biāo)點(diǎn),陰影柵格為篩選后留下的跳點(diǎn)。起始點(diǎn)S的當(dāng)前方向?yàn)榭?則沿著8 個(gè)方向擴(kuò)展搜索跳點(diǎn)。從S出發(fā)只有下、右、右下3 個(gè)方向可走,但向右搜索遇到邊界,向下搜索至障礙物,右下方向搜索到跳點(diǎn)M。將M作擴(kuò)展節(jié)點(diǎn)繼續(xù)搜索,M的當(dāng)前方向?yàn)閷?duì)角線方向,但此時(shí)可走的方向只有向右,向右搜索到跳點(diǎn)W。節(jié)點(diǎn)W的當(dāng)前方向?yàn)樗椒较?沿右、右下2 個(gè)方向搜索到跳點(diǎn)V。節(jié)點(diǎn)V沿著當(dāng)前方向搜索到L,L繼續(xù)搜索直至目標(biāo)點(diǎn)D,順著父節(jié)點(diǎn)回溯到起始點(diǎn)便得到了最終路徑。

圖3 JPS 算法尋路過(guò)程

2 改進(jìn)JPS 算法的設(shè)計(jì)

在路徑搜索的過(guò)程中,JPS 算法可優(yōu)化A*算法尋找后繼節(jié)點(diǎn)的操作,它是根據(jù)當(dāng)前節(jié)點(diǎn)的方向和鄰居節(jié)點(diǎn)的特性跳過(guò)其他多余的節(jié)點(diǎn),由此省略了重復(fù)多余的計(jì)算過(guò)程。然而,JPS 算法所規(guī)劃路徑往往過(guò)于靠近障礙物,易產(chǎn)生碰撞甚至橫穿障礙物的情況,從而影響路徑的安全性;其次,當(dāng)大規(guī)模地圖中存在不對(duì)稱的情況時(shí),JPS 算法會(huì)找到過(guò)多的跳點(diǎn),同時(shí)也會(huì)不斷地操作open 列表和close 列表中的節(jié)點(diǎn),導(dǎo)致路徑搜索效率降低。針對(duì)移動(dòng)機(jī)器人在對(duì)角線穿越障礙物時(shí),可能會(huì)發(fā)生一定的碰撞而影響尋路過(guò)程中的安全性,本文通過(guò)修改冗余節(jié)點(diǎn)刪減規(guī)則和跳點(diǎn)篩選規(guī)則,改善JPS 算法路徑尋優(yōu)的性能。

2.1 冗余跳點(diǎn)的刪除

JPS 算法中跳點(diǎn)可以分為兩種:至少有一個(gè)強(qiáng)迫鄰居的跳點(diǎn)和沒(méi)有強(qiáng)迫鄰居的跳點(diǎn)[9]。前一種類型的跳點(diǎn)至少相鄰一個(gè)障礙物,并且它們?cè)趦蓚€(gè)不相鄰的節(jié)點(diǎn)之間至少有一條最佳路徑。如果刪除這些跳點(diǎn),很有可能導(dǎo)致算法不能返回最優(yōu)路徑。而后一種類型的跳點(diǎn)不與任何障礙物相鄰,即中間跳點(diǎn),該跳點(diǎn)只作為轉(zhuǎn)折節(jié)點(diǎn),最優(yōu)路徑選擇時(shí)可以改變方向,到達(dá)前一種跳點(diǎn)或者目標(biāo)節(jié)點(diǎn)。

因此,中間跳點(diǎn)是可以安全修剪的,并且不會(huì)影響算法的最優(yōu)性。如圖4 所示,數(shù)字1、4、6 為中間跳點(diǎn),其他黑色數(shù)字為至少有一個(gè)強(qiáng)迫鄰居的跳點(diǎn)。每個(gè)中間跳點(diǎn)最多有3 個(gè)后繼節(jié)點(diǎn):第1 種是水平可達(dá)的跳點(diǎn),第2 種是垂直可達(dá)的跳點(diǎn),第3 種是不改變方向的情況下可以到達(dá)下一個(gè)中間跳點(diǎn)。當(dāng)修剪中間跳點(diǎn)時(shí),將它的后繼跳點(diǎn)存儲(chǔ)在一個(gè)列表中,并用該后繼者代替中間跳點(diǎn),將這個(gè)過(guò)程不斷遞歸,直至刪除所有中間跳點(diǎn)。

圖4 修剪中間跳點(diǎn)

2.2 跳點(diǎn)篩選規(guī)則的改進(jìn)

改進(jìn)的跳點(diǎn)篩選規(guī)則如圖5 所示。跳點(diǎn)篩選分直線和對(duì)角線方向,鄰節(jié)點(diǎn)裁減規(guī)則不變。直線方向上改進(jìn)的跳點(diǎn)篩選規(guī)則如圖5(a)所示,節(jié)點(diǎn)n是x的強(qiáng)制鄰居,當(dāng)鄰節(jié)點(diǎn)存在障礙物時(shí),改進(jìn)算法是不允許對(duì)角線穿過(guò)障礙物到達(dá)強(qiáng)制鄰居。故從p(x) 到達(dá)節(jié)點(diǎn)n是必須經(jīng)過(guò)節(jié)點(diǎn)x、y的,此時(shí)將x視作普通節(jié)點(diǎn),將節(jié)點(diǎn)y視為跳點(diǎn)進(jìn)行規(guī)劃。

圖5(b)是對(duì)角線方向上改進(jìn)的跳點(diǎn)篩選規(guī)則,若不能以對(duì)角線穿過(guò)障礙物,p(x) 必須經(jīng)過(guò)節(jié)點(diǎn)y、x、z才能到達(dá)節(jié)點(diǎn)n,此時(shí)將x視為普通節(jié)點(diǎn),y和z當(dāng)做跳點(diǎn)。

圖5 改進(jìn)跳點(diǎn)篩選規(guī)則

2.3 安全性評(píng)估模型設(shè)計(jì)

為了評(píng)估所搜尋跳點(diǎn)的安全性,在JPS 算法中引入安全性評(píng)估函數(shù)對(duì)求解路徑的安全性進(jìn)行評(píng)估。本文采用二維高斯模型構(gòu)建跳點(diǎn)安全性評(píng)估模型,包括平均碰撞度和碰撞度函數(shù),分別如式(4)、(5)所示。

FT為平均碰撞度,O為影響范圍內(nèi)障礙物的個(gè)數(shù),I為求解路徑的節(jié)點(diǎn)個(gè)數(shù)。T為碰撞度函數(shù),(xi,yi) 和(xo,yo) 分別是路徑節(jié)點(diǎn)坐標(biāo)和障礙物坐標(biāo),ρ((xi,yi),(xo,yo)) 是路徑當(dāng)前節(jié)點(diǎn)到最近障礙物的距離,do是障礙物影響范圍,與機(jī)器人本身的模型有關(guān),α、β決定碰撞對(duì)機(jī)器人造成危險(xiǎn)的程度,由機(jī)器人的速率以及障礙物的材質(zhì)決定。

3 改進(jìn)JPS 和A*組合路徑規(guī)劃算法

JPS 算法不是從相鄰節(jié)點(diǎn)中選擇下一個(gè)節(jié)點(diǎn),而是跳過(guò)大量可能會(huì)添加到open 列表和close 列表中的中間節(jié)點(diǎn),旨在消除路徑間的對(duì)稱性,提高搜索效率[10]。但是,當(dāng)尋路過(guò)程中存在障礙物稠密區(qū)域且存在非對(duì)稱路徑時(shí),相比于A*算法只需要從open 列表中選擇具有最小代價(jià)函數(shù)值的節(jié)點(diǎn),JPS算法每生成一個(gè)節(jié)點(diǎn)就需要尋找一個(gè)跳躍點(diǎn),對(duì)于下一個(gè)節(jié)點(diǎn)的選擇過(guò)程需要更多處理時(shí)間,此時(shí),JPS 算法的尋路代價(jià)大,且規(guī)劃的路徑存在一定的安全隱患。因此,本文將所設(shè)計(jì)的改進(jìn)JPS 算法與A*相結(jié)合,根據(jù)由地圖環(huán)境的復(fù)雜度信息確定的跳點(diǎn)閾值函數(shù)選擇不同的路徑搜索規(guī)則。通過(guò)組合路徑規(guī)劃算法,一方面利用改進(jìn)JPS 算法裁減掉對(duì)稱路徑搜索過(guò)程中的無(wú)意義節(jié)點(diǎn),減少節(jié)點(diǎn)擴(kuò)展的數(shù)量;另一方面基于A*算法有效避免復(fù)雜路徑搜索過(guò)程中存在的安全隱患,提高路徑搜索效率。

3.1 跳點(diǎn)閾值函數(shù)的設(shè)計(jì)

JPS 算法尋路時(shí),環(huán)境中的障礙物越混亂,擴(kuò)展的跳點(diǎn)數(shù)量越多,搜索效率越低。因此,設(shè)計(jì)了直通率Pe和障礙率Po判斷地圖環(huán)境的復(fù)雜程度。

式(6)中,ne為一行或一列均為無(wú)障礙柵格的條數(shù),R和C為環(huán)境地圖的行數(shù)和列 數(shù)。Pe值越大,環(huán)境的混亂程度越低。式(7)中,no為地圖中障礙物柵格的數(shù)量,N為地圖總柵格的數(shù)量。

環(huán)境的復(fù)雜程度直接影響跳點(diǎn)數(shù)量,從而影響路徑搜索的效率。將路徑搜索一定區(qū)域內(nèi)跳點(diǎn)數(shù)量進(jìn)行量化,記為K,則有

式中,U表示當(dāng)前節(jié)點(diǎn)的搜索范圍,K表示搜索范圍U內(nèi)跳點(diǎn)數(shù)量。

跳點(diǎn)閾值與直通率Pe和障礙率Po有關(guān),地圖環(huán)境越復(fù)雜,跳點(diǎn)就越多。因此,根據(jù)環(huán)境地圖的復(fù)雜度,由式(6)和式(7)定義跳點(diǎn)閾值λ為

因此,改進(jìn)JPS+A*組合規(guī)劃算法的切換條件為:當(dāng)K≥λ時(shí),由改進(jìn)JPS 算法切換為A*算法搜索。

3.2 改進(jìn)JPS+A*組合規(guī)劃算法流程

基于式(9)所定義的跳點(diǎn)閾值函數(shù),將所設(shè)計(jì)的改進(jìn)JPS 與A*算法相結(jié)合,構(gòu)成組合規(guī)劃算法,即當(dāng)跳點(diǎn)數(shù)量較少時(shí),采用JPS 算法規(guī)劃以便快速穿過(guò)對(duì)稱路徑,避免不必要節(jié)點(diǎn)的擴(kuò)展;當(dāng)跳點(diǎn)數(shù)量過(guò)多時(shí),便轉(zhuǎn)換為A*算法進(jìn)行路徑規(guī)劃,安全且高效通過(guò)障礙物稠密的地圖環(huán)境,由此構(gòu)成一條完整的規(guī)劃路徑。改進(jìn)JPS +A*組合規(guī)劃算法流程圖如圖6 所示。

圖6 改進(jìn)JPS+A*組合規(guī)劃算法流程圖

3.3 組合規(guī)劃算法步驟

設(shè)置搜索open 列表和close 列表,起始點(diǎn)為S,目標(biāo)點(diǎn)為D。改進(jìn)JPS+A*的組合規(guī)劃算法步驟如下。

步驟1初始化,判斷起點(diǎn)與終點(diǎn)是否在同一連通區(qū),若不在,搜索失敗退出。

步驟2計(jì)算地圖的直通率Pe和障礙率Po,根據(jù)式(9)得到該地圖的跳點(diǎn)閾值λ。

步驟3將起點(diǎn)S加入到open 列表中。

步驟4將open 列表中f(n) 值最小的節(jié)點(diǎn)i取出,并將其加入到close 列表中。若i=D,沿著父節(jié)點(diǎn)回溯得到路徑,轉(zhuǎn)到步驟10;若不是,擴(kuò)展節(jié)點(diǎn)i。

步驟5判斷當(dāng)前節(jié)點(diǎn)i搜索范圍內(nèi)跳點(diǎn)數(shù)量K(基于式(8)),比較K、λ,若K ＜λ,轉(zhuǎn)到步驟6;否則轉(zhuǎn)到步驟7。

步驟6改進(jìn)JPS 算法搜索一步,尋找不在close 列表中跳點(diǎn)。

步驟7A*算法搜索一步,沿8 個(gè)方向?qū)ふ耶?dāng)前節(jié)點(diǎn)不在close 列表中的可達(dá)鄰節(jié)點(diǎn)。

步驟8判斷該節(jié)點(diǎn)是否在open 列表中,若不在,將該節(jié)點(diǎn)加入到open 列表中;若在,計(jì)算該節(jié)點(diǎn)g(n) 和父節(jié)點(diǎn)的判斷更新。

步驟9轉(zhuǎn)到步驟4。

步驟10基于式(4)、(5),通過(guò)安全評(píng)估模型計(jì)算所得路徑的平均碰撞度,尋路成功。

4 仿真及實(shí)驗(yàn)驗(yàn)證

環(huán)境建模是建立一個(gè)供移動(dòng)機(jī)器人自主移動(dòng)的場(chǎng)所,對(duì)環(huán)境模型的要求是便于機(jī)器人控制器存儲(chǔ)、處理、更新和使用。因此本文選擇了存儲(chǔ)簡(jiǎn)單且易于實(shí)現(xiàn)的柵格法構(gòu)建地圖,并建立安全性評(píng)估模型對(duì)路徑安全性進(jìn)行評(píng)估,式(5)中參數(shù)取α=1,β=3。

首先,建立15 m×15 m 的移動(dòng)機(jī)器人工作地圖環(huán)境,將本文算法改進(jìn)的JPS 算法與A*算法和JPS算法進(jìn)行仿真測(cè)試。然后,擴(kuò)大地圖規(guī)模,建立20 m×20 m 和30 m×30 m 的地圖模型,將改進(jìn)的JPS +A*算法與JPS 算法作仿真實(shí)驗(yàn),驗(yàn)證組合算法的合理性。最后,在50 m ×50 m 的地圖模型中,將改進(jìn)JPS+A*算法與改進(jìn)JPS 算法比較,驗(yàn)證隨著地圖規(guī)模的增大,組合規(guī)劃算法在路徑搜索時(shí)間及路徑長(zhǎng)度等方面的優(yōu)勢(shì)。

4.1 實(shí)驗(yàn)1

在15 m ×15 m 的地圖環(huán)境下,基于A*算法、JPS 算法和本文所設(shè)計(jì)的改進(jìn)JPS 算法的路徑規(guī)劃結(jié)果如圖7 所示,其中陰影柵格為擴(kuò)展節(jié)點(diǎn)。3 種算法的實(shí)驗(yàn)路徑參數(shù)如表1 所示。

對(duì)于規(guī)模較小且障礙物較少的地圖環(huán)境,比較圖7(a)、(b)可知,相比于A*算法,JPS 算法快速穿越對(duì)稱路徑,擴(kuò)展節(jié)點(diǎn)相比A*算法大大減少。由表1 的實(shí)驗(yàn)數(shù)據(jù)可知,當(dāng)路徑長(zhǎng)度相同的情況下,JPS 算法較A*算法,移動(dòng)時(shí)間縮短了47.16 ms;而改進(jìn)JPS 算法與JPS 算法相比,路徑長(zhǎng)度縮短了5.01%,移動(dòng)時(shí)間減少了16.63%,且由于對(duì)跳點(diǎn)篩選規(guī)則的改進(jìn),路徑的平均碰撞度降低了40.00%。綜合上述分析,所設(shè)計(jì)的改進(jìn)JPS 算法提高了搜索效率和路徑安全性。

表1 路徑規(guī)劃參數(shù)表

圖7 基于15 m×15 m 柵格地圖的3 種算法路徑規(guī)劃結(jié)果

4.2 實(shí)驗(yàn)2

為了驗(yàn)證本文改進(jìn)JPS +A*算法在復(fù)雜環(huán)境的地圖中的合理性,將地圖規(guī)模擴(kuò)大為20 m ×20 m和30 m×30 m,基于JPS 算法、A*算法和改進(jìn)JPS+A*算法仿真結(jié)果如圖8 和圖9 所示。

圖8 20 m×20 m 柵格地圖中不同算法的路徑規(guī)劃

圖9 30 m×30 m 柵格地圖中不同算法的路徑規(guī)劃

由圖8 和圖9 橢圓標(biāo)記區(qū)域可知,在穿越障礙物稠密的環(huán)境時(shí),改進(jìn)JPS+A*算法相較于JPS 算法規(guī)劃的路徑更平滑且更合理。由表2 可得,在路徑長(zhǎng)度和移動(dòng)時(shí)間上,改進(jìn)JPS+A*算法較傳統(tǒng)A*和JPS 算法具有較大的優(yōu)勢(shì);且柵格地圖的規(guī)模越大,改進(jìn)JPS +A*算法的搜索效率提升越明顯。在路徑安全性上,改進(jìn)JPS+A*算法的平均碰撞度遠(yuǎn)小于其他兩種算法且所規(guī)劃的路徑更加合理。由上述分析可知,本文改進(jìn)的組合規(guī)劃算法適用于規(guī)模較大、對(duì)移動(dòng)機(jī)器人的安全性要求較高的環(huán)境。

表2 不同規(guī)模地圖中各算法的路徑規(guī)劃參數(shù)表

4.3 實(shí)驗(yàn)3

將地圖規(guī)模進(jìn)一步擴(kuò)大為50 m ×50 m?；诟倪M(jìn)JPS +A*的組合路徑規(guī)劃算法和改進(jìn)JPS 算法的規(guī)劃結(jié)果如圖10 所示。

圖10 本文算法與改進(jìn)JPS 算法的路徑規(guī)劃結(jié)果

由圖10 中橢圓標(biāo)記區(qū)域可得,當(dāng)改進(jìn)的JPS 與A*算法相結(jié)合后,利用A*算法有效處理復(fù)雜非對(duì)稱路徑。由表3 實(shí)驗(yàn)數(shù)據(jù)可知,JPS +A*組合路徑規(guī)劃算法規(guī)劃出的路徑長(zhǎng)度比改進(jìn)JPS 算法減少了0.91 m,移動(dòng)時(shí)間縮短了23.11%,路徑搜索效率顯著提高。

表3 路徑規(guī)劃參數(shù)表

5 結(jié)論

本文設(shè)計(jì)了一種基于改進(jìn)JPS +A*的組合路徑規(guī)劃算法。該算法針對(duì)JPS 算法內(nèi)部運(yùn)算機(jī)制及復(fù)雜地圖環(huán)境因素對(duì)移動(dòng)機(jī)器人路徑尋優(yōu)效率影響的問(wèn)題,通過(guò)刪除冗余中間跳點(diǎn)、改進(jìn)跳點(diǎn)篩選規(guī)則及建立安全性評(píng)估模型實(shí)現(xiàn)了一種改進(jìn)的JPS 算法;在此基礎(chǔ)上,根據(jù)環(huán)境的復(fù)雜度設(shè)計(jì)了跳點(diǎn)閾值函數(shù),將所設(shè)計(jì)的改進(jìn)JPS 算法與A*算法相結(jié)合,實(shí)現(xiàn)了復(fù)雜地圖環(huán)境下的路徑尋優(yōu)且提高路徑搜索的效率。仿真實(shí)驗(yàn)結(jié)果表明,相比于傳統(tǒng)的JPS 算法,本文所設(shè)計(jì)的改進(jìn)JPS+A*組和路徑規(guī)劃算法更適用于復(fù)雜地圖環(huán)境,尤其是存在非對(duì)稱路徑的地圖環(huán)境,有效地減少了節(jié)點(diǎn)數(shù)量、移動(dòng)時(shí)間和平均碰撞度,提高了移動(dòng)機(jī)器人的安全性和工作效率。后續(xù)工作將進(jìn)一步改善算法的避障能力和求解路徑的平滑性。