基于改進(jìn)蟻群算法在機(jī)器人路徑優(yōu)化中的應(yīng)用

侯遠(yuǎn)韶

（河南工業(yè)貿(mào)易職業(yè)學(xué)院機(jī)電工程系，鄭州451191）

機(jī)器人導(dǎo)航方式主要有視覺導(dǎo)航、電磁導(dǎo)航和慣性導(dǎo)航[1]。視覺導(dǎo)航技術(shù)以路徑規(guī)劃作為主要研究對象，根據(jù)各種已知信息尋找最佳路徑的搜索問題，進(jìn)而完成自主移動。路徑規(guī)劃方式根據(jù)所掌握環(huán)境信息量的不同可以分為局部路徑規(guī)劃（環(huán)境未知或部分未知）和全局路徑規(guī)劃（環(huán)境完全已知），同時環(huán)境又有動態(tài)和靜態(tài)之分。因此，對路徑規(guī)劃的研究具體分為：在全局和局部路徑規(guī)劃的基礎(chǔ)上又分為靜態(tài)路徑規(guī)劃和動態(tài)路徑規(guī)劃。具體的代表算法有：粒子群算法、遺傳算法、模糊邏輯算法和人工勢場法；A*算法、柵格法、構(gòu)型空間法和自由空間法[2]。蟻群算法（ACO）又稱螞蟻算法，是基于模擬蟻群覓食行為尋找優(yōu)化路徑的一種自然估算算法，是意大利人Marco Dorigo在1992年首次提出的一種具有啟發(fā)式的仿生智能優(yōu)化搜索算法。ACO有著正反饋性、簡單性和并行性等特點(diǎn)，在機(jī)器人路徑規(guī)劃中有著非常重要的作用，但是蟻群算法收斂速度慢，容易陷入局部最優(yōu)進(jìn)而導(dǎo)致死鎖現(xiàn)象[3]。而遺傳算法有利于尋找全局最優(yōu)點(diǎn)，具有極強(qiáng)的容錯能力，可以求解非線性復(fù)雜組合的優(yōu)化問題[4]。因此，本文為了克服蟻群算法存在的缺陷，減少算法的迭代次數(shù)進(jìn)而加快收斂速度，在基礎(chǔ)蟻群算法的原理上融合遺傳算法的優(yōu)勢。

1 最優(yōu)化問題

1.1 最優(yōu)化問題的定義

根據(jù)已知條件，對數(shù)據(jù)參數(shù)和方案進(jìn)行設(shè)計，進(jìn)而得到滿意的答案，稱之為最優(yōu)化問題。最優(yōu)化的數(shù)學(xué)表示為：

式（1）中，f(x)為目標(biāo)函數(shù)，gi(x)和hi(x)為等式約束條件和不等式約束條件（其中x∈S），S為目標(biāo)可行域。求解最優(yōu)化的問題可以轉(zhuǎn)化為在目標(biāo)可行域S中為了得到符合目標(biāo)函數(shù)f(x)極大值x的數(shù)據(jù)集，同時滿足其約束條件，其中極大值問題也可以根據(jù)極小值進(jìn)行計算maxf(x)=f(x)-minf(x)。

1.2 蟻群優(yōu)化原理及數(shù)學(xué)模型

式（2）中，α為信息啟發(fā)式因子，β為期望啟發(fā)式因子，ηij為小鎮(zhèn)i到小鎮(zhèn)j的能見度。為了避免啟發(fā)信息被過多的殘留信息所覆蓋，需要及時將殘留信息替換為新的信息，替換后t+n時間點(diǎn)道路(i,j)信息素總量為：

式（3）中，ρ∈[0 , 1]為殘留信息素?fù)]發(fā)系數(shù)，Δτij為新的信息素增量。

蟻群對路徑優(yōu)化步驟如圖1所示：

圖1 蟻群算法求解最優(yōu)路徑流程

2 機(jī)器人路徑優(yōu)化問題

2.1 障礙物檢測算法

移動簡單的物體是容易的，而路徑搜索是復(fù)雜的。障礙物檢測算法用于對機(jī)器人移動路徑障礙物進(jìn)行檢測，進(jìn)而規(guī)劃合理的路徑[5]。該算法的原理為：在機(jī)器人起點(diǎn)和終點(diǎn)之間搭建一條直線，繼而沿直線從起點(diǎn)到終點(diǎn)進(jìn)行檢測，如果發(fā)現(xiàn)障礙物進(jìn)行標(biāo)記，并計算障礙物到起點(diǎn)和終點(diǎn)的距離，得到兩個極值，然后利用兩個極值點(diǎn)得到路徑中間點(diǎn)，最終根據(jù)中間點(diǎn)對機(jī)器人進(jìn)行路徑規(guī)劃[6]。障礙物檢測算法數(shù)學(xué)模型為：假設(shè)起點(diǎn)坐標(biāo)用Xs=[xs,ys]T表示，終點(diǎn)坐標(biāo)用XD=[xd,yd]T表示，那么機(jī)器人初始位置和終點(diǎn)位置的線性方程為：

