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

徐 興，俞旭陽(yáng)，趙 蕓，劉成星，吳 祥

(1.浙江科技學(xué)院 機(jī)械與能源工程學(xué)院，浙江 杭州 310023； 2.浙江科技學(xué)院 信息與電子工程學(xué)院，浙江 杭州 310023)

0 引言

隨著智能制造與電商經(jīng)濟(jì)的迅猛發(fā)展，適應(yīng)性強(qiáng)、靈活性高和智能性好的倉(cāng)儲(chǔ)移動(dòng)機(jī)器人需求呈井噴式增長(zhǎng)，尤其在各類生產(chǎn)線及倉(cāng)儲(chǔ)物流中被大量運(yùn)用，其中路徑規(guī)劃問(wèn)題[1-3]一直是移動(dòng)機(jī)器人領(lǐng)域的核心研究?jī)?nèi)容，其首要任務(wù)便是根據(jù)特定條件和環(huán)境規(guī)劃出可供移動(dòng)機(jī)器人高效穩(wěn)定行走的無(wú)障礙路徑，但移動(dòng)機(jī)器人的路徑規(guī)劃屬于NP(nonlinear programming)難題，只能根據(jù)問(wèn)題尋求有效的近似算法而非精確算法。路徑規(guī)劃算法主要分為基于傳統(tǒng)和基于群集智能策略兩大類，傳統(tǒng)全局路徑規(guī)劃算法包括人工勢(shì)場(chǎng)算法[4]、Dijkstra算法[5]、A*算法[6]等，群集智能全局規(guī)劃算法包括遺傳算法[7]、蟻群算法[8-9]和粒子群優(yōu)化算法等[10]。

已有大量學(xué)者開(kāi)展了路徑規(guī)劃研究，劉二輝等[11]提出一種基于相連路徑片段組成三角形使路徑縮短的啟發(fā)式變異規(guī)則，提高了路徑的平滑度，改善了算法局部尋優(yōu)能力；魏彤等[12]提出一種基于改進(jìn)遺傳算法的幀間關(guān)聯(lián)平穩(wěn)路徑規(guī)劃方法，提高了移動(dòng)機(jī)器人的行駛效率和平穩(wěn)性；馬小陸等[13]提出一種基于勢(shì)場(chǎng)跳點(diǎn)的蟻群算法，算法引入勢(shì)場(chǎng)合力遞減系數(shù)，減少了勢(shì)場(chǎng)蟻群陷入局部最優(yōu)的問(wèn)題，提高了規(guī)劃路徑的平滑度；TUNCER等[14]針對(duì)移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題提出一種新的遺傳算法變異算子，用以避免算法早熟收斂，提高了遺傳算法的收斂速度；劉子豪等[15]提出一種基于跳躍點(diǎn)搜索的改進(jìn)A*算法，從而減小了計(jì)算量，提高了運(yùn)算速度；AHMED等[16]提出一種多目標(biāo)車輛路徑規(guī)劃方法，該方法利用精英非支配排序遺傳算法對(duì)路徑長(zhǎng)度、路徑安全性和路徑平滑度進(jìn)行優(yōu)化，在解決復(fù)雜路徑規(guī)劃問(wèn)題時(shí)具有魯棒性和高效性；徐力等[17]針對(duì)現(xiàn)有遺傳算法易陷入早熟、收斂速度慢等問(wèn)題，提出一種基于自適應(yīng)遺傳算法的機(jī)器人路徑規(guī)劃方法，雖然能較好地避免陷入局部最優(yōu)，但是仍需要較大的初始種群，降低了算法的計(jì)算效率。

