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

李昌華，石如雪，李智杰，張 頡

(西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055)

0 引言

移動(dòng)機(jī)器人路徑規(guī)劃是指在復(fù)雜環(huán)境中，在不同條件的約束下，搜索從起點(diǎn)到終點(diǎn)的最優(yōu)或近最優(yōu)路徑[1]。移動(dòng)機(jī)器人路徑規(guī)劃建模主要有以下難點(diǎn)：(1)障礙物的定義[2]；(2)有效路徑的確定[3]。在過去幾十年里，許多學(xué)者對(duì)此進(jìn)行了大量的研究，并提出了一系列算法來解決這一優(yōu)化問題。其中，元胞自動(dòng)機(jī)建模具有時(shí)間、空間、狀態(tài)均離散，每個(gè)變量只取有限多個(gè)狀態(tài)，且其狀態(tài)改變的規(guī)則在時(shí)間和空間上都是局部的優(yōu)點(diǎn)，成為解決移動(dòng)機(jī)器人路徑規(guī)劃問題的有效方法之一[4]，元胞密度的增加能夠提高障礙物表示的精度，但也造成了算法的復(fù)雜度提升，搜索范圍呈指數(shù)增長[5-6]。因此，需要一種具有更好的多樣性和收斂性的智能算法來解決此問題。

近年來，智能算法由于其結(jié)構(gòu)簡單，控制參數(shù)較少，得到了廣泛的研究和應(yīng)用，尤以遺傳算法應(yīng)用最廣。遺傳算法是通過模擬自然界的進(jìn)化過程來搜索最優(yōu)解[7-8]，不僅具有編碼效率高、自組織性和自適應(yīng)性較強(qiáng)等優(yōu)勢(shì)，也可以同時(shí)處理多個(gè)個(gè)體，具有內(nèi)在隱并行性[9]。但針對(duì)復(fù)雜環(huán)境設(shè)計(jì)相應(yīng)的遺傳算子易產(chǎn)生非法個(gè)體，存在較大困難。Vincent等[10]將遺傳算法與粒子群算法相融合去處理在三維復(fù)雜環(huán)境下的問題，使用“單程序，多數(shù)據(jù)”并行編程縮短執(zhí)行時(shí)間，實(shí)現(xiàn)實(shí)時(shí)路徑規(guī)劃；魏彤等[11]將插入算子和刪除算子引入經(jīng)典遺傳操作算子中，在適應(yīng)度函數(shù)中考慮路徑連貫性，計(jì)算的適應(yīng)度值最高的路徑為最優(yōu)路徑。

然而遺傳算法本身運(yùn)算效率低，求解移動(dòng)機(jī)器人路徑規(guī)劃問題時(shí)容易陷入局部收斂。為了解決上述問題，引入元胞遺傳算法，元胞遺傳算法不但擁有元胞自動(dòng)機(jī)的部分特性，也繼承了遺傳算法的優(yōu)良品質(zhì)，它通過內(nèi)部隱性遷移機(jī)制作用，使得中心個(gè)體在其周圍鄰居間進(jìn)行遺傳操作，保留了種群的多樣性，也減少了算法陷入局部收斂的可能性[6]。

在本文中，對(duì)移動(dòng)機(jī)器人路徑規(guī)劃問題使用元胞模型進(jìn)行環(huán)境建模，使用元胞遺傳算法，借由分解演算法的慢度，考慮路徑平滑因素，找出可能的距離短且平滑的路徑，作為最優(yōu)性準(zhǔn)則，尋找路徑規(guī)劃問題的最優(yōu)解。結(jié)果表明，改進(jìn)的元胞遺傳算法為移動(dòng)機(jī)器人提供了一個(gè)高精度、低碰撞、低損耗的路徑。

1 元胞遺傳算法

1.1 元胞遺傳算法思想

元胞自動(dòng)機(jī)和遺傳算法結(jié)合而成的元胞遺傳算法具有啟發(fā)性的生物學(xué)思想。元胞遺傳算法可描述為：基于元胞自動(dòng)機(jī)的模型，將遺傳算法種群中的每個(gè)個(gè)體都視為一個(gè)元胞，將個(gè)體隨機(jī)映射到二維網(wǎng)格中，添加演化規(guī)則，進(jìn)行個(gè)體選擇、交叉和變異操作等遺傳操作，但遺傳操作僅限于元胞鄰域范圍內(nèi)。通過種群不斷得演化和迭代，最終尋找到最優(yōu)個(gè)體的解。

