俞燁+賀乃寶+高倩+姚靈靈

摘 要：針對移動機器人路徑規(guī)劃中的不足，文中提出了一種改進蟻群算法的路徑規(guī)劃方法。算法中通過對距離啟發(fā)因子、初始信息素分配策略、信息素更新規(guī)則以及全局信息素?fù)]發(fā)因子進行改進，可有效避免陷入局部最優(yōu)解并提高算法的收斂速度。實驗證明，改進蟻群算法在避免局部最優(yōu)以及尋找最優(yōu)解能力方面具有良好的效果。

關(guān)鍵詞：移動機器人；路徑規(guī)劃；蟻群算法；信息素更新

中圖分類號：TP391.9 文獻標(biāo)識碼：A 文章編號：2095-1302（2017）03-00-04

0 引 言

移動機器人路徑規(guī)劃是機器人學(xué)的一個重要研究領(lǐng)域，是指移動機器人在有障礙物的工作環(huán)境中，按照某一性能指標(biāo)（如工作代價最小、行走時間最少、行走路線最短等）搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的安全的、無碰的最優(yōu)或次優(yōu)路徑。目前，常用于移動機器人路徑規(guī)劃的算法主要有人工勢場法、A*算法、神經(jīng)網(wǎng)絡(luò)法、模糊推理法、遺傳算法等。人工勢場法存在局部最優(yōu)點和障礙物附近目標(biāo)不可達問題。A*算法雖然對比較簡單的地圖搜索速度非?？欤材苷业阶顑?yōu)路徑，但全局性較差，啟發(fā)函數(shù)選擇不當(dāng)容易陷入死循環(huán)。神經(jīng)網(wǎng)絡(luò)法雖然能收斂到最優(yōu)路徑，但環(huán)境改變后必須重新學(xué)習(xí)，在環(huán)境信息不完整或環(huán)境經(jīng)常改變的情況下難以應(yīng)用。模糊推理法雖然避開了其它算法中存在的對環(huán)境信息依賴性強等缺點，但適應(yīng)能力比較差。遺傳算法雖然具有魯棒性強、全局優(yōu)化等優(yōu)點，但計算速度不快，容易提前收斂[1-3]。

蟻群算法是一種模擬進化算法，具有正反饋、自組織、分布式計算、較強的魯棒性等優(yōu)點，因此在眾多優(yōu)化問題中得到了廣泛應(yīng)用，尤其在機器人路徑規(guī)劃應(yīng)用中成效顯著[4-6]。文獻[5]提出了一種融入遺傳算子并利用交叉和變異操作來擴大搜索空間的改進蟻群算法；文獻[6]提出根據(jù)目標(biāo)點自適應(yīng)調(diào)整啟發(fā)函數(shù)來提高算法收斂速度的路徑搜索方法；文獻[7]提出一種螞蟻落入陷阱回退策略和相遇策略的路徑尋優(yōu)策略；文獻[8]提出一種改進信息素更新方式、引入最大最小蟻群系統(tǒng)以及改進狀態(tài)轉(zhuǎn)移規(guī)則的路徑規(guī)劃方法。

盡管上述方法都能在一定程度上找到問題的最優(yōu)解或次優(yōu)解，但在實際應(yīng)用中也或多或少存在一定的缺陷，如所得路徑雖然是最短路徑，但存在個別不必要的尖峰，在一定程度上忽視了路徑平滑性的要求，與實際情況也有一定出入。抑或所得路徑雖然最短，但路徑中轉(zhuǎn)彎過多，機器人在實際運行過程中耗能較大，達不到能源節(jié)約的要求。為此，在傳統(tǒng)蟻群算法的基礎(chǔ)上，本文提出一種改進蟻群算法，可有效改善傳統(tǒng)蟻群算法中的不足，并且通過實驗取得了良好的效果。

1 環(huán)境建模

環(huán)境建模的目的是建立一個便于計算機編程模擬路徑規(guī)劃過程的地圖模型。環(huán)境建模是機器人路徑規(guī)劃的首要環(huán)節(jié)，由于柵格法的地圖創(chuàng)建和維護比較容易，而且簡單明了，大大減小了建模的復(fù)雜性，因此本文采用柵格法對環(huán)境進行建模。

設(shè)機器人的工作空間為一個二維區(qū)域，該二維區(qū)域分布著許多大大小小的障礙物，這些障礙物的大小和位置已知，同時假定機器人路徑規(guī)劃過程中障礙物都靜止。如圖1所示，障礙物面積占據(jù)半個或半個柵格以上的，該柵格設(shè)定為黑色，標(biāo)記為障礙柵格，反之設(shè)定為白色，標(biāo)記為自由柵格。為了便于標(biāo)記機器人的位置，將地圖中的柵格按圖1進行編碼，按照從左到右、從上到下的順序依次對柵格編號。

