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

宋宇 王志明

摘要：將遺傳算法用于路徑規劃時，傳統算法雖然簡單，但不適用轉彎情況較多的復雜地圖。針對這一問題，首先將RRT算法用于柵格環境下產生初始路徑，其次提出一種新的插入算子，最后進行路徑優化。根據不同地圖與其他文獻中的改進遺傳算法，進行對比研究與分析，制定路徑長度與算法用時2個指標來評判算法的優劣。仿真結果表明，改進算法得到的路徑長度縮短了70%，路徑長度達到最優的用時減少了8%。

關鍵詞：移動機器人;遺傳算法;路徑規劃;算法評判;插入算子;路徑優化

中圖分類號：TN820.4-34;TP301.6

文獻標識碼：A

文章編號：1004-373X（2019）24-0172-04

遺傳算法是一種模擬自然界選擇進化的全局優化算法，利用遺傳算法求解最優問題是通過選擇交叉變異算子不斷迭代來實現的。采用遺傳算法路徑規劃的文獻并不少見[1-5]。文獻[1]提出了人工勢場法與遺傳算法相結合的方法，使得算法得到的路徑平滑度較高;文獻[2]采用了Dijstar算法初始化種群，用遺傳算法得到了安全度較高的路徑;文獻[5]提出了根據種群的適應度方差自適應選擇的選擇策略;文獻[6]在遺傳算法得到的路徑上重新排列基因優化了路徑長度與路徑平滑度;文獻[7]采用了在當前點附近產生個體的方法，以距離為適應度函數，用遺傳算法進行了路徑規劃。

1 基于改進遺傳算法的路徑規劃

在傳統遺傳算法柵格路徑規劃的基礎上提出了新的初始化方式、變異方式以及插入方式，改善了全局尋優效果。

1.1 柵格模型

首先將給定地圖柵格化，將障礙物所占的柵格用黑色柵格表示，自由空間用白色柵格表示，圖1中黑色曲線表示一條典型的柵格環境路徑，該路徑是由從起點到終點的一系列路徑點組成的路徑規劃算法的任務，即尋找從起點到終點的一系列連續路徑點，使得連接路徑點的路徑長度或安全度最優。路徑點的位置可以用直角坐標或柵格序號表示，給定柵格中心點的柵格序號P（i，j）與直角坐標[X（i，j ），Y（i，j）]的轉換關系如下：

X（i，j）= mod （P（i，j），10）- 0.5

Y（i，j）= floor （P（i，J），10）+ 0.5

（1）

P（i，j）=X（i，j）+0.5+10（1，（i，j）一0.5）

