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

劉永建，曾國輝，黃 勃，李曉斌

(1.上海工程技術大學 電子電氣工程學院，上海 201620；2.上海應用技術大學 電氣與電子工程學院，上海 200235)

移動機器人路徑規(guī)劃是當下研究的熱點，在移動機器人路徑規(guī)劃的發(fā)展過程中，科學家提出了各種算法，如RRT算法[1]、模擬退火算法[2]、人工勢場算法[3]、粒子群算法[4]、Dijkstra算法[5]、A*算法[6]和蟻群算法[7]等。

但是上述提及的各種算法，都存在各自的缺點。RRT算法在搜索過程中進行隨機搜索，只要從起始點到目標點有連線，則立即生成一條路徑，所以生成的路徑既不能保證路徑最優(yōu)，又不能保證搜索時間最短。粒子群算法與模擬退火算法效果的優(yōu)劣在于適應度函數(shù)的選擇。Dijkstra算法，屬于一種貪心算法，其只考慮當前節(jié)點到下一節(jié)點的距離，易陷入局部最優(yōu)。算法在搜索期間進行全局搜索，搜索時間慢，而且搜索的方向有可能與目標點相背離，最終導致搜索失敗。A*算法在Dijkstra算法的基礎上，引入啟發(fā)函數(shù)引導路徑搜索的方向。但傳統(tǒng)A*算法通過比較鄰域的啟發(fā)函數(shù)值F來逐步確定下一個路徑柵格，當啟發(fā)函數(shù)值存在多個最小值時，A*算法不能保證路徑搜索獲得最佳解決方案。

對于路徑規(guī)劃問題，國內(nèi)外學者做了大量研究。在文獻[8]中，提出了一種改進的遺傳算法。該方法在初始種群生成過程中增加了偏移機制，并且將人工勢場算法和偏移機制分別引入到交叉算子和變異算子中，提高了全局搜索的能力。文獻[9]提出了最大最小螞蟻思想，在一定程度上解決了因信息素增長過快導致的局部最優(yōu)問題。文獻[10]提出了一種改進的蟻群算法，在算法中基于狼群法則對信息素進行更新，避免陷入局部最優(yōu)。

傳統(tǒng)的蟻群算法[11]存在搜索速度慢且易陷入局部最優(yōu)的缺點。本文對傳統(tǒng)的蟻群算法進行改進，將A*算法[12]和蟻群算法相結合，在傳統(tǒng)的A*算法的基礎上，改進估價函數(shù)，增加了目標點對路徑搜索的影響程度。然后，文中改進信息素揮發(fā)因子[13]，使信息素揮發(fā)因子動態(tài)變化。最后通過MATLAB仿真驗證，結果表明改進的蟻群算法在最短路徑上明顯短于傳統(tǒng)的蟻群算法，且在收斂速度上明顯比傳統(tǒng)的蟻群算法[14]快。仿真驗證結果證明本文提出的改進算法是有效的。

1 建立柵格地圖環(huán)境

柵格法(網(wǎng)格法)是機器人路徑規(guī)劃建立地圖環(huán)境的常用方法，適用于各種算法的環(huán)境建模。本文采用柵格法對蟻群算法[15]的地圖環(huán)境進行建模，建立大小為20×20的方格，坐標軸依次從左到右，從上到下標注。本研究將機器人的整個工作環(huán)境劃分為20×20的大小。環(huán)境中若存在障礙物，將其對應的方格標注為黑色，不滿一方格的按照一個完整的方格計算；白色的區(qū)域代表完全可通行區(qū)域。在(0.5,19.5)處設為起始點，在(19.5,0.5)處設為目標點。在網(wǎng)格環(huán)境中，機器人可以安全地搜索可行的最佳路徑，同時避開障礙物，如圖1所示。

2 傳統(tǒng)的蟻群算法

蟻群算法是科學家從螞蟻覓食的行為中得到的啟發(fā)，它是由Marco Dorigo于1992年在他的博士論文中提出的。傳統(tǒng)的蟻群算法主要模仿螞蟻覓食的行為，螞蟻通過釋放信息素進行信息的傳遞。當然，并不是所有的螞蟻都會循規(guī)蹈矩，有的螞蟻會另辟蹊徑，有可能會發(fā)現(xiàn)更短的路徑。在蟻群算法中，針對這一現(xiàn)象，科學家引入信息素與啟發(fā)函數(shù)對目標點的影響對路徑進行選擇。

螞蟻k(k=1,2,3,…,m)根據(jù)移動過程中所有先前螞蟻留下的信息素對下一節(jié)點進行選擇。傳統(tǒng)的蟻群算法根據(jù)狀態(tài)轉移規(guī)則選擇下一個節(jié)點。在蟻群算法中，禁忌表tabuk(k=1,2,3,…,m)表示螞蟻k當前正在傳遞的節(jié)點。當螞蟻全部尋徑完成時，清空禁忌表并繼續(xù)下一次迭代。根據(jù)信息素和啟發(fā)式信息的分布確定螞蟻的狀態(tài)轉移概率。

