基于混合參數(shù)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃

荊學(xué)東，杜黎童，郭泰，蔡震寰

(上海應(yīng)用技術(shù)大學(xué)機(jī)械工程學(xué)院，上海 201418)

0 前言

全局路徑規(guī)劃是研究室內(nèi)移動(dòng)機(jī)器人運(yùn)動(dòng)控制的重點(diǎn)技術(shù)之一。移動(dòng)機(jī)器人根據(jù)自身所處的全局地圖環(huán)境和目標(biāo)點(diǎn)的信息，它可以迅速地通過(guò)自主計(jì)算找到一條從當(dāng)前位置到達(dá)指定目標(biāo)點(diǎn)的適宜路徑。路徑規(guī)劃的算法許多，主要有A算法、柵格解耦法和人工勢(shì)場(chǎng)法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法和粒子群算法等。

蟻群算法(Ant Colony Optimization,ACO)是由意大利學(xué)者DORIGO等提出的一種群集智能算法。算法早期主要是用來(lái)解決商旅問(wèn)題，隨著算法的應(yīng)用發(fā)展，且ACO算法本身具備的分布式計(jì)算、正反饋性和強(qiáng)魯棒行等特點(diǎn)，它也廣泛應(yīng)用到路徑規(guī)劃領(lǐng)域，并且取得了許多優(yōu)秀成果。雖然ACO算法優(yōu)點(diǎn)很多，但也存在許多缺點(diǎn)。對(duì)它的缺點(diǎn)，STüTZLE、HOOS提出了最大最小蟻群系統(tǒng)；文獻(xiàn)[14]提出了把ACO算法和遺傳算法(Genetic Algorithm,GA)結(jié)合使用的混合算法(Genetic Algorithm-Ant Algorithm,GAAA)；文獻(xiàn)[15-18]則把GAAA算法成功運(yùn)用到旅行商、車間調(diào)度等生產(chǎn)生活的問(wèn)題中去。本文作者設(shè)計(jì)了一種混合參數(shù)的蟻群進(jìn)化算法(Hybrid Parameter Ant Colony Evolutionary Algorithm,HPACEA)，此算法在GA算法和ACO算法融合節(jié)點(diǎn)和銜接處進(jìn)行優(yōu)化改進(jìn)，并通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的可行性和有效性。

1 基于柵格地圖的環(huán)境建模

文中的室內(nèi)移動(dòng)機(jī)器人搭載單線激光雷達(dá)，它無(wú)法獲取周圍物體的高度信息，僅能獲取平面數(shù)據(jù)，掃描數(shù)據(jù)為二維數(shù)據(jù)。為簡(jiǎn)化室內(nèi)環(huán)境，采用柵格地圖法對(duì)移動(dòng)機(jī)器人獲得的室內(nèi)環(huán)境數(shù)據(jù)進(jìn)行建圖，柵格尺寸大小與移動(dòng)機(jī)器人的外形大小有關(guān)，用黑白2色柵格表示不可行路徑節(jié)點(diǎn)和可行路徑節(jié)點(diǎn)。為保證機(jī)器人和障礙物有安全的間隔距離，根據(jù)機(jī)器人實(shí)際尺寸取邊長(zhǎng)的二分之一長(zhǎng)度對(duì)障礙物進(jìn)行“膨化”處理，用黃色柵格表示膨化處理的安全距離空間。當(dāng)雷達(dá)數(shù)據(jù)映射到地圖中時(shí)，如果障礙物面積不足一個(gè)柵格，則當(dāng)作占據(jù)一個(gè)完整柵格。文中柵格地圖中每個(gè)柵格的序號(hào)從左上角開(kāi)始，依次編號(hào)為1、2、…、。對(duì)環(huán)境進(jìn)行柵格建圖，如圖1所示。

圖1 柵格法的環(huán)境地圖

2 混合參數(shù)蟻群進(jìn)化算法的原理與改進(jìn)

本文作者提出的混合參數(shù)蟻群進(jìn)化算法(HPACEA)的總體框架如圖2所示。

圖2 HPACEA算法框架

2.1 HPACEA中遺傳算法的設(shè)定

2.1.1 交叉概率和變異概率的改進(jìn)

為增加算法初期蟻群信息素分布的多樣性，對(duì)遺傳算法的交叉概率和變異概率引入高斯變異算子。首先在種群每次迭代中隨機(jī)在區(qū)間[0.2，0.9]中選擇交叉概率，然后對(duì)該交叉概率隨機(jī)選擇一定數(shù)量的維度進(jìn)行高斯變異操作，生成的滿足+=1。其操作方式為