元胞自動(dòng)機(jī)中使用簡單的進(jìn)化規(guī)則操作就可以模擬復(fù)雜系統(tǒng)的變化過程，并展示局部種群如何影響整個(gè)種群的進(jìn)化過程。元胞遺傳算法思想還源于不斷變化的系統(tǒng)性能，可以有效解決復(fù)雜問題。

1.2 元胞自動(dòng)機(jī)鄰域模型

John Von Neumann于20世紀(jì)50年代，提出了元胞自動(dòng)機(jī)模型(cellular automata，CA)，該模型是根據(jù)預(yù)先指定的規(guī)則在時(shí)間和空間上由一系列離散單元形成的模型,它不同于通?；诙x的函數(shù)建立的動(dòng)態(tài)模型，它的單元空間由一系列具有相同規(guī)格的單元組成,在這個(gè)空間中，每個(gè)單元格處于有限數(shù)量的狀態(tài)，并且每個(gè)單元格根據(jù)特定的演化規(guī)則更新其自己的狀態(tài)。

經(jīng)典的元胞自動(dòng)機(jī)模型分為Von Neumann鄰域模型和Moore鄰域模型，Von Neumann鄰域模型是中心元胞只有上、下、左、右四個(gè)方位的鄰域元胞可供使用，Moore鄰域模型的中心元胞的鄰域是除Von Neumann鄰域的四個(gè)元胞外還包括左上、右上、左下、右下共8個(gè)方位的鄰域。使用元胞模型可以根據(jù)鄰域元胞的占用狀態(tài)快速判斷是否有障礙物，很好地達(dá)到避障效果。

1.3 隱性遷移機(jī)制

在元胞自動(dòng)機(jī)中，鄰居彼此重疊的個(gè)體具有隱性遷移機(jī)制，該機(jī)制可使最優(yōu)解在整個(gè)種群中平穩(wěn)擴(kuò)散。因此，與非結(jié)構(gòu)化種群遺傳算法相比，元胞遺傳算法可以更持久地保持種群多樣性。這種擴(kuò)散遷移機(jī)制允許元胞遺傳算法在搜索解空間時(shí)在全局搜索與局部優(yōu)化之間取得平衡[6]。鄰域中會(huì)影響個(gè)體遷移的重疊程度隨鄰域的大小而變化。通過更改規(guī)模，可以調(diào)整鄰域重疊的程度，從而影響全局搜索和局部優(yōu)化之間的平衡，保持進(jìn)化過程中的種群多樣性。這保證了使用元胞遺傳算法可以用來解決實(shí)際的復(fù)雜問題。

2 算法的模型構(gòu)建

圖1 顯示機(jī)器人R所在單元格及其相鄰單元格

目標(biāo)是找到機(jī)器人到達(dá)目的地的最短路徑和轉(zhuǎn)向次數(shù)最少的路徑?？紤]到元胞自動(dòng)機(jī)網(wǎng)格的性質(zhì)，可以認(rèn)為網(wǎng)格環(huán)境對(duì)應(yīng)于元胞自動(dòng)機(jī)。元胞自動(dòng)機(jī)是一個(gè)離散的時(shí)間動(dòng)態(tài)系統(tǒng)，即在每個(gè)時(shí)間點(diǎn)上，所有的細(xì)胞都根據(jù)傳遞函數(shù)同時(shí)移動(dòng)。結(jié)果，目標(biāo)環(huán)境適應(yīng)元胞自動(dòng)機(jī)的功能，使得所有障礙物在每個(gè)時(shí)間階段保持不變。

我們先假設(shè)要達(dá)到出口目標(biāo)G。因此，從目標(biāo)點(diǎn)G移動(dòng)到一行，并為每個(gè)單元格指定一個(gè)數(shù)字，通過這種方式將標(biāo)簽分配到單元格。單元格編號(hào)如圖2所示。

圖2 單元格編號(hào)

網(wǎng)格被轉(zhuǎn)換成一個(gè)加權(quán)網(wǎng)格，使得每個(gè)除障礙物之外的網(wǎng)格相對(duì)應(yīng)的數(shù)字顯示從所在位置到目標(biāo)的最小距離，而不考慮元胞的位置。每個(gè)單元的數(shù)量開始移動(dòng)，每個(gè)單元與其相鄰單元之間的最小距離計(jì)算到距G點(diǎn)最近的單元，并分配給該單元。

圖3 加權(quán)模式網(wǎng)格

3 路徑規(guī)劃

