基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃

徐夢(mèng)穎,王嬌嬌,劉寶,馬良,柴林杰,向麗,周杰

(石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院,新疆 石河子832003)

提高路徑規(guī)劃效率逐漸成為移動(dòng)機(jī)器人領(lǐng)域中的研究熱點(diǎn),其任務(wù)在于已知起點(diǎn)和終點(diǎn),探尋出一條無碰撞的最優(yōu)路徑[1-3]。遺傳算法是現(xiàn)今應(yīng)用最為廣泛的最優(yōu)解處理算法[4-6],傳統(tǒng)算法容易陷入局部最優(yōu)解,通過改進(jìn)傳統(tǒng)遺傳算法提升機(jī)器人路徑規(guī)劃效率[8-9]。解決路徑規(guī)劃的問題,首先要對(duì)環(huán)境進(jìn)行建模[10-13],柵格法是研究人員解決機(jī)器人路徑規(guī)劃問題并建立環(huán)境模型使用的主要方法[14-15]。目前,一些學(xué)者提出了許多智能算法,ZHANG J H[16]使用粒子群算法(Particle Swarm Optimization,PSO)提高運(yùn)動(dòng)效率,該算法能夠有效優(yōu)化路徑長(zhǎng)度、路徑的平滑度和安全程度,然而算法容易出現(xiàn)早熟收斂的問題;鞏敦衛(wèi)等[17]提出了一種模擬退火算法(Simulated Annealing,SA)能有效避免節(jié)點(diǎn)布置中一些路徑暴露問題;混合遺傳算法容易陷入進(jìn)化停滯,導(dǎo)致得到的解集質(zhì)量較低。

為了解決尋找最短路徑時(shí)存在解的質(zhì)量較低的問題,本文提出一種免疫克隆自適應(yīng)遺傳算法(Immune Clone Adaptive Genetic Algorithm,ICAGA),通過建立柵格模型對(duì)柵格進(jìn)行編碼,再進(jìn)行選擇、交叉、變異,計(jì)算出最短路徑,并使用Matlab對(duì)其進(jìn)行仿真實(shí)驗(yàn)驗(yàn)證,并與SA、PSO進(jìn)行比較。

1 基于ICAGA的最優(yōu)路徑規(guī)劃

1.1 路徑規(guī)劃模型

路徑規(guī)劃是指如何讓移動(dòng)機(jī)器人依照特定指標(biāo)完成從起始點(diǎn)到終點(diǎn)而且能夠避開途中障礙物的一種技術(shù)。柵格法是解決路徑規(guī)劃問題的重要方法[18],機(jī)器人所處的柵格有可行動(dòng)?xùn)鸥窈驼系K柵格2種。

圖1表示二維空間的柵格模型,模型中的圓形為障礙柵格,該模型中共有5個(gè)障礙。圖形左下角第1個(gè)柵格為1號(hào)柵格,按照從下到上、從左往右的順序依次根據(jù)標(biāo)號(hào)對(duì)柵格進(jìn)行命名。二維空間左下角的序號(hào)是1,二維空間右上角的序號(hào)是100。機(jī)器人從第1個(gè)柵格出發(fā),隨機(jī)得到一條可行的不可重復(fù)的連續(xù)路徑,最后到達(dá)第100號(hào)柵格。機(jī)器人的所有運(yùn)動(dòng)軌跡全部存儲(chǔ)在一個(gè)數(shù)組中,障礙物的位置也記錄下來,通過計(jì)算染色體的總長(zhǎng)并對(duì)其進(jìn)行比較,最后將最優(yōu)個(gè)體求解出來。

圖1 柵格模型

當(dāng)移動(dòng)機(jī)器人到達(dá)第h號(hào)格子時(shí),此時(shí)機(jī)器人可選擇的下一步可行格子的序號(hào)分別為h+1、h-1、h+10、h-10。若移動(dòng)機(jī)器人運(yùn)動(dòng)到整個(gè)柵格平面的邊緣,則只有鄰近的3個(gè)柵格可以選擇,當(dāng)機(jī)器人運(yùn)動(dòng)到柵格平面的頂點(diǎn)處,則只有2個(gè)柵格可以選擇。同時(shí)所經(jīng)過的柵格不得重復(fù)。

