自適應(yīng)遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用

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

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

0 引 言

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

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

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

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

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

(1)

式中: mod表示取余運(yùn)算;[·]表示取整運(yùn)算。

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

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

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

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

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

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

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

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

(2)

該個(gè)體總的移動(dòng)距離L為

(3)

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

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

(4)

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

相鄰2點(diǎn)間的距離為

(5)

相鄰3點(diǎn)間的距離為

(6)

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

(7)

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

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

(8)

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

fit=af1+bf2

(9)

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

2.3 交叉操作

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

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

2.4 變異操作

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

圖 4 變異策略Fig.4 Mutation strategy

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

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

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

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

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

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

(10)

(11)

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

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

3 仿真分析

為了驗(yàn)證算法的有效性，選取2種不同環(huán)境對(duì)機(jī)器人路徑規(guī)劃進(jìn)行仿真實(shí)驗(yàn)。環(huán)境1選取障礙物柵格數(shù)為19個(gè)，環(huán)境2選取障礙物柵格數(shù)為77個(gè)。設(shè)定對(duì)基本遺傳算法參數(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。對(duì)于環(huán)境1，2種算法仿真實(shí)驗(yàn)最優(yōu)路徑軌跡和收斂曲線如圖5所示。

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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