基于改進(jìn)蟻群算法的自動落布車路徑規(guī)劃

沈丹峰,王 博,李許鋒,白鵬飛

(西安工程大學(xué) 機(jī)電工程學(xué)院,陜西 西安 710048)

0 引 言

自動落布車是紡織企業(yè)實現(xiàn)智慧車間的重要組成部分。落布車的自主運(yùn)動主要是指根據(jù)預(yù)定的目標(biāo)軌跡及落布車的狀態(tài)和紡織車間里的環(huán)境信息,自動控制落布車到達(dá)指定的目標(biāo)點[1]。由于自動落布車在紡織車間運(yùn)行的工作環(huán)境較為復(fù)雜,為保證自動落布車在車間能夠正常工作,有必要對自動落布車進(jìn)行路徑規(guī)劃。

路徑規(guī)劃問題實質(zhì)是如何利用已知的地圖信息,找到一條從起始點到終止點的無障礙且長度最短的路徑。目前常用的路徑規(guī)劃算法包括蟻群算法[2-3]、遺傳算法[4-5]、粒子群算法[6-7],以及A*算法[8-9]等。蟻群算法具有正反饋高、魯棒性強(qiáng)、分布式計算等優(yōu)點,但是蟻群算法在算法初期搜索過于隨機(jī)而使得算法搜索效率低,以至于算法整體收斂速度緩慢,信息素濃度在算法中后期過于集中會導(dǎo)致算法搜索停滯和易陷入局部最優(yōu)解[10]。因此,很多學(xué)者都對蟻群算法進(jìn)行了優(yōu)化。徐菱等針對蟻群算法效率低的問題提出一種16個搜索方向24個鄰域的改進(jìn)方式,針對啟發(fā)信息引入向量夾角的思想,并在轉(zhuǎn)移概率部分添加轉(zhuǎn)移概率控制參數(shù),提高了蟻群算法全局搜索能力[11];趙增旭等在轉(zhuǎn)移概率中引入向量夾角,同時融合了插點策略使算法收斂速度提高,路徑拐點減少,更加平滑[12];CHEN等在蟻群算法中引入人工勢場法進(jìn)行改進(jìn),提出一種可通過調(diào)整動態(tài)預(yù)警步長進(jìn)行避障的改進(jìn)蟻群算法[13];WANG等在改進(jìn)蟻群算法中引入方向偏心擴(kuò)展法,提出一種可用于解決靜態(tài)未知環(huán)境與動態(tài)已知環(huán)境下路徑規(guī)劃問題的改進(jìn)蟻群算法[14];王玉等將跳點搜索算法與蟻群算法相融合,并引入雙向蟻群的思想縮短了尋優(yōu)路徑[15];葉軒等通過添加動態(tài)隨機(jī)機(jī)制的轉(zhuǎn)移概率公式提高了算法的全局搜索能力,同時提出一種非必要轉(zhuǎn)折點優(yōu)化算法對路徑進(jìn)行二次優(yōu)化,減少了路徑長度[16];何心等通過引入目標(biāo)方向啟發(fā)因子提高了算法收斂速度,在采用有效拐點的路徑優(yōu)化策略的基礎(chǔ)上引入三次B樣條曲線使得規(guī)劃的路徑更加平滑[17];錢平等通過融合蟻群算法與遺傳算法加快了算法收斂速度并解決了算法陷入局部最優(yōu)的問題,同時使用平滑機(jī)制使得路徑更加平滑同時提升了算法的避障性能[18]。

以上的方法在一定程度上改進(jìn)了傳統(tǒng)蟻群算法的搜索效率與規(guī)劃的最優(yōu)路徑。本文針對自動落布車工作環(huán)境復(fù)雜,傳統(tǒng)蟻群算法存在的收斂速度慢且容易陷入局部最優(yōu)的問題,提出改進(jìn)蟻群算法(IACA)。該算法引入細(xì)菌覓食算法的趨化操作對信息素更新公式進(jìn)行改進(jìn),同時自適應(yīng)調(diào)整信息素?fù)]發(fā)因子ρ,減少搜索時間,提高全局搜索能力。

1 環(huán)境建模

