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

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

0 引 言

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

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

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

1 環(huán)境模型的建立及編碼

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

(1)

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

圖 1 環(huán)境建模Fig.1 Environmental modeling

2 機器人路徑規(guī)劃

2.1 改進(jìn)初始化種群方式

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

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

2.2 適應(yīng)度函數(shù)的選擇

機器人路徑規(guī)劃目的是尋找從起點到目標(biāo)點最優(yōu)路徑，而適應(yīng)度函數(shù)能有效評價每條路徑的優(yōu)劣程度。設(shè)計適應(yīng)度函數(shù)首先應(yīng)滿足路徑最短，其次應(yīng)確保路徑足夠平滑。因此，本文中的適應(yīng)度函數(shù)同時將路徑最短和路徑平滑度2個因素作為評價路徑優(yōu)劣的標(biāo)準(zhǔn)。

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

(2)

該個體總的移動距離L為

(3)

式中：n為該機器人運行總節(jié)點數(shù)。

適應(yīng)度函數(shù)第1部分為

(4)

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

相鄰2點間的距離為

(5)

相鄰3點間的距離為

(6)

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

(7)

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

適應(yīng)度函數(shù)第2部分為

(8)

結(jié)合路徑最短和路徑平滑度,得出本文適應(yīng)度函數(shù)為

fit=af1+bf2

(9)

式中:a和b分別表示最短路徑和平滑度的權(quán)重系數(shù)。

2.3 交叉操作

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

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

2.4 變異操作

傳統(tǒng)遺傳算法變異操作是在變異位置隨機突變，會導(dǎo)致變異前路徑是可行的，變異后路徑變?yōu)檎系K路徑，加大了不可行路徑產(chǎn)生的概率。針對這一問題，本文提出新的變異策略。本文提出的變異過程及應(yīng)對策略(見圖4)如下：

圖 4 變異策略Fig.4 Mutation strategy

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

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

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

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

2.5 自適應(yīng)調(diào)整

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

(10)

(11)

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

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

3 仿真分析

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

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

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

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

環(huán)境2仿真實驗最優(yōu)路徑和收斂曲線見圖6。

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

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

(a) 31個障礙物的路徑尋優(yōu)結(jié)果 (b) 99個障礙物的路徑尋優(yōu)結(jié)果圖 7 不同障礙物個數(shù)下路徑尋優(yōu)結(jié)果Fig.7 Path optimization results in different number of obstacles

表 1 不同環(huán)境下路徑規(guī)劃仿真實驗結(jié)果

4 結(jié) 論

1) 設(shè)計的自適應(yīng)交叉和變異概率公式，避免了算法陷入局部最優(yōu)，克服早熟的缺點。

2) 隨著障礙物增多，在環(huán)境更加復(fù)雜的情況下，本文算法得到的最優(yōu)路徑更短、轉(zhuǎn)折次數(shù)更少。仿真實驗證明了算法的可行性。