上述諸多路徑規(guī)劃研究中，文獻(xiàn)[12]未能很好解決算法應(yīng)用時(shí)易早熟、效率低的問(wèn)題；文獻(xiàn)[14]雖然改進(jìn)了算法效率，但是應(yīng)用時(shí)仍然存在較大的局限性，且路徑平滑度不高；文獻(xiàn)[17]雖然針對(duì)算法的早熟問(wèn)題提出相應(yīng)的措施，但是仍然存在收斂迭代過(guò)慢、效率低的問(wèn)題。綜合考慮常規(guī)路徑規(guī)劃算法規(guī)劃路徑非最短、平滑度較差、效率低和極易早熟等問(wèn)題，本文提出一種基于災(zāi)變策略的改進(jìn)遺傳算法(Improved Catastrophe Genetic Algorithm, ICGA)，算法有如下改進(jìn)：①改進(jìn)初始種群生成方法，大幅提高了算法前期的計(jì)算效率；②改進(jìn)災(zāi)變算子極好地避免了算法早熟；③加入篩選步驟的交叉算子提高操作效率；④重新設(shè)計(jì)動(dòng)態(tài)變異算子提高后期的局部搜索能力；⑤在適應(yīng)度函數(shù)中加入路徑轉(zhuǎn)角、轉(zhuǎn)彎次數(shù)權(quán)值等多約束條件，提高路徑的平滑度。仿真結(jié)果證明，相比遺傳算法(Genetic Algorithm, GA)、改進(jìn)的自適應(yīng)遺傳算法(Improved Adaptive Genetic Algorithm, IAGA)和啟發(fā)式通信異構(gòu)雙種群蟻群優(yōu)化算法(Heuristic communication Heterogeneous dual population Ant Colony Optimization algorithm, HHACO)，在多次規(guī)劃時(shí)ICGA能更好地避免出現(xiàn)早熟，減少算法的尋路時(shí)間，保證較高的路徑質(zhì)量。最后將算法移植到機(jī)器人操作系統(tǒng)(Robot Operating System, ROS)平臺(tái)中，經(jīng)WHEELTEC小車導(dǎo)航試驗(yàn)證明，ICGA比IAGA規(guī)劃的路徑更優(yōu)，效率和穩(wěn)定性更高。

1 工作場(chǎng)景建模和路徑規(guī)劃模型

1.1 移動(dòng)機(jī)器人工作場(chǎng)景建模

為給移動(dòng)機(jī)器人導(dǎo)航提供可靠的環(huán)境信息，采用柵格地圖對(duì)現(xiàn)實(shí)場(chǎng)景進(jìn)行建模，如圖1所示。對(duì)場(chǎng)景進(jìn)行單元化分割，地圖中黑色柵格表示障礙物。采用矩陣G存儲(chǔ)地圖信息，其中1和0元素對(duì)應(yīng)柵格地圖中的障礙柵格和可行柵格。

柵格地圖和矩陣G的對(duì)應(yīng)關(guān)系為

Map(x,y)=G(x,y)。

(1)

1.2 路徑規(guī)劃模型

采用實(shí)數(shù)編碼的方式，由下往上、從左到右的順序逐列編號(hào)，索引函數(shù)(xndx,yndx)=in2sub(siz,ndx)中柵格編號(hào)和坐標(biāo)的關(guān)系如下：

k=cumprod(siz)；

(2)

yndx=rem[(ndx-1)/k]+1；

(3)

xndx=(ndx-yndx)/k+1。

(4)

式中：ndx為編碼號(hào)；siz為地圖矩陣的行列數(shù)向量；(xndx,yndx)為編號(hào)ndx在地圖中的坐標(biāo)；rem()為整除取余函數(shù)；cumprod()為求連乘積函數(shù)。

逐列對(duì)柵格地圖編號(hào)后，路徑可用染色體基因表示，如圖1中路徑所示，無(wú)障礙路徑可以表示為Pi=[startndx1ndx2ndx3…ndx8ndx9… end]。

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

2.1 問(wèn)題描述及適應(yīng)度函數(shù)設(shè)計(jì)

考慮移動(dòng)機(jī)器人的作業(yè)效率與穩(wěn)定性，要求機(jī)器人在作業(yè)時(shí)移動(dòng)距離最短、轉(zhuǎn)向角度最小且非必要轉(zhuǎn)向次數(shù)最少，因此需對(duì)算法提出路徑長(zhǎng)度、路徑轉(zhuǎn)角和轉(zhuǎn)向次數(shù)的多目標(biāo)優(yōu)化要求，則上述問(wèn)題可描述如下：

s.t.

p∈C;

C∈G。

(5)

式中：F為向量目標(biāo)函數(shù)；p為滿足條件的路徑；C為路徑集合；G為地圖矩陣。

根據(jù)式(5)中的問(wèn)題描述設(shè)計(jì)多約束適應(yīng)度函數(shù)

(6)

(7)

(8)

(9)

