改進雙向動態(tài)JPS算法的移動機器人全局路徑規(guī)劃

摘 要：針對跳點搜索（jump point search，JPS）算法在尋路過程中所存在的路徑拐點多、中間搜索跳點數(shù)多、尋找跳點的過程中擴展節(jié)點數(shù)多和尋路時間較長等問題，提出改進雙向動態(tài)JPS算法。改進算法動態(tài)定義正、反擴展方向上的目標點，動態(tài)定義啟發(fā)函數(shù)，并利用動態(tài)約束橢圓對算法的擴展區(qū)域加以限制，以區(qū)分橢圓內(nèi)、外區(qū)域的擴展優(yōu)先級。在算法從起點和目標點兩個方向上分別向?qū)Ψ竭M行擴展的過程中，以尋找到的新的代價最小點為新橢圓的焦點，橢圓的方位和約束區(qū)域也隨之動態(tài)調(diào)整。仿真結(jié)果表明，經(jīng)過優(yōu)化改進的雙向動態(tài)JPS算法在一般地圖中有一定的表現(xiàn)，在障礙物較少且目標點距離起點較近的室內(nèi)環(huán)境地圖中表現(xiàn)尤為良好。

關(guān)鍵詞：路徑規(guī)劃； 跳點搜索； 雙向動態(tài)搜索； 移動機器人

中圖分類號：TP242.6文獻標志碼： A文章編號：1001－3695（2024）04－023－1117－06

doi：10.19734/j.issn.1001－3695.2023.08.0369

Improved bidirectional dynamic JPS algorithm forglobal path planning of mobile robot

Liu Ronghua Wang Xin Wu Dib， Xie Chunyuana

Abstract：In order to address the issues with the jump point search algorithm in the process of pathfinding， such as numerous path inflection points， numerous intermediate search hop points， numerous extended nodes， and lengthy pathfinding time in the process of finding jump points，this paper proposed the improved bidirectional dynamic JPS algorithm. The improved algorithm dynamically defined the target points in the forward and reverse expansion directions， dynamically defined the heuristic function， and used the dynamic constraint ellipse to restrict the expansion region of the algorithm to distinguish the expansion priorities of the inner and outer regions of the ellipse. The new cost minimum point served as the focus of the new ellipse， and the orientation and constraint region were dynamically changed as the extension from the starting point and goal point to each other. The simulation results show that the optimized bidirectional dynamic JPS algorithm has a certain performance in general maps， especially in indoor environment maps with fewer obstacles and the target point is close to the starting point.

Key words：path planning; jump point search; bidirectional dynamic search; mobile robot

0 引言

在移動機器人自主導(dǎo)航相關(guān)的研究中，路徑規(guī)劃作為連接機器人感知和控制的紐帶，是實現(xiàn)機器人自主導(dǎo)航功能的一項關(guān)鍵技術(shù)［1］。移動機器人的全局路徑規(guī)劃指的是在環(huán)境條件已知的基礎(chǔ)上，利用路徑規(guī)劃算法規(guī)劃出一條從起點到目標點的最優(yōu)或近似最優(yōu)路徑，規(guī)劃出的路徑需要保證能夠順利避開障礙物，并且滿足機器人的各種性能指標［2］。目前，較為常見的全局路徑規(guī)劃算法有Dijkstra算法［3］、A算法［4］、人工勢場法［5］、RRT算法［6］和跳點搜索算法等。其中，跳點搜索算法由A算法發(fā)展而來。A算法在尋路過程中會擴展大量無效的中間節(jié)點，需頻繁訪問列表以獲取節(jié)點信息，導(dǎo)致算法計算量大、尋路時間長［7］。為了彌補A算法存在的不足，Harabor等人［8］在保留A算法啟發(fā)式函數(shù)的基礎(chǔ)上提出了跳點搜索算法，算法通過特殊的節(jié)點篩選規(guī)則，在尋路過程中裁剪掉不滿足規(guī)則的中間節(jié)點，只保留特殊節(jié)點加入到開放列表當中，大幅降低了算法訪問列表的頻率，減少了算法的計算量，提升了算法的尋路效率。

