基于改進蟻群算法的移動機器人路徑規(guī)劃

徐宏宇,唐澤坤,葉長龍

(沈陽航空航天大學(xué)1.電子信息工程學(xué)院，2.機電工程學(xué)院，沈陽 110136)

科技發(fā)展帶動機器人技術(shù)的進步，智能移動機器人已經(jīng)成為眾多學(xué)者的研究重點,倉儲搬運機器人也隨之進入人們視野。能夠讓機器人良好地解決其在不同工作環(huán)境下的路徑規(guī)劃問題十分關(guān)鍵。讓機器人在有障礙物的環(huán)境中，規(guī)劃出一條從起始點到目標(biāo)點的連續(xù)的、無碰撞的最優(yōu)或次最優(yōu)路徑[1]。對于解決路徑規(guī)劃問題的算法已經(jīng)被學(xué)者提出，如A*算法[2-3]、人工勢場法[4-5]等傳統(tǒng)算法，以及近些年學(xué)者提出的仿生算法也應(yīng)用在路徑規(guī)劃中，如遺傳算法[6]、粒子群算法[7]、蟻群算法等。

意大利學(xué)者Marco Dorigo受到自然界中真實蟻群集體行為的啟發(fā)，于1991年首次提出基于蟻群的新型優(yōu)化算法[8]。由于蟻群算法是一種隨機搜索尋優(yōu)算法，具有信息正反饋機制，能夠進行并行計算，并且魯棒性強等特點，在機器人路徑規(guī)劃上的研究取得了很好的成果。如在文獻[9]中將算法應(yīng)用于機器人搜救,使得其在復(fù)雜的障礙環(huán)境中也能正確到達目標(biāo)點。但傳統(tǒng)蟻群算法也存在一些缺陷，如計算周期長、收斂速度慢、出現(xiàn)局部最小化等問題。針對算法這些缺陷許多學(xué)者進行了改進研究。文獻[10]分析闡述了算法的主要參數(shù)對結(jié)果的影響，通過數(shù)據(jù)統(tǒng)計對比分析得到優(yōu)化的算法參數(shù)組合；文獻[11]采用螞蟻回退策略來杜絕遇到U型障礙物時容易陷入死鎖現(xiàn)象，導(dǎo)致蟻群算法停滯的問題；文獻[12]通過引入最大、最小蟻群系統(tǒng)對更新的信息素濃度進行限制，解決了蟻群算法中因信息素差異過大而陷入“早熟”的問題；文獻[13]將蟻群算法與遺傳算法進行融合，將遺傳算法的全局搜索能力和群算法的快速收斂互補，實現(xiàn)快速搜索。

本文提出一種蟻群算法的自適應(yīng)啟發(fā)式函數(shù)，引入自適應(yīng)權(quán)重的目標(biāo)點吸引評估，對尋優(yōu)螞蟻實行獎勵提高信息素，以提高算法的收斂速度、全局搜索能力，并引入轉(zhuǎn)向代價，以進一步縮短所尋路徑并起到平滑處理的作用。針對死鎖問題，通過A*算法隨機對死鎖螞蟻進行輔助實現(xiàn)復(fù)活。通過MATLAB仿真與傳統(tǒng)算法對比驗證，得出改進算法在路徑規(guī)劃的準(zhǔn)確性以及快速收斂能力。

1 環(huán)境模型建立

利用柵格法[14]將外部環(huán)境抽象離散化建立機器人二維運動環(huán)境模型，使復(fù)雜問題簡單化，減少數(shù)據(jù)的計算量。

首先將室內(nèi)環(huán)境抽象成二維平面，在靜態(tài)二維地圖中將地圖按照一定步長分割，并將環(huán)境用黑白網(wǎng)格表示。黑色網(wǎng)格代表障礙物不可同行區(qū)域；白色網(wǎng)格則代表可通行區(qū)域，又稱自由行駛區(qū)域。將不可行區(qū)域和自由行駛區(qū)域用一個二進制矩陣表示，矩陣中1代表障礙物，0代表自由柵格，由此在環(huán)境中建立一個可描述環(huán)境的路徑規(guī)劃地圖如圖1所示。

圖1 柵格地圖

以自身所在柵格為中心的8個節(jié)點任由機器人選擇，如圖2所示。

圖2 機器人運動方向

左下角第一個柵格的序號為1，依次向右序號增加，則序號1的柵格坐標(biāo)是(0.5,0.5)，序號5的柵格坐標(biāo)是(4.5,0.5)，序號6的柵格坐標(biāo)是(0.5,1.5)，依次類推，則柵格序號對應(yīng)的節(jié)點坐標(biāo)關(guān)系如公式(1)所示。

(1)

2 蟻群算法及改進

2.1 蟻群算法的基本原理

自然界的螞蟻覓食過程中，能在其走過的路徑上分泌一種化學(xué)物質(zhì)稱為信息素[15]。信息素會留在螞蟻所經(jīng)過的路線并保留一段時間，引導(dǎo)螞蟻的運動方向，使螞蟻傾向于朝著信息素濃度大的方向選擇。同時一些螞蟻會開辟新的道路，當(dāng)尋找到更短的道路后，相同時間內(nèi)較短路徑上信息素含量高，逐漸吸引更多的螞蟻到這條道路。如此重復(fù)，最后使得最短的道路被保留下來。

