基于改進蟻群算法的電動叉車路徑規劃技術研究

劉顯貴, 趙率棚

(廈門理工學院 機械與汽車工程學院, 福建 廈門 361021)

0 引 言

電動叉車由于其無排放、低噪音、高效率等優點,在港口、倉儲及煙草、食品、紡織等行業應用逐漸廣泛[1]。路徑的選擇及優化極大地影響電動叉車的運輸效率。優秀的路徑規劃能力是移動機器人的一個重要指標[2],而路徑規劃的好壞,關鍵在于路徑搜索算法的選取[3]。目前,常用的路徑規劃算法主要包括蟻群算法、遺傳算法、人工勢場法、A*算法等[4-7]。

蟻群算法有很多優點,如正反饋、并行計算、魯棒性強等,受到研究者的廣泛關注[8]。但蟻群算法在計算過程中容易求得局部最優解且收斂性能差,所以很多學者對蟻群算法進行了改進。文獻[9]引入精英螞蟻策略和最大最小螞蟻機制,通過改進信息素更新方式,更好地平衡了尋優能力和收斂速度。文獻[10]采用偽隨機狀態規則進行路徑選擇,通過提出一種獎懲機制更新信息素增量,定義一種信息素自適應揮發因子,限制信息素濃度上下限等改進措施,提高了算法收斂速度。文獻[11]基于蟻群算法的信息素提出自適應的信息素揮發系數,對啟發函數進行相應的變化,提高了算法的搜索效率和準確性。文獻[12]結合人工勢場法,對啟發函數通過距離改進,避免了算法早期由于盲目搜索導致路徑交叉及收斂速度慢等問題。文獻[13]賦予不同柵格位置不同的初始信息素,設定迭代閾值,自適應調節信息素揮發系數,降低蟻群搜索的盲目性,提高全局搜索能力。

基于蟻群算法的諸多優點,結合電動叉車工作情況,對傳統蟻群算法進行改進。為了改變其前期盲目搜索導致收斂速度慢的問題,文中融合人工勢場法算法,加入人工勢場引力,構建人工勢場啟發函數中的啟發信息函數,指導螞蟻進行初始搜索,避免了傳統蟻群算法搜索過于隨機;改進信息素更新規則,根據最優最差螞蟻策略使得信息素在更小的區間內變化,提高算法的全局搜索能力;提出三角剪枝算法,實現了更優的路徑平滑規劃,為提高電動叉車工作效率打下良好基礎。

1 基于柵格法的環境建模

環境建模是建立電動叉車仿真環境,也是路徑規劃的載體。柵格法具有簡單易實現等特點,因此,文中選取柵格法搭建仿真環境。

2 基本算法

2.1 傳統蟻群算法

蟻群算法是受螞蟻覓食過程啟發而設計出來的群智能算法。螞蟻在覓食過程中會留下信息素,同時會感知信息素,其濃度大小引導向前移動。螞蟻自身攜帶的信息素是定量的,所以信息素濃度較高的路徑距離是較短的,后續迭代過程中螞蟻選擇此路徑的概率就較大。由此形成的正反饋使螞蟻不斷逼近最優路徑,找到最優解。蟻群算法的兩個重要步驟是概率選擇和信息素的更新。

概率選擇就是螞蟻從當前節點選擇到下一節點的概率。蟻群算法采用偽隨機比例原則進行計算,規則如下:

(1)

其中,螞蟻k從當前節點i移動到下一節點j的概率為q0,j是使概率值取得最大的節點:

(2)

(3)

τij(t)----t時刻螞蟻從當前節點i移動到下一節點j的信息素濃度;

τis(t)----t時刻螞蟻從當前節點i移動到下一節點s的信息素濃度;

ηij(t)----t時刻螞蟻從當前節點i移動到下一節點j的啟發函數;

ηis(t)----t時刻螞蟻從當前節點i移動到下一節點s的啟發函數;

