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

,，，,

(西安工程大學(xué)機(jī)電工程學(xué)院，陜西 西安710048)

0 引言

移動(dòng)機(jī)器人在倉儲(chǔ)物流中作用日益增大，而最重要的就是讓機(jī)器人自主路徑規(guī)劃來代替人工進(jìn)行作業(yè)，路徑規(guī)劃的目的是尋找從起點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑或者近似最優(yōu)路徑[1-3]。路徑質(zhì)量對(duì)機(jī)器人工作穩(wěn)定性和倉庫運(yùn)行效率起著至關(guān)重要的作用。

國(guó)內(nèi)外學(xué)者對(duì)通過改進(jìn)算法來解決路徑規(guī)劃問題做了大量的研究，而蟻群算法被認(rèn)為是解決路徑規(guī)劃算法有效算法之一，基本蟻群算法在解決路徑規(guī)劃問題時(shí)還存在一定的缺陷，近些年來眾多學(xué)者對(duì)其進(jìn)行了一定的改進(jìn)，取得了不錯(cuò)的效果。萬逸飛等[4]引進(jìn)A*算法確定蟻群的初始信息，加入了算子，并對(duì)算法的信息素更新公式和啟發(fā)函數(shù)進(jìn)行了改進(jìn)，雖全局尋優(yōu)能力增強(qiáng)，但收斂速度還略慢。曹新亮等[5]構(gòu)造新的數(shù)學(xué)模型對(duì)初始信息素進(jìn)行差異化設(shè)置，提高了算法收斂速度，但在路徑尋優(yōu)上還有待改進(jìn)。李任江等[6]在對(duì)啟發(fā)函數(shù)進(jìn)行改進(jìn)時(shí)引入了方向系數(shù)，融合了局部和全局信息素的更新方式，考慮到安全距離的影響，仿真結(jié)果提高了算法收斂速度且路徑距離更短，但存在搜索結(jié)果不穩(wěn)定問題。張?zhí)K英等[7]采用自適應(yīng)調(diào)整偽隨機(jī)狀態(tài)轉(zhuǎn)移策略改變參數(shù)值避免算法早熟，其次，改進(jìn)信息素更新方式加快算法收斂速度，但最優(yōu)路徑長(zhǎng)度還需改進(jìn)。王蘇彧等[8]提出一種信息素?fù)]發(fā)因子自適應(yīng)策略，改進(jìn)啟發(fā)信息的距離評(píng)價(jià)函數(shù)以達(dá)到搜索速率快，迭代次數(shù)更少的目標(biāo)，但尋優(yōu)路徑長(zhǎng)度未能得到改善。

機(jī)器人路徑規(guī)劃屬于非確定性復(fù)雜問題[9]，本文針對(duì)蟻群算法在路徑規(guī)劃時(shí)易陷入局部最優(yōu)，搜索效率不高的問題，提出一種基于方向夾角的啟發(fā)因子，在對(duì)啟發(fā)函數(shù)改進(jìn)時(shí)結(jié)合了A*算法估價(jià)函數(shù)思想，同時(shí)讓信息素?fù)]發(fā)系數(shù)滿足拉普拉斯概率分布變化。

1 環(huán)境建模

本文采用柵格地圖進(jìn)行建模，如圖1所示。其中黑色柵格表示有障礙物，白色柵格表示無障礙物，考慮到機(jī)器人體積，障礙物形狀等問題對(duì)環(huán)境中的障礙物柵格進(jìn)行膨化處理，即對(duì)于障礙物大小不足1個(gè)柵格當(dāng)作1個(gè)柵格處理。

圖1 環(huán)境建模

2 基本蟻群算法

螞蟻在覓食過程中受到信息素濃度和距離啟發(fā)函數(shù)的影響[10]，t時(shí)刻，螞蟻k從1個(gè)柵格移動(dòng)到另一柵格的轉(zhuǎn)移概率為

(1)

Α和β分別為信息素重要程度因子和啟發(fā)函數(shù)重要程度因子；Ak為螞蟻下一步所能訪問所有節(jié)點(diǎn)的集合；τij(t)為t時(shí)刻路徑中信息素濃度；ηij(t)為距離啟發(fā)函數(shù)。

(2)

(3)

螞蟻在完成1次路徑循環(huán)后會(huì)對(duì)其信息素進(jìn)行1次更新，根據(jù)式(4)～式(6)調(diào)整信息素。

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