規(guī)劃路徑前,需要建立一個二維地圖,常見的二維地圖建模方法有拓?fù)鋱D法、單元數(shù)法以及柵格圖法,因為柵格圖法相比其他2種地圖建模方法更容易實現(xiàn)且更直觀地看出障礙物和可行區(qū)域,所以選擇柵格圖法對地圖建模[19]。矩陣中的0和1分別表示通行節(jié)點(白色柵格)和障礙物節(jié)點(黑色柵格)[20]。

規(guī)定每個柵格的邊長是1。坐標(biāo)原點O在柵格地圖左下角,原點向上和向右為y軸、x軸正方向。螞蟻算法采用八鄰域搜索法。

直角坐標(biāo)系與柵格地圖轉(zhuǎn)換公式為

(1)

式中：Mx代表柵格序號;n代表每行或每列的柵格數(shù)目;mod(Mx,n)為Mx/n的取余函數(shù);ceil(Mx/n)為求大于等于Mx/n的最小整數(shù)函數(shù)。

通過式(1)可以獲取自動落布車在柵格地圖中的坐標(biāo)位置。

2 傳統(tǒng)蟻群算法的原理

蟻群算法是一種通過模擬螞蟻群體與環(huán)境之間的信息交互,實現(xiàn)最優(yōu)路徑選擇的元啟發(fā)式算法,具有自組織、分布式與正反饋等特點[21]。

螞蟻在構(gòu)建行走路徑時,會按照一個隨機(jī)概率選擇下一步所走節(jié)點,通常是通過輪盤賭法計算狀態(tài)轉(zhuǎn)移概率。計算狀態(tài)轉(zhuǎn)移概率公式為

(2)

啟發(fā)信息值計算公式為

ηij(t)=1/dij

(3)

(4)

式中：dij是節(jié)點i到節(jié)點j的歐氏路徑距離。

螞蟻路徑信息素更新為

(5)

3 IACA算法

傳統(tǒng)的蟻群算法在應(yīng)用于路徑規(guī)劃問題中時容易出現(xiàn)以下問題：1)傳統(tǒng)的蟻群算法在早期進(jìn)行搜索時,搜索空間較大,加上螞蟻在路徑留下的信息素較為均勻,使得螞蟻容易進(jìn)行盲目搜索,產(chǎn)生大量的無用路徑,造成算法收斂速度慢;2)傳統(tǒng)蟻群算法后期容易出現(xiàn)某條路徑信息素濃度較高,使得算法陷入局部最優(yōu)的情況。為改善傳統(tǒng)蟻群算法,本文提出一種改進(jìn)蟻群算法IACA。

3.1 引入細(xì)菌覓食算法BFO

BFO算法就是模擬大腸桿菌在覓食行為過程中所體現(xiàn)出來的生理行為,是進(jìn)行建模迭代產(chǎn)生最優(yōu)解的一種仿生搜索算法[22]。該算法具有全局最優(yōu)、易跳出局部最優(yōu)、并行搜索和魯棒性強(qiáng)等優(yōu)點[23]。

趨化操作是對細(xì)菌尋找適合自身生存環(huán)境的覓食行為的模擬,包括旋轉(zhuǎn)和游動。細(xì)菌向任意方向移動單位步長定義為旋轉(zhuǎn)[24]。旋轉(zhuǎn)后計算適應(yīng)度值,若得到的路徑適應(yīng)度值更小則繼續(xù)沿著該方向游動,直到達(dá)到最大步長或者適應(yīng)度值不發(fā)生改變,此過程稱為游動[24]。趨化操作位置更新公式為

P(e,f+1,g,h)=P(e,f,g,h)+

(6)

(7)

將進(jìn)行信息素更新公式改進(jìn)的蟻群算法與傳統(tǒng)蟻群算法在文獻(xiàn)[19]的20×20地圖中的a類地圖進(jìn)行仿真對比,結(jié)果如圖1所示。

圖 1 不同算法收斂曲線對比Fig.1 Convergence curve comparison of the different algorithms

從圖1可以看出：相比傳統(tǒng)蟻群算法,改進(jìn)后的算法在迭代次數(shù)方面減少7次,在最小路徑長度方面降低3.2 m。因此,改進(jìn)后的算法相比傳統(tǒng)蟻群算法有了很大的改善。

