改進蟻群算法在物流機器人路徑規(guī)劃上的研究

于蓮芝，秦 天

（上海理工大學 光電信息與計算機工程學院，上海 200093）

0 引言

隨著科學技術的發(fā)展，機器人現(xiàn)已廣泛應用在倉儲物流、現(xiàn)代化農(nóng)業(yè)、智能制造工廠、智慧醫(yī)療等領域。在此背景下，移動機器人的路徑規(guī)劃研究即已成為時下學界的關注熱點。路徑規(guī)劃是指規(guī)定移動機器人在具有障礙物的環(huán)境中從初始位置出發(fā)尋找一條無碰撞、安全到達目標位置的一條最優(yōu)路徑。目前，國內(nèi)外已對移動機器人在路徑規(guī)劃的算法方向上進行了大量研究，最為常見的路徑有規(guī)劃算法Dijstra，A算法等。伴隨著該項研究的快速發(fā)展，現(xiàn)已衍生出了一系列的仿生智能算法，諸如遺傳算法、粒子群算法、蟻群算法等。

本文即重點針對蟻群算法展開研究。初期，是由學者Dorigo提出了最早的蟻群算法，算法是通過對螞蟻覓食行為的仿生研究模擬而來。傳統(tǒng)的蟻群算法在進行路徑規(guī)劃時，通常會出現(xiàn)如收斂速度慢、容易陷入局部最優(yōu)化等問題。因而，國內(nèi)外的眾多專家學者都對最早期的蟻群算法進行了研究改進。文獻［8］通過建立信息素不均勻分布矩陣，在目標點和蟻群的初始搜索點之間構(gòu)建有利矩陣，目標點和初始點之間的信息素大于其它區(qū)域的信息素濃度，改變狀態(tài)轉(zhuǎn)移概率，但是卻對環(huán)境的要求較高，目標點和初始點沒有明確路徑的環(huán)境會使得搜索問題變得更為復雜，對收斂速度和路徑縮短方面，取得成效并不明顯。文獻［9］先是建立信息素不均勻分布矩陣，在目標點和蟻群的初始搜索點間劃分出優(yōu)選區(qū)域，形成有利矩陣，將信息素在此區(qū)域按照新建立的數(shù)學模型重新分布，在前期搜索速度上得到了有效的提升，迭代時間也大大減少，但是建立的數(shù)學模型較為復雜，運算量十分可觀，運行時間上較傳統(tǒng)算法更長，特別是在復雜環(huán)境下的算法路徑規(guī)劃能力還有了明顯下降。文獻［10］采用新的啟發(fā)函數(shù)，把當前所在位置和下一步位置間的距離d、和下一個將要移動到的位置與目標點之間的距離d，兩者和的平方的倒數(shù)作為算法的啟發(fā)函數(shù)，這就提升了算法的效率。但卻沒有考慮到d＜＜d，而這種情況卻容易導致局部最優(yōu)化問題。文獻［11］提出信息素揮發(fā)因子自適應策略，在全局搜索能力上得到增強。但在處理局部最優(yōu)化問題方面卻未能給出有效解決方案，同時迭代次數(shù)較傳統(tǒng)算法也未見到更大改進。文獻［12］將傳統(tǒng)蟻群算法和人工蜂群算法相結(jié)合，將2種算法的信息素濃度賦予不同的權重，得出更新策略，有效解決了局部最優(yōu)化問題，加快了收斂速度，路徑尋優(yōu)過程中的多樣性也得到了保證。但是在一些復雜環(huán)境中，容易出現(xiàn)死鎖問題，進而容易使算法出現(xiàn)失敗。文獻［13］引入虛擬節(jié)點將搜索空間大大縮小，降低了迭代次數(shù)，提升了算法運行的收斂速度。但是設置的準換節(jié)點卻降低路徑尋優(yōu)的多樣性，而且還引入了新的拐點。這些則會直接導致機器人出現(xiàn)安全和功耗問題。

