基于跳點搜索-遺傳算法的自主移動機器人路徑規劃

田雅琴，胡夢輝，劉文濤，侯寅智

（太原科技大學 機械工程學院，山西 太原 030024）

機器人在軍事領域中的應用越來越廣泛。在軍事活動中，機器人快速、高效地完成任務的第1步在于確定任務路線即路徑規劃。在具有若干障礙物的復雜環境下，自主移動機器人路徑規劃的核心是在起點與終點之間規劃一條綜合性能（如規劃速度、路徑長度、能量損耗等）最優的路徑[1]。綜合考慮復雜三維地形和動態障礙物環境等諸多因素下的路徑規劃是目前研究的新方向[2]。算法的優劣性在路徑規劃中起著關鍵作用?，F有的算法包括傳統算法和智能算法，其中常用的路徑規劃算法有遺傳算法[3-8]、人工勢場法[9-11]、蟻群算法[12]、灰狼算法[13]、跳點搜索（jump point search, JPS）算法[14]和A*算法[15]等。無論是傳統算法還是智能算法都存在著自身缺陷，但可以通過融合算法彌補各算法的不足而使其呈現更優異的性能。

遺傳算法是一種智能搜索算法。它以生物進化為原型，相較于傳統的路徑規劃算法具有較好的全局搜索能力和收斂性，但局部搜索能力差。其具有良好的可擴展性，易與其他算法結合，因此是融合算法中常用的一種算法。楊博等[16]采用中間插值法，通過改進交叉算子、變異算子和適應度函數來優化遺傳算法，避免了早熟現象發生，但是未考慮動態障礙物環境下算法的適應性。陳亮等[17]將遺傳算法與鯨魚算法相結合，使得融合算法能在短時間內完成進化，但是當規劃空間規模較大時仍存在迭代次數較大的問題。徐興等[18]提出了基于災變策略的遺傳算法，相對于傳統遺傳算法，可避免早熟現象且縮短尋優時間。Zhou 等[19]研究后發現，面對現實復雜地形和環境，采用單一的遺傳算法因受到算法本身的限制而不能得到理想的結果。

遺傳算法借用達爾文進化理論以算法的形式表現出來就是遺傳算法的運行過程。遺傳算法在計算種群適應度函數時具有較大的計算量，導致算法執行處理時間較長，搜索效率低下[20]。JPS 算法實際上是通過改進A*尋路算法而發展起來的一種新型啟發式算法，其相對于A*尋路算法具有更高的搜索效率，但其規劃路徑的質量易受到周圍障礙物影響[21]。

基于遺傳算法效率低、運行時間長和JPS算法整體搜索能力易受周圍障礙物影響，為了滿足戰時需求，作者提出一種以快速性、準確性、穩定性為目標的優化算法——跳點搜索-遺傳（jump point search-genetic，JPSG）算法。該算法兼顧了遺傳算法全局搜索能力和JPS 算法較強的局部搜索能力，可以在自主移動機器人的路徑規劃中突破局部最優解，提高求解速度，尋優準確率，以及增強該融合算法對動態環境的適應能力。

本研究采用柵格法對自主移動機器人在靜態和動態環境下的路徑規劃進行分析，進而驗證JPSG算法在靜態環境下的可行性和在動態環境下的良好適應性。

1 柵格建模

首先對環境建模作如下假設：

1）在環境空間中分布著有限個靜態障礙物和動態障礙物，每個障礙物大小相等且不考慮高度因素，但需考慮動態障礙物的移動速度大小和方向；

2）自主移動機器人僅僅考慮移動方向，不考慮移動速度大??；

3）用黑白網格區分障礙物和自由移動空間，連續坐標代表移動路徑，不重復連續相鄰坐標的距離之和代表路徑長度。

設自主移動機器人的運動環境空間為A。將機器人移動步長默認為單位長度，并確定其運動空間為30×30的柵格矩陣（即30×30方格圖），如圖1所示。由圖可知，自主移動機器人在非規則邊界區域的移動方向共有8個。

圖1 30 × 30的柵格矩陣示意圖Fig.1 Schematic diagram of 30×30 grid matrix

柵格矩陣中存在若干靜態障礙物和動態障礙物。對于任意位置的柵格都有唯一的坐標(x,y)和序號與之相對應，在30×30 的柵格環境中柵格序號s和坐標(x,y)的關系為：

式中：fix為向零舍入運算，mod為求余運算，G為障礙物矩陣。

由柵格的坐標(x,y)結合障礙物矩陣判斷該位置是否為障礙物。