3.2 自適應(yīng)調(diào)整信息素?fù)]發(fā)因子ρ

一般蟻群算法的信息素?fù)]發(fā)系數(shù)為常數(shù)[25]。信息素?fù)]發(fā)因子ρ對于算法整體的效果有顯著的影響。ρ越大,信息素?fù)]發(fā)速度越快,從而影響算法收斂速度;ρ越小,信息素?fù)]發(fā)速度越慢,影響全局搜索能力,容易陷入局部搜索[26]。針對以上情況,提出一種假設(shè)：如果可以使信息素?fù)]發(fā)因子ρ實現(xiàn)自適應(yīng)變化,迭代開始數(shù)值較大,隨著迭代的進(jìn)行逐漸減小,就可以在提高算法全局搜索能力的前提下降低收斂時間,又可以避免算法陷入局部最優(yōu),從而提高算法效率。為實現(xiàn)假設(shè),對信息素?fù)]發(fā)因子ρ作自適應(yīng)調(diào)整,構(gòu)造如下

ρ=exp[-(s/p)r],0

(8)

式中：s為當(dāng)前的迭代次數(shù);p為最大迭代次數(shù),取p=100。

對r取值進(jìn)行討論。圖2(a)是r取值從1～6對ρ數(shù)值影響結(jié)果,圖2(b)是在文獻(xiàn)[19]的a類20×20地圖中,算法對r取值從1～6的仿真結(jié)果。

(a) ρ值變化

由圖2(a)看出,構(gòu)造式(8)中,信息素?fù)]發(fā)因子與迭代次數(shù)的變化趨勢是迭代前期數(shù)值較大,后期數(shù)值較小,滿足假設(shè)。由圖2(b)看出,當(dāng)r=2時,算法的結(jié)果最好,取r=2。

將只進(jìn)行自適應(yīng)調(diào)整信息素?fù)]發(fā)因子改進(jìn)的蟻群算法與傳統(tǒng)蟻群算法在文獻(xiàn)[19]的20×20地圖中的a類地圖進(jìn)行仿真對比,結(jié)果如圖3所示。

圖 3 自適應(yīng)調(diào)節(jié)ρ與傳統(tǒng)蟻群算法收斂曲線對比Fig.3 Convergence curve comparison ofthe adaptive adjustment ρ and traditional ant colony algorithm

由圖3可以看出：相比傳統(tǒng)蟻群算法,改進(jìn)后的算法在迭代次數(shù)方面減少39次,在最小路徑長度方面減少3.3 m。因此,改進(jìn)后的算法相比傳統(tǒng)蟻群算法有了很大的改善。

3.3 IACA算法流程

本文改進(jìn)的蟻群算法IACA是在傳統(tǒng)蟻群算法的基礎(chǔ)上,對信息素?fù)]發(fā)因子ρ進(jìn)行自適應(yīng)調(diào)整,并引入細(xì)菌覓食算法的趨化操作對信息素更新公式進(jìn)行改進(jìn)。具體流程圖如圖4所示。

4 IACA算法仿真分析

為驗證IACA應(yīng)用于自動落布車路徑規(guī)劃方面的效果,利用MATLAB對IACA、ACA和文獻(xiàn)[19]中的改進(jìn)算法進(jìn)行仿真對比。仿真環(huán)境：Windows 10(64位)操作系統(tǒng)、Intel(R) Core(TM)i5-8250U處理器、1.60 GHzCPU。

4.1 參數(shù)初始化

首先對3種算法的參數(shù)進(jìn)行賦值,具體如表1所示。

表 1 相關(guān)參數(shù)數(shù)值

為驗證IACA的有效性,引入文獻(xiàn)[19]的20×20地圖中的a、b類地圖與30×30地圖,分別對IACA、傳統(tǒng)蟻群算法和文獻(xiàn)[19]的改進(jìn)蟻群算法進(jìn)行仿真對比。

4.2 20×20地圖環(huán)境

4.2.1 20×20的a類地圖

