基于混合蟻群算法的AGV路徑規(guī)劃*

孟冠軍，陳信華，陶細佩，張 偉

(合肥工業(yè)大學機械工程學院，合肥 230009)

0 引言

路徑規(guī)劃是指在具有障礙物的環(huán)境中，移動物依照某一特定的性能指標(如空間距離、時間等)搜索一條從起始位置到目標位置的最優(yōu)或次優(yōu)路徑[1]。自動導引運輸車(Automated Guided Vehicle，AGV)路徑規(guī)劃主要包含兩個核心問題：地圖信息表達和搜索策略[2]。針對AGV路徑規(guī)劃問題，國內(nèi)外學者進行了長期的深入研究，并相繼提出了多種較為有效的方法，常用的地圖信息表達方法有柵格法[3]、圖論法[4]、可視圖法[5]。搜索策略方面主要包括A*算法[6-7]、dijkstra算法[8]、蟻群算法(Ant Colony Optimization, ACO)[9-10]、粒子群算法[11]等較為常用。文獻[10]采用一種改進蟻群算法，通過自適應的信息素更新機制，算法的全局搜索能力被提高，但算法的收斂速度卻依然較慢。文獻[11]提出了一種將粒子群算法與模擬退火算法、遺傳算法相結合的方法，在一定程度上提高了算法的尋優(yōu)能力，但算法操作復雜度也相應增加了。本文首先利用可視圖法進行環(huán)境建模，而后采用改進蟻群算法進行路徑搜索。針對蟻群算法搜索效率低的缺點，利用A*算法尋優(yōu)速度快及蟻群算法易于與其它算法相結合的特點，采用A*算法與蟻群算法的混合蟻群算法。即先采用A*算法搜索出一條較優(yōu)路徑，以這條次優(yōu)路徑作為蟻群算法迭代搜索的初始路徑，避免了蟻群算法在初期搜索的盲目性，大幅度提升蟻群算法的尋優(yōu)能力。為了避免使用蟻群算法時陷入局部最優(yōu)而導致算法停滯，本文對節(jié)點轉(zhuǎn)移概率公式的啟發(fā)函數(shù)加以改進，引入全局距離參數(shù)。同時為了提高算法收斂速度，本文提出一種面向?qū)ο蟮男畔⑺馗乱?guī)則，只對非最優(yōu)路徑上的信息素量進行削減。最后，通過實例分析，驗證了本文提出的混合蟻群算法在AGV路徑規(guī)劃問題上的有效性。

1 環(huán)境建模

本文利用可視圖法建立AGV車間路徑規(guī)劃的二維空間模型，環(huán)境模型如圖1所示。

圖1 環(huán)境模型圖

圖中S、T分別表示AGV的起始點和目標點，黑色區(qū)域表示障礙區(qū)域，不同障礙區(qū)域頂點之間的虛線即可視線如AB?？梢晥D法將AGV視為一點，將障礙物多邊形的各頂點進行鏈接，并保證這些鏈接線與障礙物均不相交，這樣就形成了一張網(wǎng)絡圖，稱為可視圖[12]。搜索最優(yōu)路徑的問題便轉(zhuǎn)化為在可視圖的基礎上利用搜索算法，尋找一條從起始點穿過可視圖中部分可視線到達目標點的最短路徑問題。由于搜索到的路徑是穿過可視線的，即保證了這些路徑均是無碰撞路徑。

2 混合蟻群算法

2.1 算法原理

混合蟻群算法共包括兩個階段，是A*算法和蟻群算法的結合，運用兩種算法的特點和優(yōu)勢來求解AGV最優(yōu)運動路徑。

第一階段為A*算法，A*算法是一種啟發(fā)式搜索算法，其適用于靜態(tài)路網(wǎng)環(huán)境。它的根本思想是通過運用啟發(fā)式搜索的方式來找尋恰當?shù)膯l(fā)函數(shù)，其計算和評估各個擴展節(jié)點的代價來選擇代價值最優(yōu)的結點并加以擴展，直到目標節(jié)點被找到為止。在路徑搜索問題中，當前節(jié)點到目標點的代價值即路徑長度的評估值就通過啟發(fā)函數(shù)來計算獲得。