2 JPSG算法原理

JPSG算法是利用JPS算法高效率地搜索出一條局部最優路徑來減少遺傳算法的迭代次數，提高整體種群質量。采用JPSG算法可以有效解決遺傳算法早期盲目搜索造成的收斂時間長、最優解不穩定的問題，能在較少的已知數據下保障最優解。隨著迭代次數增加，最優解越早出現，則對提高遺傳算法的穩定性越有好處。

2.1 改進遺傳算法

改進遺傳算法主要通過采用自適應交叉概率、變異概率和改進適應度函數計算方法來加快算法的收斂速度。

2.1.1 選擇算子

輪盤賭法的選擇方式是根據概率且將概率大小與適應度相關聯，從而使有較高適應度的個體具有更大優勢。表示為：

式中：pi為輪盤賭法中的種群個體的概率值；fi為種群個體的適應度值；j為種群數量，j=1, 2, …,M。

2.1.2 交叉算子

交叉算子的主要作用是產生新的個體。交叉概率越大，新個體產生速度越快，同時種群中最優個體被破壞的概率越大；交叉概率越小，遺傳算法的收斂速度越慢。表示為：

式中：pc為交叉概率，pmax、pmin分別為本次迭代中種群的最大、最小路徑長度。

由式(4)可知：若當前種群的最大路徑長度與最小路徑長度的比值變大時，交叉概率隨之變大。通過不斷交叉使種群路徑長度加速向當前迭代種群最優路徑長度靠攏；當交叉概率較小時，可以避免種群中最優路徑長度被破壞。

2.1.3 變異算子

變異運算是使遺傳算法突破局部最優解的重要方法。變異概率太小，則產生新個體的幾率較小，且容易出現早熟現象；變異概率太大，則隨機概率較大。表示為：

式中：pm為變異概率，xs、ys分別為起點的橫坐標和縱坐標，xg、yg分別為終點的橫坐標和縱坐標。

若迭代時迭代種群內最大路徑長度與起點與終點之間的距離相差較大，則當變異概率逐漸增大時，變異后得出更優的路徑長度，而不至于使種群路徑長度陷入局部最優路徑長度。當變異概率減小時，不會破壞當前種群內路徑長度的穩定性。

2.1.4 插入算子

根據式(6)可以判斷路徑中相鄰柵格節點間是否連續。根據式(2)中G值是否為0，來判斷每相鄰兩步之間是否需要重新插入節點。表示為：

式中：abs 為絕對值函數，max 為取最大值函數，floor為向下取整函數，xnow、ynow分別為當前節點的橫坐標和縱坐標，xnext、ynext分別為下一節點的橫坐標和縱坐標，xinsert、yinsert分別為插入點的橫坐標和縱坐標。

2.1.5 適應度函數

個體i的適應度表示個體在種群生存的優勢程度，用于區分個體的優劣。

式中：Fi為路徑長度，F為起點與終點之間的距離，ε為在區間服從均勻分布的隨機數，m為最優跳點個數。

原適應度值僅僅由路徑長度的倒數決定，當路徑長度相近并接近最優解時，適應度值相差不大而難以區分，改進后以Fi與F的差值作為分母。當2個路徑長度接近時能較好區分出更優路徑長度而加速收斂。

2.2 JPS算法

通過式(11)所示當前節點與上一節點之間的距離關系來判斷當前方向是直行還是沿對角線方向。跳點搜索算法的優點是可以兼顧當前節點和上一節點的位置，即根據上下節點的位置關系判斷下一步前進方向，同時為當前節點識別出自然鄰居和強制性鄰居。

式中：xpre、ypre分別為上一節點的橫坐標和縱坐標。

自然鄰居定義為當前節點沿對角線方向上的下一個節點、水平方向上的下一個水平節點和垂直方向上的下一個垂直節點。若當前節點的鄰居節點中有障礙物，且從上一節點經過當前節點到達下一節點的距離比不經過當前節點到達下一節點的距離小，則稱下一節點為強制鄰居，如圖2和圖3所示。

圖2 斜線強制鄰居示意圖Fig.2 Schematic diagram of oblique line forced neighbors

圖3 直線強制鄰居示意圖Fig.3 Schematic diagram of linear forced neighbors

2.2.1 跳點評估函數

通過搜索規則對跳點進行評估，選擇出最優跳點以組成最優路徑。評估函數如下：

式中：fcost為當前經過路徑長度，fvalue為當前點與終點之間的距離，fjps為評估函數值。

