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

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

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

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

中圖分類(lèi)號(hào)：TP391.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2017）03-00-04

0 引 言

移動(dòng)機(jī)器人路徑規(guī)劃是機(jī)器人學(xué)的一個(gè)重要研究領(lǐng)域，是指移動(dòng)機(jī)器人在有障礙物的工作環(huán)境中，按照某一性能指標(biāo)（如工作代價(jià)最小、行走時(shí)間最少、行走路線最短等）搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的安全的、無(wú)碰的最優(yōu)或次優(yōu)路徑。目前，常用于移動(dòng)機(jī)器人路徑規(guī)劃的算法主要有人工勢(shì)場(chǎng)法、A*算法、神經(jīng)網(wǎng)絡(luò)法、模糊推理法、遺傳算法等。人工勢(shì)場(chǎng)法存在局部最優(yōu)點(diǎn)和障礙物附近目標(biāo)不可達(dá)問(wèn)題。A*算法雖然對(duì)比較簡(jiǎn)單的地圖搜索速度非?？?，也能找到最優(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)用。模糊推理法雖然避開(kāi)了其它算法中存在的對(duì)環(huán)境信息依賴(lài)性強(qiáng)等缺點(diǎn)，但適應(yīng)能力比較差。遺傳算法雖然具有魯棒性強(qiáng)、全局優(yōu)化等優(yōu)點(diǎn)，但計(jì)算速度不快，容易提前收斂[1-3]。

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

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

1 環(huán)境建模

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

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

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

為提高機(jī)器人運(yùn)動(dòng)的靈活性和可靠性，我們對(duì)機(jī)器人作如下約定：

（1）機(jī)器人的中心位置用質(zhì)點(diǎn)表示，同時(shí)對(duì)障礙物的尺寸按機(jī)器人的半徑作適當(dāng)擴(kuò)展，以保證機(jī)器人能夠無(wú)碰撞地運(yùn)動(dòng)。

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

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

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

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

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

2 蟻群算法基本原理

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

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

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

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

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

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

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

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

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

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

3.2 初始信息素分配策略

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

3.3 信息素更新方式的改進(jìn)

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

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

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

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

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

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

3.5 算法步驟

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

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

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

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

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

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

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

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

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

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

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

改進(jìn)蟻群算法的流程圖如圖2所示。

4 仿真

為了驗(yàn)證上述改進(jìn)蟻群算法的有效性及可行性，采用20×20柵格環(huán)境下的機(jī)器人路徑規(guī)劃問(wèn)題進(jìn)行驗(yàn)證，在Matlab2010b環(huán)境下進(jìn)行編程仿真。如圖1所示，機(jī)器人的起始點(diǎn)坐標(biāo)為（0.5，19.5），目標(biāo)點(diǎn)坐標(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)蟻群算法和改進(jìn)蟻群算法在Matlab環(huán)境下進(jìn)行編程仿真，其仿真結(jié)果對(duì)比見(jiàn)表1所列。

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

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

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

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

5 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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