假設(shè)機器人外接圓直徑為R，為保證機器人能夠在柵格環(huán)境中無碰撞運動，取R作為柵格單元的邊長。設(shè)工作環(huán)境是長為X，寬為Y的方形區(qū)域，從左上角開始將柵格區(qū)域劃分為m行n列個邊長為R的柵格[7]。

為提高機器人運動的靈活性和可靠性，我們對機器人作如下約定：

（1）機器人的中心位置用質(zhì)點表示，同時對障礙物的尺寸按機器人的半徑作適當(dāng)擴展，以保證機器人能夠無碰撞地運動。

（2）機器人每次運動只能從一個柵格的中心位置移動到另一個柵格的中心位置，且只能位于自由柵格內(nèi)部；

（3）機器人的下一位置只能是與當(dāng)前位置相鄰的八個柵格的自由柵格中；

（4）為避免沒必要的局部最優(yōu)，某一柵格的上下左右柵格中有三個是障礙柵格，此柵格就默認(rèn)為障礙柵格，如圖1所示的38號柵格，這樣機器人就不會走該無效柵格了。

基于以上約定，柵格中心坐標(biāo)和該柵格序號N之間有如下關(guān)系：

式中，mod表示取余操作，int表示取整操作[8]。

2 蟻群算法基本原理

蟻群算法是由意大利學(xué)者M.Dorigo等人于20世紀(jì)90年代初提出的一種新模擬進化算法，真實地模擬了自然界螞蟻群體的覓食行為。該算法最初成功應(yīng)用于解決著名的旅行商問題，并取得了較好的結(jié)果。蟻群算法的基本原理如下：螞蟻k（k=1，2，...，m）根據(jù)各條路徑上的信息素濃度來決定它下一步轉(zhuǎn)移的方向，設(shè)Pkij（t）表示t時刻螞蟻k從節(jié)點i轉(zhuǎn)移到節(jié)點j的概率，計算公式如下：

式中， τij（t）為t時刻節(jié)點i與節(jié)點j連接路徑上的信息素濃度； ηij（t）為啟發(fā)函數(shù)，ηij（t）=1/dij表示螞蟻k從節(jié)點i轉(zhuǎn)移到節(jié)點j的期望程度；allowk（k=1，2，...，m）為螞蟻k待訪問節(jié)點的集合，螞蟻剛開始尋優(yōu)時，allowk中有（n-1）個元素，即包含除螞蟻k出發(fā)節(jié)點的其他所有節(jié)點，隨著螞蟻尋優(yōu)的進行，allowk中的元素不斷減少，直至訪問到目標(biāo)節(jié)點。α為信息素重要程度因子，其值越大，表示信息素的濃度在轉(zhuǎn)移中起的作用越大；β為啟發(fā)函數(shù)重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉(zhuǎn)移中的作用越大，其狀態(tài)轉(zhuǎn)移概率越接近貪心規(guī)則。

此外，在螞蟻釋放信息素的同時，各條路徑上的信息素也會逐漸消失，設(shè)參數(shù)ρ（0<ρ<1）表示信息素的揮發(fā)程度。因此，當(dāng)所有螞蟻完成一次循環(huán)后，各個節(jié)點連接路徑上的信息素濃度需要實時更新，即

式中，Δτkij表示第k只螞蟻在節(jié)點i與節(jié)點j連接路徑上釋放的信息素濃度；Δτij表示所有螞蟻在節(jié)點i與節(jié)點j連接路徑上釋放的信息素濃度之和。其中，Δτij按下式進行更新：

式中，Q為常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量；Lk為第k只螞蟻經(jīng)過路徑的長度[9，10]。

3 改進的蟻群算法

3.1 距離啟發(fā)因子的改進

在傳統(tǒng)蟻群算法中，距離啟發(fā)因子ηij=1/dij，采用此啟發(fā)公式全局性不強，只考慮到下一步要選擇距離最近的節(jié)點，往往會因為貪圖這一小步而選擇了偏離目標(biāo)節(jié)點的方向，從而形成局部最優(yōu)解或無效解。因此，本文從全局出發(fā)，增加目標(biāo)節(jié)點對下一節(jié)點的影響，改進公式如下：

式中，dis（i，j）表示節(jié)點i到節(jié)點j的距離，dis（j，E）表示節(jié)點j到目標(biāo)節(jié)點E的距離，w是一個參數(shù)，w∈（0，5），參數(shù)w的選擇決定了螞蟻更傾向于選擇距離目標(biāo)節(jié)點更近的節(jié)點。因此，概率公式改進為：

通過對距離啟發(fā)因子的改進，螞蟻在尋優(yōu)時可以同時兼顧本節(jié)點到下一節(jié)點的距離以及下一節(jié)點到目標(biāo)節(jié)點的距離，并且更加傾向于選擇距離目標(biāo)節(jié)點更近的節(jié)點，使得螞蟻在尋優(yōu)時全局性更強，更好地避免了局部最優(yōu)。