柵格分為自由柵格和障礙柵格,在式(1)中,柵格分別用0、1來表示,二進(jìn)制環(huán)境矩陣E表示柵格環(huán)境的全部信息,其中0代表自由柵格,1代表障礙柵格。

式(2)中S為一條可行路徑,其中{s1,s2,……}分別對(duì)應(yīng)路徑上的柵格序號(hào)。

針對(duì)路徑規(guī)劃問題,本文設(shè)計(jì)了適應(yīng)度函數(shù)求路徑長(zhǎng)度。適應(yīng)度函數(shù)f通過計(jì)算染色體的長(zhǎng)度表示:

用柵格法建立模型應(yīng)遵從以下規(guī)則:不用考慮機(jī)器人以及障礙物的高度影響,把機(jī)器人當(dāng)成為一個(gè)質(zhì)點(diǎn)放在二維空間來運(yùn)行;機(jī)器人在柵格中做勻速直線運(yùn)動(dòng),且機(jī)器人每次都處于每個(gè)柵格的正中心,它與其他柵格中心連線不經(jīng)過障礙物即認(rèn)為兩者之間可以直線到達(dá),第1號(hào)柵格與最后一個(gè)柵格不可設(shè)置障礙。

1.2 路徑規(guī)劃算法

遺傳算法(Genetic Algorithm,GA)[19]自20世紀(jì)提出后不斷用于解決一些實(shí)際問題,也取得了很多成果,但是該算法存在一些缺陷,主要是容易陷入局部最優(yōu),不利于優(yōu)化機(jī)器人運(yùn)動(dòng)路徑長(zhǎng)度。本文研究在傳統(tǒng)GA算法的基礎(chǔ)上加入免疫克隆算子和自適應(yīng)算子,組成一種新的算法ICAGA,通過免疫克隆算子和自適應(yīng)算子可加快算法的收斂速度,從而找到優(yōu)質(zhì)路徑。ICAGA可以通過以下步驟優(yōu)化機(jī)器人運(yùn)動(dòng)路徑。

1.2.1 個(gè)體編碼

在ICAGA中,編碼策略需要路徑規(guī)劃問題而定。二進(jìn)制字符串較長(zhǎng)會(huì)影響算法的運(yùn)行時(shí)間,在ICAGA中采用十進(jìn)制編碼方法。在進(jìn)行算法處理時(shí),必須將機(jī)器人經(jīng)過的路徑節(jié)點(diǎn)逐一取出放入數(shù)組中,從而形成一條完整的路徑。圖1中個(gè)體S表示為{1,2,3,13,12,22,23,24,25,35,36,46,45,55,56,57,58,68,67,77,87,97,98,99,100},在這些運(yùn)動(dòng)節(jié)點(diǎn)上,關(guān)于該運(yùn)動(dòng)路徑以及算法的實(shí)現(xiàn)步驟,均在這些路徑節(jié)點(diǎn)上進(jìn)行。

1.2.2 初始化種群

在ICAGA中,由于每條路徑的長(zhǎng)度是不確定的,所以染色體長(zhǎng)度也是不等的,每個(gè)染色體的起點(diǎn)和終點(diǎn)相同。具體操作是:先定義種群的數(shù)量,將起始點(diǎn)和終點(diǎn)定義成個(gè)體的第一位基因與最后一位基因,從起點(diǎn)開始,隨機(jī)選擇上、下、左、右4個(gè)方向的可行柵格,由這些柵格組成的線段形成一條可行路徑,機(jī)器人在尋找下一可行柵格時(shí)不可重復(fù)選擇,不可碰壁,否則該個(gè)體被視為不可行路徑被舍棄。

1.2.3 選擇

在種群中選擇機(jī)器人運(yùn)動(dòng)長(zhǎng)度較短個(gè)體,舍棄運(yùn)動(dòng)長(zhǎng)度較長(zhǎng)個(gè)體,通過計(jì)算適應(yīng)度獲得每條路徑被遺傳到下一代的概率。選擇是為了提升較短路徑遺傳到下一代的概率。

