基于改進蟻群算法的自動落布車路徑規劃

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

(西安工程大學 機電工程學院,陜西 西安 710048)

0 引 言

自動落布車是紡織企業實現智慧車間的重要組成部分。落布車的自主運動主要是指根據預定的目標軌跡及落布車的狀態和紡織車間里的環境信息,自動控制落布車到達指定的目標點[1]。由于自動落布車在紡織車間運行的工作環境較為復雜,為保證自動落布車在車間能夠正常工作,有必要對自動落布車進行路徑規劃。

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

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

1 環境建模

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

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

直角坐標系與柵格地圖轉換公式為

(1)

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

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

2 傳統蟻群算法的原理

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

螞蟻在構建行走路徑時,會按照一個隨機概率選擇下一步所走節點,通常是通過輪盤賭法計算狀態轉移概率。計算狀態轉移概率公式為

(2)

啟發信息值計算公式為

ηij(t)=1/dij

(3)

(4)

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

螞蟻路徑信息素更新為

(5)

3 IACA算法

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

3.1 引入細菌覓食算法BFO

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

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

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

(6)

(7)

將進行信息素更新公式改進的蟻群算法與傳統蟻群算法在文獻[19]的20×20地圖中的a類地圖進行仿真對比,結果如圖1所示。

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

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

3.2 自適應調整信息素揮發因子ρ

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

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

(8)

式中：s為當前的迭代次數;p為最大迭代次數,取p=100。

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

(a) ρ值變化

由圖2(a)看出,構造式(8)中,信息素揮發因子與迭代次數的變化趨勢是迭代前期數值較大,后期數值較小,滿足假設。由圖2(b)看出,當r=2時,算法的結果最好,取r=2。

將只進行自適應調整信息素揮發因子改進的蟻群算法與傳統蟻群算法在文獻[19]的20×20地圖中的a類地圖進行仿真對比,結果如圖3所示。

圖 3 自適應調節ρ與傳統蟻群算法收斂曲線對比Fig.3 Convergence curve comparison ofthe adaptive adjustment ρ and traditional ant colony algorithm

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

3.3 IACA算法流程

本文改進的蟻群算法IACA是在傳統蟻群算法的基礎上,對信息素揮發因子ρ進行自適應調整,并引入細菌覓食算法的趨化操作對信息素更新公式進行改進。具體流程圖如圖4所示。

4 IACA算法仿真分析

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

4.1 參數初始化

首先對3種算法的參數進行賦值,具體如表1所示。

表 1 相關參數數值

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

4.2 20×20地圖環境

4.2.1 20×20的a類地圖

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

(a) IACA

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

表 2 a類20×20地圖各類實驗數值

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

4.2.2 20×20的b類地圖

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

(a) IACA

3種算法在b類20×20地圖進行仿真實驗得到的各實驗數據如表3。

表 3 b類20×20地圖各類實驗數值

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

4.2.3 30×30地圖環境

為驗證IACA在復雜環境下的有效性與優越性,將IACA算法、傳統蟻群算法與文獻[19]算法在30×30地圖中進行仿真對比驗證。其中IACA仿真結果如圖7(a)所示,傳統蟻群算法與文獻[19]算法在地圖中的仿真結果如圖7(b)、(c)所示。圖7(d)是這3種算法收斂時的收斂次數與最小路徑長度。

(a) IACA

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

3種算法在30×30地圖進行仿真實驗得到的各實驗數據如表4所示。

表 4 30×30地圖各類實驗數值

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

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

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

5 實驗分析驗證

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

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

(a) 實驗用ROS小車

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

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

(a) 小車在起點位置

實驗采用的ROS小車的運動速度為0.5 m/s,圖中傳統蟻群算法與IACA規劃的路徑長度相同,但IACA總運行時間是30.65 s,傳統蟻群算法總運行時間為33.52 s,相比傳統蟻群算法,IACA在運行時間上減少了8.6%。

由此可以得出：IACA能夠尋找到一條不亞于傳統蟻群算法的路徑,同時耗時更短。該結論與仿真結果基本吻合。

6 結 語

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