狀態(tài)轉移概率公式

(1)

啟發(fā)函數(shù)

(2)

其中，ηij(t)為啟發(fā)函數(shù)，表示的是路徑長短對節(jié)點的選擇影響程度，在求解距離的方法中，典型的有歐式距離與曼哈頓距離。曼哈頓距離不能直接確定對角節(jié)點之間的距離，歐氏距離是兩點之間的線性距離。本文選擇歐式距離法。距離越大，啟發(fā)函數(shù)的值越小，相反，距離越小，啟發(fā)函數(shù)的值越大，則從當前節(jié)點選擇下一節(jié)點的概率越大。

信息素濃度

Tij(t+n)=(1-ρ)·Tij(t)+ΔTij(t)

(3)

(4)

3 改進的蟻群算法

3.1 A*算法

A*算法是一種啟發(fā)式搜索[16]算法，它是在Dijkstra算法的基礎上，提出的一種新算法。Dijkstra算法是一種貪心算法[17]。A*算法在其基礎上，引入一個啟發(fā)函數(shù)，在保證最優(yōu)路徑的前提下，采用啟發(fā)式搜索。A*算法通過估價函數(shù)確定搜索方向，使其朝著目標點前進，該啟發(fā)式搜索的估價函數(shù)是

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

(6)

其中，f(n)表示節(jié)點n的估價函數(shù)；g(n)表示從起點到當前節(jié)點的實際代價；h(n)表示當前節(jié)點到目標點的估計成本。本文使用歐式距離測量兩點之間距離

(7)

其中，(x1,y1)、(x2,y2)分別表示兩節(jié)點n1、n2的坐標。

本文將A*算法與蟻群算法相結合，在A*算法的基礎上，將啟發(fā)函數(shù)作如下改進

f(n)=mg(n)+(1-m)eh(n)h(n)

(8)

其中，m為[0,1]之間的常數(shù)，表示g(n)與h(n)對f(n)的影響程度；eh(n)增強了啟發(fā)函數(shù)對估價函數(shù)的影響程度，增加了目標點對路徑搜索的吸引力。

3.2 改進信息素揮發(fā)因子

在傳統(tǒng)的蟻群算法中，信息素揮發(fā)因子[18]代表螞蟻剩余信息量的揮發(fā)速度，通常為一固定常數(shù)。若在搜索時全程保持信息素的揮發(fā)速度為一恒量，則會降低全局搜索的效率。本文通過改進信息素揮發(fā)因子ρ，使ρ隨時間服從泊松分布。ρ的變化情況如下：在路徑搜索前期，路徑的選擇主要依靠信息素的指引，此時使信息素揮發(fā)因子的值為一較小值；在路徑搜索中期，信息素量已積累到一定程度，為了提高全局搜索的能力，將信息素揮發(fā)因子的值取為一較大值；在路徑搜索后期，路徑的選擇較單一，使信息素揮發(fā)因子的值降低，增加信息素的導向作用。信息素揮發(fā)因子ρ根據(jù)以下公式改進

(9)

稱x服從參數(shù)為λ(λ>0)的泊松分布，并且根據(jù)實驗獲得λ的值，本文λ取值為10。k取NC的值，代表算法的迭代次數(shù)。

3.3 改進啟發(fā)函數(shù)

在傳統(tǒng)的蟻群算法中，啟發(fā)因子η與當前節(jié)點到下一節(jié)點之間的距離成反比。不考慮目標點和當前節(jié)點的影響程度，容易陷入局部最優(yōu)。本文將A*算法的思想融合到蟻群算法中，將兩種算法相結合，可以提高收斂速度。改進的啟發(fā)函數(shù)如下

(10)

其中，ηij代表啟發(fā)函數(shù)；m為(0,1)的常數(shù)，m的取值根據(jù)實時環(huán)境確定。dij表示當前節(jié)點到下一節(jié)點的距離，die表示當前節(jié)點到目標點的距離，本文增加了目標點對節(jié)點選擇的導向作用。

3.4 改進的算法具體步驟

步驟1環(huán)境建模。使用網(wǎng)格法構建二維靜態(tài)地圖模型。黑色代表障礙物信息，白色代表安全可通行區(qū)域，不滿一格的障礙物按照一個網(wǎng)格計算，機器人可以自由地通過白色區(qū)域；

步驟2 初始化參數(shù)。例如迭代次數(shù)NC、信息素因子α和期望啟發(fā)因子β等參數(shù)；

步驟3將所有螞蟻置于起點并準備搜索；

步驟4結合輪盤賭法和狀態(tài)轉移概率公式對下一節(jié)點進行選擇；

步驟5信息素更新。在螞蟻k完成搜索后，根據(jù)改進的算法更新信息素；

