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

裴以建 楊亮亮 楊超杰

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

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

中圖分類號： TN830.1?34; TP242 ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： 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 ?引 ?言

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

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

1 ?環(huán)境模型的建立

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

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

2） 所構(gòu)建的地圖網(wǎng)格大小一樣，用數(shù)字“1”標(biāo)記障礙物網(wǎng)格，可用數(shù)字“0”標(biāo)記機器人的路徑可行區(qū)域。

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

如圖2所示，描述網(wǎng)格相對位置方面優(yōu)勢的直角坐標(biāo)法能夠計算分析路徑長度和路徑的可行性。另外，序列法占用的內(nèi)存空間相對較少，常用在遺傳操作。本文將這兩種方法相結(jié)合，當(dāng)然在算法過程中這兩種方法需要運用換算公式進(jìn)行轉(zhuǎn)換。

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

式中：（[xi]，[yi]）表示路徑點坐標(biāo);[Ni]表示網(wǎng)格序列;n表示坐標(biāo)長度。

2 ?遺傳模擬退火算法設(shè)計

2.1 ?路徑編碼方式

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

2.2 ?初始種群生成

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

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

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

假設(shè)Si，Si+1為路徑中的兩點，Oj表示一個障礙物，則適應(yīng)度函數(shù)滿足：

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

式中：m為路徑上的點;n為障礙物的個數(shù)。如果不發(fā)生碰撞則其適應(yīng)度為1，反之為0。

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

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

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

最后得到的適應(yīng)度函數(shù)為：

[fit=fit1×fit2] （4）

2.4 ?模擬退火算法

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

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

2） 如何防止遺傳算法的早熟現(xiàn)象。

2.4.1 ?溫度更新函數(shù)

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

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

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

2.4.2 ?個體接收準(zhǔn)則

新個體產(chǎn)生后，需要判斷哪些優(yōu)良個體是否加入種群中生存。如果父代個體i生成子代新個體i′，需要構(gòu)造目標(biāo)函數(shù)以保證變異生成過的個體具有優(yōu)良的特性被接收。

[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為溫度參數(shù)。

2.5 ?遺傳算子

2.5.1 ?選擇算子

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

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