基于改進蟻群優化算法的AGV路徑規劃

陳歲繁,王湞元,李其朋

(浙江科技大學 機械與能源工程學院,杭州 310023)

路徑規劃是移動機器人(automatic guided vehicle,AGV)實現自主移動與導航功能中必不可少的一部分[1-2]。傳統的優化算法主要有經典算法和智能算法。經典算法有A*算法[4]、快速隨機樹(rapid random tree,RRT)算法[5]等,智能算法包括遺傳算法[6]、粒子群算法[7]、蟻群算法[8]等。蟻群算法由于魯棒性強,且易與其他算法結合,成為研究熱點。但是蟻群算法也存在搜索空間大、局部最優、收斂速度慢、拐點較多等問題。研究者基于蟻群算法缺點,提出了很多改進方案。例如:劉新宇等[9]提出一種蟻群-聚類自適應路徑規劃方法,解決了傳統蟻群收斂速度慢的問題;宋宇等[10]通過結合A*算法,對啟發函數、信息素濃度及揮發因子進行重新定義,提高了算法的尋優能力和搜索效率。Masoumi等[11]設計了一種以用戶為多目標中心的蟻群優化算法,能適應不同優先級的多目標優化問題;高茂源等[12]分別從啟發因子、信息素及揮發因子三個方向改進蟻群算法,提升了算法的收斂速度和尋優效率。

基于傳統蟻群算法在AGV路徑規劃中有搜索效率低、尋找路徑長、拐點個數多等方面的問題,本研究設計了一種改進的蟻群優化算法。首先對啟發函數進行改進,提升搜索效率;然后更新信息素,解決路徑規劃時易陷入局部最優的問題;接著降低路徑的拐點;最后引入動態避障策略,解決路徑規劃時出現的死鎖。

1 環境模型構建

1.1 柵格圖

環境模型有很多,比如可視圖空間、拓撲圖、柵格地圖等。柵格地圖是運用黑白兩色柵格表示AGV的可移動區域和禁行區域[13-14],對障礙物的表示簡單易懂,是目前環境建模中應用較多的模型。以10×10柵格為例,建立靜態環境下AGV運動柵格地圖,如圖1所示。

圖1 柵格地圖Fig.1 Grid map

根據環境模型,設置柵格地圖的柵格號從下往上、從左往右依次按1、2…10的順序遞增,坐標(xi,yi)(i為柵格號)與柵格編號的關系如下:

(1)

式(1)中:L為柵格邊長;X為柵格地圖行數;Y為柵格地圖列數。

1.2 步長搜索方式

圖2 步長搜索方式Fig.2 Step size search method

圖3 路徑的各個節點Fig.3 Each node of the path

2 蟻群算法

蟻群算法是20世紀末科學家Dorigo等最早提出的一種智能算法[16],該過程包括狀態概率(state transition probability,STP)的選擇和信息素的更新(pheromone update,PU)。

2.1 狀態概率選擇

傳統蟻群算法在搜索過程中根據螞蟻當前柵格和障礙物選擇下一可行柵格,螞蟻t時刻從節點i運動到節點j的概率一般通過輪盤賭法確定,它的狀態轉移概率

(2)

2.2 信息素更新

信息素更新包括信息素揮發和強化。信息素揮發,一是防止信息素濃度過高掩蓋啟發信息,二是避免過快陷入局部最優。信息素強化是為了讓螞蟻向最優解靠近,增加經過路徑上的信息素濃度,加快路徑最優解的尋找速度。信息素更新表達式如下:

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

(3)

(4)

式(3)和式(4)中:(1-ρ)為信息素殘留;Δτij(t)為t時刻螞蟻從路徑坐標(i,j)中經過時的信息素增量;Q為信息素強化系數;Lk為螞蟻k從起始點到目標點之間的路徑總長。

3 改進的蟻群算法

3.1 改進的啟發信息

傳統蟻群算法只考慮了螞蟻t時刻在路徑坐標(i,j)上的距離,本研究引入起始點和目標點,路徑的各個節點如圖4所示。

圖4 改進的蟻群優化算法流程圖Fig.4 Flowchart of improved ant colony optimal algorithm

