移動(dòng)機(jī)器人路徑規(guī)劃的改進(jìn)蟻群算法

張 儀 趙苗慧 楊 兵 張 彤

（陜西省可控中子源工程技術(shù)研究中心，西京學(xué)院理學(xué)院，陜西 西安710123）

近年來，由于人工智能的飛速發(fā)展，移動(dòng)機(jī)器人的發(fā)展也成為人們討論的熱點(diǎn)，同時(shí)路徑規(guī)劃是移動(dòng)機(jī)器人主要討論的焦點(diǎn)。路徑規(guī)劃是指移動(dòng)機(jī)器人在有障礙的環(huán)境中尋找一條無碰撞的路徑[1]。路徑規(guī)劃的智能優(yōu)化算法主要有：遺傳算法、模擬退火算法、粒子群算法、免疫算法等。這些算法在移動(dòng)機(jī)器人路徑規(guī)劃時(shí)能取得很好的結(jié)果，但面對(duì)復(fù)雜環(huán)境時(shí)依然存在一定的缺陷[2]。

本文將改進(jìn)的蟻群算法是一種啟發(fā)式的隨機(jī)搜索算法。蟻群算法來源于自然界螞蟻尋找食物的過程。該算法主要模擬螞蟻群體覓食的過程，螞蟻在尋找食物的過程中，會(huì)在所經(jīng)過的路徑上留下信息素，而在找到食物，且路程較短的路徑上留下較多的信息素，這也給后來尋找食物的螞蟻提供了強(qiáng)有力的方向指引，更多的螞蟻會(huì)往信息素濃度高的路徑上走[3]。但傳統(tǒng)的蟻群算法存在收斂速度慢、容易陷入局部最優(yōu)解等問題[4]。本文將根據(jù)傳統(tǒng)蟻群算法所存在的問題提出一種改進(jìn)蟻群算法。

1 障礙物模型建立

本文將利用柵格法來模擬障礙物環(huán)境，黑格表示障礙物，在矩陣中由1 表示，白格表示可行空間，在矩陣中由0 表示。柵格點(diǎn)標(biāo)號(hào)依據(jù)從左到右，從上到下的順序依次標(biāo)號(hào)。每個(gè)標(biāo)號(hào)代表一個(gè)柵格點(diǎn)。每個(gè)柵格長(zhǎng)度定義為1。坐標(biāo)原點(diǎn)定義為左上點(diǎn)。并建立XOY 坐標(biāo)系。坐標(biāo)點(diǎn)（X,Y）和柵格標(biāo)號(hào)G 對(duì)應(yīng)的關(guān)系為式（1）和式（2）所示：

式中，G 是柵格點(diǎn)標(biāo)號(hào)，N 是矩陣的行列數(shù)，mod 是進(jìn)行取余數(shù)操作，ceil 是進(jìn)行朝正向元素方向取整操作。對(duì)移動(dòng)機(jī)器人在柵格中的移動(dòng)規(guī)定以下準(zhǔn)則:（1）移動(dòng)機(jī)器人只能在白格中移動(dòng)，并將移動(dòng)機(jī)器人作為質(zhì)點(diǎn)。（2）移動(dòng)機(jī)器人每次從每個(gè)柵格的中心出發(fā)，每次只能向周圍八個(gè)中心移動(dòng)，每次移動(dòng)的距離為1 或1.414。向上下左右移動(dòng)時(shí)的距離為1，向左上、左下、右上、右下移動(dòng)時(shí)距離為1.414。

2 蟻群算法

2.1 傳統(tǒng)蟻群算法

2.2 傳統(tǒng)蟻群算法的不足

2.2.1 迭代次數(shù)多。傳統(tǒng)蟻群算法在前期迭代時(shí)，每條路徑上的信息素濃度差別不大，就加大了螞蟻尋找最優(yōu)路徑的范圍，需要更多的時(shí)間去搜索路徑，直到找到最優(yōu)路徑。

2.2.2 易陷入局部最優(yōu)解。傳統(tǒng)蟻群算法尋找到較優(yōu)路徑時(shí)，就會(huì)往這條路徑上釋放更多的信息素，從而引來更多的螞蟻在這條路徑上留下信息素，通過正反饋，令較優(yōu)解成為了最佳路徑。

2.2.3 參數(shù)的大小選擇影響算法尋優(yōu)能力。參數(shù)的選擇直接影響算法的尋優(yōu)能力，參數(shù)選擇不當(dāng)直接影響算法的可行性。

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

通過上述分析的不足，對(duì)蟻群算法提出以下改進(jìn)：

