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

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

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

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

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

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

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

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

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

1 元胞遺傳算法

1.1 元胞遺傳算法思想

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

1.2 元胞鄰居結構

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

圖1 元胞遺傳算法中常見的4種鄰居結構

1.3 隱性遷移機制

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

圖2 Von.Neumann鄰居結構下的隱性遷移

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

2.1 環(huán)境表示

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

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

圖3 路徑編碼方法

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

圖4 編碼格式

2.2 障礙判斷

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

3 路徑規(guī)劃

3.1 適配值函數(shù)

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

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

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

3.1.2 柵格狀態(tài)、坐標和序號的關系

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

(2)直角坐標法。以柵格左下角為坐標原點，水平向右為x軸正方向，豎直方向為y軸正方向，以每一個柵格中心點 (x，y)表示該柵格，如此柵格均可唯一標識。

(3)序號法。按照從左到右，從上到下的順序，從柵格左下角第一個柵格開始，給每一個柵格編號，記為P(從1開始計數(shù))。

結合序號法和直角坐標法，柵格內點 (x，y)與柵格序號P有如下對應關系

通過柵格坐標與柵格序號之間的一一對應關系，結合柵格狀態(tài)反求柵格序號，如此可以判斷移動機器人是否通過障礙物，也能及時避免穿越障礙。

3.2 遺傳操作

3.2.1 選擇操作

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

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

步驟2:參考Von.Neumann鄰居結構，找到中心元胞個體周圍鄰居;

步驟3:由以下公式，計算鄰居個體適應度，通過輪盤賭方式選擇出與中心元胞交叉的鄰居個體。

3.2.2 交叉操作

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

3.2.3 變異操作

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

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

步驟2:在路徑變異點處，用通過該點垂線上的自由柵格代替變異點;

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

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

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

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

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

4 仿真實驗

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

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

圖5 算法輸出結果a

圖6 a對應的進化代數(shù)與適應度值關系

圖7 算法輸出結果b

圖8 b對應的進化代數(shù)與適應度值關系

表1 仿真運行結果記錄

圖10 算法輸出結果d

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

圖9 算法輸出結果c

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

5 結論

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

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

［2］琚兆杰.移動機器人路徑規(guī)劃研究［D］.武漢:華中科技大學，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］嚴宣輝，肖國寶.基于定長實數(shù)路徑編碼機制的移動機器人路徑編碼［J］.山東大學學報:工學版，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］王強，姚進，王進戈.基于遺傳算法的移動機器人的一種路徑規(guī)劃方法［J］.哈爾濱工業(yè)大學學報，2004，36(7): 867－870.

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

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

［11］孫樹棟，曲彥冰.遺傳算法在機器人路徑規(guī)劃中的應用研究［J］.西北工業(yè)大學學報，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

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

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