由于元胞自動(dòng)機(jī)模型是將地圖劃分為網(wǎng)格，基于網(wǎng)格的模型中的路徑查找包括遍歷平方單元的中心。在網(wǎng)格上計(jì)算的地圖存在以下問題：它們產(chǎn)生高度不切實(shí)際的空間利用率，不能保證回程的等效性，扭曲了路徑長度和機(jī)器人的行駛時(shí)間，因此需要加入平滑度因素進(jìn)行調(diào)節(jié)，以此來改進(jìn)適應(yīng)度函數(shù)，以求得到更加平滑和距離最短的路徑。

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

考慮到元胞的工作環(huán)境和環(huán)境的屏障輪廓，有必要確定元胞能夠以最低的成本通過的路徑。將要被最小化的適應(yīng)度函數(shù)分成判斷路徑的路徑長短和平滑程度兩部分來考慮。

路徑長度的計(jì)算公式如下：

(1)

式中,PL表示元胞行進(jìn)的路徑長度，或者換句話說，表示從起點(diǎn)到終點(diǎn)的路徑距離；(xi，yi)為第i個(gè)路徑節(jié)點(diǎn)的坐標(biāo)。

適應(yīng)度函數(shù)的第一部分，采用輪盤賭的方式，因?yàn)橐蟮氖菣C(jī)器人的最短路徑，所以取距離的倒數(shù)：

f1=1/PL

(2)

由于動(dòng)力學(xué)和運(yùn)動(dòng)學(xué)的限制，機(jī)器人在行駛時(shí)不應(yīng)轉(zhuǎn)彎太多，因此所產(chǎn)生的路徑需要平滑。路徑越平滑，三個(gè)連續(xù)點(diǎn)的夾角越大，相鄰三個(gè)點(diǎn)形成的角度也越大。會(huì)出現(xiàn)的四種情況是180度，鈍角，直角和銳角，其中180度的三個(gè)點(diǎn)位于一條直線，光滑度最好，其次是鈍角和直角。由于機(jī)器人動(dòng)力學(xué)的限制，機(jī)器人路徑不得具有銳角。因此，對(duì)于除直線以外的三種情況，懲罰函數(shù)值分別取5、20和無窮大。適應(yīng)度函數(shù)的第二部分是懲罰的總和，可以根據(jù)實(shí)際情況改變懲罰值的大小。計(jì)算公式如下：

AB2=(xi+1-xi)2+(yi+1-yi)2

(3)

BC2=(xi+2-xi+1)2+(yi+2-yi+1)2

(4)

AC2=(xi+2-xi)2+(yi+2-yi)2

(5)

(6)

(7)

A、B、C為連續(xù)三點(diǎn)構(gòu)成的三角形的三個(gè)角，AB、BC、AC為三角形的三條邊。

PS表示與路徑的平滑度有關(guān)的函數(shù)。

適應(yīng)度函數(shù)的路徑長度部分和路徑平滑度部分分別取一個(gè)權(quán)重，構(gòu)成完整的適應(yīng)度函數(shù)：

f=af1+bf2

(8)

3.2 遺傳算子

搜索引擎設(shè)計(jì)成從一個(gè)起點(diǎn)創(chuàng)建一條路徑。這條路徑就是種群中一個(gè)個(gè)體，然后將所有種群中的個(gè)體視為一個(gè)元胞，將個(gè)體隨機(jī)映射到二維網(wǎng)格中，添加演化規(guī)則，在元胞鄰域范圍內(nèi)進(jìn)行如下的遺傳操作，并存儲(chǔ)最佳和最差響應(yīng)。

3.2.1 選擇操作

在算法選擇操作中采用異步元胞遺傳算法，父代個(gè)體按照以下原理被選擇，來優(yōu)化生成路徑：

1)按照順序掃描方式，依次選擇中心元胞個(gè)體；

2)參考Moore鄰域結(jié)構(gòu)，找到中心元胞個(gè)體周圍鄰居；

3)計(jì)算鄰居個(gè)體適應(yīng)度，通過輪盤賭方式選擇出與中心元胞交叉的鄰居個(gè)體。

輪盤賭的方式可以有效的防止算法陷入局部最優(yōu)解，保證了部分非最優(yōu)的個(gè)體。計(jì)算公式如下：

(9)

3.2.2 同點(diǎn)交叉

采用同點(diǎn)交叉:

1)先確定一個(gè)交叉概率Pc，將選擇出的鄰居與中心個(gè)體一一配對(duì)；

2)然后對(duì)每一對(duì)個(gè)體產(chǎn)生一個(gè)[0，1]的隨機(jī)數(shù)r，如果r

3)若無除了起點(diǎn)和終點(diǎn)以外的其它相同點(diǎn)時(shí)，則對(duì)該對(duì)個(gè)體隨機(jī)指定的基因位置進(jìn)行交叉操作。

