改進JPS算法融合DWA的多機器人路徑規劃

摘 要：針對傳統的跳點搜索（jump point search，JPS）算法在移動機器人路徑規劃時，存在路徑拐點以及中間跳點過多，路徑規劃時間較長等問題，提出了改進的跳點搜索算法I-JPS。I-JPS算法通過改進代價函數、引入叉積公式，來剔除冗余節點、增加機器人與障礙物之間的安全距離。同時引入了動態窗口法（dynamic window approach，DWA）作局部路徑規劃，用于機器人臨時避障和路徑平滑化，并通過改進DWA提高多機器人之間的避障優先級。最后引入了多機器人協同路徑規劃，多機器人可以共同合作并完成復雜的任務，機器人之間還可以共享信息、協調行動，并通過分工合作來解決問題，提高任務的完成效率。最后，實驗仿真結果表明改進后的算法相較于改進前的，在各方面都得到了極大的提升。

關鍵詞：跳點搜索；路徑規劃；動態窗口法；代價函數；多機器人

中圖分類號：TP242.6 文獻標志碼：A 文章編號：1001-3695（2024）11-007-3251-07

doi：10.19734/j.issn.1001-3695.2024.03.0099

Improved JPS algorithm fused with DWA for multi robot path planning

Ren Xiangrui， Wang Zhenggang^?， Tang Junyang

（College of Electrical Engineering， Anhui Polytechnic University， Wuhu Anhui 241000， China）

Abstract：For the traditional JPS algorithm in mobile robot path planning， there are path inflection points as well as too many intermediate jump points， and the path planning time is long. This paper proposed an improved jump point search （JPS） algorithm. The I-JPS algorithm eliminated redundant nodes and increased the safe distance between the robot and obstacles by improving the cost function and introducing the fork product formula. It also introduced DWA for local path planning for temporary obstacle avoidance and path smoothing by robots， and increased the priority of obstacle avoidance between multiple robots by improving DWA. Finally， it introduced multi-robot collaborative path planning， where multiple robots could work together and complete complex tasks， and the robots could also share information， coordinate their actions， and solve problems through division of labour to improve the efficiency of task completion. Finally， the experimental simulation results show that the improved algorithm is greatly improved in all aspects compared to the pre-improved one.

Key words：jump point search; path planning; dynamic window method; heuristic function; multiple robots

0 引言

在現代自動化領域，隨著技術的不斷發展，機器人系統廣泛應用于物流、制造、服務等多個領域，路徑規劃是機器人和自主系統中至關重要的一環，特別是在多機器人系統中。多機器人系統的路徑規劃問題涉及到如何高效地協調和規劃多個機器人的運動軌跡，以實現任務的順利完成^［1］。

機器人路徑規劃一直是機器人領域至關重要的組成部分，具有理論和應用價值。它幫助機器人解決在簡單或者復雜環境下需要應對的困難^［2］。路徑規劃方法可以分為全局路徑規劃和局部路徑規劃。全局路徑規劃包括傳統的蟻群算法^［3］、A^*算法^［4］、粒子群算法^［5］、Dijkstra 算法^［6］、遺傳算法^［7］等。局部路徑規劃包括動態窗口法^［8］、人工勢場法^［9］等。面對不同的復雜環境，選擇一個合適的算法對于路徑規劃來說尤為重要。

朱敏等人^［10］利用跳點搜索算法不均勻分配初始信息素，降低蟻群前期盲目搜索的概率；然后，引入切比雪夫距離加權因子和轉彎代價改進啟發函數，提高算法的收斂速度、全局路徑尋優能力和搜索路徑的平滑程度；最后，提出一種新的信息素更新策略，引入自適應獎懲因子，自適應調整迭代前、后期的信息素獎懲因子，保證了算法全局最優收斂。周滔等人^［11］選擇了A^*作為路徑規劃算法。建立了具有非完整約束特征的移動機器 人運動學模型和跟蹤誤差模型，采用改進的自適應軌跡跟蹤控制對A^*運動軌跡進行有效跟蹤。劉榮華等人^［12］提出改進雙向動態 JPS 算法。改進算法動態定義正、反擴展方向上的目標點，動態定義啟發函數，并利用動態約束橢圓對算法的擴展區域加以限制，以區分橢圓內、外區域的擴展優先級。苗紅霞等人^［13］提出了并行-交替式雙向跳點搜索算法。采用改進了預計代價函數的并行式雙向跳點搜索算法，然后，采用交替式雙向跳點搜索算法，規劃中心熱點區域內部的路徑。林信川^［14］提出一種融合跳點搜索和雙向并行蟻群搜索的改進算法。首先使用改進的跳點搜索算法生成雙向搜索的初始次優路徑，為雙向蟻群搜索提供初始搜索方向參考。其次在雙向并行蟻群搜索過程采用改進的轉移概率啟發函數，該函數在確定下一個轉移節點時考慮了避免AGV與障礙物碰撞的因素，同時通過設計信息素共享機制并結合改進的信息素增量及濃度兩種融合模型。