2.2 蟻群算法模型

(2)

螞蟻完成一次循環(huán)后進行信息素的更新，各路徑信息素根據(jù)下式進行調(diào)整

τij(t+1)=(1-ρ)τij(t)+Δτij

(3)

(4)

(5)

其中，ρ表示揮發(fā)系數(shù)，通常設(shè)置ρ<1來避免軌跡上的信息量無限累加；Δτij表示本次循環(huán)中節(jié)點i到節(jié)點j的信息素增量；Q是定值表示信息素總量；Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。

2.3 蟻群算法的改進

針對基本蟻群算法的收斂速度慢、容易局部最優(yōu)的缺點，本文提出幾點改進：(1)轉(zhuǎn)移概率中加入轉(zhuǎn)彎代價；(2)節(jié)點的啟發(fā)信息改進；(3)信息素更新方式的改進。

2.3.1 改進轉(zhuǎn)移概率

機器人在運動過程中轉(zhuǎn)彎會造成，因此要盡量避免機器人大量轉(zhuǎn)彎，增強路徑的平滑性，因此引入轉(zhuǎn)彎代價評估，由螞蟻在柵格中的運動方向可知，轉(zhuǎn)角只能是0°、45°、90°和135°，因此加大轉(zhuǎn)角的懲罰力度。轉(zhuǎn)彎代價值如公式，轉(zhuǎn)彎角度越小，被選中的概率越大，改進后的節(jié)點轉(zhuǎn)移概率公式如下

(6)

(7)

2.3.2 啟發(fā)函數(shù)的改進

在柵格地圖中僅使用相鄰柵格構(gòu)造的啟發(fā)函數(shù)差異較小，造成算法搜索效率低。因此利用A*算法中目標(biāo)節(jié)點對待選節(jié)點的影響引入到啟發(fā)函數(shù)，由此來加快蟻群算法的收斂速度，提高效率。通過利用到當(dāng)前節(jié)點、轉(zhuǎn)移節(jié)點、目標(biāo)節(jié)點的歐氏距離來構(gòu)造評價函數(shù)，改進后的算法啟發(fā)函數(shù)見以下公式

(8)

(9)

其中，dij為節(jié)點i和節(jié)點j之間的歐氏距離，djE為節(jié)點j和終點E之間的歐氏距離。將轉(zhuǎn)移節(jié)點與目標(biāo)節(jié)點的關(guān)系添加到啟發(fā)函數(shù)中，使得螞蟻在運動過程中更具有方向性。ω權(quán)重值根據(jù)路徑動態(tài)調(diào)整，可以讓螞蟻隨著目標(biāo)的接近方向感越強，提高算法的效率。

2.3.3 改進信息素分配機制

傳統(tǒng)蟻群算法在信息素更新時是將所有路徑的信息素進行更新，這樣使得步長較長的路徑上的信息素也得以更新，這就導(dǎo)致所有探索到的路徑信息素含量差別較小，最優(yōu)路線對后續(xù)螞蟻吸引力弱，導(dǎo)致無法快速收斂。為了增加路徑的吸引力，本文使用了信息素獎勵機制，對本次迭代的最優(yōu)路徑和所有路徑中最優(yōu)路徑進行獎勵，增加其路徑上的信息素量。改進的信息素分配方式如式(10)。

(10)

3 改進算法步驟

步驟1：柵格地圖的構(gòu)建，建立對應(yīng)的描述矩陣用于存儲障礙物情況。

步驟2：對種群數(shù)量M，迭代次數(shù)k,軌跡的重要性α，路徑的能見度β，轉(zhuǎn)折代價因子γ，信息素的揮發(fā)系數(shù)ρ，信息量Q以及起始點這些參數(shù)的初始化。

步驟3：將螞蟻種群放置在起點。

步驟4：根據(jù)公式(7)選擇下一節(jié)點，運用公式(6)記錄轉(zhuǎn)折代價同時記錄拐點。

步驟5：更新運動節(jié)點禁忌表并判斷螞蟻是否運動至目標(biāo)節(jié)點，如若螞蟻無路可走判定該螞蟻死亡并執(zhí)行步驟6。

步驟6：隨機選擇是否進行操作，若未被選擇，則此螞蟻徹底死亡。若被選擇，借助A*算法進行從死亡節(jié)點到目標(biāo)點的局部路徑規(guī)劃，實現(xiàn)此螞蟻的“偽存活”，并將局部路線與已經(jīng)探索路線進行拼接融合。

步驟7：記錄目前為止最短路徑，同時記錄本種群中最短路徑，利用公式(5)和公式(10)對全局信息素進行更新。

步驟8：判斷是否達到最大迭代次數(shù)，條件成立則輸出最優(yōu)路徑，否則執(zhí)行步驟(2)。

算法流程圖如圖3所示。

圖3 算法流程圖

4 算法仿真分析

