改進蟻群算法用于移動機器人路徑規劃時的研究

杜 磊，史健芳

(太原理工大學 信息與計算機學院，山西 晉中 030600)

移動機器人作為自動化控制和人工智能領域的重要產物，是近年來最熱門的研究領域之一。隨著相關技術研究的深入，移動機器人的功能得到了極大的豐富，性能也更加完善，已經被廣泛應用到農業，工業，交通運輸，醫療救助，國防軍事等行業。路徑規劃是移動機器人的核心技術之一，其優劣程度直接影響到移動機器人的性能水平，是其能夠高效、可靠工作的重要條件。目前，路徑規劃中常用的算法大概分為4類：經典算法，如人工勢場法[1]、模擬退火法[2]等；圖形法，如voronoi圖法[3]、深度優先搜索算法等；智能算法，如神經網絡法[4]、遺傳算法[5]、蟻群算法、粒子群算法[6]和人工魚群算法[7]等；其他算法，如Dijkstra鏈法[8]、A*[9]法等。蟻群算法作為典型的路徑規劃算法，能夠對路徑進行分布式搜索，具備很強的全局搜索能力，但依然存在一些缺陷，例如運算時間長，容易出現“早熟”現象等，導致移動機器人搜索的路徑效果不夠好，工作效率低[10]。現有改進蟻群算法通過對算法本身更加細致地調整，雖然改善了運算效果，但是使得算法更加復雜，規劃路徑時需要經過更長的時間[11]。例如在帶精英策略的螞蟻系統中提出的“精英螞蟻”概念，能夠提高已經獲得較好解的螞蟻對之后螞蟻的指導性，從而提高收斂速度，但它不僅提高了運算的復雜程度，還讓蟻群更容易發生“早熟”。又如一種引入“遺傳因子”的改進蟻群算法，利用“遺傳、變異”思想對蟻群算法的結果進行二次優化，雖然提高了尋優能力，但也將運算時間翻了幾倍。本文針對上述問題，利用鳥群算法搜索效率高的優點，研究了一種將鳥群算法(BSA)與蟻群算法(ACO)相融合的改進算法，并且利用自適應期望函數來優化路徑質量，極大程度地發揮兩者各自的優點，避其不足，能夠更高效、更快捷地求解出更優的路徑，在移動機器人路徑規劃中發揮更大的作用。

1 環境建模

柵格法對障礙物環境的表示簡單直接，是環境建模中最常用的方法之一。本文使用柵格法建模，對障礙物的形狀作適當擴充，執行預處理。當障礙物過小，不能占滿單個柵格時，將此柵格填滿。當障礙物內部存在小型凹陷空間時，機器人進去之后無法找到出路，需要對其作填充處理。圖1表示了一些預處理前后障礙物環境的情況，其中白色柵格為自由柵格，可供機器人選擇，黑色區域表示障礙物的位置。

(a) 預處理前 (b) 預處理后圖1 預處理前后的障礙物環境Fig.1 Obstacle environment before and after preprocessing

2 改進蟻群算法的路徑規劃

由于蟻群算法的原始信息素分布為整個地圖范圍內的均勻分布，螞蟻在第一次尋找路徑時等概率地選擇下一個節點，是導致算法收斂緩慢的重要原因之一。為了優化蟻群算法的路徑質量又不過度增加算法的運行時間，本文引入收斂極快的鳥群算法，先用鳥群算法在地圖上進行一次快速路徑搜索，再參照其結果制定蟻群算法的原始信息素分布，并且針對蟻群算法中相鄰節點的期望函數對螞蟻啟發程度差異不明顯的問題，提出自適應期望函數思想，在一定程度上縮短運算的時間。

2.1 鳥群算法的路徑預規劃

1) 覓食行為。所有鳥隨機性地進行覓食或警覺。鳥在覓食過程中會同時參考自己的經驗和群體的經驗。

(1)

式中：j∈[1,…,D]，C為認知因子，S為社會進化因子，rand(0,1)是0～1范圍內的隨機矩陣，pi,j表示第i只鳥的個體最優解，gj表示群體最優解。

2) 警覺行為。處于警覺中的鳥會嘗試著向群體的中心位置飛行，同時會產生與其他鳥之間的競爭。