式中：fit1為路徑長(zhǎng)度；fit2為路徑角度；Tnum為路徑中的轉(zhuǎn)向次數(shù)；ω1，ω2，ω3為權(quán)值系數(shù)；PRECI為節(jié)點(diǎn)數(shù)，(xi,yi)為節(jié)點(diǎn)坐標(biāo)；Γ()為條件函數(shù)，θ為路徑中的轉(zhuǎn)向角度，若θ≠0°，則Γ(θ)=1。

2.2 改進(jìn)種群初始化方法

初始種群的特性對(duì)算法效率有重要影響，傳統(tǒng)GA常用一種隨機(jī)搜索可行路徑的方法[18]，該方法產(chǎn)生可行路徑的速度較快，但初始路徑質(zhì)量較差，篩選法則效率低下，因此本文提出一種基于分段A*算法的區(qū)域必經(jīng)點(diǎn)選擇策略生成初始種群的方法，步驟如圖2所示。

具體步驟如下，：

步驟1設(shè)置起點(diǎn)、終點(diǎn)與基準(zhǔn)線。根據(jù)Dmax確定選擇路徑必經(jīng)點(diǎn)的區(qū)域。

步驟2根據(jù)縱向隨機(jī)范圍D和橫向隨機(jī)范圍S確定區(qū)域，并選擇分布在基準(zhǔn)線兩側(cè)的必經(jīng)點(diǎn)。

步驟3使用A*最短路徑算法聯(lián)接路徑必經(jīng)點(diǎn)：

Si=randi(|xSp-xEp|/Nm)；

(10)

Di=±randi(Dmax)。

(11)

式中：Si為必經(jīng)點(diǎn)的橫坐標(biāo)；randi()為隨機(jī)函數(shù)；xSp，xEp分別為路徑起點(diǎn)和終點(diǎn)的橫坐標(biāo)；Nm為必經(jīng)點(diǎn)的個(gè)數(shù)；Di為必經(jīng)點(diǎn)的縱坐標(biāo)；Dmax為最大區(qū)域閾值；下標(biāo)i為必經(jīng)點(diǎn)的索引值，i=1，2，3，…，N。

種群個(gè)體多樣性減少是導(dǎo)致早熟的原因之一，為此引入路徑海明距離作為種群個(gè)體相似度評(píng)價(jià)的標(biāo)準(zhǔn)，其中路徑對(duì)應(yīng)點(diǎn)用式(12)選取，從兩條路徑中找到距離最近的一對(duì)點(diǎn)，若兩點(diǎn)間的距離滿足ε=0，則判定為對(duì)應(yīng)點(diǎn)對(duì)，路徑相似度則為對(duì)應(yīng)節(jié)點(diǎn)數(shù)在總路徑節(jié)點(diǎn)中的占比；然后設(shè)計(jì)一種以種群個(gè)體間平均相似度為標(biāo)準(zhǔn)的種群評(píng)價(jià)函數(shù)，如式(13)～式(15)所示。

(12)

式中：Cor()為滿足距離條件的相似點(diǎn)對(duì)計(jì)數(shù)函數(shù)；Г()為屬于不同路徑中兩節(jié)點(diǎn)間的距離判別函數(shù)，若節(jié)點(diǎn)P1(i)與P2(j)間的歐式距離為ε，則Г(P1(i)，P2(j))=1，反之為0。

(13)

(14)

(15)

表1所示為3種方法在4類地圖中所生成路徑參數(shù)的對(duì)比，包括平均適應(yīng)度、相似度和消耗時(shí)間。比較消耗時(shí)間可見(jiàn)，小規(guī)模地圖中隨機(jī)法具有優(yōu)勢(shì)，隨著地圖規(guī)模的增加，區(qū)域法的優(yōu)勢(shì)逐漸凸顯；比較相似度可見(jiàn)，隨機(jī)法與加入篩選步驟的隨機(jī)法各具優(yōu)勢(shì)；比較適應(yīng)度參數(shù)可見(jiàn)區(qū)域法最優(yōu)。綜上可知，區(qū)域法能大幅提高適應(yīng)度值，降低消耗時(shí)間，提高算法前期的收斂速度。

表1 生成方法對(duì)比

2.3 改進(jìn)遺傳算子

(1)改進(jìn)選擇算子 常規(guī)GA中常采用輪盤賭選擇方法，但因?yàn)榉N群規(guī)模限制和隨機(jī)操作等，單獨(dú)使用輪盤賭方法誤差較大，易丟失優(yōu)秀個(gè)體，所以采用隨機(jī)遍歷抽樣法配合基于優(yōu)勝劣汰的精英替代算子。其中個(gè)體選擇概率