針對傳統跳點搜索算法在路徑規劃上存在時間過長、搜索效率低等問題。本文提出了改進的跳點搜索算法，該算法通過改進跳點的篩選規則，將障礙物膨化處理，提出了新的叉積擬合公式對路徑進行剪枝優化，得到一條性能最優的路徑。為考慮機器人尋路的安全性，本文又引入了障礙率，并將原本的代價函數做了全新的改進，將移動機器人的尋優路徑與柵格地圖中的隨機障礙物保持了一定的安全距離。最后考慮到路徑的平滑性，本文又引入了DWA局部路徑規劃^［15］，使移動機器人規劃出的路徑更加平滑。

1 傳統JPS算法及其改進

1.1 環境地圖構建

在移動機器人路徑規劃的研究中，環境建模是一個重要的步驟，它涉及對機器人所在環境的描述和表示。環境建模的目標是為路徑規劃算法提供一個準確的、可操作的環境表示，以便機器人能夠根據這個模型作出決策。

考慮環境建模的簡單且有易于實現，本文選用柵格法作為環境建模。如圖1所示，柵格法使用網格化的地圖來表示環境，將整個區域劃分為一系列的正方形或矩形網格，每個網格單元表示環境中的一個離散區域，可以是空的、障礙物或其他特定屬性。格柵地圖中白色方塊表示機器人可以自由通過的區域，黑色方塊表示障礙物。同時，柵格地圖中的障礙物都是進行過膨化處理的，只要被障礙物涉及的區域，無論大小，均用黑色方塊表示。柵格法的每一個方塊都有它獨一無二對應的坐標，具體公式為

x_i=a（mod（i，N_x）－0.5）

y_i=a（N_y+0.5－ceil（iN_y））（1）

其中：（x_i，y_i）表示第i個柵格的位置坐標，x_i是該柵格在水平方向上的坐標，y_i是該柵格在垂直方向上的坐標。mod（）表示取余運算，ceil（）表示取整運算，這些運算通常用于將實際坐標映射到柵格地圖中的柵格索引，N_x是柵格地圖的行數，N_y是柵格地圖的列數，a表示每個柵格的邊長。

1.2 傳統的跳點搜索算法

跳點搜索算法是一種用于路徑規劃的高效算法，它在A^*算法的基礎上進行了優化，適用于網格化地圖的路徑搜索。跳點搜索算法的核心思想是通過預處理和跳躍的方式，減少搜索空間，從而提高搜索效率。搜索過程中，在地圖的每個方向上對每個節點進行預處理，標記出可以進行跳躍的節點，JPS會跳過一些明顯不可能包含最優路徑的節點，探索真正可能包含最優路徑的節點，從而減少搜索開銷^［16］。

跳點搜索算法需要定義節點P的自然鄰節點與強制鄰節點，如圖2所示，灰色柵格即表示沒有被障礙占據的自由空間，白色柵格表示節點P的自然鄰節點， 藍色柵格表示節點P的強制鄰節點，如圖2（c）（d）所示。

關于了解跳點搜索算法，需要了解它的定義，強迫鄰居和自然節點。強迫鄰居指的是從一個節點出發，在向鄰居節點探索的過程中，由于障礙物的存在，某個鄰居節點成為“強迫”的，它是被迫被探索的，而不是自然地成為探索路徑的一部分。在JPS算法中，當算法發現一個自然節點后，會探索該節點的鄰居，如果某個鄰居節點被發現是一個強迫鄰居，算法會將其添加到路徑中。這種策略幫助算法在規劃路徑時更好地適應和繞過障礙物，提高了路徑的質量和效率，而在無障礙物環境中，查詢的節點稱為自然節點。

1.3 改進的跳點搜索算法

1.3.1 改進啟發函數

跳點搜索算法結合了A^*與Dijkstra算法的廣度優先搜索和貪心算法的啟發式搜索，通過一個估價函數來評估搜索過程中每個節點的優先級，有效地在搜索空間中選擇下一個要擴展的節點，從而達到減少搜索范圍的目的。其中總的評價函數為

f（n）=g（n）+h（n）（2）

