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

李燕 季建楠 沈葭櫟 蘇瑞

1 南京信息工程大學(xué) 自動(dòng)化學(xué)院,南京,210044 2 南京信息工程大學(xué)濱江學(xué)院 物聯(lián)網(wǎng)工程學(xué)院,無(wú)錫,214105

0 引言

隨著移動(dòng)機(jī)器人的飛速發(fā)展，路徑規(guī)劃問(wèn)題成為移動(dòng)機(jī)器人研究領(lǐng)域的基礎(chǔ)與核心.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)是機(jī)器人在復(fù)雜的環(huán)境中，從起點(diǎn)到終點(diǎn)之間無(wú)數(shù)條搜索路徑里，智能地選擇一條最優(yōu)路徑或者較優(yōu)路徑[1].傳統(tǒng)的解決路徑規(guī)劃問(wèn)題的算法主要包括廣度優(yōu)先搜索( BFS) 、深度優(yōu)先搜索( DFS) 、Dijkstra 算法和A*的算法.近年來(lái)一些研究人員采用仿生智能優(yōu)化算法解決路徑規(guī)劃問(wèn)題，這些仿生智能優(yōu)化算法主要包括蟻群算法、遺傳算法、粒子群算法、免疫算法、模擬退火算法、DNA計(jì)算方法以及各算法之間的組合優(yōu)化算法等[2-5].

蟻群算法是一種啟發(fā)式的隨機(jī)搜索算法，由意大利學(xué)者M(jìn)aniezzo團(tuán)隊(duì)受螞蟻覓食行為的啟發(fā)，在1991年首次提出[6].蟻群算法模擬螞蟻合作覓食行為，具有正反饋、高穩(wěn)健性和并行性、易于與其他算法相結(jié)合等優(yōu)點(diǎn).但傳統(tǒng)蟻群算法容易出現(xiàn)局部最優(yōu)解、計(jì)算量大、收斂速度慢等問(wèn)題[7].近年來(lái)國(guó)內(nèi)外學(xué)者相繼提出了一些改進(jìn)的蟻群算法.2000年，Stutzle等[8]提出了最大最小螞蟻系統(tǒng)( MMAS)，通過(guò)限制路徑上信息素的上下限，在一定程度上避免了陷入局部最優(yōu)解問(wèn)題.2018年，張?jiān)嚨萚9]提出一種改進(jìn)的多步長(zhǎng)蟻群算法，將蟻群每次迭代產(chǎn)生的最優(yōu)路徑作為引導(dǎo)徑，利用路徑引導(dǎo)搜索策略確定多步長(zhǎng)的移動(dòng)路徑，提高了搜索范圍的多樣性.2018年，占偉等[10]提出改進(jìn)啟發(fā)因子的方法，給定一個(gè)初步的引導(dǎo)方向，最終大大增加了算法的時(shí)間有效性，減少了算法收斂的時(shí)間,保證了最短路徑的搜索方向向著最短目標(biāo)最優(yōu)方向進(jìn)行.2020年，陳勁峰等[11]提出了一種自適應(yīng)信息素給予機(jī)制，提高了蟻群算法的收斂速度和路徑全局優(yōu)化能力.

針對(duì)現(xiàn)有蟻群算法的不足，本文提出了一種用于移動(dòng)機(jī)器人路徑規(guī)劃的改進(jìn)蟻群算法.首先用柵格法進(jìn)行環(huán)境建模，然后通過(guò)優(yōu)化信息素總量增強(qiáng)全局搜索能力，增加搜索的目的性，最后改善啟發(fā)式函數(shù)來(lái)提高狀態(tài)轉(zhuǎn)移概率，以便快速地得到路徑最優(yōu)解.仿真結(jié)果表明改進(jìn)的蟻群算法在性能指標(biāo)上有顯著提高.

1 環(huán)境建模

機(jī)器人環(huán)境建模的方法主要有柵格法、構(gòu)型空間法、自由空間法

