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

張 毅，李 奎，黃 超

(重慶郵電大學(xué) 先進制造工程學(xué)院，重慶 400065)

0 引 言

隨著國家經(jīng)濟的發(fā)展以及對機器人領(lǐng)域的重視，國內(nèi)移動機器人技術(shù)發(fā)展相當(dāng)快，也滲透到各個行業(yè)中[1-2]。根據(jù)移動機器人的導(dǎo)引方式不同，有激光導(dǎo)引、電磁導(dǎo)引、視覺導(dǎo)引、慣性導(dǎo)引、二維碼導(dǎo)引等。由于二維碼導(dǎo)引有成本低、柔性高、定位準(zhǔn)確、累積誤差小等優(yōu)點，本文主要對二維碼導(dǎo)引的移動機器人在結(jié)構(gòu)化柵格工作環(huán)境下的路徑規(guī)劃展開研究。

移動機器人路徑規(guī)劃一直是機器人學(xué)重要研究內(nèi)容，在過去20年里，國內(nèi)外許多學(xué)者就此展開了廣泛而深入的研究，主要的研究內(nèi)容是機器人基于不同導(dǎo)引方式、不同工作環(huán)境、不同優(yōu)化目標(biāo)下的路徑規(guī)劃問題。傳統(tǒng)的路徑規(guī)劃有A*算法和Dijkstra算法，A*算法在環(huán)境復(fù)雜的時候不一定能規(guī)劃出最優(yōu)路徑，Dijkstra算法的實質(zhì)是廣度優(yōu)先搜索，時間和空間復(fù)雜度較高。近年來，許多群體智能算法應(yīng)用在移動機器人路徑規(guī)劃中，包括神經(jīng)網(wǎng)絡(luò)算法[3]、遺傳算法[4]、粒子群算法[5]、人工勢場法[6]等，這些算法應(yīng)用在不同的環(huán)境中也有明顯的缺點和不足，例如人工勢場法容易陷入局部最優(yōu)，遺傳算法適用于全局路徑規(guī)劃，但是運行速度不快，神經(jīng)網(wǎng)絡(luò)算法收斂速度慢，計算復(fù)雜，內(nèi)存占用大。蟻群算法在解決移動機器人路徑規(guī)劃問題中是一種更成熟更有效的群體智能算法，它有啟發(fā)式搜索、魯棒性強、分布式計算、信息正反饋等優(yōu)點，但也有收斂速度慢、容易陷入局部最優(yōu)和停滯現(xiàn)象等缺點。

蟻群算法是由意大利學(xué)者Dorigo受生物進化機理的啟發(fā)而提出的一種群體智能算法，由最初的理論研究延伸到其他具體的應(yīng)用領(lǐng)域，針對蟻群算法在實際應(yīng)用中存在的問題，學(xué)者們紛紛提出了各種改進方法。文獻[7]提出了添加雙向搜索機制和比例系數(shù)引導(dǎo)因子的啟發(fā)函數(shù)，克服傳統(tǒng)蟻群算法易陷入局部最優(yōu)且收斂速度慢的影響。文獻[8]定義了一種新的動態(tài)搜索誘導(dǎo)算子，設(shè)計了動態(tài)搜索模型，加快蟻群算法的收斂速度。文獻[9]通過消除蟻群算法禁忌表限制，引入臨時權(quán)重矩陣，解決景區(qū)多景點的路徑規(guī)劃問題。文獻[10]設(shè)計了一種新的信息素強化機制，利用動態(tài)信息進行路徑優(yōu)化，在獲得解決方案的多樣性和提高算法收斂速度方面都有不錯的效果。文獻[11]通過改進蟻群算法信息素更新策略，動態(tài)調(diào)整衰減系數(shù)，提高算法的收斂速度。文獻[12]將蟻群算法和A*算法結(jié)合開發(fā)一種雙層算法，在密集障礙物的3D環(huán)境下實現(xiàn)路徑規(guī)劃。

在結(jié)構(gòu)化工作環(huán)境下，機器人只能在水平和垂直方向上移動，機器人走過的路程是當(dāng)前點到下一個點的曼哈頓距離，直接將蟻群算法應(yīng)用在此環(huán)境下存在停滯、收斂慢的問題，為了使蟻群算法能在結(jié)構(gòu)化工作環(huán)境下快速規(guī)劃出一條最優(yōu)路徑，本文對螞蟻的搜索方向進行了限制，引入自適應(yīng)期望函數(shù)和啟發(fā)因子，給出具體的算法表達式以使算法能為此環(huán)境下的機器人規(guī)劃出可行路徑，最后引入轉(zhuǎn)彎影響因子，得到擴展路徑最小的最優(yōu)路徑。實驗結(jié)果驗證了本文改進蟻群算法的可行性和準(zhǔn)確性。

1 蟻群算法環(huán)境模型

