基于遺傳算法的機器人路徑規(guī)劃研究

向浩 李哲文 張婷

摘 ? 要：在移動機器人研究領(lǐng)域中，路徑規(guī)劃問題是一項非常值得研究的問題，一般是指在規(guī)劃路徑中使得移動機器人不會碰到任何障礙物。本文針對機器人的路徑規(guī)劃問題進行了分析研究，主要分析在靜態(tài)環(huán)境下，采取網(wǎng)格法對機器人工作空間進行劃分，運用遺傳算法對路徑尋優(yōu)，引入間斷無障礙路徑概念以簡化初始種群產(chǎn)生，最終通過改進操作算子。合理選擇交叉率、變異率以及分析調(diào)整適應(yīng)度函數(shù)中的加權(quán)系數(shù)獲得最佳路徑。

關(guān)鍵詞：機器人路徑規(guī)劃 ?遺傳算法 ?網(wǎng)格法 ?路徑優(yōu)化

中圖分類號：TP24 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標(biāo)識碼：A ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1674-098X（2019）08（c）-0119-02

路徑規(guī)劃是智能機器人領(lǐng)域的核心問題之一，也是機器人人工智能研究的重要方面。典型的機器人路徑規(guī)劃是指為機器人在其工作空間中完成給定任務(wù)提供安全且有效的運動路徑。通常，機器人可以選擇許多路徑來完成給定任務(wù)，常用的準(zhǔn)則有：最短路徑、最少能耗或最短使用時間。

1 ?遺傳算法與路徑規(guī)劃

遺傳算法的基本運算過程如下。

（1）初始化：首先設(shè)置進化計數(shù)器，使得初始進化計數(shù)t=0，最大進化計數(shù)為T，初始群體P（0）中隨機生成M個個體。

（2）個體評價：在群體P（t）中，計算各個個體的適應(yīng)度。

（3）選擇運算：選擇運算能夠把優(yōu)化的個體直接遺傳或配對交叉遺傳到下一代。在群體中個體的適應(yīng)度評估基礎(chǔ)上，將選擇算子作用于群體。

（4）交叉運算：交叉運算是遺傳算法中關(guān)鍵的一步，其交叉算子在遺傳算法中起到核心作用，交叉運算是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。

（5）變異運算：變異運算是指對群體中的個體串的某些基因座上的基因值作變動。

（6）終止條件判斷：如果t=T，則在演化過程中獲得的具有最大適應(yīng)度的個體被用作最優(yōu)解決方案輸出，并且計算終止。

路徑規(guī)劃中通過第二遺傳算法機制能夠解決機器人在處理過程中出現(xiàn)動態(tài)障礙物時，只根據(jù)獲得的最優(yōu)路徑到達目的地的情況進行規(guī)劃的問題。

2 ?機器人工作空間劃分

遺傳算法參數(shù)設(shè)定方法為：群體中的個體數(shù)量是s=30，并且交叉概率為pc=0.6。根據(jù)模型的不同表達方法，機器人所處的環(huán)境有三種典型的環(huán)境建模方法：網(wǎng)格方法，網(wǎng)格解耦方法，多面模型表示等，這里僅介紹網(wǎng)格方法建模。

機器人工作空間由網(wǎng)格方法劃分，網(wǎng)格由序列號標(biāo)識，序列號用作機器人路徑規(guī)劃參數(shù)代碼。如下面的圖1所示，機器人路徑空間是二維平面空間，障礙物的位置是已知的，并且障礙物的位置在機器人的運動期間不會改變。

通常遺傳算法中的初始種群設(shè)置可以采用以下策略：

（1）根據(jù)問題的內(nèi)在知識，嘗試掌握整個問題空間中最優(yōu)解所占空間的分布，然后在分布范圍內(nèi)設(shè)置初始群。

（2）隨機生成一定數(shù)量的個體，然后從中挑選最佳個體以添加到初始種群中。該過程是迭代的，直到初始群體中的個體數(shù)量達到預(yù)定規(guī)模。本文主要采用第二種方法對初始種群進行編程。

3 ?適應(yīng)度函數(shù)設(shè)置

在遺傳算法中，適應(yīng)度用來衡量個體利弊的指標(biāo)。 個體復(fù)制的數(shù)量根據(jù)適合度是否存在來確定，適應(yīng)度是驅(qū)動遺傳算法的動力。在特定的應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計應(yīng)該與解決問題本身的要求相結(jié)合。評估函數(shù)值與總路徑長度值成比例，即最短路徑長度用作單獨評估函數(shù)。路徑長度越短，路徑長度的適應(yīng)值越高，因此還需要在個體評估函數(shù)和適應(yīng)度函數(shù)之間進行映射。假設(shè)兩個相鄰網(wǎng)格的中心之間的距離是A并且單個路徑中包括的網(wǎng)格的數(shù)量是n，則單獨的評估函數(shù)可以取為f ＼u003d nA。 相應(yīng)的適應(yīng)度函數(shù)可取為g=fmax-f，其中fmax=18，令A(yù)=1可便于計算，適應(yīng)度函數(shù)可最終寫為g=19-n。

