張屹，劉錚，胡方軍，詹騰，丁昌鵬

(三峽大學(xué)機(jī)械與材料學(xué)院，湖北宜昌 443002)

基于元胞遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃

張屹，劉錚，胡方軍，詹騰，丁昌鵬

(三峽大學(xué)機(jī)械與材料學(xué)院，湖北宜昌 443002)

在移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題中，環(huán)境建模約束定義難，遺傳算法求解易陷入局部收斂，針對(duì)上述問(wèn)題通過(guò)建立柵格坐標(biāo)、柵格序號(hào)和柵格狀態(tài)三者之間的關(guān)系，簡(jiǎn)化了障礙物約束和有效路徑判斷，同時(shí)引入多樣性保持較好的元胞遺傳算法，使用定長(zhǎng)實(shí)數(shù)編碼對(duì)生成的路徑進(jìn)行優(yōu)化。仿真實(shí)驗(yàn)表明，由于算法具備較好的隱性遷移機(jī)制，保持了解的多樣性，提高了算法收斂效率，使移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題得到了有效解決。

元胞鄰居;遺傳算法;移動(dòng)機(jī)器人;環(huán)境建模;路徑規(guī)劃

移動(dòng)機(jī)器人路徑規(guī)劃要求在具有障礙物的環(huán)境內(nèi)按照一定的評(píng)價(jià)標(biāo)準(zhǔn)，尋找一條從起始點(diǎn)到終點(diǎn)的無(wú)碰撞路徑［1］。目前，移動(dòng)機(jī)器人路徑規(guī)劃環(huán)境建模中，主要難點(diǎn)是定義障礙物和判斷有效路徑［1－2］，采用柵格法建模有利于解決上述問(wèn)題。但與此同時(shí)，隨著柵格密度的增加，障礙物表示精度提高，也使得算法的搜索范圍呈指數(shù)式增加，所以需要多樣性和收斂性較好的智能算法對(duì)其進(jìn)行求解。

智能算法中，尤以遺傳算法應(yīng)用較為廣泛，遺傳算法編碼效率高，不產(chǎn)生無(wú)效路徑，但本身運(yùn)算效率低，求解移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題時(shí)容易陷入局部收斂［1－2］。由于元胞遺傳算法既繼承了遺傳算法的優(yōu)良品質(zhì)，又擁有元胞自動(dòng)機(jī)的部分特性，它通過(guò)內(nèi)部隱性遷移機(jī)制作用，使得中心個(gè)體在其周圍鄰居間進(jìn)行遺傳操作，保留了種群的多樣性，也降低了算法陷入局部收斂的可能性［3－4］。本文作者通過(guò)建立柵格坐標(biāo)、序號(hào)和狀態(tài)的關(guān)系，對(duì)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題進(jìn)行環(huán)境建模，引入元胞遺傳算法，采用定長(zhǎng)實(shí)數(shù)編碼方式［5］對(duì)路徑進(jìn)行優(yōu)化。最后，通過(guò)多次對(duì)各種大小不同的柵格情況進(jìn)行仿真，以解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題。

1 元胞遺傳算法

1.1 元胞遺傳算法思想

元胞遺傳算法繼承遺傳算法的基本思想，同時(shí)結(jié)合元胞自動(dòng)機(jī)理論，以元胞個(gè)體為出發(fā)點(diǎn)模擬自然界進(jìn)化過(guò)程［4］。通常情況下，其初始種群個(gè)體依次分布于環(huán)形連通的網(wǎng)狀空間拓?fù)浣Y(jié)構(gòu)中［6］，所有個(gè)體只與相鄰個(gè)體進(jìn)行相互作用，遺傳操作被限制在鄰域范圍內(nèi)進(jìn)行，其解在種群內(nèi)平緩的擴(kuò)散，不同范圍內(nèi)的個(gè)體收斂到搜索空間的不同區(qū)域，形成一個(gè)個(gè)的小生境保持種群多樣性，從而增強(qiáng)算法的探索能力，使得元胞遺傳算法表現(xiàn)出基本遺傳算法所不及的性能，因此元胞遺傳算法被認(rèn)為當(dāng)前解決復(fù)雜問(wèn)題的一種有效方法［4］。

1.2 元胞鄰居結(jié)構(gòu)