2.2 機(jī)器人路徑規(guī)劃

機(jī)器人路徑規(guī)劃是利用某些指標(biāo)進(jìn)行有規(guī)則的移動，進(jìn)而得到路徑規(guī)劃的最優(yōu)化效果。當(dāng)目標(biāo)可行區(qū)域內(nèi)存在障礙物，起點(diǎn)到終點(diǎn)無碰撞、消耗時間短則為最優(yōu)路徑[7]。指標(biāo)的尋找則需要通過算法對不同路徑實(shí)驗(yàn)得到，包括路徑尋找過程中能量的消耗、路徑的距離、尋找路徑所消耗的時間成本等[8]。路徑規(guī)劃問題和流程如圖2所示。

圖2 路徑規(guī)劃的問題和流程

在多個條件限制情況下，對機(jī)器人移動路徑進(jìn)行求解最優(yōu)化的問題即為路徑規(guī)劃。在已知自身位置的前提下，根據(jù)已得到的環(huán)境信息，實(shí)現(xiàn)移動過程中的避障。因此，根據(jù)所掌握環(huán)境信息量的不同，可以將機(jī)器人路徑規(guī)劃劃分為全局路徑規(guī)劃和局部路徑規(guī)劃[9]。全局路徑規(guī)劃是指機(jī)器人在目標(biāo)可行域內(nèi)對障礙可知，障礙不隨機(jī)器人的運(yùn)動而運(yùn)動，屬于靜態(tài)規(guī)劃，主要算法有蟻群優(yōu)化算法、柵格法、神經(jīng)網(wǎng)絡(luò)法等；局部路徑規(guī)劃是指機(jī)器人在目標(biāo)可行域內(nèi)每次移動前，通過各種傳感器不間斷收集環(huán)境信息，繼而根據(jù)自身定位和障礙物環(huán)境信息，進(jìn)行路徑選擇屬于動態(tài)規(guī)劃，主要算法有模糊邏輯控制法、人工勢場法和遺傳算法。根據(jù)具體情況全局路徑規(guī)劃和局部路徑規(guī)劃有各自的適應(yīng)范圍，因此為了避免死鎖現(xiàn)象的發(fā)生和加快收斂速度，可以將算法混合進(jìn)而改善算法性能，實(shí)現(xiàn)機(jī)器人自主避障[10]。

3 基于改進(jìn)蟻群算法的路徑優(yōu)化

3.1 算法對比

為了避免算法開始階段缺少信息素而導(dǎo)致蟻群盲目搜索，進(jìn)而帶來迭代次數(shù)多、收斂速度慢的問題，需要對算法進(jìn)行改進(jìn)。已有的機(jī)器人路徑規(guī)劃算法主要有基于柵格法的環(huán)境建模、基于神經(jīng)網(wǎng)絡(luò)算法的建模和對蟻群算法進(jìn)行各種融合改進(jìn)的全局最優(yōu)路徑規(guī)劃。

柵格法是將移動機(jī)器人的目標(biāo)可行域離散為多個柵格，通過棋盤理念將柵格分為兩大類，即障礙物柵格和可通行柵格，障礙物的柵格化主要通過數(shù)學(xué)形態(tài)學(xué)中的膨脹法和腐蝕法算子來實(shí)現(xiàn)，如圖3所示。

圖3 障礙物柵格化前后的形態(tài)

人工勢場算法是局部路徑規(guī)劃的典型應(yīng)用，利用了人工力場原理。我們可以認(rèn)為目標(biāo)點(diǎn)對機(jī)器人運(yùn)動具有引力作用，障礙物對機(jī)器人運(yùn)動有斥力作用，在引力和斥力的影響下機(jī)器人做路徑規(guī)劃運(yùn)動，機(jī)器人的加速力則是引力和斥力相互作用的結(jié)果。機(jī)器人在目標(biāo)可行域內(nèi)初始定位為X=[x,y]T，目標(biāo)定位為XM=[xm,ym]T，斥力和引力可以通過相應(yīng)的數(shù)學(xué)公式表示，稱為勢場函數(shù)：