通過路徑評估函數可以評判起點、跳點和終點依次連接后的路徑是否為最佳路徑。跳點搜索如圖4所示。圖中深灰色和淺灰色柵格為跳點，其中將最優跳點（淺灰色柵格）連接后，可以構成一條由起點到終點的最優路徑。

圖4 跳點搜索示意圖Fig.4 Schematic diagram of jump point search

2.2.2 openlist列表

在openlist列表中儲存著下一個跳點信息，根據跳點評估函數計算出各個跳點值的大小，進行排序。openlist列表中存在著函數值相同的跳點，在其中總是優先彈出第1個跳點的位置，導致后面的跳點無法被考慮到是否為最優跳點，因此，將函數值相同的跳點一一彈出，按照所彈出跳點的位置進行路徑規劃，并根據路徑長度選擇最優跳點。

3 JPSG算法流程

JPSG算法流程如圖5所示。JPS 算法具有高效的局部搜索能力，改進自適應遺傳算法具有較好的全局搜索能力。將JPS算法的解析結果融入隨機概率，初始化種群以加快迭代速度，同時將JPS算法融入變異算子，隨著斷點位置不同可得到多種局部最優結果，最后通過對比得到最優路徑。

圖5 JPSG算法流程圖Fig.5 Flow chart of JPSG algorithm

4 路徑規劃仿真研究

在所建立的柵格矩陣上進行自主移動機器人路徑規劃仿真。

4.1 基于JPS算法的路徑規劃

基于傳統JPS算法的路徑規劃結果如圖6所示。將算法中openlist 列表進行改進，得到的路徑規劃結果如圖7所示。圖6中的路徑長度為31.556 3，圖7中的路徑長度為30.970 5，可見圖7中的路徑為最優路徑。圖7中，在柵格坐標（11, 12）處存在2條到下一節點的函數值相同的路徑，算法改進后由于openlist列表在（11, 12）處彈出等值點，實現了提前規劃最優路徑。

圖6 基于傳統JPS算法的路徑規劃結果Fig.6 Path planning result based on traditional JPS al‐gorithm

圖7 基于改進JPS算法的路徑規劃結果Fig.7 Path planning result based on improved JPS algo‐rithm

4.2 靜態環境下路徑規劃

分別采用JPSG 算法、改進JPS 算法、改進遺傳算法和傳統遺傳算法進行靜態環境下的路徑規劃，并將規劃結果進行對比，來驗證JPSG算法的優越性。在相同的靜態環境下，采用MATLAB2021b軟件運行上述4 種算法。將規劃路徑的長度、準確率、收斂迭代次數和規劃時間等作為參數對算法性能進行評估，其中準確率是指該算法下出現種群最小路徑長度的次數與最大迭代次數的比值。在30×30 的柵格矩陣上進行仿真。參數設置如下：M=10 000 個，0.6≤pc≤1.0，0.02≤pm≤0.10，最 大迭代數T=100 次。路徑規劃仿真結果如圖8 所示。采用JPSG 算法、改進JPS 算法、改進遺傳算法和傳統遺傳算法得到的路徑規劃結果如圖8 所示。JPS 算法中沒有種群規模和迭代次數，因此將基于JPSG 算法、改進遺傳算法和傳統遺傳算法的規劃路徑長度進行對比，如圖9 所示，算法性能對比如表1 所示。

圖8 靜態環境下路徑規劃的仿真結果Fig.8 Simulation results of path planning in static environment

圖9 靜態環境下規劃路徑長度的仿真結果Fig.9 Simulation results of path planning length in static environment

表1 靜態環境下算法性能對比Table1 Comparison of algorithm performance in static environment

由圖8 可知：相對于改進JPS 算法、改進遺傳算法和傳統遺傳算法，JPSG算法具有更好的整體搜索能力，利用JPS算法的快速局部搜索能力可加快收斂速度，且不容易陷入局部最優解；JPS 算法的整體搜索能力易受周圍障礙物的影響；遺傳算法易陷入局部最優解。

由表1可知：相較于改進遺傳算法和傳統遺傳算法，JPSG 算法的規劃路徑長度最短，收斂迭代次數最少；準確率分別提高了72%、90%；規劃時間分別減小了12%、15%；方差值分別減小了30%、31%，表明JPSG 算法的規劃結果更加穩定?？梢奐PSG 算法融合了2 種算法的優點，能夠避免陷入局部循環、加快收斂速度以及具備較高的搜索正確率，使自主移動機器人得到最優的規劃路徑。此外，基于JPSG 算法分別在20×20 和30×30柵格矩陣上的路徑規劃結果如圖10 所示。將JPSG算法與文獻[22]和文獻[23]提出的RRT（rapidly-ex‐ploring random tree,快速搜索隨機樹）算法和改進遺傳-鯨魚融合算法等進行對比，算法性能對比如表2和表3所示。

