基于一種混合遺傳算法的移動機器人路徑規劃

裴以建 楊亮亮 楊超杰

摘 ?要： 移動機器人路徑規劃問題一直是機器人學研究的核心內容之一，而遺傳算法作為智能仿生學算法在路徑規劃中得到了廣泛的應用。針對傳統遺傳算法存在局部搜索能力差的問題，文中研究在已知環境下運用一種基于遺傳算法和模擬退火算法相結合的技術對移動機器人進行最優路徑的規劃方法。算法采用柵格法對環境建立模型，同時在遺傳算子中添加插入算子和刪除算子以優化路徑。Matlab仿真實驗結果表明，該算法相對于基本遺傳算法的收斂速度，搜索質量等有了明顯的提高。

關鍵詞： 移動機器人; 遺傳算法; 模擬退火算法; 柵格法; 路徑規劃; Matlab

中圖分類號： TN830.1?34; TP242 ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）02?0183?04

Mobile robot path planning based on a hybrid genetic algorithm

PEI Yijian， YANG Liangliang， YANG Chaojie

（School of Information， Yunnan University， Kunming 650500， China）

Abstract： The path planning problem of the mobile robot is always one of the core contents of robotics research， and the genetic algorithm， as an intelligent bionics algorithm， has been widely used in path planning. In allusion to the poor local search capability problem of the traditional genetic algorithm， the mobile robot optimal path planning method is researched in this paper by using the genetic algorithm and simulated annealing algorithm combined technology in a known environment. In the algorithm， the grid method is used to construct the environmental model. The insert operator and delete operator are added in genetic operators to optimize the path. The experimental results of the Matlab simulation show that in comparison with the basic genetic algorithm， the algorithm has an obvious improvement in convergence speed and search quality.

Keywords： mobile robot; genetic algorithm; simulated annealing algorithm; grid method; path planning; Matlab

0 ?引 ?言

移動機器人是一種集環境感知、動態決策與規劃、行為控制與執行等多項功能于一體的高智能化機器系統[1]。2013年美國提出制造業回歸，規劃機工業機器人作為先進產業，機器人革命成為第三次工業革命的切入點和重要增長點。在實際生活中，移動機器人在面對各種復雜的障礙物環境，主要依靠機器人對環境的感知，自行設計一條最優或者次優的路線達到指定的目的點[2]。路徑規劃主要解決移動機器人的兩個主要問題：選擇合理的途徑是機器人能夠達到指定位置;優化機器人到達指定位置所用的時間、精確度、路徑是否最短等條件。機器人路徑規劃圖如圖1所示。

由圖1可知，機器人的路徑規劃主要是對現實問題建立一種抽象化模型，根據符合條件的路徑搜索算法尋求一種合適的路徑。目前應用廣泛的路徑算法有人工勢場法[3]、柵格法[4]、神經網絡算法[5]等。憑借各自的優勢在路徑規劃中經常使用，但是這些算法也存在著局部極小值、計算量大等缺點。遺傳算法作為路徑規劃方面研究的熱點，遺傳算法策略的設計從微觀上主要討論群體的規模、參數的設計以及遺傳算子的方法對求解能力的影響，宏觀上主要以遺傳算法為基礎，加入其他算法形成混合遺傳算法以提高遺傳算法的尋優能力。基本遺傳算法雖然具有良好的尋優能力，但由于早熟現象以及收斂速度慢等影響著性能。為解決遺傳算法的缺陷，本文采用柵格法建立模擬環境模型，增加插入算子和刪除算子，把具有很強的局部搜索能力的模擬退火算法引入遺傳算法中以改善機器人的搜索能力。

1 ?環境模型的建立

本文的機器人使用的環境模型采用文獻[6]提出的網格理論，如何確定網格的大小是主要問題，較小的網格對障礙物的描述更精確，但會影響計算機存儲空間，導致算法變得復雜，因此需要綜合考慮網格的大小[7]。在考慮機器人的工作環境模型時，通常做一些假設：

1） 在工作空間中移動不應考慮機器人的大小，在二維空間中移動。

2） 所構建的地圖網格大小一樣，用數字“1”標記障礙物網格，可用數字“0”標記機器人的路徑可行區域。

3） 機器人在運動過程中，障礙物的大小和位置不會改變。

如圖2所示，描述網格相對位置方面優勢的直角坐標法能夠計算分析路徑長度和路徑的可行性。另外，序列法占用的內存空間相對較少，常用在遺傳操作。本文將這兩種方法相結合，當然在算法過程中這兩種方法需要運用換算公式進行轉換。