輪盤賭算法是選擇操作的主要方法之一,該方法主要用于選擇較短路徑。每一個(gè)可行路徑是輪盤上大小不一的扇形區(qū)域,區(qū)域的面積通過計(jì)算每一個(gè)個(gè)體的路徑長(zhǎng)度與種群總長(zhǎng)度的比值可得。根據(jù)適應(yīng)度可以確定該染色體被選擇并遺傳到后代的概率。在選擇時(shí),按照每一次輪盤指針旋轉(zhuǎn)之后所指向的位置隨機(jī)選擇相應(yīng)個(gè)體。

式(4)中,n為可行路徑的個(gè)數(shù),f(i)是一個(gè)可行路徑的路徑長(zhǎng)度;式(5)、(6)、(7)中,pi為第i個(gè)可行路徑長(zhǎng)度占總長(zhǎng)度的概率大小,Pi為第i-1個(gè)個(gè)體到第i個(gè)個(gè)體的概率累加和,rand為0～1之間的隨機(jī)數(shù)。

在路徑規(guī)劃中,適應(yīng)度越小則路徑越短,被選擇的概率越大。由式(3)可知,路徑長(zhǎng)度越長(zhǎng),該個(gè)體被選擇的概率就越大;通過式(4)轉(zhuǎn)換可知,f(i)越大,F(i)越小,通過該轉(zhuǎn)換方法選擇最短路徑。輪盤賭算法的主要過程如下:

(1) 計(jì)算每一個(gè)可行路徑的長(zhǎng)度,將f(i)轉(zhuǎn)換為F(i),計(jì)算所有F(i)的總和;

(2) 計(jì)算F(i)與所有F(i)總和的比值,得到每一個(gè)可行路徑在輪盤中能夠被挑選出來的概率;

(3) 在(0,1)區(qū)間上產(chǎn)生隨機(jī)數(shù)rand。

(4) 通過式(7)與隨機(jī)數(shù)作比較,如果隨機(jī)數(shù)落在第i-1個(gè)盤子和第i個(gè)盤子之間,則i個(gè)個(gè)體被選中;

(5) 重復(fù)步驟(3)、(4),直到篩選的數(shù)目達(dá)到要求。

1.2.4 交叉

ICAGA算法采用單點(diǎn)交叉的方法,將母本在隨機(jī)產(chǎn)生的位置斷開,父本也在其對(duì)應(yīng)的同一位置斷開,將母本前一部分與父本后一部分組合,母本后一部分與父本前一部分組合,形成2個(gè)新的個(gè)體。根據(jù)機(jī)器人的路徑規(guī)劃特性,本文設(shè)計(jì)的機(jī)器人交叉過程具體為:2條路徑中同一柵格后的所有柵格節(jié)點(diǎn)交換形成2條新的路徑。

一個(gè)可行路徑中若有n個(gè)柵格就有n-1個(gè)交叉點(diǎn),可行路徑中的交叉操作可以通過以下方法表示。如圖2所示,S1、S2分別表示為2條可行路徑,首先在S1、S2中隨機(jī)產(chǎn)生一個(gè)共同交叉位置,即選擇S1和S2中的相同路徑節(jié)點(diǎn)進(jìn)行交叉;其次,S1和S2在交叉點(diǎn)之前的路徑節(jié)點(diǎn)不改變位置,交叉點(diǎn)之后的柵格互換位置,生成新的路徑;最后判斷這是否是一條可行路徑,若不是一條可行的連續(xù)的路徑,則丟棄該路徑,父代個(gè)體依舊作為可行路徑遺傳到下一代。

圖2 交叉

在傳統(tǒng)遺傳算法的遺傳操作中,采用的是完全隨機(jī)的方式,但是在機(jī)器人路徑規(guī)劃問題上,完全隨機(jī)操作極有可能產(chǎn)生不可行路徑。具體操作步驟如下:

(1)隨機(jī)選擇2個(gè)個(gè)體間的共同交叉點(diǎn)作為父代;

