基于改進(jìn)遺傳算法的移動(dòng)機器人路徑規劃研究

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

1 問(wèn)題描述

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

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

圖1 環(huán)境模型

文中采用序號編碼和坐標編碼相結合的編碼方式，用A~K 分別表示10~20。設柵格序號用i表示，則i與其對所對應柵格坐標(x_i，y_i)，的關(guān)系如式（1）。

   （1）

編碼后的移動(dòng)機器人環(huán)境模型如圖2所示。

圖2 編碼的環(huán)境模型

2 改進(jìn)遺傳算法在移動(dòng)機器人路徑規劃中的應用

2.1 種群初始化算法的改進(jìn)

種群初始化最常用的方法為隨機法，此方法雖然簡(jiǎn)便，但產(chǎn)生的初始種群中不可行路徑所占比例較多，初始種群質(zhì)量低。針對此問(wèn)題，文中采用基于Cost-Gain算法的避障策略產(chǎn)生初始種群。

設定種群數目為M, 個(gè)體長(cháng)度為len，機器人出發(fā)點(diǎn)為(x₁，y₁) ，目標點(diǎn)為(x_n，y_n) ，初始種群產(chǎn)生的具體步驟如下：

步驟1：在起點(diǎn)S 和目標點(diǎn)T 之間隨機生成n-2 個(gè)非障礙柵格，組成一條初始路徑。

步驟2：判斷路徑是否為連續路徑。當兩個(gè)相鄰路徑點(diǎn)的橫坐標與縱坐標之差最大為1 時(shí)，則說(shuō)明路徑為連續可行路徑，否則需要采用平均值插入法填補間斷路徑，候補柵格坐標計算如式（2）。

   （2）

若候補柵格為自由柵格，則直接進(jìn)行插入，否則需要根據基于Cost-Gain 算法在障礙物周?chē)陌藗€(gè)自由柵格中確定候補柵格。

Cost-Gain算法是用效用來(lái)表示收益G(x，y)與代價(jià) C(x，y) 之間關(guān)系的一種算法 , 它們之間的關(guān)系如式(3)。

（3）

用路徑點(diǎn)(x_i-1,y_i-1) ， (x_i,y_i) 所組成的路徑與路徑點(diǎn)(x_i,y_i) ，所組成的路徑間的平滑度作為收益函數 G( x，y)，用路徑點(diǎn) (x_i,y_i) 與所組成路徑的距離作為代價(jià)函數C( x，y )，平滑度越大，路徑越短，說(shuō)明效用越大，柵格被選作候補柵格的優(yōu)先級越高。

步驟3：保存當前所生成的路徑作為初始路徑。

步驟4：檢查生成的路徑數目是否為M，若是，終止初始化，否則重復執行以上步驟。

2.2 適應度函數

適應度值是衡量個(gè)體質(zhì)量好壞的重要指標，個(gè)體的適應度值越大，個(gè)體保存下來(lái)的幾率越大。文中采用路徑總長(cháng)度L 和路徑平滑度H 構造適應度函數。

路徑距離計算公式如式(4)。

   （4）

式中：

d_i為第i 個(gè)路徑點(diǎn)與第i＋1個(gè)路徑點(diǎn)之間的距離（m）；L為路徑的總長(cháng)度（m）。

路徑平滑度計算如式(5)(6)。

   （5）

   （6）

式中：

H為路徑平滑度；

A₁為第 i 個(gè)路徑點(diǎn)與第 i＋1個(gè)路徑點(diǎn)的橫坐標之差。

B₁為第 i 個(gè)路徑點(diǎn)與第 i＋1個(gè)路徑點(diǎn)的縱坐標之差。

A₂為第i＋1個(gè)路徑點(diǎn)與第i＋2個(gè)路徑點(diǎn)的橫坐標之差。

B₂為第i＋1個(gè)路徑點(diǎn)與第i＋2個(gè)路徑點(diǎn)的縱坐標之差。

C_i為第 i段路徑與第i＋1段路徑的夾角。

第x 條路徑的適應度函數如式(7)。

   （7）

式中：

e 為路徑長(cháng)度系數；

c 為路徑平滑度系數；

D 為起點(diǎn)與目標點(diǎn)之間的距離（m）。

2.3 選擇算子

本文采用輪盤(pán)賭對路徑進(jìn)行選擇，具體步驟如下：

步驟1：計算每條路徑的適應度f(wàn)_x 。

步驟2：求出第x 條路徑的被選擇概率p_x ，并得出累計選擇概率P_X ，在區間（0,1）生成1 個(gè)隨機數u，當第一次出現P_X 滿(mǎn)足μ ≤ P_X 時(shí)，則選擇第x 條路徑。

步驟3：重復步驟2，直到滿(mǎn)足個(gè)體數達到設定的種群數目為止。

2.4 交叉算子

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

2.5 變異算子

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

2.6 終止條件

當滿(mǎn)足提前設定好的進(jìn)化代數M時(shí)終止遺傳操作。

3 仿真實(shí)驗

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

圖3和圖5分別為采用傳統遺傳算法進(jìn)行路徑規劃的仿真圖和適應度變化曲線(xiàn)圖，圖4和圖6分別為采用改進(jìn)后遺傳算法進(jìn)行路徑規劃的仿真圖和適應度變化曲線(xiàn)圖。

圖3 傳統遺傳算法路徑仿真圖

圖4 改進(jìn)遺傳算法路徑仿真圖

圖5 傳統遺傳算法適應度曲線(xiàn)圖

圖6 改進(jìn)遺傳算法適應度曲線(xiàn)圖

仿真數據對比如表1。

表1 數據對比表

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

4 結束語(yǔ)

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

參考文獻：

[1] 楊博,劉樹(shù)東,魯維佳,潘玉恒.改進(jìn)遺傳算法在機器人路徑規劃中的應用[J].現代制造工程,2022(6):9-16.

[2] 魏彤,龍琛.基于改進(jìn)遺傳算法的移動(dòng)機器人路徑規劃[J].北京航空航天大學(xué)學(xué)報,2020,46(4):703-711.

[3] 李培英.基于改進(jìn)遺傳算法的移動(dòng)機器人路徑規劃[J].國外電子測量技術(shù),2022,41(6):38-44.

[4] 石志剛,梅松,邵毅帆,等.基于人工勢場(chǎng)法的移動(dòng)機器人路徑規劃研究現狀與展望[J].中國農機化學(xué)報,2021,42(12):182-188.

[5] 胡杰,張華,傅海濤,等.改進(jìn)人工勢場(chǎng)法在移動(dòng)機器人路徑規劃中的應用[J].機床與液壓,2021,49(3):6-10.

[6] 楊會(huì )敏.基于粒子群優(yōu)化算法的移動(dòng)機器人路徑規劃[D].鞍山:遼寧科技大學(xué),2022.

[7] 郭世凱,孫鑫.基于改進(jìn)粒子群算法的移動(dòng)機器人路徑規劃[J].電子測量技術(shù),2019,42(3):54-58.

[8] 宋宇,王志明.基于改進(jìn)遺傳算法的移動(dòng)機器人路徑規劃[J].現代電子技術(shù),2019,42(24):172-175.

[9] 焦合軍,周萬(wàn)春,李淵博.基于混合遺傳算法的機器人路徑規劃研究[J].中州大學(xué)學(xué)報,2020,37(6):125-128.

（本文來(lái)源于《電子產(chǎn)品世界》雜志2023年8月期）