未知環(huán)境下改進(jìn)變步長(zhǎng)蟻群算法的機(jī)器人路徑規(guī)劃*

徐玉瓊，婁 柯，李志錕

(1.廣州大學(xué)松田學(xué)院 電氣與汽車工程學(xué)院，廣東 廣州 511370；2.高端裝備先進(jìn)感知與智能控制教育部重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖 241000；3.安徽工程大學(xué) 安徽省電氣傳動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖 241000)

0 引 言

路徑規(guī)劃技術(shù)[1～3]是移動(dòng)機(jī)器人研究領(lǐng)域的核心技術(shù)之一，它是指移動(dòng)機(jī)器人在有障礙物的環(huán)境中，從起點(diǎn)運(yùn)動(dòng)到終點(diǎn)搜索出一條最優(yōu)的安全路徑。為了解決移動(dòng)機(jī)器人路徑規(guī)劃問題，國(guó)內(nèi)外學(xué)者提出諸多算法，如遺傳算法(GA)、A*算法[4,5]、蟻群算法(AG)[6～10]、狼群算法[11]等。隨著群智能算法的不斷創(chuàng)新，傳統(tǒng)蟻群算法在路徑規(guī)劃技術(shù)方面成果顯著。然而，傳統(tǒng)蟻群算法存在魯棒性不強(qiáng)、死鎖、搜索停滯等問題急需被解決。針對(duì)傳統(tǒng)蟻群算法相關(guān)缺陷，大量國(guó)內(nèi)外學(xué)者深入研究，提出諸多改進(jìn)蟻群算法。文獻(xiàn)[12]利用人工勢(shì)場(chǎng)法[13]的優(yōu)勢(shì)，與蟻群算法進(jìn)行結(jié)合，加快了算法的收斂速度，但其適應(yīng)不了復(fù)雜環(huán)境。文獻(xiàn)[14]為了解決蟻群算法容易陷入局部最優(yōu)、收斂速度與尋優(yōu)能力不平衡等問題，提出了自適應(yīng)蟻群算法，針對(duì)信息素的分配重新制定策略，設(shè)置迭代閾值，使得算法在尋優(yōu)后期也具有一定的搜索能力；但該算法轉(zhuǎn)折點(diǎn)較多，降低算法搜索效率。文獻(xiàn)[15]利用雙向搜索機(jī)制以及對(duì)啟發(fā)函數(shù)設(shè)置比例系數(shù)引導(dǎo)因子進(jìn)行改進(jìn)，有效改善了移動(dòng)機(jī)器人目標(biāo)性不強(qiáng)，向目標(biāo)相反方向移動(dòng)的問題，但算法路徑冗長(zhǎng)，尋優(yōu)能力較低。相關(guān)改進(jìn)蟻群算法相對(duì)于其他群智能算法能搜索出較優(yōu)路徑，但依然耗時(shí)較長(zhǎng)、收斂較慢，很難搜索出最優(yōu)路徑。

針對(duì)以上問題，本文對(duì)蟻群算法作出相應(yīng)改進(jìn)，提出了改進(jìn)變步長(zhǎng)蟻群算法應(yīng)用于移動(dòng)機(jī)器人的路徑規(guī)劃。

1 環(huán)境建模

本文設(shè)定移動(dòng)機(jī)器人在二維柵格環(huán)境下進(jìn)行路徑規(guī)劃。障礙物的高度忽略不計(jì)，所有柵格尺寸均為1 m×1 m的正方形，空白柵格為自由柵格，在仿真程序中用0表示，黑色柵格為障礙物柵格，在仿真程序中用1表示。如圖1所示，該柵格地圖環(huán)境為20 m×20 m的正方形，由若干個(gè)障礙物組成，起點(diǎn)坐標(biāo)為(0.5,19.5),終點(diǎn)坐標(biāo)為(19.5,0.5)，移動(dòng)機(jī)器人需要從起點(diǎn)到終點(diǎn)規(guī)劃處一條最優(yōu)路徑。

圖1 柵格地圖

2 改進(jìn)變步長(zhǎng)蟻群算法

2.1 改進(jìn)平滑度機(jī)制

本文引入平滑度函數(shù)，對(duì)多次轉(zhuǎn)角的位置平滑處理，縮短移動(dòng)機(jī)器人路徑長(zhǎng)度，減少移動(dòng)機(jī)器人路徑規(guī)劃過程中產(chǎn)生的轉(zhuǎn)折次數(shù)。改進(jìn)后的路徑選擇概率公式如下

(1)

(2)

(3)

(4)