步驟6重復步驟4和步驟5，直到螞蟻到達終點；

步驟7將m只螞蟻重置為起始點并清空禁忌表以進行下一次迭代；

步驟8判斷NC是否達到設定值。如果NC達到設定值，則程序結束，否則轉到步驟4。

4 仿真與實驗

本文在MATLAB上進行仿真實驗。硬件環(huán)境：Windows 10，CPU為Core(TM)i5-3230M、2.6 GHz，內(nèi)存4 GB。通過建立二維柵格地圖，地圖模型為20×20個柵格。建立二維直角坐標系，橫縱坐標的單位取值為1，最大值為20，機器人的起點為(0.5,19.5)，目標點為(19.5,0.5)。機器人按照改進的蟻群算法進行路徑規(guī)劃。

本文對傳統(tǒng)的蟻群算法和改進的蟻群算法分別進行了仿真實驗，如圖2～圖7所示。

圖2是機器人運動軌跡，圖2(a)和圖2(b)分別為傳統(tǒng)蟻群算法和改進蟻群算法的機器人運動軌跡。由圖2可以看出，該地圖模型相對簡單，改進蟻群算法運動軌跡較傳統(tǒng)蟻群算法短，而且傳統(tǒng)的蟻群算法得到的運動軌跡較曲折。圖3是機器人各代運動軌跡。

表1 算法比較

圖4是算法收斂曲線，圖4(a)和圖4(b)分別是在傳統(tǒng)蟻群算法和改進蟻群算法下的收斂曲線變化圖。由圖4可以看出，改進蟻群算法收斂速度更快，并且最短路徑比傳統(tǒng)蟻群算法短。從收斂曲線的變化趨勢看，改進后的蟻群算法曲線變化幅度較小，說明改進后的蟻群算法收斂性較好。表1是傳統(tǒng)蟻群算法和改進蟻群算法的比較。由表1可以看出，改進蟻群算法在最短路徑上比傳統(tǒng)蟻群算法短，由于地圖環(huán)境相對簡單，最短路徑相差不大，但改進蟻群算法在迭代次數(shù)上明顯少于傳統(tǒng)蟻群算法，表明了改進算法的優(yōu)越性。

上述仿真實驗是在障礙物分布較簡單的情況下得到的，而為了驗證改進的算法對環(huán)境的強適應性，需要在復雜的障礙物環(huán)境中進行仿真實驗。

圖5是機器人運動軌跡，圖5(a)和圖5(b)分別是在傳統(tǒng)蟻群算法和改進的蟻群算法下機器人的運動軌跡。由圖5可以看出，在傳統(tǒng)的蟻群算法中，機器人的運動軌跡明顯比改進蟻群算法的運動軌跡冗長。在復雜環(huán)境條件下，改進蟻群算法具有良好的適應性。圖6是機器人的各代運動軌跡。

圖7是算法收斂曲線，圖7(a)和圖7(b)分別表示傳統(tǒng)蟻群算法和改進蟻群算法的收斂曲線變化趨勢。由圖7可以看出，改進蟻群算法在最短路徑長度上比傳統(tǒng)蟻群算法短，而且改進蟻群算法在迭代次數(shù)上也具有很大的優(yōu)勢，表明改進蟻群算法具有良好的實時性，能夠適應復雜的地圖環(huán)境。表2是傳統(tǒng)蟻群算法和改進蟻群算法的比較，可以看出在復雜的環(huán)境下，改進算法比傳統(tǒng)蟻群算法有較大的優(yōu)勢，而且改進蟻群算法在最短路徑上明顯比傳統(tǒng)蟻群算法短，表明了改進算法的強適應性。

由上述仿真顯示，在相對簡單的地圖環(huán)境下，改進蟻群算法在最短路徑上比傳統(tǒng)蟻群算法短。由于地圖環(huán)境相對簡單，最短路徑相差不大。但是改進蟻群算法在迭代次數(shù)上明顯少于傳統(tǒng)蟻群算法，驗證了改進蟻群算法的可行性。在相對復雜的地圖環(huán)境下，改進蟻群算法明顯優(yōu)于傳統(tǒng)蟻群算法，改進蟻群算法在最短路徑上明顯短于傳統(tǒng)蟻群算法，并且改進蟻群算法在收斂時間上明顯快于傳統(tǒng)蟻群算法。這些結果表明改進算法是有效的，并且能夠適應不同復雜程度的環(huán)境。

5 結束語

傳統(tǒng)蟻群算法的缺點是算法收斂緩慢且容易陷入局部最優(yōu)。本文提出的改進蟻群算法相比較于傳統(tǒng)蟻群算法，更能適應復雜的環(huán)境，在最短路徑上明顯小于傳統(tǒng)蟻群算法，而且收斂速度快、搜索時間短、實時性較好，顯示了改進后蟻群算法的有效性。