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

湯云峰,趙 靜,謝 非,李鑫煌,林智昌,劉益劍

(1.南京師范大學(xué)電氣與自動(dòng)化工程學(xué)院,江蘇 南京 210023) (2.南京郵電大學(xué)自動(dòng)化學(xué)院、人工智能學(xué)院,江蘇 南京 210023) (3.江蘇省物聯(lián)網(wǎng)智能機(jī)器人工程實(shí)驗(yàn)室,江蘇 南京 210023) (4.南京中科煜宸激光技術(shù)有限公司,江蘇 南京 210038)

路徑規(guī)劃[1-2]有著廣泛的應(yīng)用. 靜態(tài)環(huán)境下的路徑規(guī)劃適用于搬運(yùn)機(jī)器人、搜救機(jī)器人等領(lǐng)域[3],這類問題均為靜態(tài)情況下面向已知環(huán)境信息,如何安全地避開障礙物找到并到達(dá)目的地的最短路徑問題[4-5]. 為解決此類問題,需先進(jìn)行環(huán)境建模,最常用的方法是柵格法與多種智能仿生算法[6-7](如蟻群算法[8]、遺傳算法[9]、人工魚群算法[10]等)結(jié)合使用,但均存在一定的缺陷. 國內(nèi)外學(xué)者對此進(jìn)行了大量研究,一直在探索新的路徑規(guī)劃方法或改進(jìn)已有算法. 遺傳算法在路徑規(guī)劃領(lǐng)域是一種有效可行的優(yōu)化方法,已有多種改進(jìn)遺傳算法被提出. 文獻(xiàn)[11]在適應(yīng)度函數(shù)中引入倒角算子,加快了收斂速度;文獻(xiàn)[12]采用變長編碼方案,避免了遺傳算子的復(fù)雜化,節(jié)約了計(jì)算成本,使收斂速度加快;文獻(xiàn)[13]提出一種改進(jìn)的交叉算子,使得算法的早熟收斂得到明顯改善,并提出了一種考慮距離、安全性和能量的新的適應(yīng)度函數(shù),有助于算法找到最優(yōu)路徑;文獻(xiàn)[14]提出一種新的遺傳修正算子,增強(qiáng)了改進(jìn)的遺傳算法逃出局部最優(yōu)路徑的能力;文獻(xiàn)[15]提出自適應(yīng)遺傳算法,使收斂速度加快的同時(shí)保證了機(jī)器人行駛的安全性.

基本遺傳算法在機(jī)器人路徑規(guī)劃中存在收斂速度慢、易陷入局部最優(yōu)解的問題[16]. 許多改進(jìn)算法未考慮機(jī)器人的轉(zhuǎn)彎次數(shù),轉(zhuǎn)彎次數(shù)過多時(shí)會(huì)消耗更多的能量,安全性也會(huì)降低. 本文提出一種改進(jìn)的遺傳算法,針對轉(zhuǎn)彎次數(shù)較多問題,在適應(yīng)度函數(shù)中考慮了長度因子和平滑度因子,并根據(jù)機(jī)器人行走時(shí)轉(zhuǎn)彎角度的大小對平滑度因子加上了不同程度的懲罰,轉(zhuǎn)彎角度越小懲罰越大,在進(jìn)行輪盤賭選擇時(shí)被選擇的概率越小,有效減少了機(jī)器人轉(zhuǎn)彎次數(shù);針對收斂速度慢、易陷入局部最優(yōu)解問題,在進(jìn)行輪盤賭時(shí)加入精英選擇策略,將每次迭代后的最優(yōu)個(gè)體保留至下一代,同時(shí)讓交叉、變異概率自適應(yīng)改變,提高了算法逃離局部最優(yōu)路徑的能力,加快了算法的收斂速度.

1 基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法

本文在遺傳算法的適應(yīng)度函數(shù)中考慮了長度因子和平滑度因子,在平滑度因子中加入了懲罰操作,同時(shí)對交叉、變異概率進(jìn)行了調(diào)整,并引入精英保留策略以保證個(gè)體的高適應(yīng)度. 改進(jìn)后的遺傳算法流程圖如圖1所示.

