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

向浩 李哲文 張婷

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

關鍵詞：機器人路徑規劃 ?遺傳算法 ?網格法 ?路徑優化

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

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

1 ?遺傳算法與路徑規劃

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

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

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

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

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

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

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

路徑規劃中通過第二遺傳算法機制能夠解決機器人在處理過程中出現動態障礙物時，只根據獲得的最優路徑到達目的地的情況進行規劃的問題。

2 ?機器人工作空間劃分

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

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

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

（1）根據問題的內在知識，嘗試掌握整個問題空間中最優解所占空間的分布，然后在分布范圍內設置初始群。

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

3 ?適應度函數設置

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

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

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]之間的數字，產生子代個體h11和h12后，h5和h6交叉產生h13和 h14，h8和h10交叉產生h15和h16。這里用標志位判斷，能走就是0，不能走就是1，并且標志位被加起來由Sn表示，且所有位中的最小位是最佳解決方案。以這種方式，保留六個位，分成三組，選擇不同的交叉點用于單點交叉，并且消除具有大的附加標志的個體。然后繼續添加一些和新生成的個體組成一組繼續交叉，具有最小數量的標志的個體是最佳路徑。 仿真之后會發現個體{0，11，22，33，44，55，66，67，78，89，99}是最優解。

當最優個體的適應度和群體適應度不再上升或者適應度達到給定閾值時（本文給定的閾值為g），或者當迭代次數達到預設代數時，算法終止，并且預設代數被設置為100代。

5 ?結語

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

參考文獻

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

[2] 張捍東，鄭睿，岑豫皖.移動機器人路徑規劃技術的現狀與展望[J].系統仿真學報，2005，16（2）：439-443.

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

[4] 周明，孫樹持.彭曼午.基于遺傳算法的多機器人系統集中協調式路徑規劃[J].航空學報，2009，21（2）：146-49.