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

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

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

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

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

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

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

本研究采用柵格法對自主移動機器人在靜態(tài)和動態(tài)環(huán)境下的路徑規(guī)劃進行分析，進而驗證JPSG算法在靜態(tài)環(huán)境下的可行性和在動態(tài)環(huán)境下的良好適應(yīng)性。

1 柵格建模

首先對環(huán)境建模作如下假設(shè)：

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

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

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

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

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

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

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

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

2 JPSG算法原理

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

2.1 改進遺傳算法

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

2.1.1 選擇算子

輪盤賭法的選擇方式是根據(jù)概率且將概率大小與適應(yīng)度相關(guān)聯(lián)，從而使有較高適應(yīng)度的個體具有更大優(yōu)勢。表示為：

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

2.1.2 交叉算子

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

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

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

2.1.3 變異算子

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

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

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

2.1.4 插入算子

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

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

2.1.5 適應(yīng)度函數(shù)

個體i的適應(yīng)度表示個體在種群生存的優(yōu)勢程度，用于區(qū)分個體的優(yōu)劣。

式中：Fi為路徑長度，F(xiàn)為起點與終點之間的距離，ε為在區(qū)間服從均勻分布的隨機數(shù)，m為最優(yōu)跳點個數(shù)。

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

2.2 JPS算法

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

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

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

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

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

2.2.1 跳點評估函數(shù)

通過搜索規(guī)則對跳點進行評估，選擇出最優(yōu)跳點以組成最優(yōu)路徑。評估函數(shù)如下：

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

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

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

2.2.2 openlist列表

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

3 JPSG算法流程

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

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

4 路徑規(guī)劃仿真研究

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

4.1 基于JPS算法的路徑規(guī)劃

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

圖6 基于傳統(tǒng)JPS算法的路徑規(guī)劃結(jié)果Fig.6 Path planning result based on traditional JPS al‐gorithm

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

4.2 靜態(tài)環(huán)境下路徑規(guī)劃

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

圖8 靜態(tài)環(huán)境下路徑規(guī)劃的仿真結(jié)果Fig.8 Simulation results of path planning in static environment

圖9 靜態(tài)環(huán)境下規(guī)劃路徑長度的仿真結(jié)果Fig.9 Simulation results of path planning length in static environment

表1 靜態(tài)環(huán)境下算法性能對比Table1 Comparison of algorithm performance in static environment

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

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

圖10 基于JPSG算法的路徑規(guī)劃結(jié)果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算法相較于傳統(tǒng)RRT算法和RRT-Dijkstra算法具有短時間尋優(yōu)能力，與Dijkstra 算法相對比具有更高的搜索效率。

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

4.3 動態(tài)環(huán)境下路徑規(guī)劃仿真

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

表4 動態(tài)環(huán)境下不同算法的性能對比結(jié)果Table 4 Performance comparison results of different algorithms in dynamic environments

圖11 在靜態(tài)和動態(tài)環(huán)境下路徑規(guī)劃仿真結(jié)果的對比Fig.11 Comparison of simulation results of path planning in static and dynamic environments

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

圖13 動態(tài)環(huán)境下規(guī)劃路徑長度的仿真結(jié)果Fig.13 Simulation results of path planning in dynamic environment

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

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

5 結(jié) 論

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