1.1 環(huán)境建模

利用柵格地圖表示移動(dòng)機(jī)器人實(shí)際工作環(huán)境,路徑上的障礙物由一定比例黑色方塊替代,不足部分仍然填滿柵格,白色方塊為可行走空間,如圖2所示.

圖1 改進(jìn)遺傳算法的流程圖Fig.1 The flow chart of improved genetic algorithm

圖2 柵格地圖Fig.2 Grid-based map

初始化種群的具體過程為:

步驟1 設(shè)定算法所需各項(xiàng)參數(shù);

步驟2 判斷柵格是否連續(xù),判斷方法為:

Δ=max{abs(xi+1-xi),abs(yi+1-yi)},

(1)

式中,(xi,yi),(xi+1,yi+1)為兩個(gè)柵格對應(yīng)的坐標(biāo). 當(dāng)Δ=1時(shí),表示兩柵格連續(xù),否則利用平均值法插入柵格,計(jì)算方法為:

(2)

步驟3 若P′i序號柵格附近均為障礙物柵格,則淘汰此條路徑,重復(fù)上述步驟直至生成一條可行路徑.

1.2 適應(yīng)度函數(shù)的建立

適應(yīng)度的高低決定了個(gè)體適應(yīng)能力的大小,當(dāng)適應(yīng)度較高時(shí)易于生存,反之則會(huì)被淘汰,可用以判斷個(gè)體的優(yōu)劣程度[17]. 在機(jī)器人的路徑規(guī)劃中,長度是首要考慮因素,且機(jī)器人在行進(jìn)時(shí)存在一定的轉(zhuǎn)彎角度,因此本文在適應(yīng)度函數(shù)中考慮了長度因子和平滑度因子,新的適應(yīng)度函數(shù)如下:

Ffit=a×F1+b×F2,

(3)

式中,a、b為二者權(quán)重;F1為長度因子:

(4)

式中,LLength為路徑長度.F2為平滑度因子:

(5)

(6)

式中,(xi+1,yi+1)表示機(jī)器人當(dāng)前時(shí)刻所在位置;(xi,yi)表示其前一時(shí)刻所在位置;(xi+2,yi+2)表示其下一時(shí)刻所在位置;θ為機(jī)器人轉(zhuǎn)彎角度. 由于運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)的約束,轉(zhuǎn)彎角度不宜過大,因此當(dāng)機(jī)器人轉(zhuǎn)彎時(shí)給予適當(dāng)?shù)膽土P,減小其轉(zhuǎn)彎的概率. 利用余弦函數(shù)判斷轉(zhuǎn)彎角度的大小,分別對鈍角、直角、銳角給予5、30、1 000的懲罰.

1.3 遺傳操作

1.3.1 選擇操作

在遺傳算法中使用輪盤賭法選擇下一代個(gè)體,隨機(jī)性會(huì)使適應(yīng)度高的個(gè)體存在未被選中的可能. 為了避免此情況的發(fā)生,引入精英保留策略. 在使用輪盤賭選擇前,計(jì)算所有個(gè)體適應(yīng)度,把適應(yīng)度最優(yōu)的個(gè)體保留至下一代,不參與輪盤賭選擇,剩余個(gè)體通過輪盤賭法選出較優(yōu)個(gè)體,之后與精英個(gè)體進(jìn)行交叉變異操作,以提升算法尋找最優(yōu)解的能力,防止算法陷入局部最優(yōu)解.

1.3.2 交叉和變異操作

交叉概率(crossover probability)以Pc表示. 交叉操作在路徑規(guī)劃中指將已搜索到的兩條父代路徑在相交的點(diǎn)(隨機(jī)確定)進(jìn)行交換,交換后保留較短路徑,摒棄較長路徑,與基因的分裂與重組類似. 在進(jìn)行交叉操作后,子代路徑的適應(yīng)度可能高于父代路徑,達(dá)到尋優(yōu)的目的.

變異概率(mutation probability)以Pm表示. 變異操作在路徑規(guī)劃中指將已搜索到的父代路徑以概率Pm進(jìn)行翻轉(zhuǎn),結(jié)合交叉操作可能得到適應(yīng)度更高的子代路徑. 遺傳算法所擁有的變異行為能使其盡可能多地搜索到可行路徑,有利于其逃離局部最優(yōu)解.

