基于改進跳點搜索策略的安全路徑研究

黃智榜，胡立坤，張 宇，黃 彬

廣西大學 電氣工程學院，南寧530004

機器人路徑規劃是指機器人在有障礙物的工作環境中，按照一定的性能指標，尋找出一條從起始位置到目標位置的無碰撞路徑。路徑規劃是移動機器人自主導航最關鍵的一個環節，也是機器人領域的研究熱點[1]。路徑規劃常用的規劃算法有A*算法[2]、蟻群算法[3]、人工勢場法[4]、D*算法[5]、跳點搜索算法[6]、快速擴展隨機樹算法[7]和泡沫法[8]等。在靜態的柵格環境中，A*算法規劃效率最高。然而，由于A*算法在大型地圖中需要對柵格地圖的每個柵格點進行檢測，造成需要檢測的冗余節點過多。針對這個問題，Harabor等人[9]提出一種基于網格尋路的跳點搜索算法（JPS），該算法提出不必對每個柵格點進行檢測，只需根據鄰居裁剪規則篩選一些關鍵節點作為跳點進行評估，將評估后的最優跳點組合連接起來就是一條完整的最優路徑。JPS算法盡管解決了A*算法計算冗余等問題，但是經研究發現該算法存在跳點數量多，規劃的路徑存在安全隱患等問題。

針對這些問題，文獻[10]通過引入區域矩陣，將障礙物之間的中點作為跳點，使跳點與障礙物保持一定的距離，規劃出安全的路徑。但是該方法完全舍棄算法的路徑尋優性能只考慮路徑的安全性能。文獻[11-12]提出雙向跳點搜索算法，進一步減少了跳點的數量，加快了跳點搜索算法的搜索速度。然而，該方法沒有綜合考慮路徑的安全性能。本文提出一種改進JPS算法，該算法通過改進跳點的篩選規則，將障礙物膨化處理，更改算法的行進模式，得到一條綜合性能最優的路徑。最后，通過仿真和實驗驗證了算法的可行性。

1 傳統的JPS算法

1.1 鄰居裁剪規則

JPS算法是通過搜索跳點來代替向四周擴展節點的一種改進A*算法[13]，JPS算法的本質是通過避開一些冗余節點，來減少所需要計算的節點數量，提高算法的運行速度。如圖1 所示，假設在空白的柵格地圖中存在s到g的三條路徑，每條路徑都存在一個中間節點分別為a2、b2、c2，其中以經過節點b2的路徑最短，所以只需檢測b2節點而避開不必要的a2、c2節點，就可以搜索出最優路徑。這就是JPS算法的原理。

圖1 跳點原理圖示

利用跳點加速算法的搜索速度[14-15]，就是將A*算法中向鄰節點擴展改為向四周搜索跳點擴展，就類似于現實中的城市十字路口一樣，對每條路路口進行評估，選出評估值最低的路口，將它們連接起來就是一條到達目標點的最優路徑。傳統JPS 算法中采用鄰居裁剪規則來對跳點進行篩選，其具體規則如圖2 所示，其中灰色不需要查詢的節點，白色為需要查詢的節點。

圖2 傳統鄰居裁剪規則

對比以上的圖2（a）與圖2（b）可以知道，在有障礙物的柵格環境中比無障礙物柵格環境需要多查詢一個節點，稱為被迫節點n，而無障礙物環境中查詢的節點稱為自然節點。從有障礙物裁剪可以看出，傳統JPS算法尋找出的被迫節點比較靠近障礙物，且它們之間的路徑經過障礙物的拐角，這影響了規劃路徑的質量。在文獻[16]中跳點具有以下定義：

定義1 存在n ∈neighbours(x)，n不是x的自然節點，如果有len( p,x,n )＜len( p,n x )關系成立，則點n為被迫節點。

定義2 如果n以最小的值k，使得n=x+，并且下列條件之一成立，則節點n為來自節點x的跳點：（1）n為目標點。（2）節點n至少有一個鄰居節點是被迫節點。（3）若為對角查詢狀態，且存在符合條件（1）和（2）的跳點時，則n為x的跳點。

根據以上的定義，傳統的跳點分三種：分布在障礙物周圍的被迫節點、存在被迫節點的自然節點、目標點。