為進一步完善跳點搜索算法，提高算法各方面的性能，國內(nèi)外學者提出了很多改進的方法。針對跳點搜索算法在處理環(huán)境信息復(fù)雜的大規(guī)模地圖過程中存在的跳點多且混亂的問題。金震等人［9］提出一種通過改進跳點篩選規(guī)則來對冗余的中間跳點進行刪減的改進JPS和A算法相結(jié)合的規(guī)劃算法，但在尋路過程中需要頻繁切換兩種算法，對于兩種算法尋路路徑銜接處的處理較為復(fù)雜，導(dǎo)致算法計算量增大，尋路效率變低。針對跳點搜索算法在移動機器人全局路徑規(guī)劃中預(yù)處理規(guī)則存在不安全、路徑搜索時間長和內(nèi)存消耗大等問題，馬小陸等人［10］改進跳點篩選規(guī)則，從兩個方向上進行路徑搜索，提出一種雙向跳點搜索算法，但為保證兩個方向上尋路路徑的重合，采用交替式路徑尋優(yōu)，導(dǎo)致兩個方向上的尋路不能同時進行，而當出現(xiàn)兩向?qū)ぢ仿窂讲荒芟嘤龅那闆r時，選用兩條路徑中更短的一條，都將導(dǎo)致尋路效率變低。針對雙向跳點搜索算法在特定情況下出現(xiàn)兩個方向上的路徑不能相遇，導(dǎo)致冗余路徑增多的情況，苗紅霞等人［11］增添起點和目標點之間的中心熱點區(qū)域，提出并行－交替式跳點搜索算法，但由于中心熱點區(qū)域的引入加大了算法的計算復(fù)雜度，在某些特定環(huán)境中的效果并不理想。同樣為解決雙向跳點搜索存在的問題，秦齊等人［12］動態(tài)定義啟發(fā)式搜索的目標點，引入當前跳點的父節(jié)點作為相對方向上跳點擴展的目標點，提出雙向動態(tài)跳點搜索算法，但并未解決跳點搜索算法本身所存在的中間無效跳點多、無效擴展節(jié)點多等固有問題。針對傳統(tǒng)跳點搜索算法存在搜索節(jié)點數(shù)多、搜索方向不明確和搜索時間長等問題，馬少博等人［13］融合目標點方向向量和節(jié)點初始搜索方向，構(gòu)建跳點搜索方向的優(yōu)先級，提出一種方向性跳點搜索算法，但隨著尋路的進行，由于并不能知道尚未規(guī)劃的地圖的障礙物信息，將可能導(dǎo)致已經(jīng)擴展過的優(yōu)先級高的方向上的跳點連接成的路徑不是最優(yōu)，需要重新進行低優(yōu)先級方向上的尋路擴展。針對上述算法存在尋路過程中的中間搜索跳點數(shù)多、尋找跳點的過程中擴展節(jié)點數(shù)多、尋路路徑中不必要的拐點多和尋路時間較長等問題，結(jié)合雙向動態(tài)JPS算法的優(yōu)點，構(gòu)建動態(tài)約束橢圓以限制算法每一步迭代下的節(jié)點擴展范圍，通過對每一步迭代下當前代價最小點間障礙物信息進行判斷，以剔除路徑不必要的拐點，由此提出改進雙向動態(tài)JPS算法，并通過算例對比，驗證改進算法的有效性。

1 問題描述

根據(jù)對環(huán)境信息的把握程度，可以將路徑規(guī)劃算法劃分為基于先驗完全信息的全局路徑規(guī)劃和基于傳感器信息的局部路徑規(guī)劃。其中，全局路徑規(guī)劃算法需要預(yù)先知道環(huán)境地圖的所有信息，根據(jù)已知的信息進行靜態(tài)規(guī)劃，因此算法可以在整體上進行把握，能獲得一條最優(yōu)或近似最優(yōu)的路徑，但算法只能獲取靜態(tài)障礙物的信息，做不到對環(huán)境中的動態(tài)障礙物進行避障；局部路徑規(guī)劃單依靠傳感器獲取機器人自身一定范圍的局部信息進行規(guī)劃，由于缺乏后續(xù)環(huán)境地圖信息的指引，算法很容易偏離最優(yōu)路徑，但算法實時獲取周遭環(huán)境信息實現(xiàn)動態(tài)規(guī)劃，對于動態(tài)障礙物也能夠順利躲避。目前，室內(nèi)移動機器人既需要全局地圖信息的指引，通過全局路徑規(guī)劃得到起點和目標點的最優(yōu)路徑，又需要傳感器獲得的實時局部信息的指引，做到對室內(nèi)如寵物和行人等障礙物的動態(tài)避障。因此結(jié)合兩種算法得到融合算法，以實現(xiàn)最優(yōu)路徑下的動態(tài)避障，已經(jīng)成 為了當今室內(nèi)移動機器人采取的主流算法。室內(nèi)移動機器人普遍采取在全局路徑規(guī)劃得到的路徑上，選取一定數(shù)量的中間點作為局部路徑規(guī)劃的中轉(zhuǎn)目標點的方式來實現(xiàn)算法的融合。在中間目標點之間的動態(tài)規(guī)劃前會再次進行靜態(tài)規(guī)劃，以確保當前全局路徑的可靠性，這意味著算法將在全局規(guī)劃和局部規(guī)劃間頻繁切換，全局路徑規(guī)劃速度將直接影響局部規(guī)劃躲避障礙物的有效性，因此提升全局路徑規(guī)劃算法的尋路速度是必要的。