其中：n表示路徑的當前節點，f（n）表示總的代價函數，是從起始點到目標節點的總代價，它的值越小則越優。g（n）表示實際代價函數，它表示從起始點到節點n的實際代價，是固定不變的。h（n）是估計函數，表示從當前節點n到目標節點的預計代價成本，它往往是代價函數最重要的一部分。

為提高傳統的JPS算法在路徑規劃中的效率，將改進其代價函數，代價函數在路徑規劃中是至關重要的，因為它直接影響算法選擇擴展的節點，可以結合實際代價和啟發式代價，以更準確地確定節點的優先級。改進后的代價函數為

f（n）=g（n）+1+αβe^Q+h（n）（3）

其中：α為機器人當前位置到目標點的距離；β為起始點到目標點的距離。Q表示障礙覆蓋率，為

Q=pP×100%（4）

其中：P表示整個柵格地圖中所有的方塊，包括白色機器人可以自由通行方塊和黑色障礙物方塊的個數；p則表示黑色障礙物的方塊的個數。Q即被障礙物所占據的方格數量占總方格數量的比例，用于量化地圖中障礙物的密集程度，障礙率越高，表示地圖中的障礙物越密集，機器人在規劃路徑時更加復雜，需要更謹慎地避免這些區域。在柵格地圖的導航和路徑規劃中，障礙率有助于機器人系統更好地理解環境，提高決策的準確性和效率。

如圖3所示，引入新的代價函數后，改進了傳統跳點搜索算法中存在的多處危險節點等情況，使機器人與障礙物之間保持了合適的安全距離，讓規劃出的路徑安全性得到了極大的提升。通過去除危險節點，可以提高路徑規劃系統的可靠性，確保機器人在移動過程中不會遇到潛在的危險或障礙。同時跳點的輻射范圍變大，讓算法搜索目標的能力增強，迭代次數變少，搜索速度增加。

1.3.2 路徑節點優化

對于改進前的JPS算法，存儲了大量無用的跳點，導致計算量大、冗余節點多、路線過于靠近障礙物等一系列問題，本文提出了一種基于線性插值的剪枝算法，提高了運行效率，讓規劃出來的路徑得到最優的效果。改進的具體步驟如下所示。

a）對JPS算法規劃出來的路徑的每一個點進行遍歷，利用本文的改進算法，遍歷路徑中的每一個節點，對任意兩個節點進行連線，即為剪枝后的路徑。

如圖4所示，利用剪枝法剪枝前的路徑是A→B→C→D，對AC兩點進行剪枝，剪枝后的路徑為A→C→D，再次剪枝后為A→D。

b）剪枝后的路徑并非為最終路徑，還需要檢查當前節點（X_N，Y_N）與后面第二個節點（X_N+2，Y_N+2）以及后面節點之間的路徑是否與障礙物發生碰撞。

c）將當前節點（X_N，Y_N）與后面第二個點（X_N+2，Y_N+2）利用改進算法后的路徑與所有障礙物進行碰撞檢測，再利用向量叉積的符號判斷兩線段是否相交。叉積公式如下：

?=（A_X－C_X）（D_X－C_X）*（D_X－C_X）（A_X－C_X）（5）

假設線段AC與CD相交，那么其叉積結果?的符號將決定它們是否相交。如果叉積為正值，則表示相交，否則不相交。如圖5所示，可以是AC，也可以是AD。本文算法將剪枝后的路線與所有障礙物的邊進行叉積運算，作為碰撞檢測。

d）根據叉積結果?判斷，如果叉積為負，則說明剪枝成功，未發生碰撞，如圖4中的AC路徑，則表示剪枝成功了。再保留優化后的路線，刪除原始的多余路徑。如圖4中AD路徑所示，發生了碰撞，則優化失敗，刪除路徑上優化的路徑，并繼續檢查優化后的路徑，直到整個路徑被優化完成。

e）改進算法在剪枝過程中并不局限于每個拐點之間的剪枝。它可以在一條線段中截取需要的點作為剪枝點。DE是一條線段，拐點C可以在線段DE中的任意一點來連線，連線CE，線段CE與障礙物發生碰撞，繼續檢測到線段DE中的G點連接CG，線段CG并沒有與障礙物發生碰撞。同時該算法也可以檢測到除DE上G點之外的，例如F點，但F點不優于G點，所以該算法選取G點作為最優剪枝點。

經過這個優化步驟，路徑中的多余中間節點會被刪除，以避開障礙物，從而得到一條更加優化的路徑。在計算總路徑的長度，本文依然使用歐氏距離，并對這些距離進行累加。

S₁=（X₂－X₁）²+（Y₂－Y₁）²

S₂=（X₃－X₂）²+（Y₃－Y₂）²