預估代價最早出現在A*算法中,它指當前點到目標點之間的大概距離,而不是精確數值,可以引導算法朝著最短目標路徑方向去搜索。預估代價的計算一般采用曼哈頓距離[17],即兩點在水平方向上的總和。

成熟收獲前對所有試驗小區均取樣考種，共36個小區，每處理10株進行考種。考查性狀有株高、根頸粗、有效分枝部位、主花序長、單株一次和二次分枝數、單株角果數、角粒數、千粒重、單株產量。實收小區產量曬干折單產。

在引入預估代價值的基礎上,添加一個平衡因子,加快算法的收斂。綜合考慮起始點、當前點、下一點、目標點,使螞蟻搜索空間變小,搜索效率得到提升,增強路徑尋優能力。改進后的表達式如下:

(5)

(6)

式(5)和式(6)中:dje為節點j到目標點e的距離;ε為平衡因子;dsi為起始點s到節點i的距離;Nc和Nm為迭代次數。

3.2 改進的信息素更新

對信息素的更新主要圍繞著路徑來進行。

3.2.1 狼群分配機制

傳統的蟻群算法在對最優和最差路徑中的信息素進行更新時,由于所用方法相同,路徑中的信息素相差不是很大,路徑的搜索效率也有所下降。因此,需要對信息素的更新公式進行改進,在此引入狼群算法。狼群在捕獵時主要有搜索、圍攻、更新幾種行為,狼群算法是受狼群捕獵時的行為啟發提出的一種算法[18]。頭狼最具智慧和攻擊性;探狼是狼群的精銳,需要探找獵物;其余需要圍攻獵物的狼稱為猛狼。狼群捕獵的基本過程包括游走、奔襲、召喚、狼群更新等[19]。

尋找到最差路徑的螞蟻,會散發信息素,這樣會誘導在后面的搜尋路徑的螞蟻。采用狼群分配機制,可以防止路徑陷入局部最優,有效縮短螞蟻搜索路徑的長度。改進的信息素更新表達式如下:

τ′ij(t+1)=τij(t+1)+Δτij,2-Δτij,1;

(7)

(8)

(9)

式(7)、式(8)和式(9)中:Δτij,1、Δτij,2分別為最差路徑信息素減少量和最優路徑信息素增加量;ξ和λ分別為每次搜索時找到的最優、最差螞蟻數;L1和L2分別為螞蟻到達目標點的最長、最短路徑;Lav為螞蟻到達目標點的平均路徑;Q1和Q2分別為信息素的減少和增加系數,取Q1=0.5,Q2=1。

3.2.2 拐點影響因子

傳統蟻群算法在更新信息素時,一般只考慮路徑長度,而沒有考慮路徑拐點帶來的影響。因此,本研究對信息素增量Δτij(t)進行改進,加入拐點影響因子,動態調節路徑長度和拐點的數目。改進后的表達式如下:

(10)

Sk(t)=xLk+yFk。

(11)

式(11)中:x為路徑長度因子;Lk為路徑的總長;y為拐點影響因子;Fk為拐點個數;x和y的取值范圍均為(0,1]。

3.3 動態避障策略

蟻群在最初搜索時,會產生許多交叉路徑,由于禁忌表的存在,很多螞蟻沒有到終點,就在最后搜索的路徑上停下來,于是就會發生死鎖[20]。遇到復雜環境時,出現死鎖的概率更高,從而降低了收斂速度。傳統回退策略雖然可以減少死鎖螞蟻,但回退次數過多會使搜索時間變長,影響搜索效率。對此,本研究引入改進的避障策略,在螞蟻搜索初期,加入動態避障因子Tj,得到新的狀態概率表達式如下:

(12)

(13)

式(12)和式(13)中:σ為避障系數,取值為大于0的常數;G1為表示節點j周圍可行柵格;G2為障礙柵格;G3為被禁忌表限制柵格。

3.4 改進的蟻群優化算法流程

改進的蟻群優化算法流程圖見圖4。

4 仿真試驗分析

仿真平臺,MatLabR2017a軟件;仿真環境,系統為Windows 10,64 bit,內存為8 GB,CPU為core i5-82501,6 GHz。