式中γij(t)為移動(dòng)機(jī)器人從位置i到位置j的轉(zhuǎn)折啟發(fā)函數(shù)；σ為轉(zhuǎn)折啟發(fā)因子，取值為正整數(shù)；θ為當(dāng)前位置i到位置j的連線與起點(diǎn)到終點(diǎn)的連線之間的夾角，夾角越小，則線路的節(jié)點(diǎn)被選擇的概率就越大，移動(dòng)機(jī)器人規(guī)劃出來(lái)的路徑越逼近于最優(yōu)路徑；α表征信息素重要程度；β表征啟發(fā)函數(shù)重要程度；τij表征路徑(i,j)上的信息素濃度；allowed為移動(dòng)機(jī)器人所有可能到達(dá)節(jié)點(diǎn)的集合；ηij為啟發(fā)函數(shù)；f(θ)為平滑度引導(dǎo)函數(shù)；h為引導(dǎo)因子，引導(dǎo)節(jié)點(diǎn)向最優(yōu)路徑靠近，提高移動(dòng)機(jī)器人搜索效率；(ix,iy)及(jx,jy)分別為當(dāng)前節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)的坐標(biāo)。

加入平滑機(jī)制的路徑規(guī)劃效果如圖2所示，路線{1,2,3,4,5}為傳統(tǒng)蟻群算法路徑規(guī)劃圖，路線{1,3,4,5}為加入平滑機(jī)制后的路徑規(guī)劃圖，不難看出，后者轉(zhuǎn)折點(diǎn)更少，路徑長(zhǎng)度也更短。因此，加入平滑機(jī)制后的蟻群算法可以顯著提高路徑規(guī)劃質(zhì)量，有效減少移動(dòng)機(jī)器人轉(zhuǎn)折次數(shù)以及縮短路徑長(zhǎng)度。

圖2 平滑機(jī)制路徑規(guī)劃

2.2 改進(jìn)蟻群系統(tǒng)

為了避免蟻群算法過早收斂于非最優(yōu)解，蟻群系統(tǒng)對(duì)每條路徑上的信息素設(shè)定閾值。當(dāng)某條路徑信息素濃度超過最大值時(shí)，則該條路徑信息素濃度強(qiáng)制設(shè)置為τmax；當(dāng)某條路徑信息素濃度低于最小值時(shí)，則該條路徑信息素濃度強(qiáng)制設(shè)置為τmin。移動(dòng)機(jī)器人每次迭代后，對(duì)每條路徑上的信息素作全局更新，公式如下

(5)

(6)

以上可以避免部分路徑上的信息素濃度過高或者過低，避免產(chǎn)生部分螞蟻過分集中在一條非最優(yōu)路徑，加長(zhǎng)路徑長(zhǎng)度；但同時(shí)也可能限制最優(yōu)路徑上的信息素濃度，使蟻群收斂速度減慢甚至不能找出最優(yōu)路徑。

由圖2可以看出，螞蟻從起點(diǎn)1到節(jié)點(diǎn)3比起點(diǎn)1經(jīng)過節(jié)點(diǎn)2再到節(jié)點(diǎn)3路徑更短，轉(zhuǎn)折點(diǎn)也更少，因此，路徑{1,3}比路徑{1,2,3}更重要。將這條最優(yōu)路徑用Eb來(lái)表示，所以應(yīng)該加強(qiáng)路徑{1,3}的信息素濃度，同時(shí)降低路徑{1,2,3}的信息素濃度。為了解決蟻群算法在面對(duì)實(shí)際搜索的復(fù)雜性與信息素更新之間的矛盾，將路徑{1,3}進(jìn)行信息素強(qiáng)化，對(duì)其每條路徑增加信息素c/Lb，則改進(jìn)后的信息素更新公式如下

(7)

(8)

式中c為信息素增量參數(shù)，Lb為Eb的長(zhǎng)度，Q為常量，表示信息素增強(qiáng)強(qiáng)度的系數(shù)，Lbest為全局最優(yōu)解。當(dāng)蟻群算法陷入局部最優(yōu)或連續(xù)迭代3次沒有改變最優(yōu)路徑長(zhǎng)度時(shí)，設(shè)計(jì)信息素懲罰函數(shù)

(9)

式中L1為起點(diǎn)到終點(diǎn)的直線距離，L2為當(dāng)前移動(dòng)機(jī)器人從起點(diǎn)到終點(diǎn)路徑規(guī)劃的總長(zhǎng)度，有效避免凹形障礙物周圍信息素濃度過高，移動(dòng)機(jī)器人陷入死鎖現(xiàn)象。

3 算法仿真

在MATLAB R2018a平臺(tái)構(gòu)建仿真環(huán)境，分別對(duì)傳統(tǒng)蟻群算法、文獻(xiàn)[15]算法、本文算法進(jìn)行仿真實(shí)驗(yàn)。為了保證實(shí)驗(yàn)的公平性，對(duì)以上算法均采用一樣的柵格地圖，移動(dòng)機(jī)器人遇到障礙物時(shí)不能通過，可以在空白柵格自由移動(dòng)。算法仿真結(jié)果如圖3～圖5所示，實(shí)驗(yàn)數(shù)據(jù)如表1所示。這里主要考察移動(dòng)機(jī)器人路徑長(zhǎng)度、收斂速度、平滑度三個(gè)指標(biāo)。