S_n=（X_n+1－X_n）²+（Y_n+1－Y_n）²（6）

S_line=S₁+S₂+…+S_n（7）

其中：S₁為第一個點（X₁，Y₁）到第二個點（X₂，Y₂）之間的距離，S₂為第二個點（X₂，Y₂）到第三個點（X₃，Y₃）之間的距離，直到S_n，S_line將這些距離進行累加處理，為路線的總長。算法的具體流程如下：

a）柵格地圖初始化，將起點與終點確定，選擇合適的障礙物膨脹尺寸，并確定好障礙物的覆蓋率方便后面計算。

b）初始化空的openlist數組，用于存儲可擴展的節點。初始化 flag=1，表示鄰居節點未在障礙物列表中出現。將起點加入openlist中，根據改進后的最優f（n），尋找openlist中f值最小的點，為current。

c）判斷當前點current是否為最終目標點，如果是，則尋路結束，最終路徑生成，無須進行以下步驟。如果不是，繼續進行。

d）如果 flag 仍然為1，表示鄰居節點有效且不在障礙物列表中，計算鄰居節點的啟發式估計值h（n）和綜合代價f（n）。在openlist中刪除current，closelist中加入current當前點。

e）繼續探索下一個current點，在 openlist中選擇具有最小f（n）值的節點，作為下一個要擴展的節點。對于current在八個方向的鄰居點neighbor進行判斷，如果neighbor不可通過或者已經存在于closelist中，跳過。如果不在openlist中，則加入，如果存在，通過G值判定neighbor是否為父節點current，并更新G值。重復步驟c）d），直到當前點為終點。

f）遍歷openlist中所有跳點，判斷跳點間是否存在障礙物，不存在則利用多邊剪枝算法刪除多余的跳點。不斷更新迭代后形成最終路徑，規劃完成。

2 動態窗口法及改進

2.1 機器人運動模型分析

移動機器人在進行路徑規劃時會遇到很多難以預料的復雜情況，靜態路徑規劃已經不能滿足移動機器人對動態障礙物的躲避，而動態窗口法可以解決，對移動的障礙物進行有效實時的躲避。動態窗口法通過在速度空間中搜索合適的速度和方向組合，考慮機器人的動力學約束，以找到在給定時間范圍內的最佳運動策略。它具有簡單、實時性強等優點。同時，動態窗口法使用一個“窗口”來限制速度空間的搜索范圍。這個窗口基于機器人當前狀態和動力學特性，包括最大線速度、最大角速度和加速度限制等，窗口的設計是為了保持搜索的效率和合理性^［17］。

動態窗口法是基于運動學模型的一種經典的局部路徑規劃算法，通過對機器人的線速度和角速度進行采樣，并在采樣周期內對移動機器人的運動軌跡進行模擬。如果移動機器人運動軌跡是圓或者是直線，那么速度空間中的線速度和角速度變化可以反映機器人的運動狀態，機器人的運動模型如下：

x_t=x_t－1+ν_xΔtcosθ_t－ν_yΔtsinθ_t

y_t=y_t－1+ν_xΔtsinθ_t+ν_yΔtcosθ_t

θ_t=θ_t－1+ω_tΔt（8）

其中：x_t，y_t，θ_t分別代表了移動機器人在世界坐標系下的位置姿態。

2.2 速度采樣

速度采樣是DWA算法中的一個關鍵步驟，它涉及在機器人當前狀態下對速度空間進行離散采樣，生成一系列可能的速度和方向組合，以在這些組合中尋找最優的運動軌跡。根據自動引導車的自身要求和其他環境的要求，對采樣的條件進行限制，并限制在一個合理的范圍之類，需要滿足以下條件：

a）移動機器人最大最小速度的約束。

移動機器人的線速度采樣和最佳角速度采樣應控制在最佳區間，約束如下：

v_m={（ν，ω）|ν∈［v_min，v_max］，ω∈［ω_min，ω_max］}（9）

其中：v_min、v_max為移動機器人最小、最大線速度；ω_min、ω_max為移動機器人最小、最大角速度。

b）移動機器人加減速的約束。

機器人的速度采樣應考慮電機性能，機器人的加速度和減速度都在電機性能允許的范圍內。具體而言，這涉及到的關鍵約束如下：

V_d=（v，w）|v∈［v_c－_bΔt，v_c+_aΔt］w∈［w_c－_bΔt，w_c+_aΔt］（10）

其中：v_c、ω_c表示機器人當前的線速度和角速度；_c、_c表示機器人最大線加速度和最大角加速度；_b、_b表示機器人最大線減速度和最大角減速度。

