基于改進遺傳算法的移動機器人路徑規劃

摘要：標準遺傳算法在解決各類優化問題中獲得成功，但它在具體的應用中由于缺乏對特定知識的利用，其性能有待提高。將改進遺傳算法用于移動機器人的全局路徑規劃，復雜的二維編碼問題簡化為一維編碼問題，建立邊界約束，路徑點必須在障礙物之外，路徑點連線不能與障礙物相交等3個約束條件，以機器人行走路徑最短作為適應度函數進行遺傳優化。計算機仿真實驗結果證明該算法在收斂速度、最優解輸出概率方面相對于基本遺傳算法有了顯著提高。

關鍵詞：遺傳算法；路徑規劃；移動機器人

中圖分類號：TP24 文獻標識碼：A 文章編號：1009-3044(2008)31-0951-03

Enhanced Genetic Algorithm for Robotic Path Planning

GAO Yang1， WANG Yu-jiao2

(1.School of Mechatronic Engineering， Lanzhou Jiaotong University， Lanzhou 730070， China;2.College of Mathematics and Information Science， Northwest Normal University， Lanzhou 730070， China)

Abstract: Genetic algorithm has been very successful in solving optimization problems.However， due to the absence of utilizing specific knowledge of the particular context in which it is applied， its performance still requires improvements.A new approach of global path planning for mobile robot based on enhanced genetic algorithm is presented and the complex two dimension coding problem is converted into the one dimension ones. The restrictions on the boundary and the path node out of the obstacles and the restriction on the line between path nodes not crossing over the obstacles are put into .At the same time the fitness function meets the requirement of the shortest period of working length .The simulation results demonstrate that， the proposed algorithm achieved considerable improvements， with respect to the basic genetic algorithm，in convergence speed and optimal solution output rate.

Key words: genetic algorithm; path planning; mobile robot

不論是哪種類別的移動機器人，它在進行工作時，往往要求根據某準則，在工作空間中沿著一條最優的路徑行走。因此，路徑規劃是移動機器人完成任務的安全保障，同時，也是移動機器人智能化程度的重要標志。

基于不同的基本思想，有多種算法出現。包括有人工勢場法(APF)、臭蟲法(BUG)、隨機位圖法(PRM)、快速隨機樹(RRT)、神經網絡法(NN)等。這些算法都在不同的方面有著各自的優勢，然而在總體上，這些路徑規劃算法都還存在各自的不足。如計算復雜度，局部最優解，地圖適應性，動態環境下有效性，全局及多目標優化能力。

隨著遺傳算法(GA)的提出，機器人路徑規劃算法也得到相應的發展。通過GA在路徑規劃中的應用，使得機器人更加的智能，其運行路徑也更加逼近理想的優化要求。尤其是其優秀的全局優化能力和較高的搜索效率使得GA成為處理復雜環境下全局優化要求的最佳算法之一。

GA通過模擬生物進化的方式搜索解空間。問題的可能解被編碼成染色體并作為一個個體參與算法中的進化過程。最合適的解以更大的概率生存并用來產生下一代的解，從而產生連續的不斷優化的后代解。

傳統的遺傳算法采用隨機產生初始種群的方法，產生大量不可行性路徑，同時采用固定的遺傳交叉概率，大大增加了算法執行時間，降低了算法收斂速度。本文將傳統遺傳算法進行改進，在初始種群的產生時加入約束條件，使得每條路徑都是可行的，并且引入自適應機制，對交叉率和變異率進行調整。

1 機器人的路徑規劃

1.1 路徑編碼方式

在基礎坐標系XOY中，路徑點序列的坐標是二維的，進行坐標變換，新的坐標系為X'O'Y'，以Start（起始點）與Goal（目標點）的連線作為X軸，以Start為原點。將Start與Goal的連接線段n等分，等分點為xi(i=1，2，…，n-1)，過xi點作直線p與x軸正交，隨機地在直線上選擇一點yi，共產生n-1個路徑點，形成一條隨機路徑∑（如圖1所示）。其中黑色區域為障礙物。

已知X軸與X'的夾角為θ。則一點p在坐標系XOY中的坐標(x，y)與坐標系X'O'Y'中的坐標(x'，y')關系如下：

■

式中(xs，ys)為Start在坐標系XOY中的坐標。

隨機路徑∑中的各路徑點yi坐標需滿足三點：

1) 點位于規劃空間內

在xoy坐標中，邊界各個折線的方程易求。邊界的約束限制各點值yi取值范圍，yi取值范圍必須在過每一等份點的直線方程與邊界的2個交點之間。