(2)交換2個(gè)個(gè)體交叉點(diǎn)后的柵格路徑形成新的個(gè)體;

(3)計(jì)算新個(gè)體的適應(yīng)度。

1.2.5 變異

變異是模擬生物界進(jìn)化遺傳過程中染色體的基因突變過程,使用變異算子可以使種群在迭代的過程中不斷引入新基因,得到新的路徑,從而增加路徑規(guī)劃的多樣性。根據(jù)機(jī)器人的路徑規(guī)劃特性設(shè)計(jì)了路徑變異方式,具體變異過程如圖3所示。

圖3 變異

首先在種群中隨機(jī)選擇一條機(jī)器人的運(yùn)動(dòng)路徑,按照變異的概率在這條路徑上隨機(jī)選擇一個(gè)變異柵格,例如要變異圖1中第23號(hào)柵格,則需要在第22號(hào)柵格周圍的12、21、23、32這4個(gè)位置中隨機(jī)選擇一個(gè)柵格作為變異柵格,使變異后的路徑成為一條連續(xù)、可行且不重復(fù)的路徑,若該路徑不連續(xù)則丟棄該路徑,將父代個(gè)體遺傳到下一代;若可行則保留并計(jì)算適應(yīng)度。變異的具體步驟如下:

(1)隨機(jī)選取一條可行路徑;

(2)根據(jù)變異概率隨機(jī)選取該路徑上的一個(gè)柵格作為變異柵格;

(3)將變異柵格變異為其周圍的上、下、左、右中任意可行的不重復(fù)的自由柵格,并形成一個(gè)新的可行路徑;

(4)計(jì)算該可行路徑的適應(yīng)度函數(shù)。

1.2.6 計(jì)算適應(yīng)度

ICAGA中計(jì)算適應(yīng)度可以確定機(jī)器人運(yùn)動(dòng)的軌跡長(zhǎng)度,適應(yīng)度f可通過式(3)計(jì)算可得。

1.2.7 免疫克隆算子

ICAGA中免疫克隆算子用于提高解的質(zhì)量,加快ICAGA的收斂速度。將待優(yōu)化的最短路徑問題表示為抗原,路徑優(yōu)化中的一個(gè)可行路徑可以表示為一個(gè)抗體。為了方便選擇、交叉和變異,抗原和抗體編碼均通過十進(jìn)制編碼的方式,在ICAGA中把一條可行路徑對(duì)應(yīng)一個(gè)抗體,將式(3)中的f當(dāng)成評(píng)價(jià)機(jī)器人運(yùn)動(dòng)路徑親和度的指標(biāo)數(shù)。ICAGA基本算法過程如下:

(1) 初始化。路徑優(yōu)化中的一個(gè)可行路徑可以表示為一個(gè)抗體,有多少可行路徑就有多少抗體。

(2) 評(píng)價(jià)和選擇。將n個(gè)可行路徑分解成2組,分別為記憶集抗體和剩余部分,把記憶集中的抗體看作較優(yōu)路徑。

(3) 克隆。在機(jī)器人運(yùn)動(dòng)路徑較短的可行路徑中選擇k個(gè)路徑克隆,解被克隆的數(shù)量與其路徑長(zhǎng)度成反比,機(jī)器人運(yùn)動(dòng)路徑的長(zhǎng)度長(zhǎng)短將會(huì)決定個(gè)體被克隆的次數(shù)。

(4) 變異。針對(duì)克隆后的可行路徑,需要繼續(xù)對(duì)該路徑變異,通過一個(gè)變異概率隨機(jī)選取一條可行路徑從而生成一個(gè)新的個(gè)體。

(5) 評(píng)價(jià)和選擇。針對(duì)變異后的可行路徑求解路徑長(zhǎng)度,若克隆和變異操作后的可行路徑比原路徑的長(zhǎng)度還短,根據(jù)優(yōu)勝劣汰原則,機(jī)器人運(yùn)動(dòng)較長(zhǎng)的個(gè)體將被替換掉并生成新的記憶集。

1.2.8 自適應(yīng)算子