c）移動機器人安全距離的約束。

為確保移動機器人在接近障礙物時的安全性，必須在機器人到達障礙物之前采取最大減速度，使其速度迅速降為零。這樣做可以確保機器人在靠近障礙物時能夠迅速停止運動，從而避免與障礙物發生碰撞。其公式為

V_a=（v，w）|v≤2·dist（v，w）·_b

w≤2·dist（v，w）·_b（11）

其中：dist（v，ω）為（v，ω）對應軌跡障礙物的最近距離。綜合以上，動態窗口法的最終速度為

v_r=v_m∩v_d∩v_a（12）

2.3 評價函數及優化

動態窗口法的評價函數通常被設計為一個代價函數，目的是根據機器人當前狀態和運動窗口內的線速度、角速度組合來評估每個可能的運動指令。代價函數的設計影響了最終路徑規劃的質量，通常會包括與目標點的距離、與障礙物的距離、線速度角速度、動態窗口大小等多個方面的考慮。其具體的評價函數公式為

G（v，w）=σ（a₁·heading（v，w）+a₂·dist（v，w）+a₃·velocity（v，w））（13）

其中：heading（v，ω）表示方位角評價函數，為當前速度下軌跡切線與目標點的夾角；dist（v，ω）表示距離評價函數，為當前速度下軌跡與靜態障礙物的最近距離；velocity（v，ω）表示速度評價函數，為當前規矩速度的大小。σ為平滑系數，a₁、a₂、a₃為各項的加權系數。

傳統的DWA評價函數在移動機器人局部路徑規劃時可能存在避障過于激進，導致規劃路徑過分迂回，影響了路徑的快速性。容易陷入局部最優解，而難以全局搜索到更優的路徑等情況。因此，通過增加dist2（v，ω）和dist3（v，ω）兩個函數，dist2（v，ω）表示評價模擬軌跡終點到動態障礙物的最近距離，通過增加對動態障礙物的識別能力，提高機器人躲避障礙物的靈敏度。dist3（v，ω）則表示評價模擬軌跡終點到未知障礙物的最近距離，為了提高避障的靈敏度。具體改進的評價函數如下：

G（v，w）=σ（b₁·heading（v，w）+a₃·velocity（v，w）+

a₂·dist1（v，w）+a₄·dist2（v，w）+a₅·dist3（v，w））（14）

b₁=a₁·1+e^（Rdistk）（15）

其中：a₄、a₅為新增項的加權系數；R為移動機器人轉彎時的半徑；k為變量，其值為1或2或3，表示dist1、dist2、dist3機器人遇到靜態障礙物、動態障礙物以及未知障礙物的三種不同情況。引入新的系數b₁，增加了停車等待狀態的DWA，當多臺機器人同時運行并產生路徑交叉時，較長路徑的機器人將主動停車等待，以優化行進序列，確保較短路徑的機器人能夠更快地完成任務，以提高靈活性。該算法能夠讓機器人在動態環境下避免規劃不合理的路徑，且在遇到動態障礙物時能及時作出正確應對，并優化了動態窗口法。

同時，改進前移動機器人根據靜態路線的拐點作為導航點，改進后的DWA，導航點自適應地均勻插入靜態路線的每一個存在的點，從前往后，依次作為移動機器人的目標導航點。極大地減少了機器人運動時路徑規劃的誤差，局部動態路徑規劃的準確率和精度得到了很大的提升。

3 多機器人及融合算法

3.1 多機器人

對于多機器人，相比于單機器人，多機器人系統可以并行執行任務，從而提高整體效率。每個機器人可以專注于執行特定的子任務，加快任務完成速度。多機器人系統具有冗余性，即使其中的某個機器人出現故障或受到干擾，其他機器人仍然可以繼續執行任務，提高系統的魯棒性和穩健性。多機器人系統還可以同時覆蓋更大的區域，從而適用于大規模的任務，如搜索與救援、勘探、環境監測等。

多機器人進行路徑規劃時，需要在考慮彼此之間的相互作用和路徑沖突，防止它們在相同的位置或路徑上交叉。同時，多機器人在實時性要求高的情況下，路徑規劃需要考慮到動態環境中的變化，及時調整機器人的路徑以適應新的情況。

如圖5所示，為多機器人路徑規劃時可能會出現的四種交叉情況。引入優先級法，主要思想是當兩個機器人出現路徑交叉時，優先級低的機器人給優先級高的讓路，優先級高的機器人先行，并把優先級低的機器人當成障礙物處理。具體來說，系統為每個機器人或任務分配一個優先級，高優先級的機器人或任務具有更高的執行權，這可以確保在緊急情況下，高優先級的任務或機器人能夠更快地完成，從而維護系統的整體效率。對于本文的路徑規劃算法，設置離目標點越遠的機器人優先級越低，確保路徑較短的率先完成任務，提高工作效率。