等幾種.其中柵格法在機(jī)器人的環(huán)境建模上應(yīng)用最多[12].柵格法主要任務(wù)是根據(jù)環(huán)境構(gòu)建路徑網(wǎng)格圖，基本原理是將機(jī)器人的工作環(huán)境劃分為許多微小的網(wǎng)格單元，每個(gè)網(wǎng)格的規(guī)格由機(jī)器人的步驟決定.網(wǎng)格由自由網(wǎng)格和障礙網(wǎng)格組成.白色的網(wǎng)格表示自由網(wǎng)格，黑色的網(wǎng)格表示障礙網(wǎng)格.圖1是20×20的網(wǎng)格節(jié)點(diǎn)圖，每行的節(jié)點(diǎn)數(shù)Nx=20和每列的節(jié)點(diǎn)數(shù)Ny=20.坐標(biāo)原點(diǎn)定在柵格空間的左下方，定義x軸正方向?yàn)閺淖蟮接?，y軸正方向?yàn)閺南碌缴?第1個(gè)點(diǎn)的坐標(biāo)為(0，19)，第2個(gè)點(diǎn)的坐標(biāo)為(1，19)，以此類推.假設(shè)S={1,2,3,…,N}是一組節(jié)點(diǎn)的數(shù)量，第i個(gè)節(jié)點(diǎn)的坐標(biāo)為(xi,yi)，從起始點(diǎn)坐標(biāo)(0，0)開(kāi)始到終點(diǎn)坐標(biāo)(19，19)結(jié)束.機(jī)器人只能在白色的自由網(wǎng)格中移動(dòng)，需要避開(kāi)黑色的障礙網(wǎng)格.根據(jù)網(wǎng)格的位置，網(wǎng)格可以分為中間網(wǎng)格和邊界網(wǎng)格.對(duì)于中間網(wǎng)格，機(jī)器人的下一個(gè)動(dòng)作可選擇8個(gè)方向.當(dāng)機(jī)器人運(yùn)動(dòng)到邊界網(wǎng)格時(shí)，它的運(yùn)動(dòng)方向需舍去無(wú)法到達(dá)的方向.

圖1 20×20的節(jié)點(diǎn)圖Fig.1 20×20 node graph

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

蟻群算法是一種群體智能仿生啟發(fā)式算法，它通過(guò)模擬螞蟻覓食的行為來(lái)找到食物源與其蟻巢之間的最佳路徑.螞蟻在通過(guò)的路徑上會(huì)釋放信息素.通過(guò)這些信息素，螞蟻可以彼此交流并最終找到一條起點(diǎn)到終點(diǎn)的最短路徑.在搜索過(guò)程中螞蟻會(huì)隨機(jī)選擇前進(jìn)的運(yùn)動(dòng)方向，信息素在路徑上遺留的越多，對(duì)信息素濃度大的路徑選擇的概率就越大，在尋找路徑的過(guò)程中蟻群個(gè)體之間的協(xié)作形成了一種正反饋機(jī)制.

在尋找路徑的過(guò)程中螞蟻依據(jù)路徑上的信息量和啟發(fā)式信息計(jì)算轉(zhuǎn)移概率：

(1)

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

(2)

(3)

(4)

(5)

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

3.1 優(yōu)化信息素總量

對(duì)于傳統(tǒng)的蟻群算法，完成一次完整路徑搜索后所釋放的信息素總量是一個(gè)定值.隨著迭代次數(shù)的增加,后期路徑上的信息素濃度易積累過(guò)高，導(dǎo)致螞蟻一定程度上失去搜索優(yōu)質(zhì)解能力，信息素濃度在揮發(fā)因子的作用下降低，極可能增加陷入局部最優(yōu)解的概率.本文提出了對(duì)信息素總量Q進(jìn)行自適應(yīng)調(diào)整的機(jī)制，隨著迭代次數(shù)的增加Q逐步降低，大大降低陷入局部最優(yōu)解的概率.方法如下：

(6)

其中Niter表示迭代次數(shù)，Nc,iter是當(dāng)前的迭代數(shù).

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

傳統(tǒng)蟻群算法初始階段在路徑上沒(méi)有遺留信息素，螞蟻無(wú)法根據(jù)信息素濃度選擇方向，搜索沒(méi)有目的性，不能快速搜索到可行路徑.針對(duì)這一問(wèn)題，本文對(duì)迭代搜索的啟發(fā)函數(shù)進(jìn)行改進(jìn)，采用當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)的距離與下一節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)距離之和的平方來(lái)優(yōu)化啟發(fā)函數(shù)，使得螞蟻在搜索初期能夠獲得一個(gè)引導(dǎo)方向，增加目標(biāo)節(jié)點(diǎn)對(duì)下一節(jié)點(diǎn)的影響，改進(jìn)的啟發(fā)函數(shù)如下：

(7)

(8)

其中djD表示節(jié)點(diǎn)j到目標(biāo)點(diǎn)D的歐式距離.將傳統(tǒng)的dij改為(dij+djD)2，增強(qiáng)了搜索的目的性，降低了陷入局部最優(yōu)解的概率.

3.3 蟻群算法相關(guān)參數(shù)