(16)

式中：NIND為個(gè)體數(shù)；eval()為個(gè)體Uk的適應(yīng)度值計(jì)算函數(shù)。

因?yàn)殡S機(jī)遍歷采樣法中需要等距離地選擇個(gè)體，所以將npoint設(shè)為需要選擇的個(gè)體數(shù)，等距離地選擇個(gè)體每個(gè)選擇指針的距離1/npoint，選擇的起始位置由[0,1/npoint]之間的均勻隨機(jī)數(shù)決定，如圖3所示。

隨機(jī)遍歷抽樣算子選取個(gè)體后，精英替代算子根據(jù)子代的適應(yīng)度值替換父代種群中較差的個(gè)體，完成優(yōu)勝劣汰操作，保證父代種群中優(yōu)秀的個(gè)體不會(huì)因選擇誤差而被淘汰。

(2)改進(jìn)交叉算子 采用單點(diǎn)交叉的方式，交叉點(diǎn)選擇兩條路徑的對(duì)應(yīng)點(diǎn)。由于選擇算子的特性，隨著算法迭代種群逐步被高適應(yīng)度個(gè)體占據(jù)，種群中將存在大量相同的個(gè)體，而相同個(gè)體間的交叉是無(wú)效的；為防止相似度為100%的兩個(gè)個(gè)體交叉，設(shè)計(jì)了一種快速判別是否交叉的方法，而且為了消除計(jì)算相似度帶來(lái)的高時(shí)間復(fù)雜度，本文采用路徑長(zhǎng)度和柵格號(hào)的累加值作為判斷依據(jù)進(jìn)行快速篩選，如式(17)所示。若E()=1則放棄當(dāng)前次的交叉操作，避免無(wú)效交叉，節(jié)約計(jì)算資源和時(shí)間。為加大交叉算子的搜索能力與路徑可行性，若不存在相同的柵格節(jié)點(diǎn)，則隨機(jī)選取兩條路徑的不同位置進(jìn)行交叉；若交叉后路徑可行，則用插入算子填補(bǔ)交叉點(diǎn)處的空白柵格，若路徑不可行，則放棄此次交叉。

i≠j。

(17)

式中：E()為相似度評(píng)價(jià)函數(shù)；α1=1.5，α2=0.1均為權(quán)值系數(shù)；Pi，Pj分別為某兩個(gè)路徑個(gè)體；Pi(q)，Pj(r)分別為路徑個(gè)體中的某兩個(gè)柵格號(hào)；PRECIi，PRECIj分別為兩個(gè)路徑個(gè)體的柵格數(shù)。

(3)改進(jìn)變異算子 常規(guī)變異方式是在染色體隨機(jī)位置上替換基因完成變異操作，例如文獻(xiàn)[12]的變異算子采用替換該位置八鄰域基因的方法和刪除該染色體任意位置基因的方法。雖然上述方法有較大的變異成功率和路徑可行性，但是仍然存在局部搜索能力不足的問(wèn)題，因此本文提出一種內(nèi)嵌A*算法的動(dòng)態(tài)變異方法，步驟如下：

步驟1用Pm控制當(dāng)前個(gè)體是否變異，若隨機(jī)數(shù)r

步驟2動(dòng)態(tài)選擇染色體中變異路段的長(zhǎng)度，隨機(jī)選擇路徑中的兩個(gè)柵格，柵格間的距離由種群進(jìn)化程度決定。進(jìn)化初期選取的變異路徑段長(zhǎng)度應(yīng)盡量短，后期為幫助算法跳出局部最優(yōu)，則應(yīng)加大該路徑段的長(zhǎng)度。

步驟3采用A*算法再規(guī)劃路徑替換兩個(gè)柵格間的局部路徑。

(4)插入算子 為保證路徑中每個(gè)柵格節(jié)點(diǎn)間的連續(xù)性，引入一種路徑間斷連續(xù)方法[18]，步驟如下：

步驟1按式(18)判斷路徑中每?jī)蓚€(gè)相鄰柵格節(jié)點(diǎn)間是否連續(xù)。

L=max{abs(xi+1-xi)，abs(yi+1-yi)}。

(18)