通常，二維元胞自動(dòng)機(jī)中使用較多的鄰居主要有以下4種結(jié)構(gòu)類型:Von.Neumann鄰居結(jié)構(gòu)、Moore鄰居結(jié)構(gòu)、擴(kuò)展的Moore鄰居結(jié)構(gòu)和Margolus鄰居結(jié)構(gòu)［7］，算法采用不同的鄰居結(jié)構(gòu)收斂的效果也不同。

圖1 元胞遺傳算法中常見(jiàn)的4種鄰居結(jié)構(gòu)

1.3 隱性遷移機(jī)制

元胞遺傳算法中，相鄰個(gè)體的鄰居互相重疊，這種重疊為算法提供了一種隱性的遷移機(jī)制。這種機(jī)制能使求到的最優(yōu)解平緩地在整個(gè)種群中擴(kuò)散，從而使元胞遺傳算法相對(duì)于非結(jié)構(gòu)化種群的遺傳算法能更持久的保持種群多樣性。由于這種擴(kuò)散，元胞遺傳算法在對(duì)解空間進(jìn)行搜索的時(shí)候能保持全局探索和局部尋優(yōu)的良好平衡。鄰居間的重疊度隨著鄰居規(guī)模的增長(zhǎng)而增長(zhǎng)，而重疊度影響著個(gè)體的遷移，通過(guò)改變鄰居規(guī)模來(lái)調(diào)節(jié)鄰居的重疊度，從而影響全局探索和局部尋優(yōu)的平衡以及進(jìn)化過(guò)程中的種群多樣性。圖2中繪制了Von.Neumann鄰居結(jié)構(gòu)的重疊度，其中黑色區(qū)域的個(gè)體同屬于個(gè)體1和個(gè)體2的鄰居，顏色最淡的區(qū)域的個(gè)體是個(gè)體1的鄰居，另一種顏色較淡區(qū)域的個(gè)體屬于個(gè)體2的鄰居。

圖2 Von.Neumann鄰居結(jié)構(gòu)下的隱性遷移

2 環(huán)境建模［5，8－11］

2.1 環(huán)境表示

柵格法是一種較為傳統(tǒng)的環(huán)境建模方法，它將機(jī)器人工作環(huán)境離散成一系列的二值信息網(wǎng)格單元，同時(shí)對(duì)障礙物和自由空間網(wǎng)格進(jìn)行標(biāo)識(shí)，其柵格粒度的大小直接影響障礙物的表示精度，會(huì)占用計(jì)算機(jī)大量的存儲(chǔ)空間，使得算法的搜索范圍呈指數(shù)式增加。目前，柵格的標(biāo)識(shí)方法有坐標(biāo)法和序號(hào)法，序號(hào)法要求對(duì)路徑進(jìn)行不間斷編碼，增加了編碼的難度，而坐標(biāo)法能有效實(shí)現(xiàn)本文定長(zhǎng)實(shí)數(shù)編碼的需要。結(jié)合兩種標(biāo)識(shí)方法，建立兩者一一對(duì)應(yīng)的關(guān)系，為障礙物判斷奠定基礎(chǔ)。

在直角坐標(biāo)系XOY中，路徑點(diǎn)序列的坐標(biāo)是二維的，通過(guò)坐標(biāo)變化后的新坐標(biāo)系為X'OY'，X'軸為起始點(diǎn)S與目標(biāo)點(diǎn)G的連線，如圖3所示。坐標(biāo)變換方法:以機(jī)器人原始坐標(biāo)原點(diǎn)為原點(diǎn)，以起始點(diǎn)S與目標(biāo)點(diǎn)G的連線為X'軸，建立新坐標(biāo)系X'OY'。原坐標(biāo)系XOY與新坐標(biāo)系X'OY'’的變換公式如下:

圖3 路徑編碼方法

將起始點(diǎn)S和目標(biāo)點(diǎn)G連線的線段n等分，等分點(diǎn)為xi，過(guò)xi點(diǎn)作直線Li與X'軸正交，隨機(jī)地在直線Li上選擇通過(guò)柵格的點(diǎn)Pi，從而形成一條隨機(jī)的路徑。如此這樣，就將優(yōu)化的路徑點(diǎn)簡(jiǎn)化成一維的y坐標(biāo)編碼優(yōu)化問(wèn)題。編碼采用實(shí)數(shù)編碼，編碼格式如圖4所示。

