改進(jìn)蟻群算法用于移動機器人路徑規(guī)劃時的研究

杜 磊，史健芳

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

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

1 環(huán)境建模

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

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

2 改進(jìn)蟻群算法的路徑規(guī)劃

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

2.1 鳥群算法的路徑預(yù)規(guī)劃

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

(1)

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

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

(2)

(3)

(4)

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

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

(5)

(6)

式中：randn(0,1)表示均值為0，方差為1，服從標(biāo)準(zhǔn)正態(tài)分布的隨機矩陣，F(xiàn)L(FL∈[0,2])表示追隨者會跟隨覓食者飛行。

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

(7)

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

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

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

2.2 自適應(yīng)期望函數(shù)的引入

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

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

(8)

(9)

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

圖3 機器人的行進(jìn)方式Fig.3 Moving method of robot

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

(10)

(11)

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

2.3 改進(jìn)蟻群算法的流程

改進(jìn)蟻群算法的主要流程如下：

1) 根據(jù)創(chuàng)建的地圖和限制條件，利用BSA實施快速路徑預(yù)規(guī)劃，為后續(xù)的ACO提供引導(dǎo)。

2) 將預(yù)規(guī)劃出的路徑轉(zhuǎn)換為信息素，與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搜索的結(jié)果轉(zhuǎn)換出的信息素增量。

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

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

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

(13)

(14)

(15)

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

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

3 仿真結(jié)果與分析

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

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

3.1 算法對比

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

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

3.2 特殊搜索環(huán)境的路徑規(guī)劃

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

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

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

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

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

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

4 結(jié)束語

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