α----信息素重要程度因子;

β----啟發函數重要程度因子;

J----除節點j外其他某節點由式(2)產生的隨機變量;

ak----可能到達節點的集合;

djg----節點j到目標節點g的歐氏距離。

信息素的更新是指從本次迭代到下次迭代過程,路徑中信息素經過累積和揮發所剩余的濃度。各節點濃度不同,從而引導蟻群進行后續的路徑選擇。所以完成一次迭代后要對信息素進行更新,傳統蟻群算法信息素全局更新規則如下:

τij(t+1)=(1-ρ)τij(t)+Δτij(t),

(4)

(5)

(6)

式中:ρ----全局信息素揮發系數;

Δτij(t)----路徑(i,j)上釋放的信息素之和;

Q----信息素強度系數。

2.2 人工勢場法

人工勢場法的基本思想是在障礙物周圍和目標點構建斥力勢場和引力勢場,兩種力的共同作用使機器人到達目的地。在人工勢場中,機器人距離障礙物越近,斥力越大;機器人距離目標點越遠,引力越大,到達目標點時引力為零。

設移動的當前位置為

X=(x,y),

目標點的位置為

Xg=(xg,yg),

定義引力勢場函數為

(7)

式中:kgra----引力場的增益系數;

|X-Xg|----機器人與目標點的歐氏距離。

定義斥力勢場函數為

(8)

式中:krep----斥力勢場增益系數;

ρ(x,x0)----機器人與障礙物之間的歐式距離;

ρ0----斥力的有效作用范圍。

機器人受到勢場中的引力和斥力向目標點移動,并完成向一條無碰撞路徑搜索。

3 改進的勢場蟻群算法

3.1 改進啟發信息函數

傳統蟻群算法在最初搜索時,每段路徑的起始信息素濃度一致,此時主要差異在啟發信息上。由于傳統公式路徑選擇節點啟發性不強,導致路徑搜索具有盲目性,搜索后的初始路徑欠佳,而蟻群算法具有正反饋性,這造成了傳統蟻群算法前期搜索較慢,且最終路徑易陷入局部最優等問題。

對于傳統蟻群算法啟發性不強的缺點,文中在啟發信息函數中加入人工勢場引力,增強啟發函數在搜索過程中的目標性,改善算法搜索效率,改進的啟發信息為:

(9)

(10)

(11)

將式(9)～式(11)代入改進啟發信息ηij(t)*中得到

(12)

式中:δ----加入人工勢場引力的因子;

α----當前節點j到目標點的人工勢場引力;

φ----常數,取值范圍(0, 1);

π----正比例系數;

d(j,H)----當前節點j到目標點H的距離,距離越大,機器人受到人工勢場的引力就越大,距離越小,機器人受到的引力值則越小。

3.2 改進信息素更新規則

在傳統蟻群算法中,隨著地圖上螞蟻迭代數量的增加,保存信息素的數量逐漸積累,使得螞蟻越來越多地走上信息素濃度高的路徑,這在一定程度上是可行的,但容易導致蟻群行走路徑陷入局部最優。為了防止局部最優解的產生,采用自適應性的信息素調節模式τij(t)*,根據更新后信息素的傳統添加,將前一代所有螞蟻在最佳路線上攜帶的信息素常數與所有螞蟻在較差路線上攜帶的信息素常數之間做減法運算,使得信息素在更小的區間內變化,

τij(t+1)*=(1-p)·Δτij(t)+Δτij(t)*,

(13)

(14)

(15)

式中:Δτij(t)*----最優路徑上螞蟻所攜帶信息素總和與最差路徑上螞蟻所攜帶信息素總和的差值,是額外的信息素增量;

v----本次循環最優路徑上的螞蟻數量;

w----本次循環最差路徑上的螞蟻數量;

Lmin----本次迭代最優路徑長度;

Lmax----本次迭代最差路徑長度。