圖4 編碼格式

2.2 障礙判斷

通過(guò)利用坐標(biāo)法對(duì)移動(dòng)機(jī)器人路徑進(jìn)行編碼，再求解兩相鄰點(diǎn)間線段上有限點(diǎn)的坐標(biāo)，利用序號(hào)和坐標(biāo)之間的一一對(duì)應(yīng)關(guān)系返回柵格序號(hào)，結(jié)合柵格狀態(tài)判斷線段是否穿過(guò)障礙。只要所求得的柵格不是障礙物，則該生成路徑有效，否則重新生成下一柵格，繼續(xù)判斷直至路徑有效。

3 路徑規(guī)劃

3.1 適配值函數(shù)

3.1.1 路徑最短適配值函數(shù)

如圖3，移動(dòng)機(jī)器人路徑規(guī)劃就是在起點(diǎn)與終點(diǎn)之間尋找一個(gè)點(diǎn)的集合P={S，y1，…，yi，…，yD，G}，要求兩相鄰點(diǎn)之間的線段沒(méi)有通過(guò)障礙物，所以問(wèn)題的解就是尋找最短的有效路徑，如式 (2)表示:

式中:L'是單個(gè)柵格的對(duì)角線長(zhǎng)度;m為大于1的正實(shí)數(shù)，可以保證移動(dòng)機(jī)器在不同垂線人不會(huì)經(jīng)過(guò)同一柵格;LSG為起始點(diǎn)S到目標(biāo)點(diǎn)G的距離;(Xi，Yi)是第i條垂線與SG的交點(diǎn)Pi在坐標(biāo)系X'OY'中的坐標(biāo)，對(duì)應(yīng)表示相應(yīng)的柵格，此時(shí)不表示起始點(diǎn)和目標(biāo)點(diǎn)。

3.1.2 柵格狀態(tài)、坐標(biāo)和序號(hào)的關(guān)系

(1)柵格狀態(tài)。通過(guò)定義柵格的狀態(tài)判斷障礙物位置，如果柵格狀態(tài)gridState為1，此柵格為障礙物，不允許機(jī)器人通過(guò);如果柵格狀態(tài)gridState為0，此柵格可通過(guò)。

(2)直角坐標(biāo)法。以柵格左下角為坐標(biāo)原點(diǎn)，水平向右為x軸正方向，豎直方向?yàn)閥軸正方向，以每一個(gè)柵格中心點(diǎn) (x，y)表示該柵格，如此柵格均可唯一標(biāo)識(shí)。

(3)序號(hào)法。按照從左到右，從上到下的順序，從柵格左下角第一個(gè)柵格開(kāi)始，給每一個(gè)柵格編號(hào)，記為P(從1開(kāi)始計(jì)數(shù))。

結(jié)合序號(hào)法和直角坐標(biāo)法，柵格內(nèi)點(diǎn) (x，y)與柵格序號(hào)P有如下對(duì)應(yīng)關(guān)系

通過(guò)柵格坐標(biāo)與柵格序號(hào)之間的一一對(duì)應(yīng)關(guān)系，結(jié)合柵格狀態(tài)反求柵格序號(hào)，如此可以判斷移動(dòng)機(jī)器人是否通過(guò)障礙物，也能及時(shí)避免穿越障礙。

3.2 遺傳操作

3.2.1 選擇操作

元胞遺傳算法重點(diǎn)在于選擇操作，采用異步元胞遺傳算法對(duì)生成路徑進(jìn)行優(yōu)化，父代個(gè)體被選擇的原理如下:

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

步驟2:參考Von.Neumann鄰居結(jié)構(gòu)，找到中心元胞個(gè)體周圍鄰居;

步驟3:由以下公式，計(jì)算鄰居個(gè)體適應(yīng)度，通過(guò)輪盤(pán)賭方式選擇出與中心元胞交叉的鄰居個(gè)體。

3.2.2 交叉操作

采用單點(diǎn)交叉，首先確定一個(gè)交叉概率pc，將選擇出的鄰居與中心個(gè)體一一配對(duì)，然后對(duì)每一對(duì)個(gè)體產(chǎn)生一個(gè) ［0，1］的隨機(jī)數(shù)r，如果r＜pc，則對(duì)該對(duì)個(gè)體隨機(jī)指定的基因進(jìn)行交叉操作。