1.2 跳點的評估函數

通過鄰居裁剪規則可以從柵格地圖中挑選出一些關鍵節點作為跳點，但是還需對跳點進行評估和計算，增強算法的啟發性。假設已知起點s、目標點g、當前節點n以及父節點p，則算法搜索當前節點的實際代價為：

由以上幾個公式就可得出跳點的評價函數為：

通過評價函數挑選出最優的跳點組合，連接起來就是一條起點到目標點的最優路徑，其具體的算法模型如圖3所示。模型中紅色柵格為跳點，利用跳點能夠在地圖上構建出一條起始點到目標點的無碰撞最優路徑。

圖3 傳統JPS算法

1.3 碰撞危險度評估模型

為了評估機器人路徑的碰撞風險程度，采用二維高斯模型來建立危險度函數[17]，其模型如下：

其中，M為影響范圍內障礙物的個數，ρ(xi,xobs)是路徑當前點到障礙物的最近距離，d0是障礙物的影響范圍，與機器人的機身大小相關，α、β決定著碰撞對機器人造成危險程度，由機器人的速度矢量以及障礙物的質材決定。本文取α=3，β=1，N=100。

2 改進的JPS算法

2.1 改進路徑的行進方式

在傳統的JPS算法中，路徑的行進模式是固定的八鄰域行進模式，這種模式好處在于能夠簡潔形象的顯示算法的優劣性，但是卻增加了規劃路徑的長度。故在本文中選擇與實際較相符合的無限鄰域行進模式[18]，即只要兩個跳點之間沒有障礙物，就能夠直接將跳點相連形成路徑。這種行進模式的優點在于能夠縮短算法的路徑長度和減少路徑的轉彎次數。

2.2 改進的鄰居裁剪規則

在傳統JPS算法中，機器人按照一個質點來處理，只能沿著8個方向移動。但是在本文中，機器人并不是一個質點，而是具有一定形狀的物體。所以在使用傳統的鄰居裁剪規則時，機器人會與障礙物碰撞。本文基于對路徑安全性能的考慮，將位于障礙物拐角處的兩個傳統跳點結合形成新類型的跳點。具體如圖4所示。

圖4 改進的鄰居裁剪規則

如圖4（b）所示，在有障礙物的柵格環境中，將傳統跳點結合形成新類型的跳點，新選取的跳點具有以下的幾個優點：

（1）跳點之間的路徑與障礙物保持一定的距離，使得規劃路徑的安全性能得到很大的提高。

（2）跳點位于障礙物尖角處，使其容易被檢測出來，提高了算法的穩定性。

（3）跳點的輻射范圍大，使算法搜索目標的能力增強，迭代次數變少，搜索速度增加。

2.3 改進算法流程

本文使用無限鄰域行進模式構成路徑，其改進的算法流程如下所示。

（1）初始化地圖信息map，根據地圖規格對障礙物進行膨化處理，設定起點s以及目標點g，并將起點s加入Open列表中。

（2）搜索Open 中實際代價與估計代價和最小的節點n，將n加入Closed列表并刪除Open列表中的n。

（3）基于父節點n向四周擴展，具體為向四個傾斜方向擴展，即地圖的右上、右下、左上、左下四個方向，并且每擴展一步的同時向相應的方向搜索，將搜索到的跳點加入到跳點集合中。

（4）刪除跳點集合中與父節點n的直接路徑穿過障礙物的節點，確?？梢杂脽o限鄰域行進模式構成路徑。

（5）將跳點集合中的點添加到Open列表中。

（6）如果跳點集合中存在目標點g，則終止主程序并輸出路徑；否則回到步驟（2），直到找到目標點。

其效果如圖5所示。

圖5 改進算法模型

3 算法的仿真與實驗

3.1 改進JPS算法的仿真與對比

3.1.1 復雜地圖仿真

為了說明本文提出的改進JPS算法的效果，在同一臺計算機（Windows10，Intel Core i5，內存4 GB）上進行仿真。分別在U 型地圖（200×200）和大型樓層地圖（530×530）上進行仿真。