JPS算法較之傳統(tǒng)算法如（A等全局路徑規(guī)劃算法）大幅降低了訪問列表的頻率，提升了尋路效率，因此更加適合與局部路徑規(guī)劃算法結(jié)合。在障礙物較為密集的環(huán)境地圖中，因為引入障礙物附近強迫鄰居的規(guī)則，跳點的數(shù)量多，中間擴展節(jié)點的數(shù)量多且分散，跳點搜索算法較難發(fā)揮自身優(yōu)勢；然而室內(nèi)環(huán)境的障礙物一般以少量沙發(fā)、桌椅等形狀規(guī)則的家具為主，且地圖中留有大量空白可通行地段，給了跳點搜索算法很大的發(fā)揮空間。然而大面積可通行區(qū)域也導(dǎo)致跳點搜索算法需要大幅度擴展中間無效節(jié)點以獲取關(guān)鍵跳點，令算法的收斂速度下降，因此本文提出改進雙向動態(tài)JPS算法，根據(jù)環(huán)境信息構(gòu)建合適的動態(tài)約束橢圓，對于每一次迭代下的擴展范圍進行限制，避免了大量無意義跳點和中間節(jié)點的擴展。

2 改進JPS算法及其不足

2.1 傳統(tǒng)JPS算法

跳點搜索算法［14］在A算法的基礎(chǔ)上，通過一定的規(guī)則來識別并選擇性地擴展柵格地圖中滿足條件的節(jié)點，稱之為跳點，對跳點間無用的中間節(jié)點進行裁剪，從而將A算法的尋路效率提高一個數(shù)量級甚至更多。圖1為跳點篩選規(guī)則示意圖，parent為父節(jié)點，current為當前節(jié)點，node為尚未擴展的節(jié)點，forced為強迫鄰居。具體的跳點篩選規(guī)則［15］如下：

a）如圖1（a）（c）所示，當算法在無障礙的直線和斜線方向上進行搜索時，從parent只有經(jīng)過current到達node的路徑才是最短，而從parent到達灰色節(jié)點的最短路徑可以不經(jīng)過current，因此裁剪灰色節(jié)點，擴展過程中不產(chǎn)生跳點。

b）如圖1（b）（d）所示，當算法在有障礙物的直線和斜線方向上進行搜索時，從父節(jié)點到達灰色節(jié)點同樣可以不經(jīng)過current，將灰色節(jié)點進行裁剪，而從父節(jié)點到forced尋找一條最短路徑，則必須經(jīng)過current，稱forced為當前節(jié)點的強迫鄰居，current為跳點。

c）節(jié)點為起點或者目標點，或者節(jié)點為跳點。

d）斜線方向上進行擴展時，如果當前節(jié)點在直線擴展方向上存在跳點，當前節(jié)點為跳點。

跳點搜索算法的尋路規(guī)則［16］如下：

a）如果當前的代價最小點為起點，分別向直線和斜線的8個方向上尋找跳點，將跳點加入到開放列表openlist中，當某個方向上遇到地圖邊界或者障礙物時，該方向上的搜索停止。

b）如果當前代價最小點不是起點和目標點，沿父節(jié)點和當前節(jié)點向量方向和向量正交分量方向上尋找跳點，將跳點加入openlist中，當某個方向上遇到地圖邊界或者障礙物時，該方向上的搜索停止。

c）迭代選取openlist 中代價值最小的跳點作為下一個待擴展節(jié)點，重復(fù)此過程，直到搜索到目標點或openlist 為空。

d）跳點代價值由評價函數(shù)決定，常見的評價函數(shù)表示為

其中：g（n）代表從起點到當前跳點的實際距離（代價）；h（n）為啟發(fā)函數(shù)，代表從當前跳點到目標點的預(yù)估距離（代價），通常通過歐氏距離、曼哈頓距離或切比雪夫距離計算得到。

2.2 雙向JPS算法

