基于柵格地圖環(huán)境的機(jī)器人路徑規(guī)劃算法

劉琳琳

（武漢軟件工程職業(yè)學(xué)院機(jī)械工程學(xué)院，湖北武漢430205）

0 引言

移動(dòng)機(jī)器人技術(shù)是未來全球高新產(chǎn)業(yè)發(fā)展的基礎(chǔ)技術(shù)之一。21世紀(jì)以來，隨著計(jì)算機(jī)和電子技術(shù)水平的不斷提高，移動(dòng)機(jī)器人技術(shù)也進(jìn)入了快速發(fā)展的黃金階段。

路徑規(guī)劃問題是移動(dòng)機(jī)器人技術(shù)研究領(lǐng)域的熱點(diǎn)問題之一。移動(dòng)機(jī)器人路徑規(guī)劃是指機(jī)器人通過自身傳感器獲取環(huán)境信息，在工作空間內(nèi)自行規(guī)劃出一條安全的運(yùn)行路線，同時(shí)高效完成作業(yè)任務(wù)[1]。路徑規(guī)劃算法有多種，學(xué)者們針對機(jī)器人路徑規(guī)劃問題已做了大量研究，本文在前沿路徑規(guī)劃問題的研究基礎(chǔ)上，將改進(jìn)的蟻群算法運(yùn)用于基于柵格地圖環(huán)境的機(jī)器人路徑規(guī)劃方案中進(jìn)行研究。

1 基本蟻群算法

意大利學(xué)者M(jìn)arco Dorigo通過對自然界中蟻群覓食進(jìn)行分析模擬，于1992年首次提出了蟻群算法（ACO）。蟻群算法用于機(jī)器人路徑規(guī)劃時(shí)，在初始狀態(tài)下，各條路徑上的信息素濃度往往相等，螞蟻在進(jìn)行第一次路徑搜索時(shí)，通常根據(jù)周圍路徑長短進(jìn)行選擇，搜索的路徑不一定是全局最優(yōu)路徑。由于算法的正反饋特征，更多的螞蟻將集中在此路徑上，導(dǎo)致算法過早收斂[2]。本文針對蟻群算法進(jìn)行路徑規(guī)劃時(shí)效率低、局部最優(yōu)以及收斂性差等缺點(diǎn)，提出改進(jìn)措施。

2 環(huán)境建模

假設(shè)機(jī)器人的工作環(huán)境為二維空間，障礙物靜止且大小不變。本文將二維的規(guī)劃空間進(jìn)行離散化，采用柵格法構(gòu)建環(huán)境空間，采用序號法進(jìn)行柵格的標(biāo)識(shí)，如圖1所示。

圖1 地圖的柵格化處理

3 基于柵格地圖環(huán)境路徑規(guī)劃的蟻群算法

為了克服蟻群算法在路徑規(guī)劃中易陷入局部最優(yōu)解的缺陷，避免早熟現(xiàn)象的發(fā)生，本文改進(jìn)路徑點(diǎn)的搜索方式，重建信息素濃度更新機(jī)制，對可行柵格的可到達(dá)程度以及最優(yōu)程度建立評價(jià)體系，以提高算法的整體性能。

3.1 柵格地圖環(huán)境的預(yù)處理

當(dāng)環(huán)境空間比較復(fù)雜時(shí)，如圖2（a）所示，當(dāng)機(jī)器人運(yùn)動(dòng)至M時(shí)，無法向周圍任何區(qū)域移動(dòng)，此時(shí)陷入死鎖狀態(tài)[3]。

本文從柵格地圖環(huán)境入手，避免“凹”區(qū)域?qū)β窂剿阉鬟^程的干擾。采用基于并查集思想的連通區(qū)域判斷的方法，將連接在一起的障礙區(qū)域視作一個(gè)障礙物；將單個(gè)障礙物中的“凹”區(qū)域進(jìn)行填充，如圖2（b）所示。

圖2 柵格地圖環(huán)境的預(yù)處理

3.2 優(yōu)勢路徑點(diǎn)的提取

螞蟻在預(yù)處理后的環(huán)境空間中進(jìn)行路徑搜索時(shí)，其部分最優(yōu)路徑通常會(huì)經(jīng)過障礙物的“凸點(diǎn)”，本文將這些最優(yōu)路徑點(diǎn)定義為“優(yōu)勢路徑點(diǎn)（DPP）”。如圖3所示，網(wǎng)狀線標(biāo)記的柵格區(qū)域即為優(yōu)勢路徑點(diǎn)。

圖3 優(yōu)勢路徑點(diǎn)實(shí)例

本文采用基于幾何特征的模板匹配方法提取優(yōu)勢路徑點(diǎn)。該方法是將待識(shí)別的路徑點(diǎn)與事先構(gòu)造好的模板進(jìn)行比對，從而確定優(yōu)勢路徑點(diǎn)，本文采用的模板如圖4所示。

圖4 優(yōu)勢路徑點(diǎn)提取策略