2) 點位于固定障礙物外

用凸多邊形表示各障礙物，設凸多邊形各頂點逆時針編號，沿逆時針行進，點均在凸多邊形外時可表述成該點在凸多邊形各邊頂點所在直線的右側，即判定該點在障礙物所在直線的那一側。

3) 各路徑點的連線不能與各障礙物相交

在XOY坐標中，凸多邊形各邊所在直線的參數方程和路徑點的連線參數方程易求，若兩線段相交，交點的參數值應滿足在[0，1]之間，兩線段才真正相交，否則，交點在兩線段或其中某一線段的延長線上，認為兩線段不相交。

路徑點的優化就簡化為一維坐標編碼優化問題。編碼采用二進制形式，格式如圖2所示。

■

圖2 編碼格式

1.2 適應度函數

適應度函數是影響遺傳算法收斂和穩定性的重要因素。全局路徑規劃中各路徑點在選取時已滿足上述3個約束條件，在確定適應度函數時還需考慮機器人的路徑長度。

根據行走路線總長度最短建立目標函數：

■

設計適應度函數：

■

1.3 遺傳算子操作

1) 初始種群：為了提高初始種群的優良性能，可以在初始化時加入初選評估程序，即在產生初始種群時考察其邊界約束和避障條件，由此保證初始種群中所有個體滿足邊界約束和避障條件。這樣可以保證遺傳算法快速、穩定地找到全局最優解。

2) 選擇算子：采用與適應度成比例的概率來選擇個體。為了保證最優個體在進化過程中不被破壞，對于新的種群中適應度最小的個體用上一代種群中最大的個體代替，使得群體進化過程向著更優的方向發展。

3) 交叉算子：本文采用單點交叉策略。它是指在個體編碼串中只隨機設置一個交叉點，然后在該點相互交換兩個配對個體的部分染色體。交叉概率較大，一般在0.4～0.9之間。

4) 變異算子：變異操作相對于選擇和交叉操作而言處于相對次要的地位，其目的是在個體結構一定的前提下，加入隨機擾動，以尋找最優解。這樣就防止了丟失一些有用的遺傳因子。變異概率通常取值都很小，一般在0.001～0.100之間。

1.4 交叉率與變異率的自適應調整

交叉率與變異率的設置直接影響到遺傳算法的進化結果。設置過大，收斂慢，復雜環境下甚至無法收斂；設置過小，容易陷入局部最優值。環境復雜度不同，對交叉率和變異率的要求也不同。本文將率值的大小與可行性路徑的占有率結合，計算每代進化完成以后可行性路徑所占的比例。當可行性路徑數量減少時，相對增加率值大小；反之，減少率值大小。根據路徑的復雜程度及進化程度不同，能起到自適應調節作用。

2 改進遺傳算法的算法結構

初始迭代次數gen=0；

pops(0)=依據邊界約束和避障條件初始化種群；

計算在初始種群 pops(0)中每個個體的適應值；

設置初始pcros，pmutation；

While 終止條件 = 1 do begain

迭代次數 gen = gen + 1；

對種群pops (gen-1)應用交叉和變異操作；

重新選擇個體組成新的種群 pops(gen)；

計算種群 pops (gen) 中個體的適應值；

自適應調整pcros，pmutation；

end

End

3 仿真結果

為了驗證本文提出算法的有效性和正確性，對算法進行了仿真試驗，試驗平臺是VC6.0。

在試驗中，工作環境初始大小600×400，起始點Start(60，40)，目標點Goal(400，250)，兩個坐標系的夾角θ為30， Start與Goal的直線段距離為400，將Start-Goal進行20等分，遺傳算法初始群體大小為50，初始交叉概率0.4，初始變異概率0.1，運行結果如圖3所示。

4 結論

利用改進的遺傳算法，有效地提高了算法的收斂速度。仿真實驗表明了該算法的可行性和快速性，為移動機器人實現最優路徑提供了一種新型實用算法。

參考文獻：

[1] 王仲民，岳宏.一種移動機器人全局路徑規劃新型算法[J].機器人，2003，(2):152-156.

[2] 王強，姚進，王進戈.基于遺傳算法的移動機器人的一種路徑規劃方法[J].哈爾濱工業大學學報，2004，(7):867-870.

[3] 段俊花，李孝安.基于改進遺傳算法的機器人路徑規劃[J].微電子學與計算機，2005，(1):70-72.