雙向JPS算法在JPS算法的基礎(chǔ)上，在從起點開始，向目標點進行跳點擴展的同時從目標點向起點進行跳點的擴展，當兩個方向上的跳點出現(xiàn)重合時，尋路結(jié)束。

雙向跳點搜索算法較傳統(tǒng)跳點搜索算法在理論上可以加快近一倍的尋路速度，但當出現(xiàn)圖2所示的對稱型障礙物時，正反向搜索出現(xiàn)分別從障礙物兩側(cè)進行跳點擴展的情況，導(dǎo)致兩個方向上的尋路路徑不能重合。此外，由于跳點搜索裁剪過程中不是跳點柵格的特性，可能導(dǎo)致在一側(cè)跳點擴展的過程中越過另一側(cè)正在擴展的跳點的情況發(fā)生，導(dǎo)致產(chǎn)生大量冗余路徑，無法保證算法的收斂效率。

2.3 雙向動態(tài)JPS算法

雙向動態(tài)JPS算法考慮到雙向JPS算法的缺點，在搜索效率上作出一定的妥協(xié)，提出動態(tài)目標點的概念。在雙向擴展的過程中，動態(tài)定義啟發(fā)式函數(shù)，分別以對方最新擴展出來的代價最小點作為自己擴展方向上新的目標點，當兩個方向以同一個節(jié)點為目標點（兩方向上當前代價最小點重合），或者兩個方向的openlist其中之一為空時，尋路完成。雙向動態(tài)JPS搜索由于在每次循環(huán)結(jié)束后都將實時動態(tài)更新自己方向上的目標點，目標點向著對方逼近，所以提高了算法的收斂速度。

雙向動態(tài)JPS算法雖然解決了雙向JPS算法在某些環(huán)境狀態(tài)下路徑冗余的問題，但并未解決因為引入跳點導(dǎo)致的算法在遇到障礙物的情況下路徑增加大量拐點的問題。此外，雙向動態(tài)JPS算法從起點處擴展時因缺乏父節(jié)點和強迫鄰居，從部分中間跳點擴展時因強迫鄰居遠離目標點而引起盲目搜索方向和范圍，導(dǎo)致尋路過程中的中間擴展跳點多，中間無效擴展節(jié)點多。針對上述問題，本文對雙向動態(tài)JPS算法進行改進，改進的算法在雙向動態(tài)JPS算法基礎(chǔ)之上動態(tài)檢查每一步迭代過程中兩方向目標點之間的障礙物信息，可在一定程度上減少算法產(chǎn)生的路徑拐點，此外，引入動態(tài)約束橢圓以限制算法在尋路過程中的擴展范圍。

3 改進雙向動態(tài)JPS算法

3.1 動態(tài)定義目標點、啟發(fā)函數(shù)

在雙向動態(tài)JPS算法中，將分別從起點和終點開始進行交替跳點擴展，隨著擴展雙方向?qū)Ψ奖平?，兩個擴展方向上的目標點和啟發(fā)函數(shù)也隨之動態(tài)變化。具體動態(tài)目標點的定義如圖3所示。

藍色柵格為正向擴展出的跳點，紅色柵格為反向擴展出的跳點，S1和G1分別為起點和終點，黑色柵格為障礙物（參見電子版）。a）分別將S1和G1加入到正向開放列表（forward_openlist）和反向開放列表（reverse_openlist）中，取出正向開放列表當中的代價最小點S1，以反向代價最小點G1為目標點進行正向擴展，將擴展得到的跳點加入到正向開放列表，取出正向代價最小點S2。b）以G1為反向擴展起點，向步驟a）中得到的正向代價最小點S2為目標點進行反向擴展，將擴展得到的跳點加入到反向開放列表當中，取出反向代價最小點G2。c）以步驟b）中得到的反向代價最小點G2為新的正向目標點，進行正向擴展，得到正向代價最小點S3。d）以步驟c）中得到的正向代價最小點S3為新的反向目標點，進行反向擴展，得到反向代價最小點G3。e）以步驟d）得到的反向代價最小點G3為新的正向目標點，進行正向擴展，得到正向代價最小點S4。f）以步驟e）得到的正向代價最小點S4為新的反向目標點進行反向擴展，得到反向代價最小點S4，此時正反向代價最小點重合，尋路結(jié)束。

其中：xfmin和yfmin分別代表當前循環(huán)正向代價最小點的橫坐標和縱坐標；xrmin和yrmin分別代表當前循環(huán)反向代價最小點的橫坐標和縱坐標。