式中：x，y為柵格節(jié)點(diǎn)的橫縱坐標(biāo)；上標(biāo)i，i+1為路徑中該節(jié)點(diǎn)的次序；abs()為絕對(duì)值函數(shù)；max()為最大值函數(shù)。

步驟2若L≠1則兩柵格間斷，按式(19)獲得這兩個(gè)柵格的中點(diǎn)柵格，若中點(diǎn)柵格為障礙柵格，則取該柵格周圍八鄰域中的任意柵格。

(19)

式中：上標(biāo)mid表示待插入的中間柵格；int()為取整函數(shù)。

步驟3將中點(diǎn)柵格插入兩間斷柵格中間，為防止算法陷入死循環(huán)，判斷中點(diǎn)柵格是否已在路徑中，是則重新選擇，返回步驟1檢查路徑是否存在間斷，若路徑處處連續(xù)則跳出循環(huán)。

2.4 自適應(yīng)策略

交叉變異概率是影響算法行為和性能的關(guān)鍵，合理的交叉、變異概率能顯著提升算法性能，因此本文引入一種自適應(yīng)調(diào)整交叉變異概率的方法[19]，在進(jìn)行交叉變異操作前自適應(yīng)調(diào)整概率。交叉概率Pc和變異概率Pm分別為：

(20)

(21)

式中：k1，k2分別為交叉、變異概率縮放系數(shù)，k1，k2∈[0.5，1]；Pc1=1，Pc2∈[0.5，1]；Pm1=0.1，Pm2∈[0.05，0.1]；Fm為待變異個(gè)體的適應(yīng)度值，F(xiàn)avg為種群中個(gè)體的平均適應(yīng)度值，F(xiàn)max為種群中個(gè)體的最大適應(yīng)度值，F(xiàn)c為兩個(gè)待交叉?zhèn)€體中較大的適應(yīng)度值。

2.5 災(zāi)變策略

GA在實(shí)際應(yīng)用中極易發(fā)生未成熟收斂(又稱早熟)，由于進(jìn)化后期種群中的個(gè)體趨于一致，經(jīng)遺傳操作已無(wú)法產(chǎn)生更優(yōu)個(gè)體，種群陷入進(jìn)化停滯狀態(tài)。為此，本文改進(jìn)了一種災(zāi)變策略，幫助算法跳出停滯而搜索到最優(yōu)解。

根據(jù)災(zāi)變論的觀點(diǎn)，每當(dāng)發(fā)生毀滅性的自然災(zāi)害時(shí)，大部分生物被滅絕，災(zāi)變結(jié)束后造物主結(jié)合原有物種創(chuàng)造出稍有不同且更富競(jìng)爭(zhēng)力的新物種，該過(guò)程大大提高了進(jìn)化進(jìn)程，而將這一策略加入GA能極大幫助算法避免早熟，保持其應(yīng)有的性能。災(zāi)變策略實(shí)施流程如下：種群經(jīng)過(guò)n代進(jìn)化后無(wú)法產(chǎn)生更優(yōu)個(gè)體時(shí)，執(zhí)行災(zāi)變操作，將災(zāi)變判定計(jì)數(shù)值作為災(zāi)變操作執(zhí)行的條件，若在一次遺傳操作后當(dāng)前種群沒(méi)有產(chǎn)生更優(yōu)個(gè)體，則計(jì)數(shù)器減1，否則計(jì)數(shù)器重置初值；若計(jì)數(shù)器值歸零，則表示局部搜索已充分滿足災(zāi)變條件；設(shè)置災(zāi)變上限次數(shù)，若在執(zhí)行N次災(zāi)變操作后，局部最優(yōu)個(gè)體仍未發(fā)生變化，則認(rèn)為全局搜索已充分，當(dāng)前局部最優(yōu)個(gè)體即為全局最優(yōu)個(gè)體，算法結(jié)束。

災(zāi)變策略的步驟具體如下：

(2)種群在數(shù)次遺傳操作后，災(zāi)變計(jì)數(shù)器歸零，滿足災(zāi)變判定條件，執(zhí)行災(zāi)變預(yù)操作，有兩種情況：

流程如圖4所示。

綜上所述，改進(jìn)GA的流程圖如圖5所示。

(1)按方法1產(chǎn)生初期種群。

(2)設(shè)定災(zāi)變計(jì)數(shù)器(即種群進(jìn)化停滯計(jì)數(shù))和災(zāi)變次數(shù)閾值Y。