3.2.3 變異操作

變異主要是為了增加種群的多樣性，為了防止生成無(wú)效路徑，修改變異算子如下:

步驟1:在交叉后的父代路徑中隨機(jī)選擇一個(gè)路徑點(diǎn)作為變異點(diǎn)，如果選到起始點(diǎn)，則路徑保持不變;

步驟2:在路徑變異點(diǎn)處，用通過(guò)該點(diǎn)垂線上的自由柵格代替變異點(diǎn);

步驟3:判斷變異后的路徑是否為有效路徑，無(wú)效則返回步驟2，直到找到合適的變異點(diǎn)。

步驟4:計(jì)算變異后新路徑的目標(biāo)值，并與初始目標(biāo)值比較，選擇出目標(biāo)值較小的路徑，賦予新的種群。

3.3 算法執(zhí)行偽代碼

算法執(zhí)行偽代碼如下:

以上是元胞遺傳算法執(zhí)行的偽代碼，染色體由一條長(zhǎng)度確定且為實(shí)數(shù)的路徑點(diǎn)組成，通過(guò)對(duì)原始種群實(shí)施一連串遺傳操作，并最終判斷染色體即移動(dòng)機(jī)器人路徑是否穿越障礙物，將較好的染色體逐步緩慢地?cái)U(kuò)散到新的種群中，通過(guò)不斷進(jìn)化最終找到合適的最優(yōu)路徑。

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

在仿真實(shí)驗(yàn)中，算法的相關(guān)參數(shù)設(shè)置如下:種群規(guī)模100，進(jìn)化代數(shù)50，交叉概率0.05，變異概率0.01，m=1.2，左下角為起點(diǎn)，右上角為終點(diǎn)。在環(huán)境不同的兩幅10×10的圖中進(jìn)行多次仿真，典型結(jié)果如圖5和圖7，其中圖6、圖8分別為圖5和圖7對(duì)應(yīng)的進(jìn)化代數(shù)與適應(yīng)度值關(guān)系。

圖5、圖7中最優(yōu)路徑真實(shí)解為13.899 5，對(duì)其做多次仿真，統(tǒng)計(jì)結(jié)果如表1。

圖5 算法輸出結(jié)果a

圖6 a對(duì)應(yīng)的進(jìn)化代數(shù)與適應(yīng)度值關(guān)系

圖7 算法輸出結(jié)果b

圖8 b對(duì)應(yīng)的進(jìn)化代數(shù)與適應(yīng)度值關(guān)系

表1 仿真運(yùn)行結(jié)果記錄

圖10 算法輸出結(jié)果d

在種群規(guī)模225，m=1.1，其它設(shè)置參數(shù)相同的條件下，對(duì)柵格15×15的情況作了仿真，典型結(jié)果如圖9，最優(yōu)值為22.142 1，平均收斂代數(shù)為40代。在種群規(guī)模400，進(jìn)化代數(shù)100，m=1.05，其他參數(shù)相同，對(duì)柵格20×20的情況作了仿真，典型結(jié)果如圖10，最優(yōu)值為30.384 8，平均收斂代數(shù)為61代。

圖9 算法輸出結(jié)果c

通過(guò)以上的仿真測(cè)試，元胞遺傳算法均能有效地解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題。分析圖6、圖8，可以看出算法求解后最優(yōu)值與平均值差距較小，說(shuō)明算法的收斂性較穩(wěn)定，能夠準(zhǔn)確找到最優(yōu)解。分析表1發(fā)現(xiàn)，算法收斂時(shí)保持了穩(wěn)定的進(jìn)化代數(shù)，有效降低了算法陷入局部收斂的可能性。分析圖5、圖7、圖9和圖10，通過(guò)不斷改變柵格規(guī)模，元胞遺傳算法均能找到最優(yōu)解，不僅說(shuō)明算法有效，也表明移動(dòng)機(jī)器人路徑規(guī)劃環(huán)境建模的通用性較好。

5 結(jié)論