如圖6 所示，傳統的JPS 算法規劃的路徑中存在一部分路徑貼著障礙物，這部分路徑會增加機器人行走時與障礙物碰撞的幾率。而改進JPS 算法規劃出來的路徑則不存在這種問題，并且由于改進JPS算法減少了構成路徑的跳點的數量，使得規劃路徑的轉彎次數大大減少。為了排除實驗的偶然性，分別在兩個地圖中各取50組不同的起點和目標點來進行仿真，并將一百組數據按路徑長度排序，可以看到其數據根據地形以及路徑長短的不同而變化，具體如圖7、8所示。

圖6 兩種算法仿真

圖7 算法搜索時間比較

在圖7中可以看到在路徑長度較短的實驗組中，改進的JPS算法與其傳統的JPS算法相比所用的時間基本上相差不大，并存在改進JPS 算法比JPS 算法搜索時間多的現象，但隨著路徑長度的增加，地圖復雜程度的加大，改進JPS算法明顯比傳統JPS算法要快，最快可以達到一個數量級以上。同時，查看平均時間可以看到，在這一百組數據中，改進JPS算法的所用時間明顯比傳統JPS算法所用時間要少。將100組數據中的兩種算法規劃的路徑長度進行對比，結果如圖8所示。

可以看出，改進JPS算法搜索出來的路徑平均長度都比傳統JPS算法的路徑平均長度要短，但是在路徑長度短實驗組中，有時會出現傳統算法求出的路徑比改進后的算法路徑短的情況，這是由于本文算法對障礙物進行膨化處理導致的，屬于正常的現象。隨著路徑長度的增加，地圖復雜度的加大，這種現象會慢慢消失。為了對比兩種算法的路徑危險度，將由100組起訖點得出的路徑進行等距離采樣100 個點，設定影響范圍d0=3，利用方程（5）和方程（6）來計算路徑的危險程度，在路徑危險度評估中，對每個點計算危險度，并將其加起來，就是整條路徑的危險度評分。其具體數據如圖9所示。

圖8 算法搜索的路徑長度比較

圖9 路徑危險度比較

如圖9 所示，改進JPS 算法的危險度遠遠低于傳統JPS算法的危險度，從上面的數據可以看到，改進JPS算法的平均路徑危險度為45.69，傳統的JPS算法的平均路徑危險度為77.85，改進JPS算法比傳統JPS算法危險度降低41.3%。其具體數據如表1所示。

表1 實驗組平均數據

3.1.2 不同規格地圖仿真

為了探索改進JPS算法在不同規格地圖中的性能，用MATLAB 在不同規格的簡單地圖中進行仿真，仿真數據如表2所示。

表2 不同規格地圖仿真數據

從表2 看到隨著地圖規格的增加，改進JPS 算法搜索效率的比值減小，綜合表1 的數據可以得出結論：改進JPS算法搜索速度的提升幅度與地圖規格大小無關，與障礙物復雜程度有關，障礙物復雜程度度越高，搜索速度提升幅度越大。

3.2 實驗測試

為了驗證算法的有效性，在現實中搭建一個模擬的柵格地圖，并將兩種算法規劃出來的路徑導入兩輪自平衡小車中進行實驗。實驗設備如圖10 所示，其實驗場景路線如圖11所示。

圖10 兩輪平衡小車

可以看到，在圖11（a）中，傳統JPS算法的規劃路徑在拐彎處距離障礙物過近，導致兩輪平衡小車的左輪與障礙物相撞，不能到達目標位置，故實際路徑只有一小段。在圖11（b）中，改進JPS 算法的規劃路徑與實際路徑并不重合，在每個拐彎處，由于小車具有速度不能原地轉彎，所以實際路徑超出規劃路徑的范圍，但是最后卻能夠成功地到達目標位置。

圖11 規劃出來的路徑與實際路徑比較

4 結論

傳統的JPS 算法規劃的路徑存在安全隱患。本文在柵格地圖中對移動機器人的工作環境進行建模，為了提高JPS算法的性能提出改進JPS算法。改進JPS算法能快速地生成一條起點到終點的無碰撞路徑，這不僅解決了路徑安全性的問題，還保留了傳統JPS算法高效尋優的性能。通過在MATLAB 上仿真，驗證了本文提出的改進JPS 算法無論是路徑尋優還是安全性能都優于傳統算法。