除了引入了避障優先級思想，還引入了多機器人分布式任務分配，如圖6所示，機器人的任務分配一般有集中式和分布式任務分配，集中式任務分配有一個機器人擔任主機器人，它與下面的子機器人進行信息交互，但子機器人之間沒有任何聯系，分布式任務分配不需要主機器人，由子機器人相互之間進行信息交涉，兩兩之間都可以進行交流，對于本文的路徑規劃更為合適。

3.2 融合JPS算法與DWA及多機器人

將改進后的JPS算法融合多機器人再融合改進后的DWA，目的是針對JPS算法和DWA的優點和缺點進行相結合，優缺互補。改進的JPS算法得到了靜態已知障礙物環境下的最優解，但對于動態障礙物和未知障礙物，無法處理，DWA有良好的局部路徑規劃能力，但容易陷入局部最優解，所以將兩者相結合。同時，多機器人系統可以同時執行多個任務，提高任務的并行性和整體完成效率。

改進后的JPS算法結合了全局規劃路徑和DWA算法，通過提取全局規劃路徑上的關鍵點作為DWA算法的中間指引點，實現在動態環境中為DWA算法提供方向，避免陷入局部最優的狀況。該優化后的DWA算法還能夠有效區分動態障礙物和靜態障礙物，從而消除一些已知障礙物對路徑的干擾，進一步提高算法運算速度。整體而言，這種融合算法結合了兩種算法的優點，既具備避障功能，又能夠規劃出最短路徑，從而在復雜環境中表現得更為靈活和高效。具體流程如圖7所示。

4 實驗仿真

4.1 單機器人路徑規劃仿真實驗

為了驗證本文提出的I-JPS算法的有效性和性能，進行了一系列的實驗仿真。仿真的設備配置為 Windows 11專業版，處理器為Intel Core i5-11400H，仿真運行平臺為MATLAB2021a。

為了驗證實驗的可行性，在MATLAB平臺分別搭載了20×20和30×30的柵格地圖，分為簡單環境和復雜環境。簡單環境為單機器人路徑規劃，復雜環境為多機器人路徑規劃，多機器人實驗設置了三個機器人協同規劃。

針對文獻［16］在路徑規劃時，路徑長度過長以及文獻［17］危險節點過多問題，并驗證本文I-JPS算法的高效性，將原始的兩種算法，文獻［16，17］兩種算法和本文算法在相同的實驗條件下進行一系列的比對。

首先進行20×20地圖的簡單環境單機器人靜態障礙物實驗仿真。

如圖8所示，分別將原始的A^*算法、原始的跳點搜索算法、文獻［16，17］的改進算法和本文的改進算法在20×20的柵格地圖環境下進行一系列對比，圖中三角形表示移動機器人的起始點，圓形表示目標點，黑色方塊表示靜止障礙物。其實驗結果如表1和圖9所示。實驗進行了30次，最終的運行時間、路徑長度、拐點數和搜索節點均按取30次平均數所得。

由實驗仿真結果可以看出，仿真通過對比不同路徑規劃算法在任務性能上的表現，發現本文的I-JPS算法相較于其他算法具有顯著優勢。在計算規劃耗時方面，I-JPS算法僅需耗時原始A^*算法的11.96%、文獻［16］算法的17.91%、JPS算法的33.88%。路徑長度上，I-JPS算法相比其他算法仍有一定優勢，僅為原始A算法的89.94%、文獻［16］算法的93.77%。在拐點數和搜索節點數方面，I-JPS算法相較于其他算法分別僅有原始A^*算法的70%的拐點數和62.6%的搜索節點數，文獻［17］的70%的拐點數。相比于文獻［17］存在大量危險節點，靠近障礙物的情況，I-JPS算法的危險節點個數為0，極大地提高了路徑規劃的安全性和穩定性。以上結果表明，在單機器人路徑規劃時，I-JPS算法在綜合性能上表現卓越，是一種高效的路徑規劃算法。

下面進行單機器人局部路徑規劃仿真，表2為移動機器人運動學參數的設置，評價函數的五個參數分別取值a₁=0.3、a₂=0.5、a₃=0.2、a₄=0.5、a₅=0.5。

