張 毅，李 奎，黃 超

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

0 引 言

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

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

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

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

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

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

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

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

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

(1)

j=(N-1)modC+1

(2)

2 蟻群算法基本原理

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

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

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

2.1 概率選擇

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

(3)

ηAB=1/dAB

(4)

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

2.2 信息素更新過(guò)程

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

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

(5)

(6)

(7)

3 改進(jìn)的蟻群算法

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

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

(8)

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

ω=1/LB

(9)

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

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

(10)

3.2 引入啟發(fā)因子

(11)

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

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

L=LA+λn

(12)

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

3.4 算法流程

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

圖3 改進(jìn)算法流程圖Fig.3 Flow chart of improved algorithm

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

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

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

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

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

4 實(shí)驗(yàn)

4.1 仿真

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

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

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

圖6 本文改進(jìn)蟻群算法路徑規(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 文獻(xiàn)[7]蟻群算法收斂圖Fig.8 Convergence graph of reference[7]

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

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

4.2 二維碼移動(dòng)機(jī)器人實(shí)驗(yàn)驗(yàn)證

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

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

圖10 二維碼移動(dòng)機(jī)器人路徑規(guī)劃實(shí)驗(yàn)Fig.10 Path planning experiment of two dimensional code mobile robot

5 結(jié)論

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