(3)判定災(zāi)變，若種群產(chǎn)生新個(gè)體則災(zāi)變計(jì)數(shù)器重置，否則減1；若計(jì)數(shù)器為零且災(zāi)變次數(shù)未達(dá)上限，則執(zhí)行災(zāi)變，否則轉(zhuǎn)(4)。

(4)執(zhí)行遺傳操作。

(5)將子代種群個(gè)體逐一與父代種群個(gè)體比較，替換父代種群中競(jìng)爭(zhēng)力較差的個(gè)體。

(6)循環(huán)執(zhí)行(3)～(5)，直至找到全局最優(yōu)個(gè)體。

(7)輸出最優(yōu)路徑，算法結(jié)束。

3 試驗(yàn)及結(jié)果分析

3.1 MATLAB仿真試驗(yàn)

為驗(yàn)證ICGA的有效性，采用MATLAB 2016a平臺(tái)進(jìn)行編程仿真，分別對(duì)GA[18]，IAGA[20]，HHACO[21]，ICGA進(jìn)行仿真，在不同規(guī)模的柵格地圖(其中20×20，30×30分別引用自文獻(xiàn)[17]和文獻(xiàn)[13]，10×10，40×40為隨機(jī)障礙地圖)中分別進(jìn)行60次路徑規(guī)劃比較，算法參數(shù)如表2所示。

表2 算法參數(shù)設(shè)置

設(shè)置柵格邊長(zhǎng)為1 m，起點(diǎn)、終點(diǎn)分別為左下點(diǎn)和右上點(diǎn)。圖6～圖9所示為4種算法在20×20柵格地圖中的路徑規(guī)劃結(jié)果，圖10～圖12所示為4種算法的路徑長(zhǎng)度、角度和適應(yīng)度變化曲線，圖13～圖16所示為4種算法在40×40柵格地圖中的路徑規(guī)劃結(jié)果，圖17～圖19所示為4種算法的路徑長(zhǎng)度、角度和適應(yīng)度變化曲線。

由圖10～圖12和圖17～圖19所示的算法性能變化曲線可見(jiàn)，GA，HHACO，IAGA規(guī)劃的路徑存在冗余，其中GA路徑長(zhǎng)度過(guò)長(zhǎng)，HHACO，IAGA包含過(guò)多的非必要轉(zhuǎn)向次數(shù)，而ICGA則能在路徑最短的前提下減少非必要轉(zhuǎn)向次數(shù)，提高路徑平滑度。

表3和表4所示為不同地圖中60次路徑規(guī)劃的比較和統(tǒng)計(jì)結(jié)果，綜合分析可知，在不同規(guī)模地圖的多次路徑規(guī)劃試驗(yàn)中，HHACO收斂速度最快，但早熟概率最高，極易導(dǎo)致路徑質(zhì)量嚴(yán)重下降；GA收斂速度最慢，且路徑平滑度較差；IAGA的收斂速度和平滑度有所改善，但仍然容易早熟；ICGA則能在搜索到最短路徑的同時(shí)大幅減少非必要轉(zhuǎn)向次數(shù)，不但能提高路徑平滑度，縮短尋路時(shí)間，而且在多次規(guī)劃時(shí)能有效降低算法出現(xiàn)早熟的概率。

表3 不同規(guī)模地圖中的仿真組統(tǒng)計(jì)1

表4 不同規(guī)模地圖中的仿真組統(tǒng)計(jì)2

為了證明算法的有效性，排除偶然因素和抽樣誤差，本文引入小概率原理并進(jìn)行顯著性檢驗(yàn)，若Sig≤0.01，則表明兩者存在極其顯著的差異。表5所示為兩種算法(ICGA和IAGA)在40×40地圖中的60次獨(dú)立樣本檢驗(yàn)，其中評(píng)價(jià)性能各項(xiàng)值的Sig均小于0.01，說(shuō)明兩種算法的規(guī)劃路徑樣本存在明顯差異，因此本文所提ICGA是有效的。

表5 40×40地圖中的算法(ICGA和IAGA)獨(dú)立樣本檢驗(yàn)

續(xù)表5

圖21所示為小車的硬件結(jié)構(gòu)，圖22所示為雷達(dá)測(cè)距原理圖。激光雷達(dá)掃描后獲得障礙物的點(diǎn)云數(shù)據(jù)，將其與STM32控制板的編碼器信息反饋給ROS主控制器，主控制器計(jì)算速度信息并返回至STM32控制板，由STM32控制板控制WHEELTEC四輪小車實(shí)現(xiàn)自主導(dǎo)航。