第二階段為改進蟻群算法，本文針對傳統(tǒng)蟻群算法存在的缺陷與不足，做出若干改進。

2.1.1 節(jié)點轉(zhuǎn)移規(guī)則

本文針對蟻群算法易陷入局部最優(yōu)導致算法停滯現(xiàn)象的不足，采用新的節(jié)點轉(zhuǎn)移規(guī)則，以增強算法的全局搜索能力，便于算法跳出局部最優(yōu)。

在傳統(tǒng)蟻群算法中，節(jié)點轉(zhuǎn)移概率[13]由兩節(jié)點連接路徑上的信息素量τij和啟發(fā)函數(shù)ηij共同決定，且一般令ηij=1/dij，這樣啟發(fā)函數(shù)僅由單一的距離參數(shù)dij來決定，而dij只能反映節(jié)點i周圍的局部信息。在某些情況下，節(jié)點i與節(jié)點j的距離短，并不意味著節(jié)點j到目標點T的距離短。如圖2所示，起始點S到目標點T有兩條路徑，路徑L1上的第一個節(jié)點距S較遠，路徑L2上的第一個節(jié)點距S較近，如果按照傳統(tǒng)蟻群算法的節(jié)點轉(zhuǎn)移規(guī)則，最后搜索到的很可能是路徑L2，但實際上L2的長度是大于L1的長度的。

圖2 節(jié)點轉(zhuǎn)移矢量圖

(1)

其中，i、j為鏈接線上所有點的集合；α為信息素重要程度因子；β為啟發(fā)函數(shù)重要程度因子；I為螞蟻下一步選擇節(jié)點的集合。

2.1.2 信息素更新規(guī)則

為了克服傳統(tǒng)蟻群算法收斂速度慢的不足，本文引入一個常數(shù)μ，0<μ<1,其作用是減小目前非最優(yōu)路徑上的信息素增量。于是最優(yōu)路徑上的信息素增長優(yōu)勢得到加強，在保證算法全局搜索能力的情況下，加快了算法的收斂速度。新的信息素更新規(guī)則如式(2)所示：

(2)

(3)

其中，Q為常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量；dij表示節(jié)點i與節(jié)點j之間的距離。

2.2 算法流程

綜合上述描述得到混合蟻群算法，算法流程圖如圖3所示。

圖3 算法流程圖

首先采用可視圖法建立AGV運動環(huán)境模型，并運用A*算法在環(huán)境模型中搜索出一條較優(yōu)路徑；然后將其作為改進蟻群算法的初始路徑，同時根據(jù)新節(jié)點轉(zhuǎn)移公式尋找蟻群運動節(jié)點，直至到達目標點；最后在迭代次數(shù)到達限定后輸出算法求得的最優(yōu)路徑。

3 案例應用及分析

3.1 問題描述

將某車間AGV的工作環(huán)境作平面化處理，得到一個100 m×100 m的二維空間，該二維空間分布了一些障礙物，將這些障礙物進行區(qū)域劃分，得到4個障礙區(qū)域，現(xiàn)需為AGV規(guī)劃出一條從起始點S到目標點T避開障礙物且盡可能短的路徑。S、T以及障礙區(qū)域的位置可通過測量得知。

3.2 仿真環(huán)境及環(huán)境模型

為了驗證混合蟻群算法在AGV運動規(guī)劃方面的優(yōu)越性及有效性，采用MATLAB軟件進行仿真。仿真環(huán)境：利用MATLAB R13a,在Intel(R) Core(TM) i5-3210M CPU @ 2.50GHZ、4.00GB內(nèi)存、Window 7操作系統(tǒng)下進行仿真驗算。建立適當?shù)钠矫嬷苯亲鴺讼?，測得S、T以及障礙區(qū)域頂點的坐標，利用可視圖法，在MATLAB R13a上進行環(huán)境建模，如圖4所示。

圖4 環(huán)境模型圖

圖4中虛線L1，L2，……,L16為可視圖鏈接線，鏈接線上的“*”為該鏈接線的中點，黑色區(qū)域即障礙區(qū)域。

