基于混沌遺傳算法的機器人路徑規(guī)劃方法研究

任偉建，劉世聰，孫 超

(東北石油大學 電氣信息工程學院，黑龍江 大慶 163318)

路徑規(guī)劃是按照某一性能指標搜索一條從起始狀態(tài)到目標狀態(tài)的最優(yōu)或近似最優(yōu)的無碰路徑，機器人的路徑規(guī)劃是一個非線性問題，遺傳算法GA(Genetic Algorithm)可以求解此類問題。但對于復雜的大型系統(tǒng)，GA仍然有一些缺陷[1-3]。為了避免這些問題，不少人對遺傳算法的編碼方式和算法結構等進行了改進[4]。Hussein A.Abdullah等[5]采用直角坐標法編碼，將浮點數(shù)表示的坐標點鏈接成染色體，染色體為不定長，這種方法具有良好的全局搜索性能，但路徑個體中途點坐標的可取值范圍過大，路徑拐點多；周明等[6]提出一種連續(xù)空間下基于遺傳算法的機器人路徑規(guī)劃方法，該方法先建立連通圖，然后再使用遺傳算法逐步得到較優(yōu)的路線，但對于復雜環(huán)境、障礙物數(shù)目較多的情況，建立連通圖會有一定的困難；羅熊[7]等設計了一種基于隨機指導式搜索策略的初始種群的快速有效生成方法，用于具有大量不規(guī)則障礙物的環(huán)境下的機器人路徑規(guī)劃，取得很好的仿真效果；馮琦[8]等提出了一種在極坐標環(huán)境下應用遺傳算法求解機器人路徑規(guī)劃問題的方法，該方法采用簡捷有效的路徑染色體編碼方法和快速的個體適應度計算方法，并對生成的初始路徑點集進行提煉處理，以剔除其中含有的不必要拐點。

本文結合混沌優(yōu)化方法，在基本遺傳算法的搜索機制上，利用混沌優(yōu)化的遍歷性和遺傳算法優(yōu)化的反演性，提出了一種混沌遺傳算法CGA(Chaos Genetic Algorithm)。本算法通過設計編碼方式、選擇概率以及加入操作算子來改進基本遺傳算法，并在遺傳算法中引入混沌操作，將本算法運用于機器人路徑規(guī)劃中，經(jīng)MATLAB仿真實驗，證明此算法能夠有效的進行機器人路徑規(guī)劃。

1混沌遺傳算法

CGA的基本思想是利用混沌優(yōu)化策略的遍歷性生成較優(yōu)良的初始種群，根據(jù)適者生存的原則，對其進行選擇、雜交、變異遺傳操作，同時加入刪除和插入操作加快遺傳算法收斂速度，然后利用混沌的隨機性在種群中加入擾動，避免遺傳算法的早熟收斂現(xiàn)象，增強算法的魯棒性，通過不斷繁衍進化，最后得到適合環(huán)境的較優(yōu)個體。算法流程圖如圖1所示。

圖1 混沌遺傳算法流程圖

2路徑規(guī)劃方法

2.1基于地理信息的編碼

如何將問題的解轉(zhuǎn)換為編碼表達的染色體，在xoy坐標系中表示障礙物信息，并利于后續(xù)約束條件下的優(yōu)化操作是遺傳算法的關鍵問題。在遺傳算法中，對于固定的適應度函數(shù)，編碼的長度和搜索空間的大小直接決定了在線的計算時間。因此必須設計一種簡捷實用的編碼技術，才能縮短規(guī)劃時間，實現(xiàn)實時控制。在實際運動中，路徑點是二維的，如果能對路徑坐標點進行降維處理，必將大大提高計算速度。因此本文采用了簡化編碼長度的技術，即把路徑的二維編碼簡化為一維編碼。編碼形式如圖2所示。

圖2 路徑編碼形式