以上個體的適應(yīng)度為個體hn（n=1，2，3… …）表示機器人在其空間中的運動路徑，個體評估函數(shù)為 f＼ u003 d nA，適應(yīng)度函數(shù) g=19- n，個體 hn（ n=1，2，3…）表示機器人在其空間中的運動路徑，個體評估函數(shù)為 f，并且適應(yīng)度函數(shù)為18-n，該程序隨機生成100個單獨的種群，并分別使用網(wǎng)格數(shù)來表示以下模擬部分。以下10組結(jié)果可以解釋如何使用遺傳算法來優(yōu)化機器人路徑。

h1={0，1，11，21，22，23，24，35，45，55，65，66，67，68，78，88，99} ? f1=16 ?g1=2 ? ? 2/50

h2={0，1，11，21，22，23，24，35，36，37，47，57，67，78，89，99 } ? ? f2=15 ? g2=3 ? ?3/50

h3={0，11，21，22，33，44，55，65，66，67，78，89，99} ? ? ? ? ? ?f3=12 ? g3=6 ? ?6/50

h4={0，11，21，22，23，34，45，46，57，68，78，88，99} ? ? ? ? ? ?f4=12 ? g4=6 ? ?6/50

h5={0，11，22，33，44，55，65，66，67，68，79，89，99} ? ? ? ? ? ?f5=12 ? g5=6 ? ?6/50

h6={0，1，11，22，33，44，55，66，67，78，79，88，99} ? ? ? ? ? ? f6=12 ? g6=6 ? ?6/50

h7={0，11，21，22，23，33，43，54，65，66，67，68，78，88，99} ? ? ? f7=14 ? g7=4 ? ?4/50

h8={0，11，21，22，23，34，45，46，57，68，79，89，99} ? ? ? ? ? ?f8=12 ? g8=6 ? ?6/50

h9={0，11，21，22，23，34，45，46，47，57，67，78，89，99} ? ? ? ? ?f9=13 ? g9=5 ? 5/50

h10={0，11，21，22，33，44，55，66，67，68，78，88，89} ? ? ? ? ? f10=12 ?g10=6 ? 6/50

4 ?交叉仿真

本文通過選擇pc ＼u003d 0.9以隨機生成[0～1]之間的數(shù)字，產(chǎn)生子代個體h11和h12后，h5和h6交叉產(chǎn)生h13和 h14，h8和h10交叉產(chǎn)生h15和h16。這里用標(biāo)志位判斷，能走就是0，不能走就是1，并且標(biāo)志位被加起來由Sn表示，且所有位中的最小位是最佳解決方案。以這種方式，保留六個位，分成三組，選擇不同的交叉點用于單點交叉，并且消除具有大的附加標(biāo)志的個體。然后繼續(xù)添加一些和新生成的個體組成一組繼續(xù)交叉，具有最小數(shù)量的標(biāo)志的個體是最佳路徑。 仿真之后會發(fā)現(xiàn)個體{0，11，22，33，44，55，66，67，78，89，99}是最優(yōu)解。

當(dāng)最優(yōu)個體的適應(yīng)度和群體適應(yīng)度不再上升或者適應(yīng)度達到給定閾值時（本文給定的閾值為g），或者當(dāng)?shù)螖?shù)達到預(yù)設(shè)代數(shù)時，算法終止，并且預(yù)設(shè)代數(shù)被設(shè)置為100代。

5 ?結(jié)語

如何選擇遺傳算法的參數(shù)以及如何對其進行編碼是其應(yīng)用中的一個重要問題。本文針對機器人的路徑規(guī)劃問題進行了分析研究，主要分析在靜態(tài)環(huán)境下，采取網(wǎng)格法對機器人工作空間進行劃分，運用遺傳算法對路徑尋優(yōu)，引入間斷無障礙路徑概念以簡化初始種群產(chǎn)生，最終通過改進操作算子。合理選擇交叉率、變異率以及分析調(diào)整適應(yīng)度函數(shù)中的加權(quán)系數(shù)獲得最佳路徑。

參考文獻

[1] 劉國棟，謝宏斌，李春光.動態(tài)環(huán)境中基于遺傳算法的移動機器人路徑規(guī)劃的仿真[J].西安石油學(xué)院學(xué)報：自然科學(xué)版，2004（3）.

[2] 張捍東，鄭睿，岑豫皖.移動機器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望[J].系統(tǒng)仿真學(xué)報，2005，16（2）：439-443.

[3] 蔡自興，彭志紅.一種新的路徑編碼機制在移動機器人路徑規(guī)劃中的應(yīng)用[J].機器人，2001，23（3）：230-233.

[4] 周明，孫樹持.彭曼午.基于遺傳算法的多機器人系統(tǒng)集中協(xié)調(diào)式路徑規(guī)劃[J].航空學(xué)報，2009，21（2）：146-49.