3.3 A*算法規(guī)劃較優(yōu)路徑

采用可視圖法建立環(huán)境后，在MATLAB上運用A*算法搜索較優(yōu)路徑，為降低算法運算的復雜度，以可視圖各鏈接線的中點作為A*算法路網(wǎng)中的擴展節(jié)點，圖5為利用A*算法得到的搜索結果。

圖5 環(huán)境模型圖

圖中粗虛線即搜索到的較優(yōu)路徑，該路徑從起始點S出發(fā)，依次經(jīng)過L1、L2、L3、L4、L9、L10、L14、L15的中點，最后到達目標點T，該路徑總長度為107.4 m。

3.4 改進蟻群算法搜索最優(yōu)路徑

以A*算法得到的上述路徑作為改進蟻群算法的初始路徑，并進行最優(yōu)路徑搜索。同時針對原AGV路徑規(guī)劃問題，用同樣的方法進行環(huán)境建模，再利用傳統(tǒng)蟻群算法進行路徑尋優(yōu)。傳統(tǒng)蟻群算法和混合蟻群算法求得的最優(yōu)路徑比較如圖6所示。

圖6 路徑搜索結果對比圖

為了便于分析將兩種算法的迭代曲線求出并放在一起進行比較，如圖7所示。

圖7 算法迭代結果

圖6和圖7中細實線代表混合蟻群算法的結果，粗實線則代表傳統(tǒng)蟻群算法的結果。

3.5 結果分析

將以上兩種方法得到的路徑規(guī)劃結果的相關數(shù)據(jù)進行統(tǒng)計，具體見表1所列。

表1 算法結果對比

上述統(tǒng)計結果表明，本文提出的混合蟻群算法搜索到的最優(yōu)路徑比傳統(tǒng)蟻群算法在路徑長度上得到了明顯改善，符合本文AGV路徑規(guī)劃問題的目標要求。并且經(jīng)過改進后的蟻群算法在大約第98次循環(huán)迭代之后，就開始達到最優(yōu)路徑，而傳統(tǒng)蟻群算法在大約第252次循環(huán)迭代之后，才開始趨于最優(yōu)路徑。即本文的混合蟻群算法不僅搜索的路徑更優(yōu)，在算法收斂速度方面也具有明顯優(yōu)勢。為了更好的比較傳統(tǒng)蟻群算法和混合蟻群算法的性能，將兩種算法在同樣的實驗條件下運行5次，得到的結果見表2所列。

表2 算法結果對比

由表2數(shù)據(jù)可知，傳統(tǒng)蟻群算法求取的最優(yōu)路徑長度穩(wěn)定在95 m左右，相較之下混合蟻群算法求取的最優(yōu)路徑長度則在83 m左右。且混合蟻群算法所需的迭代次數(shù)要遠遠小于傳統(tǒng)蟻群算法。此外由于本文提出的AGV路徑規(guī)劃問題沒有對環(huán)境作限制，沒有明確規(guī)定障礙物的位置，因而具有現(xiàn)實的普適意義，從而證明了本文混合蟻群算法在解決AGV路徑規(guī)劃問題方面的有效性。

4 結論

文章提出了一種基于混合蟻群算法的AGV路徑規(guī)劃研究方法。在傳統(tǒng)蟻群算法的基礎上，對算法中的節(jié)點轉(zhuǎn)移概率公式以及信息素更新方式加以改進，并利用A*算法尋優(yōu)速度快的優(yōu)點將其與蟻群算法相結合，彌補了傳統(tǒng)蟻群算法收斂速度慢且易陷入局部最優(yōu)導致算法停滯的不足?；诖朔椒ㄔ贛ATLAB軟件中對實際案例進行實驗仿真，得出如下結論：混合蟻群算法可使AGV在運行過程中有效避開障礙物，并找尋出一條無碰優(yōu)化路徑；相較于傳統(tǒng)蟻群算法，混合蟻群算法規(guī)劃的路徑長度和質(zhì)量明顯優(yōu)于前者；通過算法迭代圖和多次對比試驗，表明混合蟻群算法具有較好的收斂性和較高的搜索效率等優(yōu)點。