在xoy坐標系中，機器人運動的起始點是(X1，Y1)，目標點是(Xn，Yn)，把起始點和目標點按 x坐標等分成 n段，則每個點的坐標可表示為(Xi，Yi)(i=1，2，…，n)。 在初始化種群時，由于x坐標被等分，所以每個個體表示的路徑的區(qū)別僅僅是路徑的縱坐標不同，縱坐標y的改變可以使機器人避開障礙物并按照不同的路徑運動到目標點。

2.2機器人控制參數(shù)簡化

圖3 機器人運動學模型

2.3基于約束條件的適應度函數(shù)

根據(jù)以上分析，在機器人路徑規(guī)劃中適應度函數(shù)需要滿足兩個條件：避障和路徑最短。假設障礙物的位置信息可由機器人的超聲波傳感器檢測到，由此信息計算出機器人與障礙物的距離和夾角，然后進行編碼，以直角坐標的形式表示在以機器人位置為原點的直角坐標系中，若種群中個體包含障礙物坐標越多則適應度越小，反之就比較大，適應度函數(shù)為f1。評價路徑最短的適應度函數(shù)為個體的前后基因的距離和，距離越大則適應度越小，反之就比較大，適應度函數(shù)為f2。遺傳算法的適應度函數(shù)可用如下關系表示：

其 中(Xi，Yi)為 個 體 基 因 ，n 為 基 因 個 數(shù) ，(xj，yj)為 障 礙物坐標，m為障礙物個數(shù)。F是把2個約束條件有機結合起來的綜合適應度函數(shù)，a和b為加權系數(shù)。

2.4路徑規(guī)劃方法步驟

(1)初始化參數(shù)。設定種群大小為 npop，交叉概率為pc，變異概率為 pm，最大迭代次數(shù)為 counter。

(2)環(huán)境建模。此地圖信息建立在xoy坐標下的柵格，將機器人傳感器獲得外界地理信息轉(zhuǎn)化為柵格坐標，包括障礙物的坐標點和非障礙物的坐標點。柵格大小以機器人自由轉(zhuǎn)身來確定，若障礙物大小不滿一個柵格也占據(jù)一個柵格的坐標。

(3)種群初始化。首先隨機生成一維編碼的種群，然后把此種群每個個體分別進行Logistic混沌映射，產(chǎn)生的新個體的適應值若大于原個體，則新個體替換原個體，否則保留原個體，經(jīng)混沌優(yōu)化后得到初始種群Gi(i=1，2，…，npop)。

(4)進入循環(huán)。判斷循環(huán)次數(shù)是否滿足終止條件，若滿足，則跳轉(zhuǎn)到步驟9，否則執(zhí)行下一步。

(5)將種群進行混沌擾動。

①初始化：用隨機方法產(chǎn)生新的種群 Ci(i=1，2，…，cpop)，種群數(shù)量為 cpop=pch×npop，其中 pch為混沌擾動概率。

②將生成的混沌序列Ci映射到區(qū)間[0，1]內(nèi)，設 mx為種群中最大基因值，mi為種群中最小基因值，則01映射公式為CHi(Ci-mi)/(mx-mi)。

③以CHi為初始值，用Logistic映射得到序列 CSi，Logistic 映射公式為 CSi=μ×CHi×(1-CHi)，μ 為混沌算子中的吸引算子。

④根據(jù)01映射公式作逆映射得到基因序列，將此基因序列替換掉Gi種群中適應度較高的個體，形成新的 Gi種群。

(6)以混沌擾動后的個體為基準進行遺傳操作。

①輪盤賭法選擇操作。選擇操作采用自適應調(diào)整的選擇概率ps進行操作，根據(jù)適應度函數(shù)計算種群適應度的平均值fmean和最優(yōu)個體的適應值ftop。ftop-fmean越大則表明個體適應值差別較大，ftop-fmean越小則表明個體之間的適應值差別較小，說明此種群容易達到局部最優(yōu)，過早收斂的可能性越大。因此可以近似地用最優(yōu)個體的適應值和平均適應值之差來反映種群的收斂程度。這樣選擇概率ps的自適應計算公式表示為 ps=c(ftop-fmean)/k，其中k為算法迭代次數(shù)，c為比例系數(shù)。

