裴以建 楊亮亮 楊超杰

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

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

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

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

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

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

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

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

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

3） 機(jī)器人在運(yùn)動(dòng)過(guò)程中，障礙物的大小和位置不會(huì)改變。

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

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

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

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

2.1 ?路徑編碼方式

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

2.2 ?初始種群生成

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

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

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

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

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

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

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

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

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

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

[fit=fit1×fit2] （4）

2.4 ?模擬退火算法

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

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

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

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

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

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

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

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

新個(gè)體產(chǎn)生后，需要判斷哪些優(yōu)良個(gè)體是否加入種群中生存。如果父代個(gè)體i生成子代新個(gè)體i′，需要構(gòu)造目標(biāo)函數(shù)以保證變異生成過(guò)的個(gè)體具有優(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）表示路徑長(zhǎng)度;[P（i?i′）]為新子代個(gè)體被遺傳的概率;t為溫度參數(shù)。

2.5 ?遺傳算子

2.5.1 ?選擇算子

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

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