將二維碼移動機器人的結(jié)構(gòu)化柵格工作環(huán)境設(shè)定為二維平面上一個有限區(qū)域，如圖1，每一個格子就是一個二維碼，在二維碼上分布著有限個靜態(tài)障礙物(圖中有黑色圓點的格子)。圖1中的數(shù)字表示每個二維碼的ID，起始點和目標(biāo)點分別為S和T，本文路徑規(guī)劃的優(yōu)化準(zhǔn)則是綜合算法收斂速度、路徑長度和轉(zhuǎn)彎情況尋找一條從起始點到目標(biāo)點的最優(yōu)路徑，結(jié)構(gòu)化環(huán)境下機器人只執(zhí)行前進，左轉(zhuǎn)90°和右轉(zhuǎn)90°動作。例如，機器人在56號二維碼上，車頭朝著57號二維碼，則它下一步可以到達46號、66號或57號二維碼。

圖1 二維碼柵格地圖Fig.1 Two-dimensional code grid map

設(shè)機器人的工作區(qū)域由R行C列組成，序號為N的二維碼在環(huán)境柵格的行號和列號分別為i，j，記為G(i,j)，則可得表達式

i=[(N-1)/C]+1

(1)

j=(N-1)modC+1

(2)

2 蟻群算法基本原理

根據(jù)仿生學(xué)家長期研究發(fā)現(xiàn)，螞蟻有能力在沒有任何可見的提示下找出從蟻穴到食物源的最短路徑，并且能在環(huán)境變化時搜索新路徑，產(chǎn)生新的選擇。

螞蟻集群中的個體之間以及個體與環(huán)境之間的信息傳遞大部分是依賴于信息素進行，它是一種螞蟻產(chǎn)生的化學(xué)物質(zhì)。螞蟻在所經(jīng)過的路徑中留下信息素，并且能夠感知路徑中已存在的信息素濃度[12]。信息素會隨著時間的推移逐漸揮發(fā)，這一特性可增加蟻群搜索空間，可一定程度避免算法過早收斂于局部最優(yōu)解。

一條路徑上的信息素濃度越高，被其他螞蟻選擇的概率也就越大，從而該路徑上的信息素濃度進一步增強，因此，由蟻群的集體行為表現(xiàn)出一種信息正反饋現(xiàn)象。螞蟻個體之間就是通過這種間接的通信機制達到協(xié)同搜索蟻穴到食物源的最短路徑的目的[12]。

2.1 概率選擇

圖2 柵格環(huán)境模型Fig.2 Grid environment model

(3)

ηAB=1/dAB

(4)

(4)式中，dAB為A到B的歐式距離。

2.2 信息素更新過程

隨著時間流逝，信息素會慢慢揮發(fā)，用ρ表示信息素?fù)]發(fā)系數(shù)，滿足0<ρ<1，則1-ρ為信息素殘留程度，當(dāng)經(jīng)過n個時刻，所有螞蟻構(gòu)建好路徑后，各邊上信息素強度進行更新，表示為

τAB=(1-ρ)·τAB+ΔτAB

(5)

(6)

(7)

3 改進的蟻群算法

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

蟻群算法是一種智能啟發(fā)式算法，啟發(fā)因子對算法的性能有很大影響[14]。圖2傳統(tǒng)蟻群算法的啟發(fā)因子ηAB是A點到B點的歐式距離的倒數(shù)，在二維碼移動機器人結(jié)構(gòu)化柵格環(huán)境中存在一定缺陷，二維碼移動機器人位于圖2中的位置A，則機器人下一步可以選擇的方向只有1，3，5，7，為了確保最快到達目標(biāo)點，機器人應(yīng)該盡可能選擇5，7的位置，離終點T更近。為了增大相鄰節(jié)點間概率選擇的差距引入自適應(yīng)期望函數(shù)，對相鄰節(jié)點的期望函數(shù)進行不同比例的放大，改善搜索的結(jié)果，ηAB表示為

(8)

(8)式中：ω是期望系數(shù)；R為地圖的行數(shù)；C為地圖的列數(shù)。ω可以表示為

ω=1/LB

(9)

針對結(jié)構(gòu)化工作環(huán)境特點，定義(9)式LB為點B到終點T的曼哈頓距離，即

LB=|iT-iB|+|jT-jB|

(10)

3.2 引入啟發(fā)因子

(11)

3.3 引入轉(zhuǎn)彎影響因子

機器人在轉(zhuǎn)彎時需先減速再加速再減速，轉(zhuǎn)彎次數(shù)太多，嚴(yán)重影響機器人運行效率。所以最短路徑不一定是機器人實際運行的最優(yōu)路徑，應(yīng)該考慮路徑的平滑程度。降低二維碼移動機器人的轉(zhuǎn)彎次數(shù)將提高機器人運行效率。本文將機器人運行路徑的擴展長度定義為

L=LA+λn

(12)

(12)式中：L是機器人擴展路徑長度；LA是路徑的實際長度；λ是影響因子；n是轉(zhuǎn)彎的次數(shù)。

3.4 算法流程

本文算法流程如圖3，步驟如下。