在基本算法中,Pc、Pm固定不變. 對于交叉操作,若Pc較大,則適應(yīng)度高的個(gè)體被破壞的概率會(huì)變高;若Pc較小,則搜索的速度會(huì)變慢. 對于變異操作,若Pm較大,則隨機(jī)變異個(gè)體增多,不利于搜索;若Pm較小,則存在個(gè)體不變異的可能,算法的搜索能力降低. 因此,對Pc和Pm采取自適應(yīng)操作:

(7)

(8)

式中,i表示當(dāng)前進(jìn)化次數(shù);Mg表示最大進(jìn)化次數(shù). 為了避免算法陷入隨機(jī)搜索,對變異概率設(shè)置上限Pm_max.

2 實(shí)驗(yàn)結(jié)果與分析

將本文算法與基本遺傳算法和文獻(xiàn)[18]算法進(jìn)行仿真對比,使用MATLAB在20×20的地圖中實(shí)驗(yàn). 文獻(xiàn)[18]算法求解適應(yīng)度函數(shù)時(shí)加入平滑度函數(shù),一定程度上提高了收斂速度,但其中加入的懲罰項(xiàng)以長度為參考值,存在轉(zhuǎn)彎角度為銳角和鈍角時(shí)路線長度相同的問題,無法準(zhǔn)確對機(jī)器人路徑進(jìn)行懲罰,導(dǎo)致轉(zhuǎn)彎次數(shù)過多;未使交叉、變異概率自適應(yīng)調(diào)整,在復(fù)雜障礙物環(huán)境中存在無法搜索到最短路徑的問題.

本文算法的主要參數(shù)設(shè)定為:種群規(guī)模M=100;權(quán)重系數(shù)a=1,b=7;初始交叉概率Pc=0.9;初始變異概率Pm=0.01;最大進(jìn)化次數(shù)Mg=100;變異概率上限Pm_max=0.3. 圖3～圖8為仿真結(jié)果.

圖3 簡單地圖中基本遺傳算法路徑Fig.3 Basic genetic algorithm path in simple map

圖4 簡單地圖中文獻(xiàn)[18]遺傳算法路徑Fig.4 Genetic algorithm path of literature[18]in simple map

圖5 簡單地圖中本文遺傳算法路徑Fig.5 Genetic algorithm path of this paper in simple map

圖6 簡單地圖中基本遺傳算法的收斂曲線Fig.6 Convergence curve of basic genetic algorithmin simple map

圖7 簡單地圖中文獻(xiàn)[18]遺傳算法的收斂曲線Fig.7 Convergence curve of literature[18]in simple map

圖8 簡單地圖中本文遺傳算法的收斂曲線Fig.8 Convergence curve of this paper in simple map

由圖3～圖5可看出,3種算法均能找到最短路徑. 在基本遺傳算法和文獻(xiàn)[18]算法中,機(jī)器人分別進(jìn)行了13次和16次轉(zhuǎn)彎,能耗較大且不利于機(jī)器人的行駛;本文算法中機(jī)器人僅進(jìn)行了7次轉(zhuǎn)彎,大大減少了轉(zhuǎn)彎次數(shù),提升了機(jī)器人的安全性,降低了能耗.

由圖6～圖8可看出,3種算法分別經(jīng)過30次、14次、17次迭代收斂到了最短路徑,文獻(xiàn)[18]算法與本文算法收斂到最短路徑時(shí)的迭代次數(shù)相近.

為了避免偶然性,對3種算法分別進(jìn)行20次仿真實(shí)驗(yàn)進(jìn)行對比,如表1所示.

本地圖理論上的最優(yōu)路徑為29.8,基本算法有時(shí)無法找到最短路徑,文獻(xiàn)[18]算法和本文算法均能找到最短路徑. 從表1中可以看出,文獻(xiàn)[18]算法轉(zhuǎn)彎次數(shù)較多,但找到最短路徑的能力及平均迭代次數(shù)均優(yōu)于基本算法. 本文算法中機(jī)器人轉(zhuǎn)彎次數(shù)最少,且收斂速度較快,算法的優(yōu)越性得到了初步證明.