3.3 路徑優化與更新

生成的路徑可能有大量的冗余線和轉彎點,這不僅會增加路徑的長度,而且會導致電動叉車在移動過程中需要反復改變運動方向,不利于電動叉車的快速移動。

圖 1 三角剪枝算法原理

如圖1中實線 A-B-D-C為傳統蟻群算法搜索的最短路徑,而通過剪枝算法優化后,實線 A-B-C為最短搜索路徑?？梢钥闯?剪枝算法優化路徑與原路徑相比長度明顯減少,搜索時間也相應減少?？芍羌糁Ψ梢杂行У叵D彎點所產生的多余路徑。

三角剪枝算法原理是將轉彎節點相連,如果連接后的路徑不經過障礙物,則去除該兩點間冗余的轉彎點和折線,對路徑進行更新。

定義傳統路徑節點集合為H,H={h1,h2,…,hn},剪枝優化后節點集合為P,P={p1,p2,…,pn},兩節點m1,m2的連線m1m2經過的元素集合為Nm1m2,Nm1m2={n1,n2,…,nn},障礙物元素集合為O,O={o1,o2,…,on}。在傳統路徑節點集合H中順次拿出3個節點,如h1,h2,h3,將h1與h3相連得到h1h3,若

Nh1h3∪O=?。

(16)

則把h1h3定義為剪枝優化線路,將h1,h3納入剪枝優化后的集合P中,將這兩個節點重新定義為p1,p2,以此類推,直至判斷完集合H中所有節點,把剪枝優化線路用實線表示。

3.4 算法流程

1)建立環境模型。利用柵格法建立機器人工作環境,設置可移動柵格為0,障礙物柵格為1。設置起點位置為S和目標點位置為E。

2)初始化基本參數。

3)選擇路徑節點。螞蟻k按照轉移概率公式選擇下一可行節點,由于加入人工勢場的引力函數,螞蟻在初始階段就可以感知目標點所在的位置,從而大大減少了隨機搜索方向的可能性,對此將傳統禁忌表TABUK去除。

4)記錄各路徑長度及其螞蟻數量。每次迭代完成后,對每只螞蟻的路徑曲線和路徑長度進行記錄,并對本次迭代從起點到達目標點的螞蟻數量記錄,寫入儲存結構CELL。

5)信息素更新。根據CLEE中的數據,找出本次迭代的最優路徑和最差路徑上螞蟻數量,根據式(14)～式(16)進行信息素濃度更新。

6)結束迭代。判斷算法是否達到最大迭代次數,若達到,則輸出最優路徑;若沒有達到,則返回3)進行再次迭代。

7)進行優化。對于得到的最優路線,按照三角剪枝算法進行優化,得到最優路徑線路。

4 實驗與仿真分析

為了驗證文中改進勢場蟻群算法的性能,在Matlab 2021a仿真平臺進行測試,設置兩種平面柵格仿真環境。設置仿真參數,改進蟻群算法中迭代次數為100次,螞蟻數量為50。單位柵格長度為1,總長為20,機器人起點為(0.5,19.5),終點為(19.5,0.5)。信息素濃度α為1,距離啟發因子β為2,信息素增強系數Q為10,信息素揮發系數ρ為0.8。傳統蟻群算法中距離啟發因子β為7,信息素增強系數Q為1,信息素揮發系數ρ為0.3,其余參數相同。通過傳統蟻群算法和改進勢場蟻群算法進行對比,驗證了改進勢場蟻群算法的性能。

4.1 環境1

凹形障礙物可以導致路徑搜索長度增加[8],故在搭建20*20的柵格環境1時,充分考慮凹形障礙物的影響,兩種算法的最優路徑和收斂曲線分別如圖2和圖3所示。

(a) 最優路徑

(a) 最優路徑