(4)

(5)

(6)

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

3.1 建立基于轉(zhuǎn)角啟發(fā)因子

在基本的蟻群算法基礎(chǔ)上引入方向系數(shù)ε，來增加路徑選擇的指向性，避免了算法在搜索路徑過程中因轉(zhuǎn)彎角度過大而浪費(fèi)時(shí)間。假設(shè)某時(shí)刻機(jī)器人在搜索過程中狀態(tài)如圖2所示，機(jī)器人先后經(jīng)過a點(diǎn)、b點(diǎn)、c點(diǎn)和d點(diǎn)，當(dāng)前機(jī)器人運(yùn)行節(jié)點(diǎn)為a到b，c和d為下一過程的起點(diǎn)和終點(diǎn)，機(jī)器人處于節(jié)點(diǎn)b時(shí)與x軸所形成的角度為θ1，機(jī)器人處于節(jié)點(diǎn)c時(shí)與x軸所形成的夾角為θ2。由圖2可知，當(dāng)Δθ越大時(shí)機(jī)器人運(yùn)行方向越靠近終點(diǎn)，期望值越大，設(shè)轉(zhuǎn)角啟發(fā)因子ζij為

(7)

圖2 機(jī)器人路徑搜索原理

ε為方向系數(shù)；θ1和θ2分別為機(jī)器人在節(jié)點(diǎn)b和節(jié)點(diǎn)c時(shí)與x軸所形成的夾角。

3.2 改進(jìn)啟發(fā)函數(shù)

基本蟻群算法并未考慮下一節(jié)點(diǎn)和目標(biāo)點(diǎn)之間的距離[11]，這在一定程度上降低了算法的搜索效率，因此，本文引入A*算法的估價(jià)函數(shù)思想，當(dāng)遇到自鎖時(shí)可跳出。A*算法優(yōu)點(diǎn)就是通過估計(jì)路徑中當(dāng)前節(jié)點(diǎn)與目標(biāo)點(diǎn)代價(jià)來進(jìn)行下一步選擇，從而縮小搜索范圍，提高搜索效率。估價(jià)函數(shù)表達(dá)式為

f(n)=g(n)+h(n)

(8)

g(n)為起點(diǎn)到當(dāng)前節(jié)點(diǎn)距離表示實(shí)際代價(jià)；h(n)為下一節(jié)點(diǎn)到目標(biāo)點(diǎn)間距離表示估計(jì)代價(jià)。

改進(jìn)后啟發(fā)函數(shù)為

(9)

dij表示起點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離，相當(dāng)于式(8)中的g(n)；djE表示當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離，相當(dāng)于式(8)中的h(n)。

3.3 信息素?fù)]發(fā)因子更新策略改進(jìn)

傳統(tǒng)蟻群算法中信息素常采用固定值，比較單一且并不適合螞蟻尋路過程中信息素的分配量，前期由于路徑中信息素含量低，加大了螞蟻搜索的盲目性，后期路徑中信息素含量積累太多降低了路徑的選擇性，因此采用固定的信息素值并不能滿足最優(yōu)路徑搜索要求。基于以上分析，本文提出一種信息素?fù)]發(fā)因子自適應(yīng)調(diào)整策略[12-13]，使之滿足拉普拉斯概率密度函數(shù)變化，如式(10)所示，信息素?fù)]發(fā)因子拉普拉斯概率分布如圖3所示。

(10)

μ為位置參數(shù)；b為尺度參數(shù)；當(dāng)ρ=μ時(shí)取最大值。

圖3 信息素?fù)]發(fā)因子拉普拉斯概率分布曲線

由圖3可知，前期選擇信息素?fù)]發(fā)因子較小，利于信息素積累，增加螞蟻尋路的導(dǎo)向性，中期揮發(fā)因子較大加快算法的迭代速率，后期信息素?fù)]發(fā)因子小，加快收斂。改進(jìn)后螞蟻t時(shí)刻從節(jié)點(diǎn)i到節(jié)點(diǎn)j的概率為

(11)

3.4 算法步驟

本文算法流程如圖4所示，具體步驟如下：

a.柵格法建模。

b.設(shè)置算法參數(shù)，設(shè)置起始點(diǎn)和終止點(diǎn)位置。

c.將螞蟻放置起始點(diǎn)開始尋路。

d.根據(jù)概率公式選擇螞蟻下一節(jié)點(diǎn)。