表1 簡單地圖中3種算法仿真實(shí)驗(yàn)對比Table 1 Comparison of simulation experiments of three algorithms in simple map

為進(jìn)一步驗(yàn)證本文算法的性能,在更復(fù)雜的障礙物柵格地圖中進(jìn)行仿真實(shí)驗(yàn). 仿真結(jié)果如圖9～圖14所示.

圖9 復(fù)雜地圖中基本遺傳算法路徑Fig.9 Basic genetic algorithm path in complex map

圖10 復(fù)雜地圖中文獻(xiàn)[18]遺傳算法路徑Fig.10 Genetic algorithm path of literature[18]in complex map

圖11 復(fù)雜地圖中本文遺傳算法路徑Fig.11 Genetic algorithm path of this paper in complex map

圖12 復(fù)雜地圖中基本遺傳算法的收斂曲線Fig.12 Convergence curve of basic genetic algorithmin complex map

圖13 復(fù)雜地圖中文獻(xiàn)[18]遺傳算法的收斂曲線Fig.13 Convergence curve of literature[18]in complex map

圖14 復(fù)雜地圖中本文遺傳算法的收斂曲線Fig.14 Convergence curve of this paper in complex map

從圖9～圖11可看出,當(dāng)障礙物地圖更為復(fù)雜時(shí),基本遺傳算法始終無法找到最短路徑且規(guī)劃出的路徑雜亂無章,故在本地圖中不再討論;文獻(xiàn)[18]算法未找到最短路徑,且轉(zhuǎn)彎次數(shù)較多;本文算法在復(fù)雜的地圖中轉(zhuǎn)彎次數(shù)依然較少.

本地圖中理論上的最優(yōu)路徑為31.56. 由圖12～圖14可以看出,基本遺傳算法在迭代至第60次時(shí)搜尋到的路徑長度為50.38;文獻(xiàn)[18]算法在迭代到第61次時(shí)路徑長度收斂于32.97;本文算法在迭代到第38次時(shí)收斂到的最短路徑長度為31.56,搜索到了最短路徑.

對3種算法分別進(jìn)行20次仿真實(shí)驗(yàn)進(jìn)行對比,如表2所示.

表2 復(fù)雜地圖中3種算法仿真實(shí)驗(yàn)對比Table 2 Comparison of simulation experiments of three algorithms in complex map

基本算法始終無法規(guī)劃出一條最短路徑,文獻(xiàn)[18]算法僅規(guī)劃出一次最短路徑,說明以上兩種算法不適用于復(fù)雜地圖中的路徑規(guī)劃;本文算法在復(fù)雜地圖中始終能夠準(zhǔn)確找到最短路徑,且轉(zhuǎn)彎次數(shù)較少,尋優(yōu)能力得到了進(jìn)一步證明.

從表1、表2可以看出,基本遺傳算法由于自身的局限性,其規(guī)劃效果次于改進(jìn)的算法;文獻(xiàn)[18]算法適用于障礙物較少的地圖環(huán)境;本文算法在簡單和復(fù)雜障礙物地圖中的尋優(yōu)能力、轉(zhuǎn)彎次數(shù)和平均迭代次數(shù)均優(yōu)于基本遺傳算法和文獻(xiàn)[18]算法,因而具有更優(yōu)的路徑規(guī)劃能力.

3 結(jié)論

本文提出了一種改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃算法,引入帶有懲罰機(jī)制的平滑度函數(shù),減少了機(jī)器人拐彎的次數(shù),使機(jī)器人能夠更平滑地行駛至目的地;引入精英保留策略,有利于算法尋找更優(yōu)解,提升算法的尋優(yōu)能力;提出自適應(yīng)交叉概率、變異概率,使算法的尋優(yōu)能力和收斂速度都得到了提升. 實(shí)驗(yàn)結(jié)果表明,本文算法在簡單及復(fù)雜環(huán)境下均能找到最優(yōu)路徑,且轉(zhuǎn)彎次數(shù)較少,具有較好的路徑規(guī)劃能力.