[xi=Ni%nyi=Ni/n， ?i=1，2，…，n] ? ? ? ? ?（1）

式中：（[xi]，[yi]）表示路徑點坐標;[Ni]表示網格序列;n表示坐標長度。

2 ?遺傳模擬退火算法設計

2.1 ?路徑編碼方式

遺傳算法中，影響計算時間的原因有編碼長度和搜索空間，編碼長度過長及空間太大會增加計算時間，常用的編碼方法有二進制編碼、浮點數編碼或符號編碼等。考慮到遺傳算法在編碼、交叉和變異時容易操作，本文路徑個體的產生采用序號編碼方式，考慮到障礙物在柵格中的序號問題，所以在規劃路徑時應當排除和障礙物一樣的序號。如圖3所示，序號編碼能使個體長度變短，機器人在到達目標點時得到的長度有所不同，所以會產生可變長度的個體。

2.2 ?初始種群生成

全局最優解的收斂受初始種群規模的影響，規模太大會使進化時間變長，規模太小會導致在搜索路徑中提前結束。遺傳算法中常采用簡單的隨機生成種群的方法，但是過多的不可行路徑增加了計算時間，降低了搜索速度。本文在進行種群初始化時，所產生的路徑點和障礙物的序列號不相同，排除了路徑點不可行狀態，這樣移動機器人到達目的地時可生成一條無障礙路徑。

2.3 ?適應度函數

適應度函數是用來度量群體中各個個體在優化計算中接近最優解的優良程度[8]。假設障礙物大小是經過碰撞處理的，也就是說存在一個安全距離使得機器人在臨界狀態不發生碰撞，將機器人看作一個質點，那么最優路徑應滿足兩個條件：最優路徑應沒有碰撞障礙;路徑長度應為最短。

假設Si，Si+1為路徑中的兩點，Oj表示一個障礙物，則適應度函數滿足：

[fit1=1，SiSi+1?Oj=?，i=1，2，…，m;j=1，2，…，n0，others] （2）

式中：m為路徑上的點;n為障礙物的個數。如果不發生碰撞則其適應度為1，反之為0。

要求機器人的行走路徑是最短的，可用如下關系式表示：

[fit2=i=1n-1Pi1+1num-1] ? ? ? ?（3）

式中：[Pi]表示路徑中第i段直線段的長度;num表示初始種群的數量。

最后得到的適應度函數為：

[fit=fit1×fit2] （4）

2.4 ?模擬退火算法

模擬退火算法在基于梯度的優化方法難以解決的復雜優化問題上能夠顯示出優良的特性，可以抑制遺傳算法的早熟現象，能夠跳出局部最優解[9]。模擬退火算法在和遺傳算法結合時，主要解決以下問題：

1） 合理的選擇初始溫度T0和較好的溫度更新函數;

2） 如何防止遺傳算法的早熟現象。

2.4.1 ?溫度更新函數

為了確保算法從起始就有很強的遍歷性，初始溫度T0的選取足夠高以保證避免陷入局部最優解。溫度更新函數用于修改外循環中的溫度T的值，本文采用的更新函數為：

[T（t）=T01+αt] ? ? ? ? ? ? ? ? （5）

式中：[T0]為初始溫度;[α]為常數。隨著遺傳代數的增加，遺傳前期物種的生存壓力較小，弱勢個體可以生存;遺傳后期物種生存壓力大，降溫速度較小，便于選擇最優個體。

2.4.2 ?個體接收準則

新個體產生后，需要判斷哪些優良個體是否加入種群中生存。如果父代個體i生成子代新個體i′，需要構造目標函數以保證變異生成過的個體具有優良的特性被接收。

[SA_R（i）=j=0n-1（xj+1-xj）2+（yj+1-yj）2] （6）

[P（i?i′）=exp-SA_R（i′）-SA_R（i）t，SA_R（i′）>SA_R（i）1，SA_R（i′）≤SA_R（i）] （7）

式中：SA_R（i）表示路徑長度;[P（i?i′）]為新子代個體被遺傳的概率;t為溫度參數。

2.5 ?遺傳算子

2.5.1 ?選擇算子

依照“優勝劣汰”的原則，從當前群體中選擇一些優良的個體遺傳到下一代群體，通常采用輪盤賭法[10]，根據個體的適應度值，依據概率函數選擇個體是否進入下一代，適應度值越小，被選擇的概率就越高。通過選擇可以使優秀個體增加。設種群的大小為n，則個體被選中的概率為：

[Pi=1fit（i）i=1n1fit（i）] ? ? ? ? ? ? ? ? （8）