圖10 基于JPSG算法的路徑規劃結果Fig.10 Path planning results based on JPSG algorithm

表2 JPSG算法與文獻[22]中算法的性能對比Table 2 Performance comparison between JPSG algorithm and the algorithm in literature [22]

表3 JPSG算法與文獻[23]中算法的性能對比Table 3 Performance comparison between JPSG algorithm and the algorithm in literature [23]

由表1 和表2 可知：JPSG 算法和JPS 算法在簡單障礙物下搜索效率較高；由表2 得出知改進JPS算法相較于傳統RRT算法和RRT-Dijkstra算法具有短時間尋優能力，與Dijkstra 算法相對比具有更高的搜索效率。

由表3 可知，JPSG 算法相較于文獻[23]中的遺傳算法、改進遺傳算法和改進遺傳-鯨魚融合算法在地圖規模和障礙物簡單的狀況下的搜索效率更優。

4.3 動態環境下路徑規劃仿真

上述仿真是在靜態環境下進行的，在實際中機器人所處工作環境大多是動態的，因此在動態環境下分別采用JPSG 算法、改進JPS 算法、改進遺傳算法和傳統遺傳算法進行路徑規劃仿真與對比，來驗證JPSG 算法適應動態環境的優異性。設定機器人的探測半徑為，其移動速度為單位時間內的移動步長，時間步長Δt=0.5 s，動態障礙物的移動速度為2/s。當無動態障礙物時，自主移動機器人按照原優化路徑行走。由單位時間和動態障礙物的移動速度可以計算出機器人與動態障礙物發生碰撞的時間。利用MATLAB2021b軟件運行上述4種算法，得到動態環境下路徑規劃仿真結果。在靜態和動態環境下路徑規劃仿真結果的對比如圖11 所示。其中，當采用JPSG 算法時，機器人遇到第1 和第2 個動態障礙物后的路徑規劃如圖12 所示。圖中帶有空心箭頭的實線代表動態障礙物的運動路徑，帶有實心箭頭的實線代表靜態環境下的規劃路徑，點劃線代表動態環境下的規劃路線，虛線代表動態障礙物的運動范圍，箭頭代表運動方向。 將基于JPSG算法、 改進遺傳算法和傳統遺傳算法的規劃路徑長度進行對比如圖13所示，算法性能對比如表4所示。

表4 動態環境下不同算法的性能對比結果Table 4 Performance comparison results of different algorithms in dynamic environments

圖11 在靜態和動態環境下路徑規劃仿真結果的對比Fig.11 Comparison of simulation results of path planning in static and dynamic environments

圖12 機器人遇到第1，2個動態障礙物后的路徑規劃示意Fig.12 Schematic of path planning after the robot encounters the first and second dynamic obstacles

圖13 動態環境下規劃路徑長度的仿真結果Fig.13 Simulation results of path planning in dynamic environment

由圖11可知：遺傳算法對動態環境的適應性較差；在障礙物不斷變化的情況下，JPS 算法的整體搜索能力易受周圍障礙物影響；JPSG算法對動態環境的適應能力較好，能快速收斂而節省搜索時間。

由表4 可知：相較于改進遺傳算法和傳統遺傳算法，JPSG 算法的規劃路徑長度最短，收斂迭代次數最少；準確率分別提高了55%、95%；規劃時間分別減小了12%、14%；方差值分別減小了50%、51%，表明JPSG 算法的規劃結果更加穩定?？梢奐PSG 算法融合了2 種算法的優點，能夠避免陷入局部循環、加快收斂速度以及具備較高的搜索正確率，使自主移動機器人得到最優的規劃路徑。

5 結 論

通過改進JPS算法的openlist 彈出機制優化了JPS 算法規劃路徑的準確性，同時采用自適應交叉算子和變異算子改進遺傳算法來優化收斂時間，最后將改進JPS 算法和改進自適應遺傳算法融合，得到JPSG 算法在靜態和動態環境下分別采用JPSG 算法、改進遺傳算法、傳統遺傳算法進行自主移動機器人路徑規劃，并將各算法下規劃的路徑進行對比，結果表明JPSG 算法在穩定性、快速性、準確性上具有明顯的優勢。