自適應遺傳算法在移動機器人路徑規劃中的應用

2021-04-06 13:08:40桑和成宋栓軍邢旭朋孟湲易張周強唐銘偉

西安工程大學學報 2021年1期

桑和成，宋栓軍，邢旭朋，孟湲易,張周強,唐銘偉

(西安工程大學機電工程學院，陜西西安 710048)

0 引言

移動路徑規劃是機器人研究領域不可或缺的一部分，也是機器人完成指定任務的重要保障和基礎[1-3]。對保障機器人穩定工作，提高倉庫運行效率起著至關重要的作用。

在解決路徑規劃問題方面，國內外學者做了大量的研究，遺傳算法被證明是有效算法之一[4-6]。但是，基本遺傳算法由于自身的局限性，不能解決路徑規劃中的問題。近些年一些學者對遺傳算法進行了改進，取得了很好的效果。閆雪超等在種群產生時先判斷、刪除那些與障礙物相交的染色體；其次，提出新的變異算子，根據種群中適應度值大小調節變異節點。該方法使得轉彎次數減少但增加了路徑長度[7]。田欣利用先驗知識，在保證遺傳操作后所得的個體均為在可行路徑的基礎上提出新的自適應調整方式與之配合，同時于引入模擬退火算法Metropolis準則，對遺傳操作產生的個體進行接收判定，尋優成功率和路徑效果均得到了優化，但此方法不適合復雜地圖環境[8]。陳志軍等將遺傳算法和模糊神經網絡結合，求解最優目標函數并給出了三維路徑規劃評價指標,但整個算法過于繁雜[9]。宋宇等在種群初始化時，先結合RRT算法，再引入改進的插入算子創建鄰居列表矩陣，得到的路徑長度比基本遺傳算法縮短70%，但算法收斂速度過慢[10]。雷永鋒等基于正弦式遺傳算法，通過改進交叉和變異策略，很好地解決了算法易早熟的現象,提高了算法收斂速度，但在路徑尋優上還有待改進[11]。

機器人路徑規劃屬于非確定性復雜問題。智能遺傳算法是通過模擬自然界遺傳操作的一種并行和全局搜索算法。因為能夠在參數空間同時進行多點并行計算，所以更有可能搜索到全局最優，同時對其搜索空間沒有連續的要求。但是，智能遺傳算法在種群產生、適應度函數建模、搜索效率等方面還存在一定的缺陷[12]。特別是在復雜環境下，往往需要耗費大量時間才能規劃出可行路徑。針對這一問題，本文提出一種自適應遺傳算法的機器人路徑規劃方法。該方法根據先驗知識初始化種群縮短迭代次數，提出新的自適應策略，并根據適應度值大小自動調節交叉和變異概率，避免算法陷入局部最優；對于適應度函數，選取路徑最短和平滑度雙重約束，保證路徑最短，且轉折次數更少。

1 環境模型的建立及編碼

將移動機器人工作環境表示成柵格地圖的形式，如圖1所示。圖1中，自由柵格用白色表示，障礙物柵格用黑色表示，路徑點的位置可以用直角坐標和柵格序號表示。采用二進制編碼，柵格長度和寬度均為單位長度，分別標識柵格和坐標。柵格序號與其相對應的直角坐標一一對應，序號P(i,j)的柵格坐標表示為

(1)

式中: mod表示取余運算;[·]表示取整運算。

圖 1 環境建模Fig.1 Environmental modeling

2 機器人路徑規劃

2.1 改進初始化種群方式

機器人在柵格法地圖中，在未遇到障礙物和未超過地圖邊界時，默認可以向8個方向移動。這種方法雖能找到可行路徑，但增加路徑多變性，出現路徑轉彎次數過多、路徑循環等現象，影響收算法斂速度，不利于機器人運行，故作如下改進：在機器人所在位置周圍8個柵格中舍棄遠離目標點的3個柵格，保留剩余5個方向進行初始化，具體流程如圖2所示。

圖 2 種群初始化流程Fig.2 Population initialization process

2.2 適應度函數的選擇

機器人路徑規劃目的是尋找從起點到目標點最優路徑，而適應度函數能有效評價每條路徑的優劣程度。設計適應度函數首先應滿足路徑最短，其次應確保路徑足夠平滑。因此，本文中的適應度函數同時將路徑最短和路徑平滑度2個因素作為評價路徑優劣的標準。

2.2.1 最短路徑f1假設在一個路徑中移動機器人個體從一個節點Pi(xi,yi)運動到下一個節點Px+i(xi+1,yi+1),則2節點間的距離di為

(2)

該個體總的移動距離L為

(3)

式中：n為該機器人運行總節點數。

適應度函數第1部分為

(4)

2.2.2 路徑平滑度f2首先設定機器人每次移動一個柵格。根據相鄰3個節點和相鄰2個節點間的距離判斷出此時機器人轉動的角度。假設相鄰3個節點的坐標分別為A(xi+1,yi+1)，B(xi,yi)，C(xi+2,yi+2)，路徑段夾角可用余弦定理表示。

相鄰2點間的距離為

(5)

相鄰3點間的距離為

(6)

由余弦定理可以求出相鄰3個點之間的夾角，根據角度的大小分別給予不同的懲罰值,即

(7)

式中:wk為懲罰函數系數;θ為相鄰3點之間的角度。

適應度函數第2部分為

(8)

結合路徑最短和路徑平滑度,得出本文適應度函數為

fit=af1+bf2

(9)

式中:a和b分別表示最短路徑和平滑度的權重系數。

