吳梅花

關鍵詞：移動機器人；改進遺傳算法；Cost-Gain算法；路徑規(guī)劃；MATLAB

目前，移動機器人技術已在各領域中得到廣泛應用，比如送餐機器人、導購機器人、醫(yī)療機器人和伴護機器人等，移動機器人的出現(xiàn)不僅節(jié)省了成本，也提高了人們的生活質量。路徑規(guī)劃的方法有很多，其中應用較廣泛的有遺傳算法[1-3]、人工勢場法[4-5] 和粒子群法[6-7] 等。目前，前人已經(jīng)針對相關算法提出各種改進策略，效果比較顯著。在采用遺傳算法進行路徑規(guī)劃時，有的學者提出采用RRT 算法產(chǎn)生初始路徑，并引入一種新的插入算子[8]，通過實驗證明了所提算法是有效的。另外針對在路徑規(guī)劃過程中收斂速度慢的問題，有的學者提出首先采用A* 算法產(chǎn)生初始種群，然后結合遺傳算法進行路徑優(yōu)化[9]，也取得了較好的效果。但目前在采用遺傳算法進行路徑規(guī)劃時仍存在較多問題，本文主要針對采用隨機法產(chǎn)生初始種群時不可行路徑所占比重較大的問題，提出基于Cost-Gain 算法的避障策略，然后分別對傳統(tǒng)遺傳算法和改進遺傳算法在MATLAB 仿真平臺上進行實驗，結果證明了所提算法是有效的。

1 問題描述

移動機器人在進行路徑規(guī)劃時首先需要了解周圍的環(huán)境。文中假設機器人的工作環(huán)境為二維空間，工作空間大小為20×20。在直角坐標系中，X 軸為橫軸，Y 軸為縱軸，采用柵格法建立工作環(huán)境模型?？紤]到障礙物的不規(guī)則性和機器人的外形，為提高移動機器人工作時的安全可靠性，將環(huán)境模型中靜態(tài)障礙物的四周分別按照機器人半徑的長度進行擴展，當障礙物未占滿1 個柵格時按照1 個完整柵格進行填充。

移動機器人工作環(huán)境模型如圖1 所示，其中黑色部分表示工作環(huán)境中的靜態(tài)障礙物，空白柵格為可行區(qū)，S 所在的柵格為機器人的起點，T 所在的柵格為機器人的目標點，在整個運行過程中將機器人看作質點。

步驟3：重復步驟2，直到滿足個體數(shù)達到設定的種群數(shù)目為止。

2.4 交叉算子

為避免進化過程中局部收斂問題的產(chǎn)生，需要對個體進行交叉操作。首先在種群中隨機選擇兩個個體進行單點交叉，然后將交叉操作后的各路徑點的x 坐標和y坐標進行升序排列，重新生成一條新路徑。檢查新路徑是否為可行路徑，否則，重新對路徑進行交叉操作。

2.5 變異算子

文中選用相鄰點替代法進行變異操作。首先隨機選擇除機器人起始點和終點外的一點作為變異點，然后隨機在其相鄰的八個柵格中選擇一個柵格替代該點，將變異后各路徑點的x 坐標和y 坐標進行升序排列，重新生成一條新路徑。檢查新路徑是否為可行路徑，否則，重新對路徑進行變異操作。

2.6 終止條件

當滿足提前設定好的進化代數(shù)M時終止遺傳操作。

3 仿真實驗

為驗證文中所提算法的有效性，在MATLAB 仿真平臺上分別對傳統(tǒng)遺傳算法和改進遺傳算法進行實驗。參數(shù)設置如下：種群的個體數(shù)目M = 800，個體長度len = 10，進化代數(shù)G = 100，仿真結果分別如圖3 至圖6 所示。

圖3 和圖5 分別為采用傳統(tǒng)遺傳算法進行路徑規(guī)劃的仿真圖和適應度變化曲線圖，圖4 和圖6 分別為采用改進后遺傳算法進行路徑規(guī)劃的仿真圖和適應度變化曲線圖。

仿真數(shù)據(jù)對比如表1。

由表1 可以看出，采用改進后的遺傳算法進行路徑規(guī)劃時，規(guī)劃出的路徑最優(yōu)適應度值更大，長度更短，收斂速度更快，證明了所提算法是有效的。

4 結束語

文中主要針對采用傳統(tǒng)遺傳算法進行路徑規(guī)劃時隨機產(chǎn)生初始種群中不可行路徑所占比重較大的問題提出基于Cost-Gain 算法的避障策略，從仿真結果來看，采用改進遺傳算法規(guī)劃出的路徑長度更短，收斂速度更快，充分證明了算法的有效性。