GA中參數(shù)的設(shè)置是固定的,ICAGA中通過加入自適應(yīng)算子根據(jù)適應(yīng)度自動(dòng)調(diào)節(jié)交叉概率和變異概率,可避免因參數(shù)設(shè)置不當(dāng)導(dǎo)致算法陷入局部最優(yōu)。本文通過研究機(jī)器人運(yùn)動(dòng)路徑的長(zhǎng)度設(shè)計(jì)自適應(yīng)算子自動(dòng)調(diào)整交叉概率Pa與變異概率Pb,調(diào)整公式為式(8)、式(9):

式(8)、式(9)中,f是將要變異的染色體的路徑長(zhǎng)度,f′是2個(gè)交叉路徑中路徑長(zhǎng)度較短個(gè)體的路徑長(zhǎng)度,fmin是機(jī)器人所有可行路徑中的最短路徑,favg是種群中平均路徑長(zhǎng)度,q1、q2、q3、q4分別是0～1之間的常數(shù)。

1.2.9 終止條件的設(shè)定

終止條件有很多方式,如迭代次數(shù)、是否收斂等。在ICAGA中,當(dāng)?shù)螖?shù)達(dá)到最大遺傳次數(shù)時(shí)停止迭代,并得到最優(yōu)路徑。

2 仿真實(shí)驗(yàn)

2.1 方法

仿真實(shí)驗(yàn)采用Windows10系統(tǒng)進(jìn)行,CPU使用2.0 GHz的i7處理器,內(nèi)存為16.0 GB,仿真軟件使用Matlab R2014a的版本。根據(jù)建立的數(shù)學(xué)模型設(shè)置障礙物個(gè)數(shù),在ICAGA、PSO、SA中,個(gè)體數(shù)量設(shè)置為50,最大迭代次數(shù)為100次,最大實(shí)驗(yàn)次數(shù)為50次。ICAGA的參數(shù)由多次仿真實(shí)驗(yàn)的經(jīng)驗(yàn)可得,其中交叉概率為0.9,變異概率為0.05。障礙物的數(shù)量分別設(shè)為5、10、15、20。仿真實(shí)驗(yàn)中針對(duì)求解路徑規(guī)劃問題對(duì)ICAGA和PSO、SA這3種算法進(jìn)行對(duì)比。

2.2 結(jié)果與分析

圖4～7為經(jīng)過50次實(shí)驗(yàn)且每次實(shí)驗(yàn)迭代100次后ICAGA、PSO、SA這3種算法在障礙物數(shù)量為5、10、15和20時(shí)的平均適應(yīng)度對(duì)比圖。

由圖4可知:障礙物數(shù)量為5時(shí),ICAGA的平均適應(yīng)度值遠(yuǎn)低于PSO和SA;ICAGA、PSO、SA的路徑長(zhǎng)度分別為20.08、22.19、23.76,ICAGA優(yōu)化后的平均路徑長(zhǎng)度比PSO、SA分別降低了9.51%、15.49%。這表明:機(jī)器人在一個(gè)靜態(tài)環(huán)境中尋找最優(yōu)路徑時(shí),ICAGA的收斂速度更快,尋找最優(yōu)解的效率更高。

圖4b～d顯示:當(dāng)障礙物個(gè)數(shù)為10時(shí),ICAGA、PSO、SA優(yōu)化后的機(jī)器人平均運(yùn)動(dòng)路徑長(zhǎng)度分別為22.38、24.17、26.64,ICAGA優(yōu)化后的路徑長(zhǎng)度與PSO、SA相比分別降低了7.41%、15.99%;當(dāng)障礙物個(gè)數(shù)為15時(shí),3種算法優(yōu)化過的機(jī)器人平均運(yùn)動(dòng)路徑長(zhǎng)度分別為24.43、26.71、27.69,ICAGA優(yōu)化后的路徑長(zhǎng)度與PSO、SA相比分別降低了8.54%、11.77%;當(dāng)障礙物個(gè)數(shù)為20時(shí),3種算法優(yōu)化過的機(jī)器人平均運(yùn)動(dòng)路徑長(zhǎng)度分別為26.34、28.02、29.61,ICAGA優(yōu)化后的路徑長(zhǎng)度與PSO、SA相比分別降低了5.99%、11.04%。上述結(jié)果表明:適應(yīng)度越小,機(jī)器人由起點(diǎn)到終點(diǎn)的距離越短,將ICAGA與PSO、SA相比,ICAGA算法收斂速度更快,能夠有效地找到最優(yōu)解,該算法在提高機(jī)器人的運(yùn)動(dòng)效率和尋找最短的路徑時(shí)更有優(yōu)勢(shì)。