②交叉操作。以設定好的交叉概率pc進行個體的交叉操作，適應度高的個體和適應度低的個體進行交叉。首先找到兩個交叉?zhèn)€體的交叉點，即相同的基因值，然后從此基因開始交換兩個個體后面的基因。

③變異操作。變異操作目的是在個體結構一定的前提下，加入隨機擾動，以尋找最優(yōu)解，以此來避免丟失一些有用的遺傳因子。具體操作是隨機產(chǎn)生一個[0，1]空間的數(shù)值與Pm進行比較，若小于Pm，則進行變異操作，將變異后的個體替代原個體；若隨機產(chǎn)生的隨機數(shù)大于Pm，則不做變換。

(7)對種群進行刪除和插入操作。刪除操作通過刪除個體中包含的障礙物基因，可以使不可行路徑變?yōu)橐粭l可行的路徑。插入操作即在不連續(xù)的路徑處插入基因使路徑成為一條連續(xù)可行的路徑。

(8)計算終止條件。終止條件包括迭代次數(shù)和適應值，其中迭代次數(shù)加一，并計算當前種群的適應度函數(shù)值，然后跳轉(zhuǎn)到步驟(4)。

(9)進行輸出，終止此次機器人行走的路徑規(guī)劃。

3仿真結果

為了驗證本文提出的基于混沌遺傳算法的路徑規(guī)劃方法的有效性和正確性，在MATLAB7.0中對算法進行了仿真試驗，仿真試驗的主要參數(shù)設置為：9×9矩形場地，種群規(guī)模為50，交叉概率為0.8，變異概率為0.1，最大迭代次數(shù)為100，混沌吸引算子為4。

設定移動機器人運動的起始點為左下角柵格，目標點為右上角柵格，這里用圓圈表示移動機器人走過的柵格，用矩形表示障礙物，SGA仿真實驗分別對基本遺傳算法(Simple Genetic Algorithm)和本文所設計的CGA進行仿真實驗，圖4給出其中一次應用CGA的仿真結果。

圖4 CGA仿真結果

基于混沌遺傳算法的移動機器人路徑規(guī)劃方法，把遺傳算法和混沌優(yōu)化方法各自優(yōu)點結合起來，可以克服遺傳算法在求解可行解空間巨大的大范圍優(yōu)化問題時容易陷入局部最優(yōu)值的局限，對提高路徑規(guī)劃的質(zhì)量和效率有較好的效果。仿真結果說明混沌遺傳算法在移動機器人路徑規(guī)劃中的可行性和有效性。但在移動機器人運動過程中，運動精度還有待提高。

[1]ASHIRU I， CZARNECKI C， ROUTENT.Characteristics of a genetic based approach to path planning formobile robots[J].Journal of Network and Computer Applications，1996，19： 149-159.

[2]孫樹棟，曲彥賓．遺傳算法在機器人路徑規(guī)劃中的應用研究[J]．西北工業(yè)大學學報，1998，16(1)：79-83．

[3]陳剛，沈林成．復雜環(huán)境下路徑規(guī)劃問題的遺傳路徑規(guī)劃方法[J]．機器人，2001，23(1)：40-44．

[4]章敬東，劉小輝，鄧飛其，等．混沌優(yōu)化與遺傳算法的智能集成[J]．計算機工程與應用，2003(17)：17-20．

[5]ABDULLAH H A，AREIBI S.Mobile robots path planning optimization in static and dynamic environments[J].Ahmed ELSHAMLI， 2004， 12-15.

[6]周明，孫樹棟，彭炎午．使用遺傳算法規(guī)劃移動機器人路徑[J]．西北工業(yè)大學學報，1998，16(4)：581-583．

[7]羅熊，樊曉平，易最，等．具有大量不規(guī)則障礙物的環(huán)境下機器人路徑規(guī)劃的一種新型遺傳算法 [J]．機器人，2004，26：23-24．

[8]馮琦，周德云．極坐標系下基于遺傳算法的路徑規(guī)劃方法[J]．機械科學與技術，2004，23(5)：45-48．