如圖10所示，在動態環境中對I-JPS算法與DWA耦合的移動機器人路徑規劃仿真實驗，分別設置了一個移動障礙物和三個未知障礙物，黃色方塊為移動障礙物，坐標為（13，14），紅色線段代表移動障礙物的運動軌跡，灰色方塊代表移動障礙物，其坐標分別為（2，7）（8，6）和（9，3）。機器人通過躲避已知障礙物、未知障礙物和動態障礙物最后順利到達終點，其最終運行的軌跡如圖11（a）所示。通過本文改進的DWA，其運行的姿態角度變化如圖11（b）所示，線速度和角速度的變化如圖11（c）所示。

4.2 多機器人路徑規劃仿真實驗

多機器人可以同時執行任務，相對于單機器人，能更迅速地完成一系列任務，這對于需要在有限時間內完成的任務非常重要。下面進行多機器人的路徑規劃實驗仿真，首先在30×30的復雜環境下進行靜態障礙物的實驗仿真。

如圖12所示，通過對比兩種原始算法、兩種改進算法和本文改進后的I-JPS算法可以看出，原始的A^*算法的拐點、冗余節點過多。原始JPS算法的危險節點過多、拐點相對偏多。文獻［16］算法提高了路徑規劃的安全性，危險節點大大減少，但規劃出的路徑仍有很大提升的空間。文獻［17］算法雖然規劃出的路徑相當短，但危險節點并未作出及時的處理。由圖12可知，本文提出的I-JPS算法在考慮去除危險節點的情況下，保證規劃出的路徑最優、用時最短且拐點最少，達到了理想的效果。

如圖13和表3所示，表3中的時間、路徑長度、拓展點數和總的拓展節點均為三條移動機器人路線所得數據的總和，實驗結果均為進行30次實驗所取得的平均值。根據實驗數據可以得出，在多機器人處于靜態障礙物的復雜環境下，本文改進后I-JPS算法在時間、拐點數、路徑長短和拓展點數均優于原始的算法和文獻［16，17］的算法。

下面進行多機器人動態路徑規劃的研究。如圖14所示，三角形代表機器人的起點，星號代表機器人的終點，圖14（a）中，三個機器人分別開始了它們的動態路徑規劃，機器人1即將開始躲避黃色的移動動態障礙物，機器人2沒有碰到動態障礙物，無須躲避，機器人3已經完成了動態障礙物的躲避。其中，紅色方塊代表未知障礙物。如圖14（b）所示，多機器人按照避障優先級，完成了三個機器人在中心點相遇的過程。

如圖15所示，其中（a）為多機器人已完成路徑規劃，動態路徑的長度分別為34.172 0、29.728 0、36.478 0。姿態角度分別為-2.132 7、-2.741 4、2.335 8。圖（b）為三個機器人線速度的變化，圖（c）為三個機器人角速度的變化，圖（d）為三個機器人角度的變化。 綜上所述， 本文提出的I-JPS算法可以為機器人在復雜環境中快速且有效地規劃出全局路徑。同時，當路徑上出現動態障礙物以及未知障礙物時，機器人也能夠通過局部路徑規劃順利繞開障礙物，確保自身安全。最后，對于多機器人系統之間的協調問題，算法也能夠根據動態優先級規則完成機器人之間的避讓。實驗結果表明，該改進算法可以很好地適應于各種簡單以及復雜的環境，為移動機器人規劃出一條安全無碰撞路徑，且在沒有人為干涉的前提下處理各種突發狀況。

5 結束語

本文針對傳統的JPS算法在路徑規劃中無效跳點過多、路徑不安全等缺點，提出了一種改進的跳點搜索算法，稱為I-JPS算法。新算法通過引入向量叉積公式對多余節點進行去除，同時通過改進代價函數進一步提高路徑規劃的時間，并增大了機器人與障礙物之間的安全距離。對于未知和動態障礙物，本文引入了DWA并進行進一步的改進，改進后的DWA可以讓多機器人在路徑規劃時避免發生碰撞并遵循避障有優先級原則。實驗結果表明，改進后的多種算法相較于改進前的，得到了極大的提升。同時本文的不足之處是多機器人運行時計算量較大，DWA動態局部路徑規劃時，機器人運行速度比較慢，偶爾會出現局部路徑過長等現象。

參考文獻：

［1］陳浩， 陳珺， 劉飛. 基于自主探索的移動機器人路徑規劃研究 ［J］. 計算機工程. ［2024-05-17］. https：//www.cnki.com.cn/Article/CJFDTotalJSJC20240419005.htm. （Chen Hao， Chen Jun， Liu Fei. Research on mobile robot path planning based on autonomous exploration ［J/OL］. Computer Engineering. ［2024-05-17］. https：//www.cnki.com.cn/Article/CJFDTotalJSJC20240419005.htm.）