1 改進蟻群算法的路徑規(guī)劃方法研究

1.1 蟻群算法原理

蟻群算法通過信息素引導整個搜索過程，人工計算機模擬自然界中蟻群的覓食行為是該算法的核心內(nèi)容。每只螞蟻都會在路徑上留下一種物質(zhì)，將其稱為信息素，當其他螞蟻稍后經(jīng)過時，就能夠感知到這種物質(zhì)，以此為向?qū)В瑢Ψ较蜻x擇做出引導。一般來說，當每只螞蟻離開巢穴時，大多都會選擇一條通往目的地的路徑。在每一個交叉節(jié)點上，將前一個螞蟻釋放的信息素作為標記來選擇前行路徑，最終得到最優(yōu)路徑。

1.2 節(jié)點狀態(tài)轉(zhuǎn)移概率

其中，，表示當前節(jié)點和下一個節(jié)點；T（）表示信息素濃度；η（）表示啟發(fā)式函數(shù)；是信息素因素；是啟發(fā)式因素。

1.3 啟發(fā)式函數(shù)

研究中推得η（）的計算公式如下：

其中，d表示，節(jié)點之間的距離，用于評估路徑長度對節(jié)點選擇的影響程度。

在求解距離的方法中，比較典型的是求解算法。然而，在使用曼哈頓距離求解算法時，不能直接確定對角節(jié)點之間的距離。歐氏距離是計算2個節(jié)點間的線性距離，可用于對角線節(jié)點間的距離計算。因此，本研究選擇歐幾里得距離法來計算距離。如果2個節(jié)點間的距離越大，相應的啟發(fā)式函數(shù)值越??；反之，如果2個節(jié)點間的距離越小，相應的啟發(fā)式函數(shù)值就越大，那么從當前節(jié)點中選擇一個節(jié)點的概率就越大。

1.4 信息素濃度

信息素濃度由式（3）、式（4）進行計算：

式（3）是信息素刷新公式，表示信息素的波動系數(shù)。式（4）中的T()為前一時間信息素濃度。式（3）中隨著的增加，螞蟻的信息素揮發(fā)越快，直接影響算法的收斂速度；信息素揮發(fā)系數(shù)越小，信息素揮發(fā)越慢，則會影響整個區(qū)域的搜索能力，容易陷入局部搜索。（1-）表示信息素殘留程度。

其中，L表示螞蟻行走的距離，即從起始位置到當前位置的距離；是信息素增強系數(shù)，在傳統(tǒng)的蟻群算法中，表示一個常數(shù)。

1.5 環(huán)境建模

在典型的倉庫模型中，包括的主要設備有：貨架、傳送帶、隔離帶和揀選臺。為了對機器人路徑在此環(huán)境下進行更好的規(guī)劃，就要驗證機器人改進算法在較為復雜環(huán)境中的可行性，首先就要進行環(huán)境地圖建模。由于該方法可以在網(wǎng)格環(huán)境下方便地進行建模，并具有節(jié)省空間的優(yōu)點。圖1即顯示了構(gòu)建的光柵環(huán)境地圖。

圖1 柵格圖Fig.1 Raster map

移動機器人在執(zhí)行任務時，以20×20網(wǎng)格地圖為例，將其工作區(qū)域劃分為網(wǎng)格，參見圖1。指定機器人在柵格的中心點上移動，柵格坐標由中心點表示?；顒訁^(qū)域用白色標示，機器人可以通過；黑色為禁止區(qū)域，表示路徑上有障礙物。當機器人移動到圖形中的網(wǎng)格時，最后一個移動方向被移除，機器人可以向接近其當前位置的任何方向移動（障礙物的方向不能移動），即無法返回。柵格坐標由柵格編號表示，數(shù)學公式具體如下：

其中，是行數(shù)，是列數(shù)。

2 改進的蟻群算法及仿真分析

2.1 改進的蟻群算法