根據(jù)圖4（a），當(dāng)障礙柵格的8鄰域范圍內(nèi)1-2-4區(qū)域?yàn)樽杂蓞^(qū)域時(shí)，1柵格即為當(dāng)前障礙柵格的“凸”點(diǎn)（SPUL），如圖4（b）所示；同理，（c）（d）（e）中3、6、8柵格分別表示當(dāng)前障礙柵格的“凸”點(diǎn)（SPUR、SPDL、SPDR）。這些“凸”點(diǎn)集合即為優(yōu)勢路徑點(diǎn)（DPP）。

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

3.3.1 信息素濃度更新方式的改進(jìn)

為了使螞蟻搜索到的路徑集中在最優(yōu)路徑附近，改進(jìn)的算法將信息素濃度更新函數(shù)進(jìn)行改進(jìn)，通過加強(qiáng)最優(yōu)路徑上的信息素濃度，對求解到的全局最優(yōu)路徑給予獎(jiǎng)勵(lì)。“優(yōu)勢路徑點(diǎn)”對全局最優(yōu)路徑有著明顯的貢獻(xiàn)，本文將搜索到的包含優(yōu)勢路徑點(diǎn)路徑上的信息素濃度進(jìn)行增強(qiáng)。改進(jìn)的信息素濃度更新方式如式（1）所示：

式中，ω表示優(yōu)勢路徑點(diǎn)對信息素濃度的貢獻(xiàn)參數(shù)；L′表示本次循環(huán)中包含優(yōu)勢路徑點(diǎn)的路徑長度。

3.3.2 信息素閾值的限定

為了提高蟻群算法的全局搜索能力，抑制算法過早地收斂，保證算法具有良好的多樣性和隨機(jī)性，在信息素濃度不斷進(jìn)行更新的同時(shí)，要對其濃度強(qiáng)度τ進(jìn)行限制。濃度強(qiáng)度閾值按公式（3）進(jìn)行限定[4]：

4 基于柵格地圖環(huán)境機(jī)器人路徑規(guī)劃的算法步驟

（1）采用柵格法對機(jī)器人的運(yùn)行環(huán)境進(jìn)行環(huán)境建模，設(shè)置機(jī)器人起始點(diǎn)Start、目標(biāo)點(diǎn)End，對螞蟻數(shù)量、信息啟發(fā)算子α、期望啟發(fā)算子β、貢獻(xiàn)參數(shù)ω等進(jìn)行初始化，確定最大迭代次數(shù)N。

（2）對柵格地圖環(huán)境進(jìn)行預(yù)處理。

（3）提取環(huán)境中全部的優(yōu)勢路徑點(diǎn)。

（4）螞蟻開始搜索路徑，根據(jù)公式（4）找出螞蟻下一步可以到達(dá)的柵格。

（5）判斷螞蟻是否在規(guī)定的步數(shù)內(nèi)到達(dá)目標(biāo)點(diǎn)，若是，則記錄下來螞蟻?zhàn)哌^的路徑及長度；否則，將此螞蟻從螞蟻序列里剔除。

（6）更新信息素濃度，根據(jù)公式（1）（3）更新已搜索到的路徑上的信息素濃度。

（7）判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到，則輸出當(dāng)前搜索到的路徑中最短的路徑，程序結(jié)束；否則，重復(fù)步驟（4）～（7）。

5 仿真實(shí)驗(yàn)及分析

5.1 仿真環(huán)境

用MATLAB構(gòu)建仿真平臺(tái)，設(shè)置仿真環(huán)境如圖5所示，地圖環(huán)境為10×10的柵格矩陣，障礙柵格用黑色填充，自由柵格用白色填充，機(jī)器人起點(diǎn)為Start，終點(diǎn)為End，蟻群算法的初始化參數(shù)為：螞蟻數(shù)量m=50，最大迭代次數(shù)N=100，信息啟發(fā)算子α=1，期望啟發(fā)算子β=7，貢獻(xiàn)參數(shù)ω=1.5，信息素強(qiáng)度Q=100，信息素?fù)]發(fā)系數(shù)ρ=0.7。

圖5 仿真環(huán)境

5.2 實(shí)驗(yàn)結(jié)果分析

對本文算法與基本蟻群算法在圖5的環(huán)境地圖上進(jìn)行仿真實(shí)驗(yàn)，仿真結(jié)果如圖6及表1所示。

圖6 柵格地圖環(huán)境下的規(guī)劃路徑

從圖6及表1可以看出，基本蟻群算法并未找到全局最優(yōu)解，迭代次數(shù)較多，搜索時(shí)間較長；本文的算法提高了路徑搜索質(zhì)量以及算法效率。仿真結(jié)果證明了本方法能夠較為有效地解決機(jī)器人路徑規(guī)劃問題。

6 結(jié)語

本文研究了基于柵格地圖環(huán)境的移動(dòng)機(jī)器人路徑規(guī)劃方法。針對蟻群算法在機(jī)器人路徑規(guī)劃過程中出現(xiàn)的路徑質(zhì)量差、搜索效率低等缺陷，本文通過對柵格地圖環(huán)境進(jìn)行預(yù)處理，提取優(yōu)勢路徑點(diǎn)，改進(jìn)信息素濃度更新機(jī)制，限制信息素濃度強(qiáng)度的方式對蟻群算法進(jìn)行了改進(jìn)。仿真實(shí)驗(yàn)證明，本文提出的算法方案能夠有效地避免蟻群算法的早熟問題，提高路徑質(zhì)量以及算法效率。