為了驗證本文改進蟻群算法性能，本文使用MATLAB2014a仿真軟件,利用上文提到的柵格法構(gòu)建環(huán)境模型，在相同環(huán)境下對兩種算法進行大量仿真對比驗證。

4.1 參數(shù)選擇

蟻群算法的參數(shù)選擇對算法實際應(yīng)用效果有著重要影響，而參數(shù)的設(shè)置主要還是通過統(tǒng)計和經(jīng)驗值，而蟻群算法中重要的參數(shù)有螞蟻數(shù)目M，軌跡的重要性啟發(fā)因子α，路徑的能見度因子β，以及揮發(fā)系數(shù)ρ，這些系數(shù)的不同組合直接影響著路徑的最優(yōu)效果。

螞蟻數(shù)量的多少影響著算法的穩(wěn)定性，但螞蟻數(shù)目增加，算法的收斂速度降低影響到算法的運算效率，而螞蟻數(shù)量過少又無法準(zhǔn)確地尋找出最優(yōu)路徑。啟發(fā)因子α過高會導(dǎo)致螞蟻對路徑上信息素更加敏感而忽略路徑節(jié)點距離代價，啟發(fā)因子β過高則導(dǎo)致螞蟻只注重節(jié)點距離而忽略其他節(jié)點信息素的誘導(dǎo)，因此要設(shè)置好合理的α與β的比例關(guān)系。揮發(fā)系數(shù)ρ對算法的隨機選擇產(chǎn)生影響，ρ設(shè)置過大導(dǎo)致信息素損失過快，降低先前探索路徑的吸引力。通過大量計算機仿真、組合、統(tǒng)計確定參數(shù)，選擇參數(shù)如下：M=20，α=1，β=8，ρ=0.45。

4.2 仿真

此次仿真搭建了規(guī)模為20×20的兩種不同的工作環(huán)境，在相同環(huán)境下將兩種算法進行仿真對比。兩種算法在不同環(huán)境下分別仿真20次，并對數(shù)據(jù)進行比對分析。

圖4為在障礙物較為集中的環(huán)境地圖下算法路徑搜索結(jié)果和迭代效果，圖5是障礙物相對復(fù)雜分散環(huán)境下的算法比較。改進的蟻群算法與傳統(tǒng)蟻群算法分別由星型線和實線表示。通過仿真圖的比較可以看出，改進的蟻群算法與傳統(tǒng)蟻群算法比較，在不同的環(huán)境中改進算法均體現(xiàn)出良好的路徑搜索能力。表1給出了兩種算法在不同環(huán)境下分別運行20次的數(shù)據(jù)統(tǒng)計。兩種算法均找出最短路徑，但從多次算法的最優(yōu)解次數(shù)來看，本文改進的蟻群算法具有良好的準(zhǔn)確性、穩(wěn)定性。從算法的迭代效果來看，算法在整體上呈現(xiàn)收斂趨勢，在初期出現(xiàn)波動變化，在后期逐漸趨于穩(wěn)定。傳統(tǒng)蟻群算法收斂速度緩慢，而且在收斂中期還會出現(xiàn)小幅度的波動現(xiàn)象。而本文算法在初期路徑探索后，快速穩(wěn)定的收斂到最優(yōu)值，并且改進的蟻群算法在轉(zhuǎn)彎次數(shù)上少于傳統(tǒng)算法，對路線進行了平滑處理。

圖4 簡單環(huán)境下實驗效果與迭代收斂

圖5 復(fù)雜環(huán)境下實驗效果與迭代收斂

環(huán)境算法最優(yōu)解最差解平均值平均拐點數(shù)平均迭代收斂數(shù)最優(yōu)解次數(shù)環(huán)境1傳統(tǒng)算法34.384838.799037.224412383改進算法34.384834.384834.384810920環(huán)境2傳統(tǒng)算法30.384840.041638.524814496改進算法30.384830.384830.384811920

5 結(jié)論

文章中利用柵格法構(gòu)建二維環(huán)境地圖，為算法提供環(huán)境基礎(chǔ)，研究分析傳統(tǒng)算法的不足之處后通過改進自適應(yīng)啟發(fā)式函數(shù)，引入自適應(yīng)權(quán)重的目標(biāo)點吸引評估，使螞蟻在路程前期有足夠探索能力，離目標(biāo)點越近方向感增強快速收斂。對尋得最優(yōu)路徑螞蟻的獎勵制度增加了最優(yōu)路徑的吸引力，達到快速收斂。設(shè)置運動方向引入轉(zhuǎn)向代價，減小了運動過程中不必要的轉(zhuǎn)彎，實現(xiàn)路徑平滑，解決在搜索初期螞蟻死鎖問題，借助A*算法隨機性的對死鎖螞蟻進行輔助實現(xiàn)“偽存活”的措施對傳統(tǒng)算法進行改進優(yōu)化。

利用MATLAB對算法進行仿真對比后可以看出，改進后的蟻群算法不僅提高算法的收斂速度、全局搜索能力，還進一步減少路徑上不必要的轉(zhuǎn)向，起到平滑處理的作用，具有足夠的準(zhǔn)確性和穩(wěn)定性，實驗結(jié)果良好。