3.2.3 鄰域變異

變異主要是為了防止生成無效路徑，用以增加種群的多樣性，設(shè)定變異算子如下：

1)首先確定突變概率Pm，生成0到1之間的隨機(jī)數(shù)，然后比較突變概率Pm。如果小于Pm，則執(zhí)行變異操作；

2)隨機(jī)選擇一個(gè)交叉后的父代路徑點(diǎn)作為路徑的變異點(diǎn)，如果選擇的點(diǎn)是起點(diǎn)或者終點(diǎn)，則路徑不變；

3)確定修改后的路徑是否有效，如果無效，返回2)直到找到適當(dāng)?shù)淖儺慄c(diǎn)；

4)計(jì)算新變異后路徑的目標(biāo)值，將其與初始目標(biāo)值進(jìn)行比較，選擇目標(biāo)值較小的路徑，然后將其分配給種群。

3.3 元胞遺傳算法流程

Begin

初始化種群P0；

初始化種群個(gè)體在元胞空間的生死狀態(tài)S(0)；

Repeat

For 某個(gè)狀態(tài)為生的個(gè)體Ii

遺傳操作：

選擇：選擇Ii的鄰居Ni內(nèi)的最優(yōu)個(gè)體Ib；

交叉：對(duì)兩個(gè)個(gè)體中用相同點(diǎn)的位置進(jìn)行交叉操作；

變異：隨機(jī)選擇兩個(gè)不相同的中間點(diǎn)，將這條路徑一中這兩個(gè)點(diǎn)為起始點(diǎn)重新生成路徑；

計(jì)算適應(yīng)度f；

If min(f)

用子代的最優(yōu)個(gè)體替換掉Ii；

End

End

然后用規(guī)則更新元胞空間內(nèi)的生死狀態(tài)；

Until

找到最優(yōu)解或到達(dá)最大運(yùn)行代數(shù)(即滿足停止運(yùn)行條件)；

End

以上是元胞遺傳算法的算法流程，使一條長度確定的且為實(shí)數(shù)的路徑點(diǎn)即為元胞遺傳算法中的染色體，將較好的染色體逐步緩慢的擴(kuò)散到新的種群中，通過不斷進(jìn)化最終找到合適的最優(yōu)路徑。算法停止的條件，首先，得到的解是可行的或者是已經(jīng)達(dá)到最大運(yùn)行次數(shù)。第二，連續(xù)重復(fù)30次后目標(biāo)函數(shù)是恒定的則停止運(yùn)算。在前一步得到的可接受響應(yīng)中，選擇目標(biāo)函數(shù)值最小的響應(yīng)作為最優(yōu)響應(yīng)。

4 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證算法的性能，對(duì)算法的優(yōu)化路徑結(jié)果進(jìn)行仿真，在Windows7(CPU2.4 G，內(nèi)存512 M)下，運(yùn)用MTLAB建立仿真平臺(tái)，模擬實(shí)現(xiàn)路徑輸出，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

4.1 實(shí)驗(yàn)1基本遺傳算法路徑規(guī)劃和元胞遺傳算法路徑規(guī)劃的路徑

針對(duì)規(guī)劃空間為20×20，種群規(guī)模為200，基本遺傳算法和元胞遺傳算法均取交叉概率為0.8，變異概率為0.1，運(yùn)行代數(shù)為50，進(jìn)行測(cè)試。關(guān)于環(huán)境尺寸、單元數(shù)量和障礙物數(shù)量的信息見表1。

表1 環(huán)境信息表

考慮到遺傳算法產(chǎn)生隨機(jī)答案，在每次運(yùn)行時(shí)會(huì)得到不同的響應(yīng)。為了評(píng)估算法產(chǎn)生的響應(yīng)，進(jìn)行多次仿真，然后根據(jù)最佳答案或給出的答案的平均值，對(duì)結(jié)果進(jìn)行分析和評(píng)估。兩種算法路徑尋優(yōu)結(jié)果對(duì)比如圖4所示，收斂性曲線對(duì)比如圖5所示。

圖4 基本遺傳算法和元胞遺傳算法輸出結(jié)果

圖5 收斂性曲線對(duì)比圖

分析實(shí)驗(yàn)1的結(jié)果，基本遺傳算法路徑規(guī)劃距離為35.970 6，元胞遺傳算法路徑規(guī)劃距離為31.177 9，即路徑規(guī)劃距離縮短了13.32%；使用基本遺傳算法的機(jī)器人在行進(jìn)過程中進(jìn)行了16次轉(zhuǎn)向，使用元胞遺傳算法的機(jī)器人進(jìn)行了15次轉(zhuǎn)向，即轉(zhuǎn)角絕對(duì)值之和減小了6.38%。