圖4 障礙物數(shù)量為5(a)、10(b)、5(c)、20(d)時(shí)算法適應(yīng)度的對(duì)比

ICAGA、PSO、SA在不同障礙物數(shù)量且實(shí)驗(yàn)次數(shù)分別為1、20、50次時(shí)運(yùn)行時(shí)間的對(duì)比結(jié)果(表1)表明:隨著實(shí)驗(yàn)次數(shù)與障礙物數(shù)量的增加,算法的計(jì)算難度加大,因此算法運(yùn)行時(shí)間也在不斷提高。

表1 算法運(yùn)行時(shí)間對(duì)比

3 討論

(1)針對(duì)機(jī)器人尋找最短路徑的問題,本文設(shè)計(jì)了柵格模型,該模型按照順序?qū)鸥襁M(jìn)行標(biāo)記,并設(shè)計(jì)了計(jì)算運(yùn)動(dòng)路徑長(zhǎng)度的適應(yīng)度函數(shù),再在GA基礎(chǔ)上提出了一種新的算法ICAGA。在機(jī)器人運(yùn)動(dòng)的靜態(tài)環(huán)境中,隨機(jī)設(shè)置障礙物的位置,隨著障礙物數(shù)量不斷增加,機(jī)器人運(yùn)動(dòng)路徑變長(zhǎng),路徑規(guī)劃復(fù)雜度提升。在迭代過程中,ICAGA不斷收斂,在迭代后期算法的收斂速度降低。在障礙物數(shù)量增加至20時(shí),ICAGA算法優(yōu)化過的路徑長(zhǎng)度為26.34,與PSO、SA相比分別降低了5.99%、11.04%。在障礙物數(shù)量為5、10、15、20且ICAGA分別實(shí)驗(yàn)1、20、50次時(shí),隨著障礙物數(shù)量的增加,算法運(yùn)行時(shí)間增大;當(dāng)不斷提高實(shí)驗(yàn)次數(shù)時(shí),算法的計(jì)算難度加大,因此機(jī)器人尋找最優(yōu)路徑時(shí)間不斷提高。

(2)由于傳統(tǒng)PSO與SA具有收斂速度慢、易陷入局部最優(yōu)的缺點(diǎn),所以在達(dá)到最大迭代次數(shù)后,當(dāng)障礙物數(shù)量增加至20時(shí),PSO、SA優(yōu)化后的路徑長(zhǎng)度分別為28.02、29.61,都大于ICAGA優(yōu)化后的機(jī)器人運(yùn)動(dòng)路徑長(zhǎng)度,而且與ICAGA相比,PSO與SA運(yùn)行時(shí)間更長(zhǎng),機(jī)器人路徑規(guī)劃效率更低。

4 結(jié)論

(1)本文提出的ICAGA使用免疫克隆算子將種群中最優(yōu)個(gè)體復(fù)制到下一代能提高種群的尋優(yōu)能力,并通過加入自適應(yīng)算子在迭代的過程中不斷調(diào)整交叉概率與變異概率而提高種群的收斂速度,降低路徑搜索的盲目性并縮短路徑長(zhǎng)度。

(2)與PSO、SA算法相比,ICAGA尋優(yōu)能力更強(qiáng),有效縮短了機(jī)器人的運(yùn)動(dòng)路徑長(zhǎng)度。

(3)ICAGA具有良好的靜態(tài)避障性能,能有效降低機(jī)器人的運(yùn)動(dòng)路徑長(zhǎng)度,且收斂速度更快,能實(shí)現(xiàn)路徑規(guī)劃的高效尋優(yōu),為機(jī)器人的應(yīng)用提供可靠依據(jù)。