3.2 環(huán)境復(fù)雜度和動態(tài)約束橢圓

改進雙向動態(tài)JPS算法引入動態(tài)約束橢圓。在擴展過程中，以一個擴展方向上的當前代價最小點為橢圓焦點F1，以另一個擴展方向上的當前代價最小點為橢圓焦點F2，橢圓焦距即為啟發(fā)函數(shù)值，以ζ倍的焦距為橢圓的長軸長，就可以確定當前迭代下的動態(tài)約束橢圓，本文給出動態(tài)約束橢圓的標準，如式（4）所示。

其中：m= xmin（1）+xmin（2）/2 代表橢圓中心點的橫坐標，xmin（1）和xmin（2）是兩個擴展方向上的當前代價最小點的橫坐標；n= ymin（1）+ymin（2）/2 代表橢圓中心點的縱坐標，ymin（1）和ymin（2）分別是兩個擴展方向上的當前代價最小點的縱坐標；a=ζh代表橢圓的長軸長，ζ為橢圓膨脹系數(shù)，通過表1環(huán)境復(fù)雜度和橢圓膨脹系數(shù)的關(guān)系來確定，h代表橢圓的焦距，可以通過當前迭代下的啟發(fā)函數(shù)式（2）或（3）求得b= h 4ζ2-1 /2 ，代表橢圓的短軸長。

橢圓膨脹系數(shù)ζ的確定與環(huán)境復(fù)雜度有關(guān)。將以當前迭代下正反向擴展的代價最小點的連線為對角線的矩形范圍設(shè)為環(huán)境復(fù)雜度的計算區(qū)域，通過計算矩形范圍內(nèi)障礙物柵格占整個矩形所包含柵格的比重來確定環(huán)境復(fù)雜度。

以圖4為例，紅色和藍色柵格分別代表兩個擴展方向上每一步迭代下的當前代價最小點，黑色柵格代表障礙物（參見電子版）。在算法進行第一步迭代時，首先以起點start和終點goal的連線為矩形對角線，確定環(huán)境復(fù)雜度的計算區(qū)域，圖中以綠色虛線線框表示。從圖中可以看出，線框內(nèi)所包含的黑色柵格數(shù)為28個，占線框所包含的總柵格數(shù)的19.58%，即第一步迭代下的環(huán)境復(fù)雜度k1為0.196。后續(xù)迭代下環(huán)境復(fù)雜度的確定與第一步類似，不再贅述。

動態(tài)約束橢圓的具體構(gòu)建方法如圖5所示。紅、藍節(jié)點是兩個擴展方向上每一步迭代產(chǎn)生的代價最小點，在尋路剛開始時，分別以起點start和目標點goal作為橢圓的兩個焦點，以ζ 倍的焦距為橢圓的長軸長，得到橢圓ellipse 1。下一步的迭代中以正向擴展出的代價最小點S1和反向擴展出的代價最小點G1為新的橢圓焦點，同樣以ζ倍的焦距為橢圓的長軸長，得到新的約束擴展橢圓ellipse 2。重復(fù)上述過程，直到尋路完成。

動態(tài)約束橢圓用于限制當前迭代下節(jié)點的擴展范圍，圖6和7分別展示了在進行第一輪跳點的擴展過程中，有、無約束橢圓對于節(jié)點擴展范圍的影響，其中，綠色和灰色代表兩個方向上的擴展節(jié)點（參見電子版）。圖6提取同橢圓邊界相交的柵格，賦給橢圓邊界外和邊界上的柵格小于無障礙物柵格，但大于有障礙物柵格的擴展權(quán)重，將環(huán)境地圖分橢圓內(nèi)高優(yōu)先級擴展區(qū)和橢圓外次優(yōu)先級擴展區(qū)。對比圖7的無約束擴展，算法在尋找跳點時將優(yōu)先在橢圓內(nèi)進行擴展，由于橢圓邊界并不是障礙物，將不會引入更多的跳點，尋路過程中的中間擴展節(jié)點和中間跳點反而會因為橢圓的限制而減少，從而加快了雙向搜索向?qū)Ψ綌U展的速度，算法的收斂效率得到提高。

3.3 正反向當前代價最小點間障礙物判斷