2.3 交叉操作

本文采用單點交叉方式[13]，當且僅當2個交叉個體在交叉點的柵格序號相同時進行交叉操作。如果2個個體在交叉點相同的序號不止一個，則任選一處進行交叉。假設2個待交叉個體為父代A和母代B，選擇交叉點序號為33，具體過程如圖3所示。在交叉完成后通過比較父代和子代適應度值大小，決定其去留，即適應度值大的保留，反之舍去，這樣可使算法總是朝著最優方向進化。

圖 3 交叉示意圖Fig.3 Cross diagram

2.4 變異操作

傳統遺傳算法變異操作是在變異位置隨機突變，會導致變異前路徑是可行的，變異后路徑變為障礙路徑，加大了不可行路徑產生的概率。針對這一問題，本文提出新的變異策略。本文提出的變異過程及應對策略(見圖4)如下：

圖 4 變異策略Fig.4 Mutation strategy

1) 假設路徑為[1 7 12 18 24 25](見圖4),隨機選擇變異位置Bi為12號柵格。

2) 判斷出Bi的右方13號、上方17號和右上方18號柵格均為自由柵格且未超出工作邊界，此時，隨機向這3個方向進行變異。

3) 向右方變異后的路徑為[1 7 12 13 19 24 25]，向上方變異路徑為[1 7 12 17 18 24 25],向右上方變異路徑為[1 7 18 24 25]。此時，判斷出變異后的3條路徑均未經過障礙物,都是可行路徑。若變異后的路徑經過障礙物，則刪除此條路徑。

4) 分別計算出包括原路徑的4條路徑到目標點長度，得出[1 7 18 24 25]路徑長度最短，用此路徑替換原路徑，完成變異操作。

2.5 自適應調整

遺傳算法中交叉概率(Pc)和變異概率(Pm)對算法收斂性和路徑求解質量起著至關重要的作用[14]，且傳統遺傳算法中(Pc)和(Pm)都固定不變，不利于種群的進化。Pc選擇過大將會破壞群體的平衡性,導致適應度值大的個體被破壞；相反，選擇過小將會延緩群體進化速度。同樣，Pm選擇太大群體進化方向多變,不利于優勢個體保留；選擇過小，不利于新個體的產生，算法易早熟陷入局部最優。所以，采用固定的Pc和Pm很難滿足路徑規劃的要求。針對這一問題，本文對交叉和變異進行自適應調整改進[15-17]，調整為

(10)

(11)

式中:fav是每代群體的平均適應度值;f′是要交叉的2個個體中較小的適應度值，f是要變異個體的適應度值;設定k1、k2的區間為[0.6,1]。

由式(10)和(11)可以看出：新的自適應調整公式采用指數形式保證了交叉和變異概率呈現穩定的變化趨勢，避免交叉和變異概率出現極度增大或減小的情況。進化初期群體良莠不齊，選擇小的交叉和變異概率有利于群體中優良個體保留；相反，那些適應度值小的個體則被加快淘汰。在進化后期種群個體的適應度值無限接近,此時選擇較大的交叉和變異概率加快新個體產生，避免算法陷入停滯狀態，克服早熟[18-20]。

3 仿真分析

為了驗證算法的有效性，選取2種不同環境對機器人路徑規劃進行仿真實驗。環境1選取障礙物柵格數為19個，環境2選取障礙物柵格數為77個。設定對基本遺傳算法參數如下：種群大小NP=100，最大進化代數G=100,交叉概率Pc=0.6 ，變異概率Pm=0.2。在本文算法中，路徑最短權重系數a=4，路徑平滑度權重系數b=3，種群大小及最大進化代數與基本遺傳算法中的選擇相同；交叉概率Pc1=0.9，Pc2=0.6 ，變異概率Pm1=0.2，Pm2=0.1；在自適應交叉和變異概率中取k1=0.9，k2=0.8。對于環境1，2種算法仿真實驗最優路徑軌跡和收斂曲線如圖5所示。

(a) 2種算法最優路徑對比

(b) 最優路徑進化曲線對比圖 5 環境1最優路徑及其進化曲線對比Fig.5 Comparison of the optimal path and its evolution curve in environment 1

從圖5可以看出：在相對簡單的地圖環境中，基本遺傳算法在第8代左右得到最優解，此時路徑長度為14.486，路徑中轉折點數為6；而本文算法搜索到全局最優路徑長度為13.314，路徑轉折點數為4。顯然，相比基本遺傳算法,本文算法路徑長度縮短8.1%，轉折次數更少，路徑更加平滑。

環境2仿真實驗最優路徑和收斂曲線見圖6。

從圖6可以看出：在相對復雜的環境中更能體現本文算法的優越性?；具z傳算法在9代左右便陷入局部最優解，最終搜索結果為29.799，路徑轉折點數為15，沒達到理想結果；而本文算法在第7代左右就趨于穩定，搜索到全局最優解為28.627，路徑轉折點個數為11。本文算法節約時間，路徑更加平滑，同時也得到了機器人最優路徑。

為驗證本文算法的有效性，又選取了8種不同的機器人工作環境，即8種不同障礙物個數仿真實驗。圖7是障礙物個數為31和99的尋優結果。然后，對8種不同環境條件，各進行20次路徑規劃仿真實驗，結果見表1。從表1可看出，對于本文的改進算法，隨著障礙物個數不斷增加，路徑長度降低的比重逐漸增大，且路徑中轉折點個數相對基本遺傳算法減少3～5個，算法迭代次數也優于基本遺傳算法。