基本蟻群算法中，多數(shù)算法驗證場景設置較為簡單，為了解決算法適用性差、容易形成局部最優(yōu)路徑的問題，提出建立信息素濃度動態(tài)差異化分布矩陣，使得搜索速率加快，同時縮短搜索路徑。改進的算法與傳統(tǒng)的蟻群算法最大的區(qū)別就在于螞蟻在搜尋路徑時更新信息素的規(guī)則。

初始信息素濃度矩陣為，改進后螞蟻在每一次迭代尋找到目標后，對信息素進行一次動態(tài)更新，更新公式如下：

其中，為平衡系數(shù)，為方差。螞蟻在行進過程中對路徑進行不斷地優(yōu)化，由于每次螞蟻釋放的信息素都是按照標準正態(tài)分布，距離此螞蟻越近的柵格獲得的信息素濃度就越高，在拐點處按照公式（7）會產(chǎn)生信息素的堆積效應，即在拐彎處，在弧內(nèi)的信息素濃度堆積會越來越多，而弧外相對于弧內(nèi)的信息素濃度則會低很多。螞蟻選擇下一個目的地的概率與信息素濃度成正比，如圖2所示，會在有弧度的地方進行自動的矯正，因此按照式（7）進行信息素更新，有利于減少發(fā)生局部最優(yōu)化的可能性，縮短搜索路徑。

圖2 信息素更新示意圖Fig.2 Pheromone update diagram

2.2 死鎖問題的處理

蟻群在進行路徑尋優(yōu)的過程中，從當前點轉(zhuǎn)移到下一個柵格時，以當前柵格為中心，除自身所在位置的柵格外、其它柵格不可選，此時螞蟻就進入死鎖狀態(tài)，會給算法準確性和效率帶來很大影響，于是提出了在每次尋找到路徑后來重新規(guī)劃信息素分布的策略。只需要得到一個可以到達目的地的路徑，緊接著會自動調(diào)整信息素的分布，所以不需要在每次迭代過程中每只螞蟻都必須到達目的地才會進行下一次迭代，在螞蟻尋找路徑的過程中將陷入死鎖狀態(tài)的螞蟻直接清除，并將形成死鎖的柵格加入禁忌表，這一策略可以有效提高算法的效率。

假設螞蟻在時刻進入某個節(jié)點，如果按照搜索條件，下一個可選節(jié)點集為空，即判斷螞蟻進入死鎖狀態(tài)。將此時處于死鎖狀態(tài)的螞蟻進行直接清除處理，并將當前形成死鎖的節(jié)點加入禁忌集合(K)，再將當前螞蟻爬過節(jié)點的信息素清空，將螞蟻直接清除的策略有效解決了傳統(tǒng)蟻群算法中螞蟻陷入死鎖狀態(tài)的缺點，并且可以顯著提高算法效率。

3 改進蟻群算法的仿真

3.1 改進蟻群算法的算法步驟

設置初始化參數(shù)。在算法中將參數(shù)設置為初始值。

構(gòu)建一個環(huán)境模型。繪制一個網(wǎng)格地圖并將其轉(zhuǎn)換為鄰接矩陣。根據(jù)起始點和結(jié)束點構(gòu)造信息素矩陣。初始化起始點、爬行路徑長度和禁忌列表。

搜索路徑。將只螞蟻放在起始點，根據(jù)信息素和狀態(tài)轉(zhuǎn)移概率搜索螞蟻下一個將要到達的節(jié)點，直至尋找到設置的目標點。當某只螞蟻陷入死鎖陷阱，則根據(jù)清除策略加以處理。

更新信息素。根據(jù)算法改進的信息素更新策略，將每個柵格上的信息素按照正態(tài)分布進行更新。

循環(huán)迭代。根據(jù)預先設定的迭代次數(shù)，判斷在算法運行中是否到達預先設定的迭代次數(shù)，如果達到，則將當前尋優(yōu)得到的最短路徑輸出，否則算法步驟回調(diào)，繼續(xù)執(zhí)行步驟3，直至到達最大迭代次數(shù)，輸出結(jié)果。