蟻群算法中，參數(shù)的選取影響收斂速度和尋優(yōu)結(jié)果，主要涉及的參數(shù)有螞蟻數(shù)量、信息素?fù)]發(fā)系數(shù)、啟發(fā)因子α與期望啟發(fā)因子β、迭代次數(shù).具體分析如下：

1)螞蟻數(shù)量.算法中蟻群數(shù)量是一個(gè)關(guān)鍵的參數(shù)，蟻群數(shù)量過(guò)大，搜索路徑上的信息素會(huì)趨于相等，無(wú)法確定最優(yōu)路徑；蟻群數(shù)量過(guò)小，有可能出現(xiàn)早熟，不能獲取全局最優(yōu)路徑.本文螞蟻數(shù)量M設(shè)置為50.

2)信息素?fù)]發(fā)系數(shù).信息素反映螞蟻搜索進(jìn)程中積攢的信息量，指導(dǎo)蟻群搜索路徑的方向.隨著蟻群算法迭代的進(jìn)行，節(jié)點(diǎn)上的信息素將逐漸揮發(fā).信息素?fù)]發(fā)系數(shù)ρ對(duì)蟻群算法的收斂速度和尋優(yōu)能力都有著至關(guān)重要的影響.ρ增大信息素?fù)]發(fā)加快，蟻群算法的隨機(jī)性和搜索能力降低;ρ減小，全局搜索能力提高，但收斂速度也相應(yīng)減慢.本文信息素?fù)]發(fā)系數(shù)ρ設(shè)置為0.2.

3)啟發(fā)因子α與期望啟發(fā)因子β.啟發(fā)因子α表示路徑上的信息素濃度對(duì)整個(gè)蟻群的指導(dǎo)作用;期望啟發(fā)因子β表示路徑相關(guān)信息對(duì)蟻群的影響.α的大小決定螞蟻選擇之前路徑的概率大小，β的大小決定了算法的搜索效率.本文啟發(fā)因子α設(shè)置為0.9、期望啟發(fā)因子β設(shè)置為4.

4) 最大迭代次數(shù).迭代次數(shù)主要根據(jù)執(zhí)行的收斂軌跡來(lái)調(diào)整，迭代次數(shù)過(guò)小，會(huì)導(dǎo)致算法未收斂就已結(jié)束，過(guò)大會(huì)造成資源浪費(fèi).本文迭代次數(shù)設(shè)置為200.

3.4 路徑規(guī)劃步驟

為了實(shí)現(xiàn)改進(jìn)的路徑規(guī)劃算法，本文對(duì)算法整體流程進(jìn)行了設(shè)計(jì).路徑規(guī)劃流程如圖2所示，具體步驟如下：

圖2 路徑規(guī)劃流程Fig.2 Path planning

1)利用柵格法進(jìn)行環(huán)境建模；

2)對(duì)最大的迭代數(shù)、螞蟻個(gè)數(shù),以及其他參數(shù)如α,β,ρ等進(jìn)行初始化；

3)將所有螞蟻放在起點(diǎn)處，計(jì)算啟發(fā)信息；

4)根據(jù)狀態(tài)轉(zhuǎn)移概率方程確定要選擇的路徑；

5)蟻群遍歷所有節(jié)點(diǎn)后根據(jù)信息素策略更新信息素；

6)保存每個(gè)循環(huán)中每只螞蟻的路徑和路徑長(zhǎng)度；

7)循環(huán)執(zhí)行4)至6)直到獲得最優(yōu)解或者達(dá)到最大迭代數(shù).

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

為了檢測(cè)改進(jìn)的蟻群算法在機(jī)器人尋找最優(yōu)路徑中的效率，本文實(shí)驗(yàn)通過(guò)pycharm在Windows 10的系統(tǒng)下進(jìn)行了大量的仿真實(shí)驗(yàn).通過(guò)20×20的柵格環(huán)境，0表示障礙節(jié)點(diǎn)，1表示自由節(jié)點(diǎn)，環(huán)境中的所有障礙的范圍都可以由各章障礙節(jié)點(diǎn)組合形成.對(duì)傳統(tǒng)蟻群算法[14]、文獻(xiàn)[10]中改進(jìn)的蟻群算法和本文改進(jìn)的蟻群算法在相同的障礙環(huán)境下進(jìn)行仿真比較.3種蟻群算法初始設(shè)置為螞蟻的個(gè)數(shù)M=50,最大迭代數(shù)為200，α=0.9，β=4，ρ=0.2，Q=2.

