基于跳點(diǎn)搜索-遺傳算法的自主移動(dòng)機(jī)器人路徑規(guī)劃

田雅琴，胡夢(mèng)輝，劉文濤，侯寅智

（太原科技大學(xué) 機(jī)械工程學(xué)院，山西 太原 030024）

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

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

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

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

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

1 柵格建模

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

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

2）自主移動(dòng)機(jī)器人僅僅考慮移動(dòng)方向，不考慮移動(dòng)速度大小；

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

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

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

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

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

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

2 JPSG算法原理

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

2.1 改進(jìn)遺傳算法

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

2.1.1 選擇算子

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

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

2.1.2 交叉算子

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

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

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

2.1.3 變異算子

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

式中：pm為變異概率，xs、ys分別為起點(diǎn)的橫坐標(biāo)和縱坐標(biāo)，xg、yg分別為終點(diǎn)的橫坐標(biāo)和縱坐標(biāo)。

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

2.1.4 插入算子

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

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

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

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

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

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

2.2 JPS算法

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

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

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

圖2 斜線強(qiáng)制鄰居示意圖Fig.2 Schematic diagram of oblique line forced neighbors

圖3 直線強(qiáng)制鄰居示意圖Fig.3 Schematic diagram of linear forced neighbors

2.2.1 跳點(diǎn)評(píng)估函數(shù)

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

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

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

圖4 跳點(diǎn)搜索示意圖Fig.4 Schematic diagram of jump point search

2.2.2 openlist列表

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

3 JPSG算法流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖10 基于JPSG算法的路徑規(guī)劃結(jié)果Fig.10 Path planning results based on JPSG algorithm

表2 JPSG算法與文獻(xiàn)[22]中算法的性能對(duì)比Table 2 Performance comparison between JPSG algorithm and the algorithm in literature [22]

表3 JPSG算法與文獻(xiàn)[23]中算法的性能對(duì)比Table 3 Performance comparison between JPSG algorithm and the algorithm in literature [23]

由表1 和表2 可知：JPSG 算法和JPS 算法在簡(jiǎn)單障礙物下搜索效率較高；由表2 得出知改進(jìn)JPS算法相較于傳統(tǒng)RRT算法和RRT-Dijkstra算法具有短時(shí)間尋優(yōu)能力，與Dijkstra 算法相對(duì)比具有更高的搜索效率。

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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