3.2 初始信息素分配策略

在傳統(tǒng)蟻群算法中，將每條路徑信息素濃度初始化為一個常數(shù)，這就為螞蟻初期尋優(yōu)帶來極大的隱患，導(dǎo)致初期搜索過慢，效率低下。因此，本文做出如下改進：適當(dāng)加大起點與終點連線附近區(qū)域的信息素濃度，減小與起點和終點連線相對的兩個對角區(qū)域的信息素濃度。因為往往最優(yōu)路徑就在起點與終點連線的附近區(qū)域形成，而其對角區(qū)域形成的基本不會是最優(yōu)路徑。這樣的初始信息素濃度分配為螞蟻初期搜索提供了導(dǎo)向，提高了螞蟻初期的搜索效率。

3.3 信息素更新方式的改進

螞蟻在搜尋最優(yōu)路徑時依靠最重要的一個因素就是信息素濃度，因此信息素濃度的更新方式對搜索效率以及最優(yōu)解的好壞顯得極為重要。

螞蟻每移動一次稱為一次搜索，經(jīng)過n次搜索后，所有螞蟻就完成了一次迭代。當(dāng)螞蟻每完成一次搜索，就對其走過路徑上的信息素進行局部更新，更新公式如下：

當(dāng)所有螞蟻完成一次迭代后，對接近當(dāng)前最優(yōu)路徑的部分較優(yōu)路徑進行信息素加強，對遠(yuǎn)離當(dāng)前較優(yōu)路徑的較差路徑進行信息素減弱，全局更新公式如下：

通過局部和全局信息素更新，螞蟻能夠?qū)ψ顑?yōu)路徑搜索更有導(dǎo)向性的同時又能探索未走過的路徑，使得螞蟻避免局部最優(yōu)的同時又能提高尋優(yōu)效率。

3.4 信息素?fù)]發(fā)因子的改進

在傳統(tǒng)蟻群算法中，全局信息素?fù)]發(fā)因子ρ是一個常數(shù)，可能導(dǎo)致算法陷入局部最優(yōu)解，影響算法的性能。因此，本文對其做出改進，使其全局信息素?fù)]發(fā)因子ρ隨時間服從正態(tài)分布，即在搜索初期和末期，信息素?fù)]發(fā)因子較小，信息素濃度也相對較高。在這期間，路徑搜索相對單一，路徑之間差別較小，信息素給予螞蟻的導(dǎo)向性較強，使得螞蟻沿著信息素濃度較高的路徑搜索，沒必要去探尋一些較差路徑；而在搜索中期，信息素?fù)]發(fā)因子較大，信息素濃度相對較低，信息素給予螞蟻的導(dǎo)向性相對較弱，使得螞蟻有較多的概率去搜索其他未走過的路徑，避免局部最優(yōu)。

3.5 算法步驟

用于移動機器人路徑規(guī)劃的改進蟻群算法步驟如下：

（1）環(huán)境建模。對環(huán)境進行柵格坐標(biāo)建模，黑色代表障礙柵格，白色代表自由柵格，機器人能在自由柵格中任意行走；

（2）初始信息素分配。初始信息素按照起點與終點連線附近區(qū)域濃度較大，起點和終點連線相對兩個對角區(qū)域的信息素濃度較小的原則進行分配；

（3）初始化各參數(shù)。對信息素重要程度因子α、啟發(fā)函數(shù)重要程度因子β、局部信息素?fù)]發(fā)因子ε、最大迭代次數(shù)Nmax等參數(shù)進行初始化，全局信息素?fù)]發(fā)因子ρ隨時間服從正態(tài)分布；

（4）所有螞蟻置于起始點，準(zhǔn)備搜索；

（5）選擇下一節(jié)點。根據(jù)概率公式（6）選擇所要行走的下一節(jié)點；

（6）局部信息素更新。當(dāng)所有螞蟻都完成一次搜索后，根據(jù)式（7）進行局部信息素更新；

（7）判斷所有螞蟻是否都完成一次迭代，若完成，轉(zhuǎn)（8），否則轉(zhuǎn)（5）；

（8）全局信息素更新。當(dāng)所有螞蟻都完成一次從起點到終點的搜索，則按式（8）進行全局信息素更新，輸出本次最優(yōu)路徑；

（9）判斷是否達到最大迭代次數(shù)，若達到，轉(zhuǎn)（10），否則轉(zhuǎn)（4）；

（10）尋優(yōu)結(jié)束，輸出最優(yōu)路徑。

改進蟻群算法的流程圖如圖2所示。

4 仿真