如圖8（a）黑色路徑所示，由于JPS算法在柵格地圖中只能沿直線和柵格對角線方向規(guī)劃路徑，導(dǎo)致算法引入無意義拐點；如圖8（b）黑色路徑所示，由于在障礙物附近引入強迫鄰居的概念，同樣導(dǎo)致算法在某些環(huán)境下引入大量無意義的中間拐點。雙向動態(tài)JPS算法由于從兩個方向上向?qū)Ψ竭M行擴展的特點，可以在每一步迭代的過程中對兩個方向上的代價最小點之間的環(huán)境信息進行判斷。如果兩個代價最小點的連線不穿過任何障礙物，則直接將兩點相連（圖示藍色路徑，參見電子版），同規(guī)劃過的路徑拼接成完整的尋路路徑，有助于減少路徑無意義的拐點。

3.4 改進雙向動態(tài)JPS算法路徑規(guī)劃

改進雙向動態(tài)JPS算法通過動態(tài)約束橢圓，限制了每一次迭代找尋跳點所需要擴展的中間節(jié)點，避免了將遠離當前迭代下正、反向代價最小點連線周圍大概率無效的跳點加入到開放列表；同時，每次迭代后對兩個方向上代價最小點連線是否穿過障礙物進行判斷，減少了算法尋路路徑不必要的拐點。

改進雙向動態(tài)JPS算法的路徑規(guī)劃流程如圖9所示。具體路徑規(guī)劃流程如下：

a）初始化柵格地圖，得到柵格環(huán)境中的起點、目標點和障礙物坐標信息，將起點加入到正向開放列表forward_openlist當中，將目標點加入到反向開放列表reverse_openlist當中。

b）判斷forward_openlist和reverse_openlist是否為空，若有列表為空，則尋路結(jié)束，若兩個列表都不為空，取出兩個開放列表當中的代價最小點，并將其設(shè)為對向擴展的新的目標點。

c）判斷兩個擴展方向上的目標點是否重合。若目標點重合，尋路完成；若目標點不重合，判斷兩個目標點的連線是否穿過障礙物。若目標點連線不穿過障礙物，將連線看成尋路路徑的一部分，尋路完成；若目標點連線穿過障礙物，繼續(xù)進行后續(xù)步驟。

d）以兩個方向上的代價最小點為橢圓焦點，以ζ倍的焦距為長軸長，構(gòu)建約束橢圓，在約束橢圓內(nèi)高優(yōu)先級擴展區(qū)進行跳點搜索，若橢圓內(nèi)有滿足條件的跳點，則將跳點加入開放列表，若沒有滿足條件的跳點，則在橢圓外進行跳點擴展，同樣將滿足條件的跳點加入開放列表。

4 仿真與實驗分析

為驗證改進雙向動態(tài)JPS算法的有效性，分別采用20×20和40×40兩種不同尺寸的柵格地圖針對Dijkstra、A、傳統(tǒng)JPS、雙向動態(tài)JPS和本文算法進行仿真對比實驗。仿真使用的設(shè)備配置為：Windows 10 64位操作系統(tǒng)，Core i7－10700F處理器，主頻為2.9 GHz，安裝內(nèi)存為16 GB，仿真運行平臺為MATLAB R2020b。

仿真環(huán)境如圖10和11所示。柵格地圖中，△和○分別代表起點和目標點，黑色柵格代表障礙物，灰色柵格代表中間擴展點，紅色柵格代表跳點（Dijkstra和A算法當中的擴展點需加入開放列表，每次擴展需遍歷訪問列表，效果等同于JPS算法的跳點，因此視為跳點，Dijkstra和A算法無中間擴展點）。表2和3分別展示了五種算法在兩種不同的柵格地圖下路徑長度、算法運行時間、中間擴展節(jié)點數(shù)、跳點數(shù)和拐點數(shù)的對比情況。

由圖10和表2可以看出，當環(huán)境地圖中障礙物柵格占整個環(huán)境地圖柵格較大比重時，也就是地圖較小且環(huán)境較為復(fù)雜的情況下，對比Dijkstra、A和JPS的跳點數(shù)可以發(fā)現(xiàn)，Dijkstra由于引入了大量的跳點（擴展點）導(dǎo)致算法頻繁訪問開放列表，算法的尋路效率低下，而A和JPS算法由于引入較少的跳點，算法的尋路速度得到明顯提升，但傳統(tǒng)JPS和雙向動態(tài)JPS由于引入了額外的中間擴展節(jié)點，導(dǎo)致算法尋路速度較之A反而略有下降，但同樣可以看出，少量中間擴展點對于算法尋路效率的影響并不大，當采用改進雙向動態(tài)JPS時，由于約束橢圓的限制，跳點數(shù)和中間擴展節(jié)點數(shù)減少，算法的尋路速度得到較為明顯的提升。