3.2 ROS平臺(tái)試驗(yàn)

為驗(yàn)證本文算法，將ICGA與對(duì)比算法移植到基于Ubuntu 18.04的ROSmelodic機(jī)器人操作平臺(tái)中，試驗(yàn)所采用的機(jī)器人為WHEELTEC四輪小車，該機(jī)器人搭載Jetson TX2主控和STM32底盤控制板，如圖20所示。

圖23所示為ROS平臺(tái)整體框架原理圖，其中move_base包為ROS導(dǎo)航提供各類接口，主要包括全局路徑規(guī)劃(global planner)和本地實(shí)時(shí)規(guī)劃(local planner)。本次試驗(yàn)只需根據(jù)給定的目標(biāo)位置規(guī)劃總體路徑，因此只用nav_core包中nav_core::BaseGlobalPlanner的預(yù)留接口為規(guī)劃器編寫一個(gè)新類，新規(guī)劃器包括路徑規(guī)劃所需的核心庫(kù)，并將ICGA路徑規(guī)劃算法添加為一個(gè)新的全局路徑規(guī)劃器，使move_base能夠調(diào)用本文算法的全局路徑規(guī)劃器。

選取實(shí)驗(yàn)室作為試驗(yàn)場(chǎng)景，如圖24所示。利用gmapping建圖和amcl自定位模塊完成試驗(yàn)環(huán)境的二維建圖，用Rviz作為查看導(dǎo)航路徑的可視化工具，并設(shè)置兩次導(dǎo)航任務(wù)PLAN 1和PLAN 2，結(jié)果如圖25～圖28所示?？梢?jiàn)，在短距離導(dǎo)航任務(wù)1和長(zhǎng)距離導(dǎo)航任務(wù)2中，IAGA規(guī)劃路徑都出現(xiàn)了≥90°的轉(zhuǎn)角和大量的非必要轉(zhuǎn)向，其中大轉(zhuǎn)角在移動(dòng)機(jī)器人導(dǎo)航中最致命，其增加了機(jī)器人的碰撞概率，降低了機(jī)器人作業(yè)的穩(wěn)定性和效率。通過(guò)分析表6和表7所示的規(guī)劃結(jié)果可知ICGA規(guī)劃的路徑更優(yōu)。該路徑不但更短，而且大幅減少了大轉(zhuǎn)角和非必要轉(zhuǎn)向次數(shù)，大大增加了移動(dòng)機(jī)器人的行走穩(wěn)定性、效率以及驅(qū)動(dòng)電機(jī)的使用壽命。

表6 PLAN 1兩種算法路徑規(guī)劃結(jié)果對(duì)比

表7 PLAN 2兩種算法路徑規(guī)劃結(jié)果對(duì)比

4 結(jié)束語(yǔ)

本文針對(duì)GA在路徑規(guī)劃應(yīng)用時(shí)極易出現(xiàn)早熟、效率低、路徑平滑度差等問(wèn)題：①在IAGA的基礎(chǔ)上，加入并改進(jìn)了條件災(zāi)變策略，幫助算法跳出局部最優(yōu)，同時(shí)增加個(gè)體多樣性并減小種群規(guī)模來(lái)提高算法效率；②利用重新設(shè)計(jì)的區(qū)域必經(jīng)點(diǎn)選擇策略提高初始種群的質(zhì)量，來(lái)提升算法初期的收斂速度；③采用帶有篩選步驟的改進(jìn)交叉算子避免相同個(gè)體間的無(wú)效交叉，節(jié)省計(jì)算資源；④通過(guò)改進(jìn)內(nèi)嵌A*算法的動(dòng)態(tài)變異算子加大算法后期的局部搜索能力，并采用改進(jìn)的多約束條件適應(yīng)度函數(shù)大幅提高路徑平滑度。通過(guò)不同規(guī)模地圖的仿真試驗(yàn)證明，ICGA的路徑搜索速度、早熟概率和路徑質(zhì)量均優(yōu)于常規(guī)算法，經(jīng)ROS平臺(tái)導(dǎo)航試驗(yàn)證明，ICGA規(guī)劃器規(guī)劃的路徑較常規(guī)路徑規(guī)劃器更優(yōu)、效率更高。