=roundn(0.2+0.7×rand(),-1)

(1)

(2)

(3)

式中:～(1,1),(1,1)表示均值為1、方差為1的高斯分布；roundn為四舍五入函數(shù)；rand產(chǎn)生[0,1)均勻分布隨機(jī)數(shù)。

在高斯變異過(guò)程中，產(chǎn)生的可能會(huì)超出區(qū)間范圍。當(dāng)它在維度上超出邊界，通過(guò)式(4)的映射規(guī)則映射到可行區(qū)間的新位置。

(4)

式中:、分別為交叉概率區(qū)間的上邊界和下邊界。

2.1.2 適應(yīng)度函數(shù)改進(jìn)

GA算法的適應(yīng)度函數(shù)是基于路徑長(zhǎng)度和路徑拐角獎(jiǎng)懲機(jī)制進(jìn)行評(píng)價(jià)的。路徑長(zhǎng)度計(jì)算公式如下：

(5)

=1

(6)

式中:為連續(xù)路徑的總長(zhǎng)度。

為減少路徑的拐彎個(gè)數(shù)，讓路徑盡量平滑，引入拐點(diǎn)獎(jiǎng)懲機(jī)制，公式如式(7)所示：

(7)

=1

(8)

式中:為連續(xù)路徑的獎(jiǎng)懲點(diǎn)數(shù)。

適應(yīng)度函數(shù)總的計(jì)算公式如下：

=+

(9)

根據(jù)路徑長(zhǎng)度和拐角獎(jiǎng)懲點(diǎn)數(shù)選擇合適的權(quán)重參數(shù)。

2.1.3 交叉方法

遺傳算法的交叉操作流程如圖3所示。

圖3 交叉方法流程

2.1.4 變異方法

遺傳算法的變異操作流程如圖4所示。

圖4 變異方法流程

2.2 HPACEA中蟻群算法的改進(jìn)與鏈接

2.2.1 蟻群算法銜接設(shè)置

為了充分發(fā)揮GA算法的進(jìn)化效果，減少算法的無(wú)用迭代,在GA算法和ACO算法融合處采用最小進(jìn)化率參數(shù)評(píng)估是否由GA算法進(jìn)入ACO算法。對(duì)GA算法設(shè)置一個(gè)最小迭代數(shù)和最大迭代數(shù),當(dāng)GA算法的進(jìn)化率連續(xù)代小于給定的最小進(jìn)化率時(shí)開(kāi)始進(jìn)入ACO算法。進(jìn)化率計(jì)算方法如下：

=(--1)-1=2,3,…,

(10)

(11)

式中：為適應(yīng)度評(píng)價(jià)值；為個(gè)體的進(jìn)化率；為進(jìn)化代數(shù)；為種群規(guī)模；RE為每一代的進(jìn)化率。

當(dāng)確定由GA算法進(jìn)入ACO算法時(shí)，將GA算法最后一代得到的路徑中排名前15%路徑信息轉(zhuǎn)化為HPACEA算法中的初始信息素分布。

=+

(12)

式中：為信息素常數(shù)；為由遺傳算法得到的初始路徑經(jīng)過(guò)計(jì)算得到的信息素值。

2.2.2 蟻群算法信息因子和期望因子改進(jìn)

HPACEA算法螞蟻尋路時(shí)采用混合參數(shù)來(lái)提高蟻群尋路的多樣性，即每次迭代都引入高斯變異產(chǎn)生新的和。∈(0,3),∈(0,7),其選擇公式如下:

=roundn(((3-rand())·min(3,2+7)),-2)

(13)

(14)

=roundn(7×rand()06,-2)

(15)

(16)

(17)

(18)

式中:、、、分別為、的上邊界和下邊界。

2.2.3 信息素更新方法

在每代蟻群尋路結(jié)束后，進(jìn)行信息素更新時(shí)采用精化策略，其更新方式為

(19)

(20)

對(duì)信息素?fù)]發(fā)因子采用一種自適應(yīng)調(diào)整方式：

(21)

式中:為的最小值；為的最大值；為適應(yīng)度最大值；為適應(yīng)度最小值。

在ACO算法的最后再次引入遺傳操作，當(dāng)ACO算法每次迭代路徑的進(jìn)化率大于給定的時(shí)，根據(jù)輪盤賭的概率決定是否對(duì)當(dāng)代產(chǎn)生的路徑進(jìn)行交叉操作或變異操作，這樣HPACEA算法總體形成了一個(gè)類似閉環(huán)的算法機(jī)制。