對比40×40和20×20地圖尺寸下的運行結(jié)果可以看出，在障礙物較少的大尺寸環(huán)境地圖下，JPS較之A引入更少的跳點，算法運行時間得以降低，而雙向動態(tài)JPS相較于傳統(tǒng)JPS在尋路時間上的改進并不大，這是因為雙向動態(tài)JPS雖然從兩個方向上進行擴展，但兩個方向上的擴展并不是并行的，而是交替進行，同時雙向動態(tài)JPS并未解決傳統(tǒng)JPS存在的尋路過程中的中間無效擴展節(jié)點多、無效跳點多的問題，但該算法有著隨擴展的進行，兩個方向上的擴展向?qū)Ψ奖平奶攸c。結(jié)合這一特點，當引入動態(tài)約束橢圓對算法每一步的擴展范圍進行優(yōu)先級的劃分，采用改進雙向動態(tài)JPS時，算法在擴展過程中產(chǎn)生的大量無效擴展節(jié)點和跳點被舍棄?？梢钥闯?，經(jīng)過優(yōu)化后的算法在保證路徑最優(yōu)或趨于最優(yōu)的情況下能夠有效提升算法的收斂速度，加快算法的尋路效率。

5 結(jié)束語

為解決傳統(tǒng)JPS尋路過程中存在的中間無效擴展節(jié)點多、跳點多、中間拐點多等問題，本文在雙向動態(tài)JPS的基礎(chǔ)上引入動態(tài)約束橢圓，限制算法每一步迭代下的擴展范圍，同時動態(tài)檢查每一步迭代下兩個擴展方向上代價最小點之間的障礙物信息。通過仿真實驗驗證，本文算法在一定程度上提升了算法的收斂速度與尋路效率，尤其是在障礙物較少且形狀規(guī)則的室內(nèi)較大的地圖環(huán)境下表現(xiàn)尤為明顯。后續(xù)工作將以改進的雙向動態(tài)JPS作為機器人的全局路徑規(guī)劃算法，結(jié)合局部路徑規(guī)劃算法中的動態(tài)窗口法得到融合算法，通過融合算法以實現(xiàn)機器人在室內(nèi)環(huán)境下的高效自主導(dǎo)航和動態(tài)避障功能。

參考文獻：

［1］宋曉茹， 任怡悅， 高嵩， 等. 移動機器人路徑規(guī)劃綜述［J］. 計算機測量與控制， 2019， 27 （4）： 1－5，17. （Song Xiaoru， Ren Yiyue， Gao Song，et al.Survey on technology of mobile robot path planning［J］.Computer Measurement and Control ， 2019， 27 （4）： 1－5，17.）

［2］楊韻， 王成彥， 巫凱旋， 等. 移動機器人全局路徑規(guī)劃算法綜述［J］. 信息記錄材料， 2022，23 （3）： 29－32. （Yang Yun， Wang Chengyan， Wu Kaixuan，et al.Overview of global path planning algorithms for mobile robots［J］.Information Recording Materials ， 2022， 23 （3）： 29－32.）

［3］吳鵬， 寇瑋華， 許木南， 等. 基于Dijkstra和深度優(yōu)先搜索的進路搜索算法研究［J］. 交通運輸工程與信息學報， 2017， 15 （4）： 38－43. （Wu Peng， Kou Weihu Xu Munan，et al.Research on route searching algorithms using Dijkstra and depth first search［J］.Journal of Transportation Engineering and Information，2017， 15 （4）： 38－43.）

［4］Cui Shigang， Wang Hui， Yang Li. A simulation study of A－star algorithm for robot path planning［C］//Proc of the 16th International Conference on Mechatronics Technology. 2012： 506－509.

［5］胡錚， 徐斌. 改進人工勢場法的軌跡規(guī)劃［J］. 電光與控制， 2023， 30 （3）： 38－41，53. （Hu Zheng， Xu Bin. Trajectory planning of improved artificial potential field method［J］.Electro－Optical and Control ， 2023， 30 （3）： 38－41，53.）

［6］Asqui L， Andauz V， Sánchez J， et al. Path planning based in algorithm rapidly－exploring random tree RRT［J］.Advanced Science Letters ， 2018， 24 （11）： 8831－8836.

［7］張永濤. 基于改進Astar算法的AGV路徑規(guī)劃［J］. 信息與電腦， 2022， 34 （23）： 67－70. （Zhang Yongtao. AGV path planning based on improved Astar algorithm［J］.Information and Computers ， 2022， 34 （23）： 67－70.）

