于蓮芝，秦 天

（上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093）

0 引言

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

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

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

1.1 蟻群算法原理

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

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

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

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

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

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

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

1.4 信息素濃度

信息素濃度由式（3）、式（4）進(jìn)行計算：

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

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

1.5 環(huán)境建模

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

圖1 柵格圖Fig.1 Raster map

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

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

2 改進(jìn)的蟻群算法及仿真分析

2.1 改進(jìn)的蟻群算法

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

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

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

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

2.2 死鎖問題的處理

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

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

3 改進(jìn)蟻群算法的仿真

3.1 改進(jìn)蟻群算法的算法步驟

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

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

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

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

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

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

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

3.2 仿真與分析

基于前文分析，在20×20網(wǎng)格環(huán)境下進(jìn)行實驗仿真。利用Matlab進(jìn)行柵格建模，算法參數(shù)設(shè)置見表1。實驗過程中，算法改進(jìn)信息素分布變化動態(tài)如圖4所示。圖4演示了信息素濃度在拐點的地方進(jìn)行自我優(yōu)化調(diào)整的過程。對傳統(tǒng)的蟻群算法路徑尋優(yōu)算法、文獻(xiàn)［11］提出的蟻群算法的路徑規(guī)劃方法和本文提出的改進(jìn)蟻群算法進(jìn)行迭代次數(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ù)設(shè)置Tab.1 Parameters setting

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

4 結(jié)束語

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

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