(2)

(3)

(4)

式中：k為1到N之間不等于i的隨機整數，a1，a2為0到2之間的常數，meanj為群體最優位置，pFi為個體最佳適應度值，sumF為種群適應度值之和，ε為最小常數，防止分母為0.

3) 遷徙行為。所有鳥都會按照食物的儲存量劃分成兩類，即覓食者、追隨者。設鳥群飛往其他地方覓食的時間間隔為FQ.當時刻t為FQ的整數倍時，鳥群遷徙，否則覓食或保持警惕。到達后，覓食者開始繼續尋找食物，追隨者跟隨覓食者飛行。覓食者和追隨者的數學表示如下。

(5)

(6)

式中：randn(0,1)表示均值為0，方差為1，服從標準正態分布的隨機矩陣，FL(FL∈[0,2])表示追隨者會跟隨覓食者飛行。

在路徑規劃中，將路徑長度作為適應度函數的值是最直接、最有效的方法。因此，本文使用解中所有點的距離之和作為適應度函數，即將無碰路徑的長度作為對應適應度函數值的大小。

(7)

式中：(xi,yi)表示i時刻鳥的位置，(xi+1,yi+1)表示i+1時刻鳥的位置，n為路徑點數目。

圖2表示了將預規劃產生的路徑轉化為ACO信息素的過程，其中左圖為BSA生成的路徑，右圖為由它轉化成的原始信息素分布，白色方格表示提前生成的均勻信息素分布，灰色方格為在此基礎上增強的信息素分布。若螞蟻所在位置的相鄰方格中既有白色方格又有灰色方格，則有更大的概率選擇灰色方格，使它走過的路徑更接近最優路徑，對之后經過的螞蟻有更加正向的引導。

(a) 生成的路徑 (b) 轉化成的信息素圖2 路徑轉化為信息素Fig.2 Transform the path into a pheromone

2.2 自適應期望函數的引入

機器人的行進方式有8種，如圖3所示。假設起始點為“s”，目標點為“g”，機器人現在的位置為“0”，則下一步的位置只能從“1”到“8”這8個位置里挑選。在情況允許的條件下，為了確保路徑最短，機器人盡量選擇“1”，“2”，“3”這3個位置，避免出現“迂回”的情況。

ACO中，螞蟻m在第i個節點對第j個節點的選擇概率是：

(8)

(9)

式中：η(i,j)是期望函數，表示節點i與j之間的期望值，dij節點是i到j的距離。α是信息素啟發因子，β是期望啟發因子。Ji表示下一個節點可選擇的范圍。

圖3 機器人的行進方式Fig.3 Moving method of robot

由于期望函數僅和兩節點之間的距離有關，而相鄰節點之間的距離差異很小，所以在選擇節點時對螞蟻的啟發程度不夠，這是造成ACO搜索效率不高的又一因素。例如在圖3中，螞蟻選擇“1”，“2”，“3”這3個位置的概率沒有明顯高于其他位置。為了增大相鄰節點之間選擇概率的差距，本文引入自適應期望函數，并對相鄰節點的期望函數進行不同比例的放大，以增加優勢節點被選擇的概率，改善路徑的搜索結果。自適應期望函數表示為：

(10)

(11)

式中：ω是期望系數；N表示節點的列數；Dj指節點j到終點的距離。

2.3 改進蟻群算法的流程

改進蟻群算法的主要流程如下：

1) 根據創建的地圖和限制條件，利用BSA實施快速路徑預規劃，為后續的ACO提供引導。

2) 將預規劃出的路徑轉換為信息素，與ACO的原始信息素分布相融合。

τ(i,j)=τs(i,j)+ΔτB(i,j) .

(12)

式中：τ(i,j)表示i-j上的信息素濃度，τs(i,j)為i-j上的原始信息素，ΔτB(i,j)是指i-j中把BSA搜索的結果轉換出的信息素增量。

3) 按照式(8)，螞蟻利用輪盤賭的方法選擇下一步移動到的節點，其概率為Pm(i,j).其中，自適應期望函數η(i,j)的值由式(10)和式(11)確定。

4) 所有螞蟻都搜索到路徑之后，在已有信息素基礎上增加這一代螞蟻生成的信息素，完成全局的信息素更新。