為了驗證上述改進蟻群算法的有效性及可行性，采用20×20柵格環(huán)境下的機器人路徑規(guī)劃問題進行驗證，在Matlab2010b環(huán)境下進行編程仿真。如圖1所示，機器人的起始點坐標(biāo)為（0.5，19.5），目標(biāo)點坐標(biāo)為（19.5，0.5），障礙物覆蓋率為27%，算法中出現(xiàn)的參數(shù)設(shè)置：α=1，β=6，ε=0.4，Nmax=200，m=32，參數(shù)w取0.35，常數(shù)δ取3.2。

分別采用傳統(tǒng)蟻群算法和改進蟻群算法在Matlab環(huán)境下進行編程仿真，其仿真結(jié)果對比見表1所列。

通過表1的數(shù)據(jù)不難看出，改進蟻群算法最短路徑、迭代次數(shù)以及運行時間方面都優(yōu)于傳統(tǒng)蟻群算法和文獻[7]所提蟻群算法，尤其在迭代次數(shù)和運行時間這兩個重要參數(shù)上優(yōu)勢明顯，有效提高了算法的收斂速度和效率。傳統(tǒng)蟻群算法、文獻[7]所提蟻群算法以及本文算法搜索到的最優(yōu)路徑對比如圖3、圖4和圖5所示。

從以上最優(yōu)路徑對比可知，傳統(tǒng)蟻群算法在搜索初期陷入了局部最優(yōu)，雖然最終也找到了一條最優(yōu)路徑，但路徑質(zhì)量不如改進蟻群算法；文獻[7]所提蟻群算法雖然尋找到的最優(yōu)路徑較傳統(tǒng)蟻群算法短，但還是在一定程度上陷入了局部最優(yōu)；而改進蟻群算法最優(yōu)路徑明顯優(yōu)于傳統(tǒng)蟻群算法。

為了更好地驗證并改進蟻群算法在收斂速度和最短路徑上的優(yōu)勢，本文給出各代路線的平均距離和最短距離的對比曲線，分別如圖6、圖7和圖8所示。

從以上三圖可以看出，傳統(tǒng)蟻群算法要迭代61次左右才能收斂到最優(yōu)解，文獻[7]所提蟻群算法也要迭代43次左右才能收斂到最優(yōu)解，而改進蟻群算法只要迭代23次左右就能收斂到最優(yōu)解，收斂速度明顯提高，且最短路徑相比傳統(tǒng)蟻群算法和文獻[7]所提蟻群算法都較優(yōu)。仿真結(jié)果證明，本文所提的改進蟻群算法具有較明顯的有效性和可行性。

5 結(jié) 語

本文提出了一種改進蟻群算法的移動機器人路徑規(guī)劃方法，通過對距離啟發(fā)因子、初始信息素分配策略、信息素更新規(guī)則以及全局信息素?fù)]發(fā)因子的改進，有效避免了算法陷入局部最優(yōu)解的同時又提高了算法的收斂速度。最后通過仿真實驗驗證了算法的有效性及可行性，在對比傳統(tǒng)蟻群算法的情況下，改進蟻群算法在尋找最優(yōu)解的能力及效率上明顯優(yōu)于傳統(tǒng)蟻群算法。

參考文獻

[1]宋紅生，王東署.基于改進蟻群算法的移動機器人路徑規(guī)劃[J].機床與液壓，2012，40（20）：120-125.

[2]萬曉鳳，胡偉，鄭博嘉，等.基于改進蟻群算法與Morphin算法的機器人路徑規(guī)劃方法[J].科技導(dǎo)報，2015，33（3）：84-89.

[3]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，2005.

[4]徐利超，張世武.基于改進蟻群算法的障礙環(huán)境下路徑規(guī)劃研究[J].智能工程，2013（7）：61-64.

[5]潘杰.基于改進蟻群算法的移動機器人路徑規(guī)劃[J].中國礦業(yè)大學(xué)學(xué)報，2012，41（1）：108-113.

[6]柳長安，鄢小虎，劉春陽，等.基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J].電子學(xué)報，2011，39（5）：1220-1224.

[7]尉朝聞，黎田.機器人路徑規(guī)劃的一種改進蟻群算法[J].科技信息，2010（35）：107-108.

[8]趙開新，魏勇，王東署.改進蟻群算法在移動機器人路徑規(guī)劃中的研究[J].計算機測量與控制，2014，22（11）：67-70.

[9]何娟，涂中英，牛玉剛.一種遺傳蟻群算法的機器人路徑規(guī)劃方法[J].計算機仿真，2010，27（3）：170-174.

[10]裴振兵，陳雪波.改進蟻群算法及其在機器人避障中的應(yīng)用[J].智能系統(tǒng)學(xué)報，2015，10（1）：90-96.

[11]周明秀，程科，汪正霞.動態(tài)路徑規(guī)劃中的改進蟻群算法[J].計算機科學(xué)，2013，40（1）：314-316.