表1 仿真結(jié)果對(duì)比

其中，圖3(a)為傳統(tǒng)蟻群算法的移動(dòng)機(jī)器人運(yùn)動(dòng)軌跡，路徑長(zhǎng)度為31.5 563 m，轉(zhuǎn)折點(diǎn)為14個(gè)；圖4(a)為文獻(xiàn)[15]算法的移動(dòng)機(jī)器人運(yùn)動(dòng)軌跡，路徑長(zhǎng)度為29.7 990 m，轉(zhuǎn)折點(diǎn)為10個(gè)。文獻(xiàn)[15]算法相較于傳統(tǒng)算法在路徑長(zhǎng)度和平滑度兩方面均有提升，但兩種算法的平滑度依然不夠，且兩種算法的路徑規(guī)劃長(zhǎng)度均過長(zhǎng)。圖5(a)為本文算法的移動(dòng)機(jī)器人運(yùn)動(dòng)軌跡，路徑長(zhǎng)度為28.7 934 m，轉(zhuǎn)折點(diǎn)為6個(gè)，本文算法引入平滑度引導(dǎo)函數(shù)，對(duì)轉(zhuǎn)折位置較多的地方平滑楚理，誘導(dǎo)移動(dòng)機(jī)器人朝向步長(zhǎng)更大的節(jié)點(diǎn)移動(dòng)。因此，本文算法規(guī)劃出的路徑比較平滑，相較于傳統(tǒng)蟻群算法及文獻(xiàn)[15]算法在路徑長(zhǎng)度方面分別縮短了8.8 %及3.4 %，證明了本文算法在路徑規(guī)劃方面明顯優(yōu)于其他兩種算法。

圖3(b)為傳統(tǒng)蟻群算法收斂迭代曲線圖，傳統(tǒng)蟻群算法各代最優(yōu)路徑不夠穩(wěn)定，收斂迭代次數(shù)為26次；圖4(b)為文獻(xiàn)[15]算法收斂迭代曲線圖，收斂迭代次數(shù)為8次，雖然相對(duì)于傳統(tǒng)蟻群算法有一定的提升，但是收斂速度依然較慢，降低移動(dòng)機(jī)器人搜索效率；圖5(b)為本文算法收斂迭代曲線圖，收斂迭代次數(shù)為3次，本文算法在移動(dòng)機(jī)器人路徑尋優(yōu)過程中，找出各代局部最優(yōu)路徑，加強(qiáng)該路徑信息素濃度，提高算法的收斂速度。本文算法相對(duì)于傳統(tǒng)蟻群算法及文獻(xiàn)[15]算法在收斂速度方面分別提高了88.5 %及62.5 %，大幅提高移動(dòng)機(jī)器人搜索效率以及縮短了算法運(yùn)行時(shí)間，驗(yàn)證了本文算法的優(yōu)越性。

圖3 傳統(tǒng)蟻群算法路徑規(guī)劃

圖4 文獻(xiàn)[15]算法路徑規(guī)劃

圖5 本文算法路徑規(guī)劃

4 結(jié) 論

本文提出了改進(jìn)變步長(zhǎng)蟻群算法。通過對(duì)平滑機(jī)制的改進(jìn)，進(jìn)而實(shí)現(xiàn)對(duì)變步長(zhǎng)的改進(jìn)，擴(kuò)大步長(zhǎng)選擇范圍，優(yōu)先選擇步長(zhǎng)更長(zhǎng)的路徑。在避開障礙物的條件下，對(duì)多次轉(zhuǎn)角的位置用大步長(zhǎng)路徑代替，減少轉(zhuǎn)折點(diǎn)，從而縮短移動(dòng)機(jī)器人路徑長(zhǎng)度；同時(shí)，死鎖問題是移動(dòng)機(jī)器人利用蟻群算法進(jìn)行路徑規(guī)劃遇到的常見問題。本文通過改進(jìn)蟻群系統(tǒng)，通過啟發(fā)式的搜索方式使得蟻群避免陷入局部最優(yōu)，便于蟻群尋找全局最優(yōu)解。對(duì)不同路徑進(jìn)行比較，加強(qiáng)最優(yōu)路徑信息素濃度，多個(gè)個(gè)體分布式的并行計(jì)算，提高路徑被選擇的概率。引入信息素懲罰函數(shù)，避免移動(dòng)機(jī)器人陷入死鎖或局部最優(yōu)，大幅提高蟻群算法的運(yùn)行效率。