［8］Harabor D， Grastien A. Online graph pruning for pathfinding on grid maps［C］//Proc of the 25th AAAI Conference on Artificial Intelligence. Palo Alto，CA： AAAI Press， 2011： 1114－1119.

［9］金震， 黃衛(wèi)華， 李傳奇， 等. 基于改進JPS和A算法的組合路徑規(guī)劃［J］. 高技術(shù)通信， 2022， 32 （4）： 412－420. （Jin Zhen， Huang Weihu Li Chuanqi，et al.Combination path planning based on improved jump point search and A algorithm［J］.High Technology Letters，2022， 32 （4）： 412－420.）

［10］馬小陸， 梅宏. 雙向跳點搜索算法的移動機器人全局路徑規(guī)劃研究［J］. 機械科學與技術(shù)， 2020， 39 （10）： 1624－1631. （Ma Xiao－lu， Mei Hong. Research on bidirectional jump point search algorithm of global path planning for mobile robots［J］.Mechanical Science and Technology，2020， 39 （10）： 1624－1631.）

［11］苗紅霞， 郭章旺， 齊本勝， 等. 基于并行－交替式雙向JPS算法的機器人路徑規(guī)劃［J］. 計算機測量與控制， 2022， 30 （7）： 233－239. （Miao Hongxi Guo Zhangwang， Qi Bensheng，et al.Robot path planning based on parallel alternate bidirectional JPS algorithm［J］.Computer Measurement and Control ， 2022， 30 （7）： 233－239.）

［12］秦齊， 萬熠， 侯嘉瑞， 等. 基于雙向動態(tài)跳點搜索算法的AGV路徑規(guī)劃研究［J］. 單片機與嵌入式系統(tǒng)應(yīng)用， 202 21 （8）： 55－58，63. （Qin Qi， Wan Yi， Hou Jiarui，et al.AGV path planning based on bidirectional dynamic jumping search algorithm［J］.Micro Controller and Embedded System Applications ， 202 21 （8）： 55－58，63.）

［13］馬少博， 王立勇， 丁炳超， 等. 方向性JPS的移動機器人全局路徑規(guī)劃方法［J］. 重慶理工大學學報： 自然科學版， 2022， 36 （10）： 192－199. （Ma Shaobo， Wang Liyong， Ding Bingchao，et al.Global path planning for mobile robots with directional JPS algorithm［J］.Journal of Chongqing University of Technology： Natural Science Edition ， 2022，36 （10）： 192－199.）

［14］邱磊， 劉輝玲， 雷建龍. 跳點搜索算法的原理解釋及性能分析［J］. 新疆大學學報： 自然科學版， 2016，33 （1）： 80－87. （Qiu Lei， Liu Huiling， Lei Jianlong. Principle explanation and perfor－mance analysis of jump point search algorithm［J］.Journal of Xinjiang University： Natural Science Edition ， 2016， 33 （1）： 80－87.）

［15］邱磊. 基于跳點搜索算法的網(wǎng)格地圖尋路［J］. 中央民族大學學報： 自然科學版， 2014， 23 （1）： 15－21. （Qiu Lei. Pathfinding on grid maps based on jump point search［J］.Journal of Minzu University of China： Natural Science Edition ， 2014， 23 （1）： 15－21.）

［16］楊鳳滿， 張奇志， 周亞麗. 家庭服務(wù)機器人路徑規(guī)劃的跳點搜索算法［J］. 北京信息科技大學學報： 自然科學版， 2018， 33 （3）： 85－89. （Yang Fengman， Zhang Qizhi， Zhou Yali. Jump point search algorithm for path planning of home service robot［J］.Journal of Beijing Information Science and Technology University： Natural Science Edition ， 2018， 33 （3）： 85－89.

收稿日期：2023－08－12；修回日期：2023－10－06基金項目：中央高?；究蒲袠I(yè)務(wù)費資助項目（DUT22LAB507）

作者簡介：劉榮華（1998—），男，山東青島人，碩士研究生，主要研究方向為機器人路徑規(guī)劃；王欣（1972—），女（通信作者），天津人，副教授，碩導(dǎo)，博士，主要研究方向為工業(yè)機器人與動作規(guī)劃（wangx@dlut.edu.cn）；吳迪（197—），男，遼寧大連人，副教授，博導(dǎo)，博士，主要研究方向為基于5G平臺的醫(yī)療機器人制造技術(shù)；謝春圓（1998—），男，遼寧朝陽人，碩士研究生，主要研究方向為洗浴機器人軌跡規(guī)劃．