綜上論述可知，算法的運算處理流程如圖3所示。

圖3 算法流程圖Fig.3 The flow chart of the algorithm

3.2 仿真與分析

基于前文分析，在20×20網(wǎng)格環(huán)境下進行實驗仿真。利用Matlab進行柵格建模，算法參數(shù)設置見表1。實驗過程中，算法改進信息素分布變化動態(tài)如圖4所示。圖4演示了信息素濃度在拐點的地方進行自我優(yōu)化調(diào)整的過程。對傳統(tǒng)的蟻群算法路徑尋優(yōu)算法、文獻［11］提出的蟻群算法的路徑規(guī)劃方法和本文提出的改進蟻群算法進行迭代次數(shù)、迭代時間、穩(wěn)定性方面的對比，實驗對比結(jié)果如圖5、圖6所示。3種蟻群算法仿真結(jié)果對比見表2。

表2 3種蟻群算法仿真結(jié)果對比Tab.2 The simulation results comparison of three ant colony algorithms

圖4 信息素動態(tài)分布變化圖Fig.4 Pheromone dynamic distribution change map

圖5 3種蟻群算法最短路徑規(guī)劃圖Fig.5 Shortest path planning diagram based on three ant colony algorithms

圖6 3種蟻群算法路徑規(guī)劃迭代收斂曲線Fig.6 Iterative convergence curves of three ant colony algorithms for path planning

表1 參數(shù)設置Tab.1 Parameters setting

在較為復雜、有不規(guī)則障礙物的實驗環(huán)境中對算法的有效性和適用性進行測試?；鞠伻核惴ā⑽墨I［11］蟻群算法和本文提出改進蟻群算法的路徑尋優(yōu)軌跡與迭代收斂曲線見圖4、圖5。分析可知，傳統(tǒng)蟻群算法在收斂速度上較慢，在不規(guī)則障礙物處容易發(fā)生死鎖，搜索結(jié)果路徑較長，算法收斂性較差。文獻［11］的算法也有類似的不足，容易陷入凹狀障礙物，不能夠進行自動優(yōu)化，進而形成局部最優(yōu)化。由圖6可知，傳統(tǒng)蟻群算法在路徑尋優(yōu)過程的前期不能夠快速地尋找到目標點的方向，收斂速度較慢。文獻［11］較基本蟻群算法在收斂速度上有所提高，但對于路徑選擇也與基本蟻群算法一樣未臻優(yōu)化。由表2可以看到，本文改進算法的搜索最優(yōu)軌跡長度與傳統(tǒng)蟻群算法相比減少8.53%，較文獻［11］算法減少5.60%，搜索效率、即迭代次數(shù)減少率較基本蟻群算法減少65.38%，較文獻［11］中改進算法減少53.63%。根據(jù)實驗與仿真的結(jié)果，在設定的復雜環(huán)境中，本文提出的改進的蟻群算法能夠有效提升路徑的尋優(yōu)效果。

4 結(jié)束語

針對物流機器人在路徑尋優(yōu)過程中收斂速度慢的問題，提出一種基于蟻群算法的改進算法。在路徑轉(zhuǎn)移概率中引入信息素高斯分布，可以動態(tài)地調(diào)整狀態(tài)轉(zhuǎn)移概率，從而避免了算法中的停滯現(xiàn)象，改進了算法中信息素的更新策略。同時，對搜索過程中出現(xiàn)的死鎖問題提出了清除策略。通過仿真結(jié)果可以看到，改進算法的迭代次數(shù)明顯減少，路徑長度縮短，搜索路徑更為光滑。有效地提高了物流機器人路徑規(guī)劃的速度和性能。

由于本文是基于柵格圖進行仿真研究的，在較小的場地環(huán)境中效果較好。隨著場地的增大，本文算法對全局性最優(yōu)化問題的解決效果變差。下一步研究將針對這個問題，不斷進行完善。