2.3 HPACEA算法路徑光滑處理

在HPACEA算法的最后階段引入三次B樣條曲線，實(shí)現(xiàn)機(jī)器人路徑的相對(duì)光滑。為判斷去除多余節(jié)點(diǎn)后新生成的路徑是否經(jīng)過(guò)障礙物區(qū)域，引入評(píng)價(jià)變量。的表達(dá)式為

(22)

式中:為障礙物節(jié)點(diǎn)中心到新生成路徑的距離。

平滑機(jī)制實(shí)施步驟：

(1)針對(duì)所有路徑的節(jié)點(diǎn)，兩兩相連計(jì)算它們的斜率，若2個(gè)斜率不相同，則取它們共有的節(jié)點(diǎn)，放入節(jié)點(diǎn)集合中。

(2)把最優(yōu)路徑的起始節(jié)點(diǎn)和終止節(jié)點(diǎn)放入集合中，設(shè)={|=1,2，…，}，為起始點(diǎn)，為目標(biāo)點(diǎn)。首先連接、，判斷、連線是否經(jīng)過(guò)障礙物，若=1;繼續(xù)連接與下一節(jié)點(diǎn)，直到、連線穿過(guò)障礙物區(qū)域停止，則把、-1連接起來(lái)，刪除它們中間的多余節(jié)點(diǎn)、…、-2，得到新的路徑;從節(jié)點(diǎn)-1開(kāi)始連接+1，依次判斷每次連線是否經(jīng)過(guò)障礙物。當(dāng)集合中的節(jié)點(diǎn)都被連線過(guò)且新生路徑中沒(méi)有多余節(jié)點(diǎn)為止。

(3)對(duì)去除多余節(jié)點(diǎn)的新路徑,采用準(zhǔn)均勻B樣條曲線對(duì)其進(jìn)行優(yōu)化處理。

圖5展示了路線光滑過(guò)程中的3個(gè)路徑階段。

圖5 光滑機(jī)制處理前后的路徑

3 仿真實(shí)驗(yàn)驗(yàn)證

為證明HPACEA算法是有效可行的，采用MATLAB軟件對(duì)柵格環(huán)境下的室內(nèi)機(jī)器人進(jìn)行路徑規(guī)劃仿真驗(yàn)證，和不同的算法進(jìn)行驗(yàn)證比較。

3.1 20×20簡(jiǎn)單環(huán)境實(shí)驗(yàn)仿真

將HPACEA算法與傳統(tǒng)的GA算法、ACO算法和文獻(xiàn)[14]中GAAA算法在20×20的柵格地圖進(jìn)行仿真對(duì)比試驗(yàn)。HPACEA算法的初始條件為：遺傳算法的迭代次數(shù)=50和=10，=3%，=50，=100，=100，∈[0,3]，∈[0,7]，(0)=07，=0.2,=1.8，設(shè)置起始點(diǎn)柵格序號(hào)為1，終止點(diǎn)為400。GA算法、ACO算法和GAAA算法，共有的參數(shù)設(shè)置和HPACEA相同，不相同參數(shù)按照經(jīng)驗(yàn)自行設(shè)定。對(duì)比算法的具體參數(shù)設(shè)為：GA算法和ACO算法最大迭代次數(shù)為120,=0.8，=0.2，=1，=7。結(jié)果如圖6、圖7所示。

從圖6可以看出:HPACEA算法獲得的路徑最短且相對(duì)光滑，ACO算法和GAAA算法次之，GA算法的運(yùn)動(dòng)軌跡最長(zhǎng)且拐角最多。圖7為4種算法的收斂曲線：GA算法的收斂速度最快，在迭代18次找到穩(wěn)定解，但找到的路徑經(jīng)常屬于次優(yōu)解；HPACEA算法的收斂速度較快，在迭代20次即可找到最優(yōu)解；GAAA算法和ACO算法都是50次迭代以后找到穩(wěn)定解，并且找到的解經(jīng)常不是最短路徑。

圖6 20×20環(huán)境中4種算法運(yùn)動(dòng)軌跡

圖7 20×20環(huán)境中4種算法的收斂曲線