由圖5的兩種算法的收斂曲線對(duì)比圖可以看出，元胞遺傳算法的收斂速度和最優(yōu)路徑長度均優(yōu)于基本的遺傳算法。這是因?yàn)樵z傳算法的初始種群合理的使用了Moore鄰域模型構(gòu)造，并且元胞空間中鄰居個(gè)體間進(jìn)行交叉操作，使群體間的優(yōu)勢(shì)個(gè)體迅速擴(kuò)散，一定程度上避免了基本遺傳算法的早熟現(xiàn)象，降低了陷入局部收斂的可能性。

4.2 實(shí)驗(yàn)2：平滑度因素對(duì)路徑規(guī)劃的影響

針對(duì)規(guī)劃空間為20×20，種群規(guī)模為200，交叉概率為0.8，變異概率為0.1，最大運(yùn)行迭代次數(shù)為50，對(duì)是否加入平滑度因素分別進(jìn)行收斂測(cè)試，測(cè)試結(jié)果如圖6和圖7所示。

如圖6是在僅考慮路徑長度情況，不考慮平滑度因素情況下的元胞遺傳算法路徑規(guī)劃結(jié)果(a)和進(jìn)化的迭代次數(shù)與路徑長度關(guān)系(b)；圖7是考慮路徑長度與平滑度因素共同作用下的元胞遺傳算法路徑規(guī)劃結(jié)果(a)和進(jìn)化的迭代次數(shù)與路徑長度關(guān)系(b)。

圖6 不加入平滑度因素

圖7 加入平滑度因素

分析實(shí)驗(yàn)2可知，在不考慮路徑平滑度的情況下，即路徑長度參數(shù)a=1，平滑度參數(shù)b=0時(shí)，機(jī)器人在行進(jìn)過程中經(jīng)過16次轉(zhuǎn)向，在第18次迭代時(shí)尋找到最優(yōu)路徑，路徑距離為31.177 9。在考慮路徑平滑度的情況下，即路徑長度參數(shù)a=5，平滑度參數(shù)b=3時(shí)，機(jī)器人在行進(jìn)過程中經(jīng)過15次轉(zhuǎn)向，在第20次迭代時(shí)尋找到最優(yōu)路徑，路徑距離也為31.177 9。

兩次實(shí)驗(yàn)得出的路徑距離沒有發(fā)生變化，但是加入平滑度參數(shù)的結(jié)果2中，機(jī)器人路徑的轉(zhuǎn)折次數(shù)少于不考慮平滑度參數(shù)的結(jié)果1，但是相應(yīng)的代價(jià)就是結(jié)果2的迭代次數(shù)比結(jié)果1多。得出結(jié)論：算法在考慮路徑平滑度因素情況下，可得到更加平滑的路徑，但是是以迭代時(shí)間為代價(jià)的。但就以為機(jī)器人尋找高精度、低碰撞、低損耗的路徑的目的來說，一點(diǎn)點(diǎn)時(shí)間代價(jià)在允許范圍內(nèi)，因此，加入平滑度參數(shù)的改進(jìn)是有效的。

5 結(jié)束語

對(duì)于基本遺傳算法進(jìn)行機(jī)器人路徑規(guī)劃時(shí)，路徑進(jìn)行插入修復(fù)無法保證解的可行性，且算法易陷入局部最優(yōu)的問題，結(jié)合元胞自動(dòng)機(jī)模型的空間特性，定義環(huán)境時(shí)首先排除了障礙物所在的格柵位置，增強(qiáng)了路徑規(guī)劃環(huán)境建模的通用性；接著，利用元胞遺傳算法的隱性遷移機(jī)制，并在算法適應(yīng)度函數(shù)中加入路徑平滑因素，改進(jìn)了元胞遺傳算法。仿真實(shí)驗(yàn)表明，所提的元胞遺傳算法和基本遺傳算法相比，機(jī)器人行駛路徑長度減少了13.32%，轉(zhuǎn)角絕對(duì)值之和減小了6.38%，得到了距離短且平滑的路徑，提高了移動(dòng)機(jī)器人的行駛效率和平穩(wěn)性。算法在局部優(yōu)化時(shí)保持了群體的多樣性，一定程度克服了算法的早熟，有效解決了移動(dòng)機(jī)器人路徑規(guī)劃問題，對(duì)機(jī)器人尋找高精度、低碰撞、低損耗的路徑具有重要意義。