2.3.1 解決陷入U(xiǎn) 型陷阱問題。當(dāng)螞蟻陷入U(xiǎn) 型陷阱時(shí)，螞蟻只能選擇回退，但上一個(gè)節(jié)點(diǎn)已經(jīng)無法回退，此螞蟻就陷入了鎖死狀態(tài)。文獻(xiàn)[5]就提出將鎖死的螞蟻丟棄。但此方法并未將螞蟻陷入鎖死時(shí)的節(jié)點(diǎn)加入禁忌表，沒有為后來出發(fā)的螞蟻留下有效信息。本文提出一種新的解決方案，當(dāng)螞蟻陷入鎖死時(shí)，將此節(jié)點(diǎn)加入禁忌表中，并將此螞蟻之前路徑上的信息素清零，再令此螞蟻從起始點(diǎn)重新出發(fā)。

2.3.2 設(shè)計(jì)自適應(yīng)信息素?fù)]發(fā)因子ρ。信息素?fù)]發(fā)因子ρ 的大小影響著蟻群算法的收斂速度，也影響算法能否找到最優(yōu)路徑。當(dāng)ρ 過大時(shí)，容易導(dǎo)致信息素?fù)]發(fā)過快，減少了較優(yōu)路徑上的信息素含量，從而導(dǎo)致最優(yōu)路徑可能被排除。當(dāng)ρ 過小時(shí)，會(huì)使各路徑上信息素含量差別不大，從而導(dǎo)致最優(yōu)路徑不容易被選擇，影響算法的收斂性。本文設(shè)計(jì)了一種自適應(yīng)信息素?fù)]發(fā)因子。本設(shè)計(jì)引入Sigmoid 函數(shù)作為信息素?fù)]發(fā)因子前面的系數(shù)。本設(shè)計(jì)只引入Sigmoid 函數(shù)大于0 的部分。改進(jìn)如式（3）所示。

式中，ρ 和N 為程序初始化設(shè)定的參數(shù)，信息素?fù)]發(fā)因子和迭代次數(shù)，Nn為進(jìn)行到第n 次的迭代。

若取N 為100，則ρ 前面的系數(shù)值與迭代次數(shù)N 的曲線關(guān)系如圖1 所示。

圖1 迭代次數(shù)和系數(shù)值的關(guān)系圖

由圖1 可知該式實(shí)現(xiàn)了ρ 的大小隨迭代次數(shù)變化而變化的效果。在迭代初期和末期，ρ 的取值最小，初期時(shí)，取值越小有利于螞蟻更容易找見最優(yōu)路勁，末期時(shí)，取值越小有利于增快收斂性。當(dāng)中期取值較大時(shí)，能增大信息素的揮發(fā)，若陷入局部最優(yōu)解，就更容易找到更優(yōu)的解，使螞蟻避免陷入局部最優(yōu)解。

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

圖2 傳統(tǒng)蟻群算法路徑規(guī)劃圖

圖3 改進(jìn)蟻群算法路徑規(guī)劃圖

由圖2 和圖3 對(duì)比可知，很直觀地就能看出改進(jìn)的蟻群算法是有效果的，改進(jìn)的蟻群算法明顯比傳統(tǒng)蟻群算法少走了許多冤枉路，拐彎次數(shù)也少了好多次。再由圖2 和圖3 對(duì)比可知，改進(jìn)蟻群算法所找到的解比傳統(tǒng)蟻群算法所找到的解要更優(yōu)，所找到的最短路徑長(zhǎng)度比傳統(tǒng)的要短11.2%。所用的迭代次數(shù)也比傳統(tǒng)蟻群算法要少。傳統(tǒng)蟻群算法與改進(jìn)蟻群算法對(duì)比數(shù)據(jù)如表1 所示。

表1 傳統(tǒng)蟻群算法與改進(jìn)蟻群算法性能指標(biāo)數(shù)據(jù)對(duì)比

4 結(jié)論

傳統(tǒng)蟻群算法確實(shí)存在容易陷入局部最優(yōu)解、無法找到最優(yōu)路徑的問題，基于此問題，設(shè)計(jì)了一種自適應(yīng)信息素?fù)]發(fā)因子與舍棄鎖死螞蟻路徑信息素但不舍棄螞蟻的方法處理陷入U(xiǎn)型障礙鎖死的問題。通過仿真證明改進(jìn)蟻群算法可以很好地使蟻群避免陷入局部最優(yōu)解而且能減少迭代次數(shù)，提高算法的效率，效果優(yōu)于傳統(tǒng)蟻群算法。