針對(duì)目前移動(dòng)機(jī)器人路徑規(guī)劃環(huán)境建模中約束定義復(fù)雜，以及遺傳算法求解易陷入局部收斂的問(wèn)題，建立柵格中心坐標(biāo)與柵格序號(hào)一一對(duì)應(yīng)的關(guān)系，以柵格狀態(tài)定義障礙物約束簡(jiǎn)化障礙物模型，在元胞遺傳算法中使用定長(zhǎng)實(shí)數(shù)編碼，充分利用算法的隱性遷移機(jī)制，不僅增強(qiáng)了算法的全局尋優(yōu)能力，也增加了最優(yōu)解的多樣性。仿真實(shí)驗(yàn)表明，通過(guò)改進(jìn)障礙物約束定義和引入元胞遺傳算法，增強(qiáng)了移動(dòng)機(jī)器人路徑規(guī)劃環(huán)境建模的通用性，同時(shí)也提高了算法的求解效率。

［1］蔡曉慧.基于智能算法的移動(dòng)機(jī)器人路徑規(guī)劃研究［D］.杭州:浙江大學(xué)，2007.

［2］琚兆杰.移動(dòng)機(jī)器人路徑規(guī)劃研究［D］.武漢:華中科技大學(xué)，2007.

［3］WHITLEY D.Cellular Genetic Algorithms［C］.Proceedings of the 5th International Conference on Genetic Algorithms，1993:658.

［4］ALBA Enrique，DORRONSORO Bernabe.Cellular Genetic Algorithms［M］.Springer，2008.

［5］嚴(yán)宣輝，肖國(guó)寶.基于定長(zhǎng)實(shí)數(shù)路徑編碼機(jī)制的移動(dòng)機(jī)器人路徑編碼［J］.山東大學(xué)學(xué)報(bào):工學(xué)版，2012，42 (1):59－65.

［6］TOMASSINI M.Spatially Structured Evolutionary Algorithms:Artificial Evolution in Space and Time［M］.Heidelberg，Berlin:Springer-Verlag，2005.

［7］ALBA E，COTTA C，TROYA J M.On the Importance of the Grid Shape in 2D Spatially Structured GAs［J］.Journal of Evolutionary Optimization，2000，1(3).

［8］王強(qiáng)，姚進(jìn)，王進(jìn)戈.基于遺傳算法的移動(dòng)機(jī)器人的一種路徑規(guī)劃方法［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2004，36(7): 867－870.

［9］郝博，秦麗娟，姜明洋.基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法研究［J］.計(jì)算機(jī)工程與科學(xué)，2010，32 (7):104－106.

［10］鄧志燕，陳熾坤.基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃研究［J］.機(jī)械設(shè)計(jì)與制造，2010，7:147－149.

［11］孫樹(shù)棟，曲彥冰.遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用研究［J］.西北工業(yè)大學(xué)學(xué)報(bào)，1998，16(1):79－83.

Path Planning of a Mobile Robot Based on Cellular Genetic Algorithm

ZHANG Yi，LIU Zheng，HU Fangjun，ZHAN Teng，DING Changpeng
(College of Mechanical＆Material Engineering，China Three Gorges University，Yichang Hubei 443002，China)

When solving the problem of path planning of a mobile robot，defining constrains in environment modeling was hard，and was easily fallen into the local convergence by traditional genetic algorithm.By aimed at the problem above，and established the relationship among grid coordinates，grid number and grid state，the constrains definition of obstacles and effective path judging were simplified，at the same time，the cellular genetic algorithm with better diversity maintaining was also brought in，while optimizing the path by using fixed-length real number encoding.Finally，the simulation results show that the algorithm maintains the better diversity and improves the efficiency of the convergence because of the implicit mechanism of migration of the algorithm，which effectively solves the problem of path planning of the mobile robot.

Cellular neighbors;Genetic algorithm;Mobile robot;Environment modeling;Path planning

TP24

A

1001－3881(2014)9－017－4

10.3969/j.issn.1001－3881.2014.09.005

2013－04－16

國(guó)家自然科學(xué)基金項(xiàng)目 (51275274);三峽大學(xué)研究生科研創(chuàng)新基金項(xiàng)目 (2012CX031)

張屹 (1976—)，男，博士，副教授，研究方向?yàn)闄C(jī)電系統(tǒng)現(xiàn)代設(shè)計(jì)方法、機(jī)電傳動(dòng)與控制系統(tǒng)設(shè)計(jì)、工業(yè)自動(dòng)化與監(jiān)控系統(tǒng)設(shè)計(jì)、CAD/CAM/CAPP/CAE/CIMS等。E－mail:jxzhangyi1976@126.com。