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

于蓮芝，秦 天

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

0 引言

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

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

1 改進蟻群算法的路徑規劃方法研究

1.1 蟻群算法原理

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

1.2 節點狀態轉移概率

其中，，表示當前節點和下一個節點；T（）表示信息素濃度；η（）表示啟發式函數；是信息素因素；是啟發式因素。

1.3 啟發式函數

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

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

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

1.4 信息素濃度

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

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

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

1.5 環境建模

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

圖1 柵格圖Fig.1 Raster map

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

其中，是行數，是列數。

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

2.1 改進的蟻群算法

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

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

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

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

2.2 死鎖問題的處理

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

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

3 改進蟻群算法的仿真

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

設置初始化參數。在算法中將參數設置為初始值。

構建一個環境模型。繪制一個網格地圖并將其轉換為鄰接矩陣。根據起始點和結束點構造信息素矩陣。初始化起始點、爬行路徑長度和禁忌列表。

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

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

循環迭代。根據預先設定的迭代次數，判斷在算法運行中是否到達預先設定的迭代次數，如果達到，則將當前尋優得到的最短路徑輸出，否則算法步驟回調，繼續執行步驟3，直至到達最大迭代次數，輸出結果。

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

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

3.2 仿真與分析

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

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

圖4 信息素動態分布變化圖Fig.4 Pheromone dynamic distribution change map

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

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

表1 參數設置Tab.1 Parameters setting

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

4 結束語

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

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