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

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

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

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

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

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

1.1 環(huán)境建模

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

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

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

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

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

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

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

(1)

式中,(xi,yi),(xi+1,yi+1)為兩個柵格對應的坐標. 當Δ=1時,表示兩柵格連續(xù),否則利用平均值法插入柵格,計算方法為:

(2)

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

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

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

Ffit=a×F1+b×F2,

(3)

式中,a、b為二者權重;F1為長度因子:

(4)

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

(5)

(6)

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

1.3 遺傳操作

1.3.1 選擇操作

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

1.3.2 交叉和變異操作

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

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

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

(7)

(8)

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

2 實驗結果與分析

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

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

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

圖4 簡單地圖中文獻[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 簡單地圖中文獻[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種算法均能找到最短路徑. 在基本遺傳算法和文獻[18]算法中,機器人分別進行了13次和16次轉彎,能耗較大且不利于機器人的行駛;本文算法中機器人僅進行了7次轉彎,大大減少了轉彎次數(shù),提升了機器人的安全性,降低了能耗.

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

為了避免偶然性,對3種算法分別進行20次仿真實驗進行對比,如表1所示.

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

表1 簡單地圖中3種算法仿真實驗對比Table 1 Comparison of simulation experiments of three algorithms in simple map

為進一步驗證本文算法的性能,在更復雜的障礙物柵格地圖中進行仿真實驗. 仿真結果如圖9～圖14所示.

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

圖10 復雜地圖中文獻[18]遺傳算法路徑Fig.10 Genetic algorithm path of literature[18]in complex map

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

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

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

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

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

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

對3種算法分別進行20次仿真實驗進行對比,如表2所示.

表2 復雜地圖中3種算法仿真實驗對比Table 2 Comparison of simulation experiments of three algorithms in complex map

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

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

3 結論

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