圖3a—3c分別為傳統(tǒng)蟻群算法、文獻(xiàn)[10]蟻群算法以及本文改進(jìn)蟻群算法的最優(yōu)路徑搜尋圖，可以發(fā)現(xiàn)圖3a和3b都能夠在起始點(diǎn)到目標(biāo)節(jié)點(diǎn)之間找到一條最短的移動(dòng)路徑，但傳統(tǒng)的蟻群算法在初始環(huán)境相同的情況下明顯比文獻(xiàn)[10]蟻群算法得到的可行路徑長(zhǎng).圖3b和圖3c相比，圖3c中的最優(yōu)路徑長(zhǎng)度優(yōu)于圖3b中的最優(yōu)路徑長(zhǎng)度.

圖3 最優(yōu)路徑搜尋效果對(duì)比Fig.3 Optimal paths obtained by traditional ant colony (a),algorithm in Ref.[10] (b),and the improved ant colony algorithm (c)

圖4a—4c分別為傳統(tǒng)蟻群算法、文獻(xiàn)[10]蟻群算法以及本文算法的收斂曲線.由圖4a可以看出傳統(tǒng)蟻群算法在復(fù)雜環(huán)境下收斂曲線波動(dòng)較大，尋優(yōu)能力極不理想，在大規(guī)模的環(huán)境中其缺點(diǎn)暴露得非常明顯，在迭代第82次找到最優(yōu)路徑并逐漸趨于穩(wěn)定.圖4b顯示文獻(xiàn)[10]算法在迭代第69次找到最優(yōu)路徑，在迭代第69次后趨于穩(wěn)定.本文算法收斂曲線(圖4c)顯示在迭代第59次找到最優(yōu)路徑，在此之后趨于穩(wěn)定.

圖4 收斂曲線Fig.4 Convergence comparison between traditional ant colony (a),algorithm in Ref.[10] (b),and the improved ant colony algorithm (c)

通過(guò)3個(gè)算法收斂曲線的對(duì)比，明顯可以看出：傳統(tǒng)蟻群算法收斂曲線波動(dòng)較大、轉(zhuǎn)折點(diǎn)過(guò)多；文獻(xiàn)[10]中的蟻群算法和改進(jìn)的蟻群算法在達(dá)到最大迭代數(shù)時(shí)雖都已收斂，但本文改進(jìn)的蟻群算法收斂速度更快、更穩(wěn)定，尋優(yōu)的效果更好.3種算法多次仿真實(shí)驗(yàn)的數(shù)據(jù)對(duì)比結(jié)果如表1所示.

表1 仿真結(jié)果對(duì)比

從表1中的實(shí)驗(yàn)數(shù)據(jù)可以看出，本文改進(jìn)的蟻群算法相對(duì)于傳統(tǒng)算法和文獻(xiàn)[10]中的算法最優(yōu)路徑長(zhǎng)度縮短，收斂的速度也更迅速，且在各代路線的平均長(zhǎng)度也優(yōu)于其他兩種算法.本文改進(jìn)的蟻群算法從起點(diǎn)到終點(diǎn)規(guī)劃軌跡有9個(gè)轉(zhuǎn)折點(diǎn)，而傳統(tǒng)的蟻群算法轉(zhuǎn)折點(diǎn)有15 個(gè)，說(shuō)明改進(jìn)的算法具有更好的路徑搜索效率.仿真結(jié)果表明本文改進(jìn)的算法具有更好的路徑規(guī)劃效果.

5 結(jié)束語(yǔ)

本文利用柵格法的便捷性對(duì)環(huán)境進(jìn)行建模，對(duì)每個(gè)柵格進(jìn)行標(biāo)記，應(yīng)用改進(jìn)的蟻群算法從初始柵格移動(dòng)到目標(biāo)柵格進(jìn)行路徑搜索，找到最優(yōu)路徑.本文主要?jiǎng)?chuàng)新在于：1)針對(duì)傳統(tǒng)算法搜索的目的性弱、不能快速搜索到可行路徑的問(wèn)題，通過(guò)改進(jìn)啟發(fā)函數(shù)，增加蟻群搜索的目的性，降低陷入局部最優(yōu)解的概率；2)本文提出了一種自適應(yīng)變化信息素總量的方式，通過(guò)迭代次數(shù)的增加對(duì)信息素總量進(jìn)行調(diào)整，提高全局搜索能力，使算法獲得較快收斂速度.通過(guò)實(shí)驗(yàn)仿真驗(yàn)證了改進(jìn)后的蟻群算法的優(yōu)越性和有效性.