將IACA與傳統(tǒng)蟻群算法以及文獻(xiàn)[19]的算法放入20×20中的a類地圖中進(jìn)行仿真驗證。其中IACA算法尋優(yōu)結(jié)果如圖5(a)所示,傳統(tǒng)蟻群算法與文獻(xiàn)[19]尋優(yōu)結(jié)果如圖5(b)、(c)所示,3種算法迭代次數(shù)與最小路徑長度如圖5(d)所示。

(a) IACA

3種算法在a類20×20地圖進(jìn)行仿真實驗得到的各實驗數(shù)據(jù)如表2所示。

表 2 a類20×20地圖各類實驗數(shù)值

從表2可以看出,IACA算法在最小路徑長度方面比傳統(tǒng)蟻群算法減少了9.3%,比文獻(xiàn)[19]算法減少了0.8%;在迭代次數(shù)方面,IACA比傳統(tǒng)蟻群算法減少了80.4%,比文獻(xiàn)[19]算法減少了52.6%;在迭代時間方面,IACA比傳統(tǒng)蟻群算法減少了28%,比文獻(xiàn)[19]算法減少了18.9%。

4.2.2 20×20的b類地圖

將IACA與傳統(tǒng)蟻群算法以及文獻(xiàn)[19]的算法放入20×20中的b類地圖中進(jìn)行仿真驗證。其中IACA算法尋優(yōu)結(jié)果如圖6(a)所示,傳統(tǒng)蟻群算法與文獻(xiàn)[19]尋優(yōu)結(jié)果如圖6(b)和圖6(c)所示,3種算法迭代次數(shù)與最小路徑長度如圖6(d)所示。

(a) IACA

3種算法在b類20×20地圖進(jìn)行仿真實驗得到的各實驗數(shù)據(jù)如表3。

表 3 b類20×20地圖各類實驗數(shù)值

通過表3可以看出,在b類地圖中,IACA在最小路徑長度方面比傳統(tǒng)蟻群算法減少了3.1%,比文獻(xiàn)[19]算法減少了0.5%;在迭代次數(shù)方面,IACA比傳統(tǒng)蟻群算法減少了81.6%,比文獻(xiàn)[19]算法減少了64%;在迭代時間上,IACA比傳統(tǒng)蟻群算法減少了13.4%,比文獻(xiàn)[19]算法減少了10.4%。

4.2.3 30×30地圖環(huán)境

為驗證IACA在復(fù)雜環(huán)境下的有效性與優(yōu)越性,將IACA算法、傳統(tǒng)蟻群算法與文獻(xiàn)[19]算法在30×30地圖中進(jìn)行仿真對比驗證。其中IACA仿真結(jié)果如圖7(a)所示,傳統(tǒng)蟻群算法與文獻(xiàn)[19]算法在地圖中的仿真結(jié)果如圖7(b)、(c)所示。圖7(d)是這3種算法收斂時的收斂次數(shù)與最小路徑長度。

(a) IACA

從圖7(a)與圖7(b)中可以看出,IACA算法相比傳統(tǒng)蟻群算法路徑上更加平滑,拐點數(shù)量更少。

3種算法在30×30地圖進(jìn)行仿真實驗得到的各實驗數(shù)據(jù)如表4所示。

表 4 30×30地圖各類實驗數(shù)值

在最小路徑長度方面,IACA算法比傳統(tǒng)蟻群算法減少了17.6%,比文獻(xiàn)[19]算法減少了2.3%;在迭代次數(shù)方面,IACA算法比傳統(tǒng)蟻群算法減少了79.7%,比文獻(xiàn)[19]算法減少了55.9%;在迭代時間方面,IACA比傳統(tǒng)蟻群算法減少了16.9%,比文獻(xiàn)[19]算法增加了1.6%。

在20×20地圖中,IACA算法比傳統(tǒng)蟻群算法在最小路徑長度方面平均減少了6.3%,迭代次數(shù)方面平均減少81.1%,迭代時間上平均減少20.7%;相比文獻(xiàn)[19]算法,IACA算法在最小路徑方面平均減少0.7%,迭代次數(shù)方面平均減少59.1%,迭代時間上平均減少14.5%。從以上數(shù)據(jù)可以看出,IACA算法相比傳統(tǒng)蟻群算法無論是在最小路徑長度還是在迭代次數(shù)上都具有明顯優(yōu)勢;相比文獻(xiàn)[19]算法,雖然在最小路徑距離方面差異不大,但在迭代次數(shù)上,IACA算法更有優(yōu)勢。