圖1中的路徑點組成的路徑點集合為{1，12，23，24，25，26，36，46，56，67，68，69，80，90，1001，移動機器人的起點序號為1，終點序號為100。遺傳算法中的個體用路徑序號組成的向量表示，1個個體代表一條無碰撞路徑。

1.2 遺傳算法初始化

傳統遺傳算法用于柵格路徑規劃時，在初始化中采用較多的是中點插值法，即隨機產生一定數量的路徑點，在每兩個路徑點之間采用中點插值的方式進行路徑插補。文中將RRT算法用于遺傳算法種群的初始化，給定起點與終點，從起點開始產生隨機樹并不斷生長，直到此隨機樹到達終點。

文中算法產生一條路徑的具體步驟如下：

1）將起點坐標（如圖1中的[1，1]）加入隨機樹中;

2）在地圖范圍內以50%的概率產生1個隨機點作為目標點，其余50%的概率以終點為目標點，計算得到距離此目標點最近的樹節點P（x，y）;

3）在P（x，y）所在柵格的鄰居柵格中選出所有非障礙物柵格，若P（x，y）的所有鄰居柵格都在障礙物中，則跳到步驟2）;

4）在步驟3）產生的滿足條件的鄰居柵格中，選擇距離步驟2）產生的隨機點最近的柵格中心點，若此點已經在樹中，跳到步驟2），若此點不在樹中，將此點作為樹節點，即將此距離最近的點加入樹中。

5）檢查步驟4）新加入樹中的點的所有鄰居柵格，若終點在這些鄰居柵格內，算法結束。若終點不在柵格內，跳到步驟2）。

按照上述算法產生種群數量的路徑，初始化結束。

1.3 適應度函數

文中適應度函數選擇為路徑長度。

1.4 選擇算子

文中采用文獻[5]提出的自適應選擇算法，個體被選擇的概率為：

P=α （1- a）i-l（2）式中：i為按個體距離長度排序后的個體序號值;α為：

產生個體概率后，使用隨機遍及取樣（SUS）算法選擇個體。

1.5 交叉算子

文中采用單點交叉算法，即在種群內隨機選擇2個待交叉個體，找到這兩個個體的除起點與終點外的公共點，隨機選擇公共點中的一個點，交換這兩個個體選擇到的點的后半部分路徑點產生兩個新的個體。個體交叉示意圖如圖2所示，圖中前兩個地圖中的個體在序號為56的點處交叉，產生后兩個個體。

1.6 變異算子

文中提出的變異算子步驟如下：

1）在種群中隨機選擇一個個體，在此個體中隨機選擇除起點與終點外的一個路徑點[X，Y]，此路徑點將個體分為前半段路徑與后半段路徑;

2）以50%的概率選擇坐標X進行變異，其余50%的概率選擇坐標Y進行變異，即在點[x，y]的同行或同列中選擇一個非障礙物柵格作為變異后的點;

3）在前半段路徑中隨機選擇一個路徑點[X1，Y1]，在后半段路徑中隨機選擇一個路徑點[X2，Y2]，使用插入算子連接[X1，Y1]與[X，Y]，[X，Y]與[X2，Y2】，若兩段路徑都連接成功，將原個體中的起點到點[X1，Y1]的路徑與[X1，Y1]與[x，y]的路徑和[X，Y]與[X2，Y2]與原個體中的點[X2，Y2]到終點的路徑拼接產生變異后的新個體，若兩段路徑有1段連接失敗，則令新個體與原個體相同。

1.7 插入算予

對于給定的兩個點，稱為start點與goal點，令start點為當前點，創建一個鄰居列表（此時為空數組），創建一個與地圖同型的考察標志矩陣（此時只有start點處的值為1，其余為0），創建一個路徑點列表（此時為空）。

1）檢查當前點的8個鄰居柵格，將不在障礙物中且未考察過的點加入鄰居列表，同時令這些點的考察標志為1。

2）如果鄰居列表為空，則插入失敗，算法結束，否則繼續執行步驟3）。

3）如果goal點在鄰居列表中，插入成功，算法結束;如果goal點不在鄰居列表中，從鄰居列表中選擇距離goal點最近的點P，將點P從鄰居列表刪除。

4）若點P與當前點是相鄰柵格，則令點P為當前點，同時將點P加入路徑點列表，跳到步驟1）;若點P與當前點不是相鄰柵格，連接失敗，算法結束。

1.8 刪除算子

刪除算子是將個體中相同路徑點之間的路徑點與這兩個相同路徑點中的一個刪除，去除了冗余路徑點。

1.9 優化算子

優化算子是檢查個體中連接第i個路徑點（path（i））的前一個路徑點（path（i-l））與后一個路徑點（path（i+l））的直線是否經過障礙物柵格，若不經過，則將此指定點從個體中刪除。優化算子的偽代碼如下：

flag=1;

while flag==l

for i=2： size（ path， 2）-1

if deletable（i，path）

delete path（i）from path

flag=1;

break

end

flag=0;

end

end

其中deletable（i，path）指的是判斷第i個路徑點是否可刪除。

1.10 改進遺傳算法柵格法路徑規劃流程

1）路徑初始化，產生給定數量的個體;

2）使用選擇算子產生下一代個體;

3）從種群中隨機選擇2個個體，使用交叉算子進行交叉;

4）從種群中隨機選擇一個個體，使用變異算子進行變異;

5）對種群中所有個體分別調用刪除算子，優化算子，若未達到指定迭代次數，跳到步驟2），否則，算法結束。

2 仿真

在Matlab 2014a，13 -4000M的CPU環境下進行仿真。仿真部分比較了文中算法與文獻[3]算法在3個地圖環境下得到的路徑長度與路徑達到最優所用時間（算法效率），如圖3、表1所示。

起點為左下角柵格，終點為右上角柵格，種群大小為5，迭代次數500。在地圖3中，由于文獻[3]算法初始化方法只選擇固定幾個方向進行移動，故對轉彎過多的環境不適用，從地圖3可以看出文中算法在復雜環境下的可行性。

3 結語

根據本文提出的初始化方式，變異及插入與優化算子，在Matlab中與文獻[3]中的改進遺傳算法對比，仿真結果表明本文提出的算法在不同環境下得到的路徑可行、有效。

注：本文通訊作者為王志明。

參考文獻

[1]喬莎莎，吳勇，張建東，等，基于遺傳算法和人T勢場法的路徑規劃[J]現代電子技術，2012，35（12）：75-78.

QIAO Shasha. WU Yong， ZHANG Jiandong， et aI.Path plan-ning based on genetic algorithm and artificial potential fieldmethod[J]. Modern electronics technique， 2012， 35（ 12）： 75-78.

[2]盧月品，趙陽，孟躍強，等.基于改進遺傳算法的狹窄空間路徑規劃[J]計算機應用研究，2015，32（2）：413-418.

LU Yuepin. ZHAO Yang， MENG Yueqiang， et al.Path plan-ning in narrow space by improved genetic algorithm [J]. Appli-cation research of computers， 2015， 32（2）：413-418.

[3]田欣，劉廣瑞，周文博，等.基于改進白適應遺傳算法的機器人路徑規劃研究[J]機床與液壓，2016，44（ 17）：24-28.

TIAN Xin. LIU Guangrui， ZHOU Wenbo. et al.Research ofrobot path planning based on improved adaptive genetic algo-rithm [J]. Machine tool and hydraulics， 2016. 44（17） ： 24-28.

[4]楊獻峰，付俊輝 .移動機器人路徑規劃的仿真研究[J]. 計算機仿真， 2012.29（ 7） ：223-226.

YANG Xianfeng， FU Junhui. Mobile robot path planning basedon grid algorithm and CGA [J]. Computer simulation. 2012， 29（7） ： 223-226.

[5] KARAMI A H. HASANZADEH M. An adaptive genetic algo-rithm for robot motion planning in 2D complex environments[J]. Computers & electrical engineering， 2015. 43 ： 317-329.

[6] 11 M F， WANG C J， CHEN Z Q， et al. Pathplanning of mo-hile rohot based on genetic algorithm and gene rearrangement[C]// Chinese Automation Congress. Jinan： IEEE， 2017： 6999- 7004.

[7] ARORA T， GIGRAS Y， ARORA V. Robotic path planning us-ing genetic algorithm in dynamic environment [J]. Internationaljournal of computer applications ， 2014. 89（ 11 ） ： 8-12.

[8] FU B. CHEN L， ZHOU Y T， et al. An improved A' algorithmfor the industrial robot path planning with high success rateand shortlength [J]. Robotics & autonomous systems. 2018，106： 26-37.

[9] PATLE B K. PARHI D R K. JAGADEESH A. et al. Matrix-Binary codes based Genetic Algorithm for path planning of mo-bile robot [J]. Computers & electrical engineering， 2017. 45 ： 1-

[10] ISLAM F， NASIR J. MALIK U. et al. RRT#-Smart： Rapidconvergence implementation of RRT* towards optimal solution[C]// International Conference on Mechatronics and Automa-tion. Chengdu ： IEEE . 2012 ： 1651-1656.

作者簡介：宋宇（1969-），男，黑龍江呼蘭人，教授，主要研究領域為嵌入式系統設計與研究。

王志明（1991-），男，山西神池人，碩士研究生，主要研究領域為路徑規劃。