e.判斷所有螞蟻是否到終點(diǎn)，若到達(dá)執(zhí)行下一步，否則返回步驟d。

f.根據(jù)改進(jìn)后的更新規(guī)則進(jìn)行信息素更新。

g.保存每只螞蟻的路徑長(zhǎng)度，選擇當(dāng)前螞蟻?zhàn)顑?yōu)路徑并與歷史最優(yōu)路徑比較輸出全局最優(yōu)解。

h.判斷是否達(dá)到迭代次數(shù)，若達(dá)到輸出最優(yōu)解，否則返回步驟c,繼續(xù)尋路。

圖4 算法流程

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

本文基于MATLAB軟件，選擇不同的環(huán)境地圖進(jìn)行仿真實(shí)驗(yàn)，設(shè)置螞蟻個(gè)數(shù)為50，最大迭代次數(shù)為100，α=1,β=6，Q=1,ρ=0.3,分別選取2種不同的地圖環(huán)境進(jìn)行仿真，每種環(huán)境各運(yùn)行30次。環(huán)境1中，機(jī)器人某次運(yùn)行最優(yōu)路徑如圖5所示，最優(yōu)路徑收斂曲線如圖6所示。

圖5 環(huán)境1下2種算法最優(yōu)路徑對(duì)比

圖6 環(huán)境1最優(yōu)路徑收斂曲線對(duì)比

由圖5和圖6可知，在相對(duì)簡(jiǎn)單的環(huán)境中，基本蟻群算法在第7代得到路徑最優(yōu)解，此時(shí)路徑長(zhǎng)度為32.04，而本文算法在迭代第4次所得到的路徑長(zhǎng)度為29.21，且此時(shí)本文算法所得到的路徑轉(zhuǎn)折次數(shù)明顯優(yōu)于基本蟻群算法得到的路徑。30次仿真實(shí)驗(yàn)取均值得到的結(jié)果如表1所示。

表1 環(huán)境1下2種算法仿真結(jié)果對(duì)比

由表1可以看出，本文在引入方向夾角啟發(fā)因子和信息素自適應(yīng)揮發(fā)策略后，不管是最優(yōu)路徑長(zhǎng)度還是平均路徑長(zhǎng)度均優(yōu)于基本蟻群算法所得到的路徑,且在運(yùn)算時(shí)間上提前了2.47 s。環(huán)境2情況下2種算法得到的結(jié)果分別如圖7和圖8所示。

圖7 環(huán)境2下2種算法最優(yōu)路徑對(duì)比

圖8 環(huán)境2最優(yōu)路徑收斂曲線

比較圖7和圖8可知，基本蟻群算法在第8代得到最優(yōu)路徑,此時(shí)長(zhǎng)度為32.04，而本文算法在第6代得到最優(yōu)路徑長(zhǎng)度為30.04，且本文算法所得路徑更加平滑。環(huán)境2下2種算法在30次仿真所得結(jié)果的平均值如表2所示。

表2 環(huán)境2下2種算法仿真結(jié)果對(duì)比

由表2可以看出，在障礙物較多的環(huán)境中本文算法相對(duì)基本蟻群算法可快速收斂，最優(yōu)路徑長(zhǎng)度29.81優(yōu)于基本蟻群算法的34.73，減少了14.17%，平均路徑長(zhǎng)度減少17.17%，并且在運(yùn)算時(shí)間上也提前了2.27 s。

5 結(jié)束語

為了加快算法的收斂速度和尋優(yōu)能力，本文提出了一種改進(jìn)的蟻群算法，主要體現(xiàn)在以下3個(gè)方面：

a.通過引入方向夾角啟發(fā)因子，增加路徑選擇的指向性，避免了算法在搜索路徑過程中因轉(zhuǎn)彎角度過大而浪費(fèi)時(shí)間。

b.引入A*算法的估價(jià)函數(shù)思想來改進(jìn)啟發(fā)函數(shù)，在基本蟻群算法的基礎(chǔ)上考慮了當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)之間的距離，這在一定程度上降低了算法的搜索效率。

c.提出基于拉普拉斯變化的信息素?fù)]發(fā)策略，加快了算法迭代速率。

仿真結(jié)果表明,本文改進(jìn)的算法在路徑尋優(yōu)性能方面優(yōu)于基本蟻群算法，證明了該算法的有效性和可行性。