4.1 參數分析

每個參數在各自合適的范圍內各選取5個值,組成相應集合:ρ∈{0.1,0.3,0.5,0.7,0.9};Q∈{1,5,8,10,12};α∈{1,2,3,4,5};β∈{1,3,5,6,8};根據參數集合,選取一組初始參數:α=1,β=1,ρ=0.1,Q=1;設置螞蟻數M=50,迭代次數N=100;仿真試驗在20×20的柵格環境下進行,每次只改變其中一個參數值。首先改變啟發因子α,分別仿真試驗5次,選擇得到最優路徑和最小迭代次數的數值,之后依此類推;將每個參數仿真所得到的數據擬合,各參數對路徑長度和迭代次數的影響見圖5。由圖5可知,上述4個參數可以取得最佳路徑和最小迭代次數的數值范圍分別為2≤α≤3、5≤β≤6、0.5≤ρ≤0.7和8≤Q≤10。根據各參數范圍可以選出最佳參數,見表1。

表1 最佳參數Table 1 Best parameter

圖5 各參數對路徑長度和迭代次數的影響Fig.5 Impact of various parameters on path length and iteration times

4.2 20×20柵格環境的試驗

選擇簡單的柵格環境進行仿真,將本研究改進的蟻群優化算法所得結果分別與傳統蟻群算法、高茂源等[12]的算法進行對比,在20×20柵格環境下的仿真數據見表2,3種蟻群算法的路徑和收斂情況如圖6所示。

表2 3種蟻群算法在20×20柵格環境下的仿真數據Table 2 Simulation data of three ant colony algorithms under grid environment 20 × 20

圖6 3種蟻群算法在20×20柵格環境下的路徑和收斂情況Fig.6 Path and convergence of three ant colony algorithms under grid environment 20 × 20

由表2可知,在簡單柵格環境下,運用本研究的改進的蟻群優化算法,得到的最佳路徑長度、迭代次數及拐點數,相比傳統蟻群算法分別降低了9.7%、57.8%、65.0%,相比高茂源等[12]的算法,分別降低了4.3%、38.5%、46.2%。

4.3 30×30柵格環境下試驗

為了更加深入地驗證改進的蟻群優化算法具有先進性,再選擇復雜的柵格環境進行仿真,在30×30柵格環境下的仿真數據及3種蟻群算法的路徑和收斂情況,見表3及圖7。

表3 3種蟻群算法在30×30柵格環境下的仿真數據Table 3 Simulation data of three ant colony algorithms under grid environment 30 × 30

圖7 3種蟻群算法在30×30柵格環境下的路徑和收斂情況Fig.7 Path and convergence of three ant colony algorithms under grid environment 30 × 30

由表3可知,在復雜柵格環境下,相比傳統蟻群算法及高茂源等[12]的算法,運用本研究的改進的蟻群優化算法,最佳路徑長度分別縮短了6.6%、3.6%,拐點數分別減少了64.0%、43.7%,迭代次數分別降低了60.5%、42.3%。

通過在簡單環境及復雜環境下進行仿真可以看出,本研究的改進的蟻群優化算法在搜索效率、收斂速度、路徑尋優等方面,相比傳統蟻群算法及高茂源等[12]的算法有了較大的提高,提升了AGV路徑規劃的綜合性能。

5 結 語

傳統的蟻群算法在AGV路徑規劃時存在搜索效率低、拐點個數多、尋找路徑長等問題。本研究設計了一種改進的蟻群優化算法:首先,在蟻群優化算法中加入預估代價值策略來改進啟發函數,不僅增強了目標點向導作用,而且提升了搜索效率;然后,更新信息素,通過結合狼群算法分配機制,解決路徑規劃時易陷入的局部最優問題;接著,降低路徑的拐點;最后,引入動態避障策略來解決死鎖。仿真試驗表明,相比傳統算法,AGV運用改進的ACO算法進行路徑規劃,迭代次數和拐點數等均有顯著降低,證明改進的ACO算法提升了AGV路徑規劃的性能,可以很好地解決AGV路徑規劃時遇到的問題。