式（6）中，K0為目標(biāo)可行域內(nèi)斥力增益系數(shù)，ξ為障礙物邊緣到機(jī)器人初始定位的最小直線路程，ξ0為機(jī)器人受障礙物影響的最大界限。式（7）中，Kg為目標(biāo)可行域內(nèi)引力增益系數(shù)，K0，Kg均大于零。

3.2 路徑優(yōu)化算法的實(shí)現(xiàn)

蟻群算法初始階段缺少信息素導(dǎo)致收斂速度慢，同時隨著路徑搜索規(guī)模的擴(kuò)大，搜索時間也隨之大幅提升，在迭代搜索過程中遺傳算法的快速性是其他算法無法比擬的，因此在基礎(chǔ)蟻群算法的原理上融合遺傳算法的優(yōu)勢，最終實(shí)現(xiàn)路徑優(yōu)化。算法思路為：首先對組合優(yōu)化問題求解較優(yōu)解，然后利用得到的較優(yōu)解進(jìn)行改進(jìn)，作為蟻群進(jìn)行全局最優(yōu)解的初始信息素，最后通過并行機(jī)制和反饋機(jī)制得到全局最優(yōu)路徑規(guī)劃的實(shí)現(xiàn)，即全局最優(yōu)解。算法具體流程為：

（1）選擇合適的遺傳基因、蟻群數(shù)量、蟻群循環(huán)迭代次數(shù)和螞蟻信息量的各種參數(shù)，如信息素常量、揮發(fā)系數(shù)、啟發(fā)因子等；

（2）求解組合優(yōu)化問題，通過遺傳算法循環(huán)迭代搜索，得到染色體種群矩陣信息；

（3）將步驟（2）中得到染色體種群矩陣信息作為蟻群進(jìn)行初始路徑搜尋的信息素分布矩陣；

（4）蟻群算法改進(jìn)后，對組合優(yōu)化問題求解最優(yōu)解；

（5）分析全部最優(yōu)解，得到最終全局最優(yōu)解。

4 實(shí)驗(yàn)仿真

本文采用Matlab 7.0實(shí)驗(yàn)平臺進(jìn)行仿真，電腦操作系統(tǒng)為win 7，內(nèi)存32 G，CPU為Intel I7處理器，數(shù)據(jù)庫采用TSP30作為實(shí)驗(yàn)例子，實(shí)驗(yàn)結(jié)果采用20次實(shí)驗(yàn)的平均值，實(shí)驗(yàn)數(shù)據(jù)如表1和表2所示。

表1 傳統(tǒng)蟻群算法實(shí)驗(yàn)結(jié)果

表2 改進(jìn)蟻群算法實(shí)驗(yàn)結(jié)果

為了驗(yàn)證算法具有普遍適應(yīng)性，實(shí)驗(yàn)給定相同的信息啟發(fā)因子和期望啟發(fā)因子，使其具有同等仿真環(huán)境，同時信息素?fù)]發(fā)系數(shù)設(shè)為定值，避免不同外部因素對實(shí)驗(yàn)帶來的影響。通過實(shí)驗(yàn)仿真結(jié)果可知，在基礎(chǔ)蟻群算法的原理上融合遺傳算法具有尋找全局最優(yōu)點(diǎn)的特征，雖然蟻群尋址最短路徑基本一致，但迭代次數(shù)大大減少，同時避免了死鎖現(xiàn)象的存在，使其在時效性以及穩(wěn)定性上具有一定的優(yōu)勢。

5 結(jié)語

本文通過最優(yōu)化定義引出了機(jī)器人路徑規(guī)劃作為視覺導(dǎo)航存在的問題，分析了蟻群優(yōu)化原理與數(shù)學(xué)模型，以及現(xiàn)有機(jī)器人路徑規(guī)劃算法對障礙物檢測存在的不足之處。繼而通過全局規(guī)劃和局部規(guī)劃，得出機(jī)器人路徑規(guī)劃所需要考慮的問題。最后通過比較柵格法、人工勢場算法和基礎(chǔ)蟻群算法的核心思想及各自的應(yīng)用范圍，提出了一種改進(jìn)的蟻群優(yōu)化算法，即在基礎(chǔ)蟻群算法的原理上融合遺傳算法的優(yōu)勢，同時保留傳統(tǒng)蟻群算法的隨機(jī)、并行特點(diǎn)和遺傳算法具有全局快速搜索的優(yōu)勢。通過實(shí)驗(yàn)仿真可知，優(yōu)化后的算法迭代次數(shù)大大減少，收斂速度得到了提高，同時避免死鎖現(xiàn)象的發(fā)生，具有一定的應(yīng)用價值。