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

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

0 引 言

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

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

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

1 環(huán)境建模

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

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

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

(1)

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

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

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

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

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

(2)

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

ηij(t)=1/dij

(3)

(4)

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

螞蟻路徑信息素更新為

(5)

3 IACA算法

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

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

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

趨化操作是對(duì)細(xì)菌尋找適合自身生存環(huán)境的覓食行為的模擬,包括旋轉(zhuǎn)和游動(dòng)。細(xì)菌向任意方向移動(dòng)單位步長(zhǎng)定義為旋轉(zhuǎn)[24]。旋轉(zhuǎn)后計(jì)算適應(yīng)度值,若得到的路徑適應(yīng)度值更小則繼續(xù)沿著該方向游動(dòng),直到達(dá)到最大步長(zhǎng)或者適應(yīng)度值不發(fā)生改變,此過(guò)程稱(chēng)為游動(dòng)[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類(lèi)地圖進(jìn)行仿真對(duì)比,結(jié)果如圖1所示。

圖 1 不同算法收斂曲線(xiàn)對(duì)比Fig.1 Convergence curve comparison of the different algorithms

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

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

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

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

(8)

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

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

(a) ρ值變化

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

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

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

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

3.3 IACA算法流程

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

4 IACA算法仿真分析

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

4.1 參數(shù)初始化

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

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

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

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

4.2.1 20×20的a類(lèi)地圖

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

(a) IACA

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

表 2 a類(lèi)20×20地圖各類(lèi)實(shí)驗(yàn)數(shù)值

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

4.2.2 20×20的b類(lèi)地圖

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

(a) IACA

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

表 3 b類(lèi)20×20地圖各類(lèi)實(shí)驗(yàn)數(shù)值

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

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

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

(a) IACA

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

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

表 4 30×30地圖各類(lèi)實(shí)驗(yàn)數(shù)值

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

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

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

5 實(shí)驗(yàn)分析驗(yàn)證

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

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

(a) 實(shí)驗(yàn)用ROS小車(chē)

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

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

(a) 小車(chē)在起點(diǎn)位置

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

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

6 結(jié) 語(yǔ)

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