表1是在20×20的柵格地圖對(duì)4種算法進(jìn)行10次路徑規(guī)劃的仿真實(shí)驗(yàn)數(shù)據(jù)，表中引入最佳尋優(yōu)性能指標(biāo)、時(shí)間性能指標(biāo)和魯棒性能指標(biāo)作為路徑規(guī)劃算法的評(píng)價(jià)指標(biāo)?？梢钥闯觯篐PACEA算法找到的最優(yōu)路徑為29.49 m,相比其他算法找到的路徑長(zhǎng)度減少4.7%～9.8%，轉(zhuǎn)彎節(jié)點(diǎn)減少45%～57%。從性能評(píng)價(jià)指標(biāo)可以看出:GAAA算法和HPACEA算法的最佳尋優(yōu)性能指標(biāo)和魯棒性能指標(biāo)明顯優(yōu)于GA和ACO算法，其中HPACEA算法最好，GAAA算法次之；從時(shí)間性能指標(biāo)上對(duì)比，GA算法收斂速度最快，HPACEA算法次之；從綜合性能指標(biāo)看出，HPACEA算法最優(yōu)，綜合性能明顯比其他3種算法優(yōu)秀。

表1 20×20環(huán)境中4種算法的仿真結(jié)果

3.2 30×30復(fù)雜環(huán)境實(shí)驗(yàn)仿真

采用30×30的復(fù)雜環(huán)境驗(yàn)證HPACEA算法的有效性，并與其他3種算法進(jìn)行驗(yàn)證對(duì)比。實(shí)驗(yàn)結(jié)果如圖8、圖9所示。

圖8 30×30環(huán)境中4種算法運(yùn)動(dòng)軌跡

由圖8知:傳統(tǒng)GA、傳統(tǒng)ACO和文獻(xiàn)[14]的GAAA算法在面臨復(fù)雜環(huán)境時(shí)，規(guī)劃的路線存在許多轉(zhuǎn)折點(diǎn);而HPACEA算法加入光滑機(jī)制后，拐點(diǎn)數(shù)減少31%～40%，并且規(guī)劃的路徑更光滑。由表2知：最短路徑長(zhǎng)度是HPACEA算法找到的43.12 m,相比其他算法找到的路徑長(zhǎng)度減少6.8%～8%；文獻(xiàn)[14]的GAAA和改進(jìn)的HPACEA算法在魯棒性能和最佳尋優(yōu)性能指標(biāo)上比較優(yōu)秀，且HPACEA算法表現(xiàn)得最好。結(jié)合圖9知:在復(fù)雜的環(huán)境里，傳統(tǒng)GA算法和HPACEA算法達(dá)到穩(wěn)定解的迭代速度是最快的，但HPACEA算法能找到更短的路徑，且它的魯棒性最好。HPACEA綜合性能比其他3種算法更優(yōu)秀，即使面對(duì)復(fù)雜的環(huán)境也能保持穩(wěn)定性和快速尋找最優(yōu)解的能力。

圖9 30×30環(huán)境中4種算法的收斂曲線

表2 30×30環(huán)境中4種算法的仿真結(jié)果

通過(guò)設(shè)計(jì)2種不同室內(nèi)環(huán)境，對(duì)傳統(tǒng)GA算法、傳統(tǒng)ACO算法、文獻(xiàn)[14]的GAAA算法和改進(jìn)HPACEA算法進(jìn)行仿真實(shí)驗(yàn)，從算法的尋優(yōu)能力、收斂速度和算法魯棒性進(jìn)行評(píng)估對(duì)比，驗(yàn)證了改進(jìn)HPACEA算法在進(jìn)行路徑規(guī)劃時(shí)具有較強(qiáng)的尋優(yōu)能力、較快的搜索速度和求解穩(wěn)定的特點(diǎn)，對(duì)復(fù)雜的環(huán)境也具有較強(qiáng)的適用性。

4 結(jié)論

(1)針對(duì)蟻群算法收斂速度慢和易陷入局部最優(yōu)等缺陷，提出了混合參數(shù)的蟻群進(jìn)化算法。該算法首先進(jìn)行選擇、交叉、變異操作，為下一步蟻群算法提供不同信息素信息;然后對(duì)蟻群算法的、、因子進(jìn)行優(yōu)化改進(jìn);最后對(duì)輸出路徑進(jìn)行光滑加工處理。通過(guò)仿真實(shí)驗(yàn)證實(shí)了算法的可行性。

(2)在MATLAB中采用柵格法建立兩種室內(nèi)環(huán)境模型，將文中算法與其他3種算法進(jìn)行仿真對(duì)比實(shí)驗(yàn)。結(jié)果表明：改進(jìn)的算法在不同的環(huán)境下，找到的路徑長(zhǎng)度比其他3種算法減少了4.7%～8%，路徑拐點(diǎn)減少了30%以上，且改進(jìn)的算法可以較快找到一條相對(duì)光滑的路徑，達(dá)到穩(wěn)定解的迭代次數(shù)比ACO和GAAA算法減少了50%。