綜上所述,IACA算法在最小路徑距離、迭代次數(shù)與迭代時間方面比傳統(tǒng)蟻群算法都有很大提升,在實際中可以提高自動落布車的運(yùn)行效率。

5 實驗分析驗證

為進(jìn)一步驗證IACA算法在織布車間環(huán)境中的運(yùn)行效果,設(shè)計了基于ROS系統(tǒng)的機(jī)器小車實驗。實驗使用的ROS小車搭載支持Ubuntu系統(tǒng)的樹莓派4B板,通過SSH與PC計算機(jī)進(jìn)行遠(yuǎn)程連接,并通過其搭載的思嵐AI單線激光雷達(dá)對室內(nèi)封閉環(huán)境中的類似織機(jī)的箱型障礙物進(jìn)行掃描建立地圖,再利用Rviz三維可視化平臺將地圖進(jìn)行可視化處理。應(yīng)用的建圖算法為Gmapping算法。

實驗步驟：首先利用ROS系統(tǒng)與Gmapping算法構(gòu)建模擬的織布車間實驗環(huán)境地圖。ROS小車與構(gòu)建的織布車間實驗環(huán)境地圖如圖8(a)、(b)所示。

(a) 實驗用ROS小車

在實驗中,為保護(hù)小車避免發(fā)生碰撞,對實驗用的障礙物織機(jī)進(jìn)行膨脹處理,通過設(shè)置膨脹半徑R(R=0.2 m),擴(kuò)大障礙物占地面積,從而降低了小車與織機(jī)進(jìn)行碰撞的風(fēng)險。

其次,在建立了織布車間的模擬環(huán)境地圖之后,分別采用IACA算法與ACA算法進(jìn)行路徑規(guī)劃步驟。實驗全過程通過電腦PC端的Rviz三維可視化平臺將小車運(yùn)動過程呈現(xiàn)出來,如圖9(a)、(b)、(c)所示。實驗小車分別用傳統(tǒng)蟻群算法與IACA進(jìn)行路徑規(guī)劃的路線圖如圖9(d)所示,其中黑色路徑是傳統(tǒng)蟻群算法,紅色路徑是IACA算法。

(a) 小車在起點位置

實驗采用的ROS小車的運(yùn)動速度為0.5 m/s,圖中傳統(tǒng)蟻群算法與IACA規(guī)劃的路徑長度相同,但I(xiàn)ACA總運(yùn)行時間是30.65 s,傳統(tǒng)蟻群算法總運(yùn)行時間為33.52 s,相比傳統(tǒng)蟻群算法,IACA在運(yùn)行時間上減少了8.6%。

由此可以得出：IACA能夠?qū)ふ业揭粭l不亞于傳統(tǒng)蟻群算法的路徑,同時耗時更短。該結(jié)論與仿真結(jié)果基本吻合。

6 結(jié) 語

本文針對自動落布車使用傳統(tǒng)蟻群算法進(jìn)行路徑規(guī)劃過程中出現(xiàn)的收斂次數(shù)多、時間長,收斂速度慢,容易陷入局部最優(yōu)的問題,提出一種改進(jìn)蟻群算法IACA。算法首先對信息素?fù)]發(fā)系數(shù)ρ進(jìn)行自適應(yīng)調(diào)整,然后引入細(xì)菌覓食算法的趨化操作對信息素更新公式進(jìn)行改進(jìn),從而使改進(jìn)后的算法能夠避免出現(xiàn)陷入局部最優(yōu)的情況,同時降低了收斂時間,提高了收斂速度。實驗結(jié)果表明,IACA相比傳統(tǒng)蟻群算法尋優(yōu)時間更短,收斂速度更快。在實際生產(chǎn)中,可以有效提高自動落布車路徑規(guī)劃效率。但從實驗中可看出,改進(jìn)算法在最小路徑長度方面提升不大,還有改進(jìn)空間。