圖3(a)中曲線1代表改進蟻群算法直接生成的原始路徑;曲線2代表原始路徑經過三角剪枝算法計算修建后生成的改進路徑。

由圖2(a)和圖3(a)可知,兩種算法都能規劃出一條可行進路徑,改進勢場蟻群路徑和傳統蟻群算法路徑差別較小,去除多余轉折點路徑相對于傳統蟻群算法路徑打破了八自由度移動的限制,轉彎次數明顯減少,軌跡更加平滑。

從圖2(b)和圖3(b)可知,改進蟻群算法和傳統蟻群算法經過一定的迭代次數后均達到較短路徑,但傳統蟻群算法收斂速度較慢,收斂性能較不穩定,搜索效率較低。改進蟻群算法明顯提高了收斂速度,收斂性能更加穩定,搜索效率較高。

對兩種算法各運行10次,從最優路徑長度、最差路徑長度、平均路徑長度和平均收斂代數上進行比較,見表1。

表1 20*20環境算法性能

由表1可知,在路徑長度方面,去除多余轉折點后,最終路徑比傳統蟻群算法路徑在最優路徑長度、最差路徑長度及平均路徑長度分別減少4.31%、2.84%、3.23%。在平均收斂代數方面,改進蟻群算法比傳統蟻群算法減少96.97%。結果表明,文中算法具有路徑搜索能力強和收斂性快的特點。

4.2 環境2

為了進一步驗證文中算法的路徑尋優能力,將柵格環境改為30*30,增加其復雜程度。調整傳統蟻群算法迭代次數為300,使其收斂。得到兩種算法的最優路徑和收斂曲線分別如圖4和圖5所示。

(a) 最優路徑

(a) 最優路徑

圖4(a)中曲線1代表改進蟻群算法直接生成的原始路徑;曲線2代表原始路徑經過三角剪枝算法計算修建后生成的改進路徑。

由圖4(a)和圖5(a)可知,在復雜環境下,改進蟻群算法和傳統蟻群算法經過一定的迭代次數均能規劃出一條無障礙通行路徑,改進蟻群算法去除多余轉折點后生成的路徑轉彎次數減少,且軌跡更加平滑。

由圖4(b)和圖5(b)可知,在復雜環境下,傳統蟻群算法收斂速度慢,收斂性能不穩定,搜索效率低;改進蟻群算法仍能保持較快的收斂速度、較穩定的收斂性能和較高的搜索效率。

對兩種算法各運行10次,從最優路徑長度、最差路徑長度、平均路徑長度和平均收斂代數上進行比較,見表2。

表 2 30*30環境算法性能

由表2可知,在路徑長度方面,去除多余轉折點后,最終路徑比傳統蟻群算法路徑在最優路徑長度、最差路徑長度及平均路徑長度分別減少3.05%、6.31%,5.45%。在平均收斂代數方面,改進勢場最優最差蟻群算法比傳統蟻群算法減少93.40%。結果表明,在復雜環境下,文中算法仍具有路徑搜索能力強和收斂性快的特點。

5 結 語

基于柵格法對移動機器人工作空間進行環境建模,針對傳統蟻群算法在路徑規劃中存在的不足,提出一種改進的蟻群算法。

1)通過人工勢場引力函數對啟發信息進行改進,減少路徑搜索初期的盲目性,且該方法在首輪迭代生成的路徑對后續迭代過程產生正反饋作用,加快了算法的收斂速度,有效提高了算法的搜索效率。

2)改進了信息素更新規則,通過引入最優最差螞蟻策略,削弱信息素累計效果,有效避免了蟻群行走路徑陷入局部最優。

3)構建三角剪枝算法去除冗余線和轉彎點,打破了傳統蟻群算法搜索規則,使路徑長度變短且更加光滑,符合電動叉車的實際運動情況。

4)仿真結果表明,相對于傳統蟻群算法,改進的蟻群算法可以更高效地規劃出一條更優、更平滑的路徑。