［2］賀志剛， 毛劍琳， 楊鄒，等. 一種面向地下管網環境的多機器人路徑規劃算法 ［J］. 機器人， 2024， 46（1）： 94-104， 117. （He Zhigang， Mao Jianling， Yang Zou， et al. A Multi robot path planning algorithm for underground pipeline network environment ［J］. Robot， 2024， 46（1）： 94-104， 117.）

［3］Dorigo M， Socha K. An introduction to ant colony optimization ［M］// Handbook of Approximation Algorithms and Metaheuristics. 2018： 395-408.

［4］Duchoň F， Babinec A， Kajan M， et al. Path planning with modified A star algorithm for a mobile robot ［J］. Procedia Engineering， 2014， 96： 59-69.

［5］Jain M， Saihjpal V， Singh N， et al. An overview of variants and advancements of PSO algorithm ［J］. Applied Sciences， 2022， 12（17）： 8392.

［6］Dhulkefl E， Durdu A， Terziolu H. Dijkstra algorithm using UAV path planning ［J］. Konya Journal of Engineering Sciences， 2020， 8： 92-105.

［7］Reddy G T， Reddy M P K， Lakshmanna K， et al. Hybrid genetic algorithm and a fuzzy logic classifier for heart disease diagnosis ［J］. Evolutionary Intelligence， 2020， 13： 185-196.

［8］Liu Lisang， Lin Jiafeng， Shi Peng， et al. Path planning for smart car based on Dijkstra algorithm and dynamic window approach ［J］. Wireless Communications and Mobile Computing， 2021， 2021： 1-12.

［9］Chen Yanli，Bai Guiqiang，Zhan Yin， et al. Path planning and obstacle avoiding of the USV based on improved ACO-APF hybrid algorithm with adaptive early-warning ［J］. IEEE Access， 2021， 9： 40728-40742.

［10］朱敏， 胡若海， 卞京. 基于改進蟻群算法的移動機器人路徑規劃 ［J］. 現代制造工程， 2024（3）： 38-44. （Zhu Min， Hu Ruohai， Bian Jing， et al. Mobile robot path planning based on improved ant colony algorithm ［J］. Modern Manufacturing Engineering， 2024（3）： 38-44.）

［11］周滔， 趙津， 胡秋霞，等. 復雜環境下移動機器人全局路徑規劃與跟蹤 ［J］. 計算機工程， 2018， 44（12）： 208-214. （Zhou Tao， Zhao Jin， Hu Qiuxia， et al. Global path planning and tracking of mobile robots in complex environments ［J］. Computer Engineering， 2018， 44（12）： 208-214.）

［12］劉榮華， 王欣， 吳迪，等. 改進雙向動態JPS算法的移動機器人全局路徑規劃 ［J］. 計算機應用研究， 2024， 41（4）： 1117-1122. （Liu Ronghua， Wang Xing， Wu Di， et al. Global path planning for mobile robots using improved bidirectional dynamic JPS algorithm ［J］. Application Research of Computers， 2024， 41（4）： 1117-1122.）

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

［14］林信川. 跳點搜索融合雙向并行蟻群算法的AGV路徑規劃研究 ［J］. 南京信息工程大學學報， 2024， 16（4）： 504-512. （Lin Xinchuan. Research on AGV path planning with jump point search fusion and bidirectional parallel ant colony algorithm ［J］. Journal of Nanjing University of Information Technology， 2024， 16（4）： 504-512.）

［15］孫巖霆， 王榮杰， 蔣德松. 融合A^*與DWA算法的水面船艇動態路徑規劃 ［J］. 儀器儀表學報，2024，45（1）：301-310. （Sun Yanting， Wang Rongjie， Jiang Desong. Dynamic path planning of surface craft by integrating A * and DWA algorithms ［J］. Chinese Journal of Scientific Instrument， 2024，45（1）：301-310.）

［16］黃智榜， 胡立坤， 張宇，等. 基于改進跳點搜索策略的安全路徑研究 ［J］. 計算機工程與應用， 2021， 57（1）： 56-61. （Huang Zhibang， Hu Likong， Zhang Yu， et al. Research on secure path based on improved skip point search strategy ［J］. Computer Engineering and Applications， 2021， 57（1）： 56-61.）

［17］龔軼群， 朱琳. 醫院場景下多機器人系統雙層路徑規劃算法 ［J/OL］. 系統仿真學報. ［2024-03-19］. （Gong Yiqun， Zhu Lin. A double layer path planning algorithm for multi robot systems in hospital scenarios ［J/OL］. Journal of System Simulation. ［2024-03-19］.）