圖3 改進算法流程圖Fig.3 Flow chart of improved algorithm

步驟1生成已知障礙物分布的柵格地圖，給每個柵格分配二維碼ID，初始化算法的各個參數(shù)，設(shè)置起始點、目標(biāo)點、螞蟻數(shù)量和最大迭代次數(shù)。

步驟2放置M只螞蟻在起始點，并將起始點添加到禁忌表中，螞蟻k按照(11)式選擇下一個可行節(jié)點S，如果S是可以選擇的，則螞蟻移動到節(jié)點S并將S添加到禁忌表中。

步驟3若螞蟻k在節(jié)點S發(fā)生死鎖，當(dāng)前節(jié)點可行域為空，螞蟻無法選擇下一個可行節(jié)點，則刪除螞蟻k，令k+1→k，轉(zhuǎn)到步驟2，重復(fù)步驟2，直到所有螞蟻到達目標(biāo)點或者達到最大迭代次數(shù)，執(zhí)行步驟4。

步驟4計算所有到達目標(biāo)點的螞蟻的路徑長度，并記錄其經(jīng)過的節(jié)點，以及轉(zhuǎn)彎次數(shù)。

步驟5將得到路徑長度以及轉(zhuǎn)彎次數(shù)根據(jù)(12)式進行篩選，輸出最優(yōu)路徑。

4 實驗

4.1 仿真

本文所有的仿真實驗都在MATLAB中實現(xiàn)，并在Core i3-2120 CPU 3.3 GHz PC上運行，操作系統(tǒng)是window7。仿真實驗分別在15×15,30×30,50×50柵格環(huán)境中驗證算法。經(jīng)過多次選擇與比較，仿真實驗中參數(shù)設(shè)置如下：ρ=0.2，α=2，β=8，Q=1，螞蟻數(shù)量M=50，迭代次數(shù)K=200，λ=0.5。

傳統(tǒng)蟻群算法，文獻[7]算法與本文改進蟻群算法的路徑規(guī)劃圖、收斂圖分別如圖4—圖9，仿真實驗數(shù)據(jù)如表1。針對不同復(fù)雜度的環(huán)境模型進行仿真實驗，在指定大小的柵格地圖中隨機生成障礙物。從實驗結(jié)果中可以得出，本文改進的蟻群算法在有解的結(jié)構(gòu)化柵格環(huán)境下能得到最優(yōu)路徑。

圖4 傳統(tǒng)蟻群算法路徑規(guī)劃圖Fig.4 Path planning graph of traditional ant colony algorithm

圖6 本文改進蟻群算法路徑規(guī)劃圖Fig.6 Improved ant colony algorithm path planning graph in this paper

圖7 傳統(tǒng)蟻群算法收斂圖Fig.7 Convergence graph of traditional ant colony algorithm

圖8 文獻[7]蟻群算法收斂圖Fig.8 Convergence graph of reference[7]

圖9 本文改進蟻群算法收斂圖Fig.9 Improved ant colony algorithm convergence graph in this paper

表1 仿真實驗數(shù)據(jù)Tab.1 Simulation experiment data

4.2 二維碼移動機器人實驗驗證

實驗在15×15的柵格地圖中進行，機器人的主控芯片采用STM32F407IGT6，二維碼選用DM碼，二維碼間距為500 mm，相機掃描DM碼獲取位置信息，將信息通過以太網(wǎng)傳輸給單片機，上位機分別采用仿真實驗中的3種算法為機器人規(guī)劃路徑，算法參數(shù)和仿真實驗設(shè)定參數(shù)一致，通過WiFi將規(guī)劃出的路徑信息傳送給單片機，設(shè)定機器人運行速度為0.6 m/s，機器人根據(jù)接收到的路徑信息移動。實驗結(jié)果如表2和圖10。實驗結(jié)果和仿真結(jié)果一致，驗證了本文改進算法的可行性和準(zhǔn)確性。

表2 路徑規(guī)劃實驗結(jié)果Tab.2 Experimental results of path planning

圖10 二維碼移動機器人路徑規(guī)劃實驗Fig.10 Path planning experiment of two dimensional code mobile robot

5 結(jié)論

本文提出了一種基于改進蟻群算法的二維碼移動機器人全局路徑規(guī)劃方法，針對實際情況，將螞蟻可以選擇的方向限制在當(dāng)前節(jié)點的上下左右4個方向，引入自適應(yīng)期望函數(shù)和啟發(fā)因子，算法可以有效避免停滯狀態(tài)，并快速找到從起始點到目標(biāo)點的可行路徑，根據(jù)機器人的運動特性，在轉(zhuǎn)彎過程中需要先減速再加速再減速，要耗費一定時間，因此，本文引入轉(zhuǎn)彎影響因子，使目標(biāo)函數(shù)更合理。實驗結(jié)果證明，在二維碼構(gòu)建的結(jié)構(gòu)化柵格環(huán)境下，本文改進的蟻群算法可以快速找到從起點到目標(biāo)點的最優(yōu)路徑。