基于改進遺傳算法的移動機器人路徑規(guī)劃研究
加入技術交流群
目前，移動機器人技術已在各領域中得到廣泛應用，比如送餐機器人、導購機器人、醫(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 仿真平臺上進行實驗，結果證明了所提算法是有效的。
本文引用地址：http://www.butianyuan.cn/article/202308/449752.htm1 問題描述
移動機器人在進行路徑規(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所在的柵格為機器人的目標點，在整個運行過程中將機器人看作質點。
圖1 環(huán)境模型
文中采用序號編碼和坐標編碼相結合的編碼方式，用A~K 分別表示10~20。設柵格序號用i表示，則i與其對所對應柵格坐標(xi，yi)，的關系如式（1）。
（1）
編碼后的移動機器人環(huán)境模型如圖2所示。
圖2 編碼的環(huán)境模型
2 改進遺傳算法在移動機器人路徑規(guī)劃中的應用
2.1 種群初始化算法的改進
種群初始化最常用的方法為隨機法，此方法雖然簡便，但產(chǎn)生的初始種群中不可行路徑所占比例較多，初始種群質量低。針對此問題，文中采用基于Cost-Gain算法的避障策略產(chǎn)生初始種群。
設定種群數(shù)目為M, 個體長度為len，機器人出發(fā)點為(x1，y1) ，目標點為(xn，yn) ，初始種群產(chǎn)生的具體步驟如下：
步驟1：在起點S 和目標點T 之間隨機生成n-2 個非障礙柵格，組成一條初始路徑。
步驟2：判斷路徑是否為連續(xù)路徑。當兩個相鄰路徑點的橫坐標與縱坐標之差最大為1 時，則說明路徑為連續(xù)可行路徑，否則需要采用平均值插入法填補間斷路徑，候補柵格坐標計算如式（2）。
（2）
若候補柵格
為自由柵格，則直接進行插入，否則需要根據(jù)基于Cost-Gain 算法在障礙物周圍的八個自由柵格中確定候補柵格。
Cost-Gain算法是用效用來表示收益G(x，y)與代價 C(x，y) 之間關系的一種算法 , 它們之間的關系如式(3)。
（3）
用路徑點(xi-1,yi-1) ， (xi,yi) 所組成的路徑與路徑點(xi,yi) ，
所組成的路徑間的平滑度作為收益函數(shù) G( x，y)，用路徑點 (xi,yi) 與
所組成路徑的距離作為代價函數(shù)C( x，y )，平滑度越大，路徑越短，說明效用越大，柵格
被選作候補柵格的優(yōu)先級越高。
步驟3：保存當前所生成的路徑作為初始路徑。
步驟4：檢查生成的路徑數(shù)目是否為M，若是，終止初始化，否則重復執(zhí)行以上步驟。
2.2 適應度函數(shù)
適應度值是衡量個體質量好壞的重要指標，個體的適應度值越大，個體保存下來的幾率越大。文中采用路徑總長度L 和路徑平滑度H 構造適應度函數(shù)。
路徑距離計算公式如式(4)。
（4）
式中：
di為第i 個路徑點與第i＋1個路徑點之間的距離（m）；L為路徑的總長度（m）。
路徑平滑度計算如式(5)(6)。
（5）
（6）
式中：
H為路徑平滑度；
A1為第 i 個路徑點與第 i＋1個路徑點的橫坐標之差。
B1為第 i 個路徑點與第 i＋1個路徑點的縱坐標之差。
A2為第i＋1個路徑點與第i＋2個路徑點的橫坐標之差。
B2為第i＋1個路徑點與第i＋2個路徑點的縱坐標之差。
Ci為第 i段路徑與第i＋1段路徑的夾角。
第x 條路徑的適應度函數(shù)如式(7)。
（7）
式中：
e 為路徑長度系數(shù)；
c 為路徑平滑度系數(shù)；
D 為起點與目標點之間的距離（m）。
2.3 選擇算子
本文采用輪盤賭對路徑進行選擇，具體步驟如下：
步驟1：計算每條路徑的適應度fx 。
步驟2：求出第x 條路徑的被選擇概率px ，并得出累計選擇概率PX ，在區(qū)間（0,1）生成1 個隨機數(shù)u，當?shù)谝淮纬霈F(xiàn)PX 滿足μ ≤ PX 時，則選擇第x 條路徑。
步驟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ī)劃的仿真圖和適應度變化曲線圖。
圖3 傳統(tǒng)遺傳算法路徑仿真圖
圖4 改進遺傳算法路徑仿真圖
圖5 傳統(tǒng)遺傳算法適應度曲線圖
圖6 改進遺傳算法適應度曲線圖
仿真數(shù)據(jù)對比如表1。
表1 數(shù)據(jù)對比表
由表1 可以看出，采用改進后的遺傳算法進行路徑規(guī)劃時，規(guī)劃出的路徑最優(yōu)適應度值更大，長度更短，收斂速度更快，證明了所提算法是有效的。
4 結束語
文中主要針對采用傳統(tǒng)遺傳算法進行路徑規(guī)劃時隨機產(chǎn)生初始種群中不可行路徑所占比重較大的問題提出基于Cost-Gain 算法的避障策略，從仿真結果來看，采用改進遺傳算法規(guī)劃出的路徑長度更短，收斂速度更快，充分證明了算法的有效性。
參考文獻：
[1] 楊博,劉樹東,魯維佳,潘玉恒.改進遺傳算法在機器人路徑規(guī)劃中的應用[J].現(xiàn)代制造工程,2022(6):9-16.
[2] 魏彤,龍琛.基于改進遺傳算法的移動機器人路徑規(guī)劃[J].北京航空航天大學學報,2020,46(4):703-711.
[3] 李培英.基于改進遺傳算法的移動機器人路徑規(guī)劃[J].國外電子測量技術,2022,41(6):38-44.
[4] 石志剛,梅松,邵毅帆,等.基于人工勢場法的移動機器人路徑規(guī)劃研究現(xiàn)狀與展望[J].中國農(nóng)機化學報,2021,42(12):182-188.
[5] 胡杰,張華,傅海濤,等.改進人工勢場法在移動機器人路徑規(guī)劃中的應用[J].機床與液壓,2021,49(3):6-10.
[6] 楊會敏.基于粒子群優(yōu)化算法的移動機器人路徑規(guī)劃[D].鞍山:遼寧科技大學,2022.
[7] 郭世凱,孫鑫.基于改進粒子群算法的移動機器人路徑規(guī)劃[J].電子測量技術,2019,42(3):54-58.
[8] 宋宇,王志明.基于改進遺傳算法的移動機器人路徑規(guī)劃[J].現(xiàn)代電子技術,2019,42(24):172-175.
[9] 焦合軍,周萬春,李淵博.基于混合遺傳算法的機器人路徑規(guī)劃研究[J].中州大學學報,2020,37(6):125-128.
（本文來源于《電子產(chǎn)品世界》雜志2023年8月期）
評論