τk+1(i,j)=(1-ρ)τk(i,j)+Δτ(i,j) .

(13)

(14)

(15)

式中：ρ是信息素的揮發系數，Δτ(i,j)是本次迭代中i-j上增加的信息素，τk(i,j)為t=k時i-j上的信息素的濃度，Mij是所有經過i-j的螞蟻集合，Δτm(i,j)為這一次迭代中螞蟻m在i-j上產生的信息素，Lm為螞蟻經過點的距離之和，即路徑總長度，Q為常數。

5) 進行迭代，每次迭代后將螞蟻從終點放回到起點，準備下一次搜索。迭代次數到達上限后，找出長度最短的路徑。

3 仿真結果與分析

在ACO中，所有參數都有其獨特的作用。參數之間相互關聯，任何一個參數發生變化都會牽連到其他參數的取值，進而很大程度上影響算法的性能。因此，合理的參數配置是蟻群算法能夠高效、穩定地得到最優解的重要保障。經過多次實驗，得到了以下參數的最佳取值范圍：ρ：[0.2-0.5]；α：[0.8-2.1]；β：[1-5].為了與其他算法相比較，其他參數按照最常用的取值設定。

經過選擇與比較，仿真實驗的參數設置為：1) 蟻群算法：最大迭代次數NC=50，蟻群規模m=30，α=1.5，β=5，ρ=0.2，信息素增強系數Q=14；2) 鳥群算法：最大迭代次數M=200，種群規模spop=100，鳥群遷徙頻率fQ=10，認知因子C=1.5，社會進化因子S=1.5，常數a1=a2=1.

3.1 算法對比

實驗中，將ACO、BSA、粒子群算法(PSO)、粒子群蟻群融合算法(PSO+ACO)以及本文提出的改進蟻群算法(BSA+ACO)在相同的搜索環境下展開全面對比。圖4為5種算法找到的最佳路徑，其結果由表1所示。由此可以得到，改進ACO的優勢非常明顯，不僅得到了5種算法中最短的路徑，而且路徑的轉彎次數比較少，沒有銳角的拐點，平滑度最高。

圖4 5種算法效果對比Fig.4 Comparison of the effect of five algorithms

3.2 特殊搜索環境的路徑規劃

圖5表示了一種在障礙物的約束下產生了迂回道路的情況。在這種特殊情況下，基本蟻群算法無法生成有效路徑，而本文算法由于利用了鳥群算法全局性強的特點，為后續蟻群算法提供引導，能夠規劃出有效路徑，具備處理這種特殊情況的能力。

表1 各種算法結果對比Table 1 Comparison of the results of various algorithms

圖5 本文算法處理迂回路徑的情況Fig.5 Method of processing circuitous path by improved ant colony algorithm

圖6和圖7表示了搜索環境里出現大型凹陷障礙物的情形。由于大型障礙物中存在大面積的“陷阱”空間，容易導致螞蟻進入其中做無用的路徑搜索，最終影響算法整體的運算結果。本文算法中螞蟻受到鳥群算法快速生成的路徑指引，從第一代開始就減小了進入“陷阱”空間的概率，從而大幅提高了算法的有效性。從圖6和圖7中可以看出，基本蟻群算法得到的路徑依然存在進入“陷阱”區域的現象，而本文算法沒有受到“陷阱”的影響。

圖6 基本蟻群算法得到的路徑Fig.6 Path obtained by the basic ant colony algorithm

圖7 改進蟻群算法得到的路徑Fig.7 Path obtained by improved ant colony algorithm

4 結束語

針對ACO在移動機器人路徑規劃中出現的搜索結果不理想，在極端情況下無法生成有效路徑等不足，提出了一種改進ACO，先通過BSA快捷、有效地構建原始信息素分布，然后利用ACO開展全面、深入地搜索，很大程度上避免了蟻群搜索初期的盲目性，縮短了路徑長度，改善了路徑質量，在一些特殊的障礙物環境中具備更強的全局搜索能力。并且引入了自適應期望函數，進一步改善了路徑質量。實驗結果表明，該算法在移動機器人全局路徑規劃的應用中是可行的、有效的。