基于改進(jìn)蟻群算法的機(jī)器人全局路徑規(guī)劃研究*

曹新亮，王智文，馮 晶，查 敏，王宇航

(1.廣西科技大學(xué)電氣與信息工程學(xué)院，廣西 柳州 545006； 2.廣西科技大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院,廣西 柳州 545006； 3.廣西師范大學(xué)多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004； 4.廣西師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，廣西 桂林 541004 )

1 引言

隨著科技的快速發(fā)展以及機(jī)器人的大量應(yīng)用，人們對(duì)機(jī)器人的要求也越來(lái)越高，尤其表現(xiàn)在對(duì)機(jī)器人的智能化方面的要求，而機(jī)器人自主路徑規(guī)劃是實(shí)現(xiàn)機(jī)器人智能化的重要步驟，路徑規(guī)劃是指規(guī)劃?rùn)C(jī)器人從起點(diǎn)位置出發(fā)，無(wú)碰撞、安全到達(dá)指定目標(biāo)位置的最優(yōu)路徑。迄今為止，國(guó)內(nèi)外很多學(xué)者圍繞機(jī)器人路徑規(guī)劃開展了大量研究，如傳統(tǒng)算法有迪杰斯特拉算法[1]、A*算法[2,3]、人工勢(shì)場(chǎng)法[4]等。隨著研究的深入，傳統(tǒng)算法已經(jīng)無(wú)法很好地解決問(wèn)題，對(duì)此許多學(xué)者提出了一系列的智能算法，如遺傳算法、花朵授粉算法[5]、粒子群算法[6]、螢火蟲算法[7]、蟻群算法[8]等，不同的算法在不同的限定條件下有著其特有的優(yōu)勢(shì)，但是也存在不足之處。

蟻群算法是由意大利學(xué)者M(jìn)aro Dorigo首次提出的，是一種分布式仿生算法，本身具有較強(qiáng)的魯棒性，但也存在著收斂速度慢、容易陷入局部最優(yōu)的問(wèn)題。為了解決這些問(wèn)題，國(guó)內(nèi)外許多學(xué)者對(duì)傳統(tǒng)的蟻群算法進(jìn)行了相應(yīng)的改進(jìn)。Lee[9]改進(jìn)蟻群算法轉(zhuǎn)移概率函數(shù)和信息素更新規(guī)則，提高了算法的尋優(yōu)能力；Mouhcine等人[10]通過(guò)獲取動(dòng)態(tài)數(shù)據(jù)，代理協(xié)作獲取最優(yōu)路徑，優(yōu)化蟻群算法，提高了算法全局尋優(yōu)性能，避免了陷入局部最優(yōu)；Jiao等人[11]在多態(tài)蟻群算法中引入了自適應(yīng)策略和自適應(yīng)信息更新策略，避免了死鎖問(wèn)題，提高其全局搜索能力；Wang等人[12]通過(guò)應(yīng)用禁忌表和網(wǎng)絡(luò)權(quán)重表，縮小了算法的搜索范圍，提高了搜索效率；Luo等人[13]使用偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則選擇路徑，提高了算法的全局搜索能力和收斂速度；王志中[14]提出了螞蟻相遇策略，提高了算法的搜索效率，改進(jìn)后的算法具有更快的收斂速度；趙峰等人[15]提出了一種自適應(yīng)搜索半徑蟻群算法規(guī)劃路徑，提高了環(huán)境適應(yīng)能力和收斂速度；黃于欣等人[16]改進(jìn)路徑啟發(fā)函數(shù)，并引入動(dòng)態(tài)參數(shù)調(diào)整機(jī)制，優(yōu)化蟻群搜索和開發(fā)機(jī)制，有效避免算法陷入局部最優(yōu)，同時(shí)提高了算法收斂速度；鄭延斌等人[17]通過(guò)引入反向?qū)W習(xí)方法對(duì)螞蟻位置進(jìn)行初化分布來(lái)改進(jìn)蟻群算法，提高了算法的全局搜索能力，同時(shí)利用粒子群算法中的自適應(yīng)慣性權(quán)重因子調(diào)節(jié)信息素濃度Q值，使其自適應(yīng)變化，避免陷入局部最優(yōu)。

本文針對(duì)傳統(tǒng)蟻群算法收斂速度慢進(jìn)行改進(jìn)，建立新的數(shù)學(xué)模型，使初始信息素濃度不均勻分布，并通過(guò)仿真實(shí)驗(yàn)與傳統(tǒng)的蟻群算法比較，以驗(yàn)證改進(jìn)前后算法的效果。實(shí)驗(yàn)結(jié)果表明，本文改進(jìn)的算法能夠有效地提高蟻群算法的收斂速度。

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

2.1 蟻群算法基本原理

蟻群算法是根據(jù)蟻群覓食行為提出的一種仿生智能算法，螞蟻在尋找食物的過(guò)程中會(huì)在經(jīng)過(guò)的路徑上留下信息素，而遺留下來(lái)的信息素能夠被其他螞蟻感知到，螞蟻根據(jù)信息素濃度選擇路徑，優(yōu)先選擇信息素濃度較高的路徑，這樣逐漸形成一種正反饋現(xiàn)象。螞蟻趨向選擇較短的路徑，經(jīng)過(guò)的螞蟻越多，表明信息素濃度越高，該路徑上的信息素濃度就越大，其它螞蟻選擇這條路徑的幾率就越大，螞蟻就是通過(guò)這種信息傳遞的方式選擇1條較優(yōu)路徑進(jìn)行覓食。蟻群算法中的路徑選擇概率和信息素濃度的更新是2個(gè)至關(guān)重要的因素，決定著算法的尋優(yōu)效果。

2.2 蟻群算法模型

(1)

信息素會(huì)在螞蟻完成1次循環(huán)后進(jìn)行更新，根據(jù)式(2)～式(4)來(lái)調(diào)整信息素。

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

(2)

(3)

(4)

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

針對(duì)傳統(tǒng)蟻群算法存在收斂速度慢的問(wèn)題，本文提出對(duì)初始信息素進(jìn)行差異化設(shè)置，防止非最優(yōu)路徑上的信息素對(duì)螞蟻產(chǎn)生誤導(dǎo)，從而實(shí)現(xiàn)快速收斂的效果。

3.1 蟻群算法的具體改進(jìn)

傳統(tǒng)蟻群算法初始信息素濃度是均勻分配的，這樣算法初期搜索具有較強(qiáng)的盲目性，進(jìn)而導(dǎo)致收斂速度慢等問(wèn)題。螞蟻通常根據(jù)路徑上信息素濃度的差異來(lái)尋找最優(yōu)路徑，在信息素的引導(dǎo)下選擇1條從起始點(diǎn)到目標(biāo)點(diǎn)的完整路徑，由于初始信息素濃度是相同的，而且初期搜索具有很強(qiáng)的盲目性，這樣就會(huì)出現(xiàn)誤導(dǎo)，無(wú)法選擇最優(yōu)路徑，容易使算法陷入局部最優(yōu)，影響算法尋優(yōu)能力。為了避免因信息素導(dǎo)致算法陷入局部最優(yōu)，減少錯(cuò)誤的啟發(fā)信息對(duì)螞蟻的誤導(dǎo)，提高其尋優(yōu)能力，考慮機(jī)器人移動(dòng)過(guò)程中的實(shí)際工作環(huán)境，本文構(gòu)造新的數(shù)學(xué)模型，對(duì)初始信息素濃度進(jìn)行預(yù)先的差異化設(shè)置，以達(dá)到快速尋優(yōu)的效果。如圖1所示，由于最優(yōu)路徑多集中在起始點(diǎn)S和目標(biāo)點(diǎn)E的連線L附近區(qū)域，同時(shí)受環(huán)境中障礙物的影響。首先根據(jù)起始點(diǎn)和目標(biāo)點(diǎn)在柵格地圖上選取出優(yōu)選區(qū)域，預(yù)設(shè)優(yōu)選區(qū)域外的初始信息素的值τ0，同時(shí)在優(yōu)選區(qū)域內(nèi)預(yù)設(shè)初始信息素值C，并為優(yōu)選區(qū)域內(nèi)的點(diǎn)設(shè)定不同的增量，具體設(shè)置方法如圖2所示：在優(yōu)選區(qū)域內(nèi)，節(jié)點(diǎn)j是螞蟻下一步移動(dòng)的節(jié)點(diǎn)，根據(jù)起始點(diǎn)與目標(biāo)點(diǎn)的直線距離X與節(jié)點(diǎn)j到起始點(diǎn)和目標(biāo)點(diǎn)的距離和的比值設(shè)置節(jié)點(diǎn)j的信息素濃度增量，對(duì)該區(qū)域的初始信息素進(jìn)行差異化增加，使得對(duì)初始信息素濃度的差異化設(shè)置更符合實(shí)際求解問(wèn)題的要求。

Figure 1 Mathematical model diagram of initial pheromone setting 圖1 初始信息素設(shè)置數(shù)學(xué)模型圖

Figure 2 Initial pheromone differentiation setting圖2 初始信息素差異化設(shè)置

假設(shè)蟻群算法尋找選擇節(jié)點(diǎn)j時(shí)，節(jié)點(diǎn)j到起始點(diǎn)S的距離為X1,到目標(biāo)點(diǎn)E的距離為X2，X1+X2的值越小，則認(rèn)為該點(diǎn)越優(yōu)。在該點(diǎn)設(shè)定的初始信息素濃度越高，越能滿足實(shí)際需求。如圖1和圖2所示，優(yōu)選區(qū)域內(nèi)各位置的初始信息素濃度增量是根據(jù)建立的數(shù)學(xué)模型進(jìn)行設(shè)置的，以起始點(diǎn)S和目標(biāo)點(diǎn)E為焦點(diǎn)可以得到無(wú)數(shù)個(gè)橢圓，這樣就可以將優(yōu)選區(qū)域劃分成多個(gè)部分，每個(gè)部分分別具有不同的信息素濃度增量，但在優(yōu)選區(qū)域中會(huì)存在一系列信息素相同的節(jié)點(diǎn)?？紤]存在障礙物的因素，為了避免算法在尋優(yōu)時(shí)選擇跨越性較大，應(yīng)盡量靠近上一個(gè)節(jié)點(diǎn)。所以，選擇節(jié)點(diǎn)j時(shí)，先判斷上一節(jié)點(diǎn)在橢圓中的位置，再對(duì)比X1、X2的值的大小。若上一個(gè)節(jié)點(diǎn)靠近起始點(diǎn)S的位置，即當(dāng)X1X2時(shí)，選擇節(jié)點(diǎn)j,這樣避免了優(yōu)化不穩(wěn)定性。

節(jié)點(diǎn)j的初始信息素濃度值計(jì)算如式(5)所示：

(5)

其中，τ0為優(yōu)選區(qū)域以外柵格地圖節(jié)點(diǎn)的信息素值，C為優(yōu)選區(qū)域內(nèi)節(jié)點(diǎn)信息素值，R為優(yōu)選區(qū)域內(nèi)節(jié)點(diǎn)集合，λ[X/(X1+X2)]為優(yōu)選區(qū)域內(nèi)柵格地圖位置的信息素增量，λ為信息素增量系數(shù)，X為理想最優(yōu)路徑SE的長(zhǎng)度，X1為節(jié)點(diǎn)j到起始點(diǎn)S的距離長(zhǎng)度，X2為節(jié)點(diǎn)j到目標(biāo)點(diǎn)E的距離長(zhǎng)度。

3.2 改進(jìn)算法步驟

本文提出的改進(jìn)蟻群算法的實(shí)施步驟分為5個(gè)階段:

(1) 設(shè)置蟻群算法基本參數(shù)：螞蟻總量M、信息啟發(fā)系數(shù)α、期望啟發(fā)系數(shù)β、信息素?fù)]發(fā)系數(shù)ρ、調(diào)整系數(shù)δ、最大迭代次數(shù)Nmax。

(2) 利用柵格法對(duì)環(huán)境地圖進(jìn)行建模，根據(jù)起始點(diǎn)和目標(biāo)點(diǎn)選出優(yōu)選區(qū)域，增加其信息素初始值，并根據(jù)節(jié)點(diǎn)與起始點(diǎn)和目標(biāo)點(diǎn)的距離之和和起始點(diǎn)與目標(biāo)點(diǎn)之間距離的比例對(duì)信息素進(jìn)行差異化增量設(shè)置。

(3) 尋找路徑，對(duì)禁忌表進(jìn)行初始化并將起點(diǎn)加入其中，根據(jù)狀態(tài)轉(zhuǎn)移概率(如式(1)所示) 尋找下一可達(dá)節(jié)點(diǎn)，直到螞蟻選取的節(jié)點(diǎn)為目標(biāo)點(diǎn)時(shí)，停止搜索。

(4) 判斷循環(huán)迭代次數(shù)是否達(dá)到設(shè)定值，如果達(dá)到，則保存信息，否則繼續(xù)進(jìn)行路徑搜索。

(5) 得到最優(yōu)路徑，算法終止。

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

4.1 實(shí)驗(yàn)環(huán)境建模

在實(shí)際工作環(huán)境中，移動(dòng)機(jī)器人工作環(huán)境是復(fù)雜多變的，且為三維空間。為了便于研究，本文對(duì)環(huán)境進(jìn)行簡(jiǎn)化建模。柵格法是一種常用的環(huán)境表示方法，因其簡(jiǎn)單方便(二維環(huán)境)，環(huán)境建模的復(fù)雜性小，因而本文環(huán)境建模采用柵格法[18]。在柵格地圖中，工作環(huán)境被劃分為很多柵格，其中包括有障礙物和無(wú)障礙的柵格，在仿真程序中用 0 表示此柵格無(wú)障礙物，機(jī)器人可以通過(guò)此柵格，用1表示柵格有障礙物，機(jī)器人無(wú)法通過(guò)，需選擇其他柵格。柵格的尺寸大小可根據(jù)工作環(huán)境中的障礙物尺寸以及安全距離進(jìn)行設(shè)置。為了實(shí)現(xiàn)程序仿真，需要對(duì)柵格進(jìn)行標(biāo)識(shí)，如圖 3 所示，以10×10的柵格環(huán)境為例來(lái)說(shuō)明。

Figure 3 Relationship between raster map and number圖3 柵格地圖與編號(hào)的關(guān)系

如圖3所示，白色柵格表示無(wú)障礙物的柵格，黑色柵格則表示有障礙物的柵格，在地圖中對(duì)每個(gè)柵格編號(hào)，不同序號(hào)的柵格在坐標(biāo)系中的坐標(biāo)可用式(6)來(lái)表示。

(6)

其中，mod為取余運(yùn)算，ceil表示向后取整，Ni是對(duì)應(yīng)柵格的標(biāo)號(hào)，N表示每一列的柵格數(shù)量，取柵格中心位置作為柵格在坐標(biāo)系中的坐標(biāo)。

這樣機(jī)器人全局路徑規(guī)劃的問(wèn)題就轉(zhuǎn)變成了利用算法在柵格地圖上尋找由起始點(diǎn)S到目標(biāo)點(diǎn)E的有序的柵格子集，這些柵格子集的中心連線便是算法尋找的路徑。

4.2 實(shí)驗(yàn)結(jié)果及分析

蟻群算法是一種概率型算法，具有一定隨機(jī)性，算法的性能可以依據(jù)算法運(yùn)行一次得到最優(yōu)解的可能性大小來(lái)判斷。在20×20的地圖環(huán)境中將傳統(tǒng)蟻群算法和本文改進(jìn)的蟻群算法各運(yùn)行 20 次進(jìn)行分析，其中螞蟻的規(guī)模M設(shè)置為50，迭代次數(shù)為100，信息啟發(fā)式因子α為1，期望啟發(fā)式因子β為7，信息素?fù)]發(fā)系數(shù)ρ為0.3，參數(shù)Q為1，C為0.5。對(duì)于蟻群算法的參數(shù)選取，是基于大量的實(shí)驗(yàn)仿真得到的，C設(shè)置為0.5，效果更優(yōu)。

Table 1 Algorithm simulation results in 20×20 environment 表1 20×20環(huán)境中算法仿真結(jié)果

由圖4～圖6及表1可知，在20×20環(huán)境下，改進(jìn)后的蟻群算法收斂速度較快，主要原因是傳統(tǒng)蟻群算法的初始信息素濃度設(shè)置的值是相同的，導(dǎo)致算法在迭代初期具有很大的搜索盲目性，進(jìn)而會(huì)收斂較慢，而改進(jìn)后的算法在初期就劃定全局最優(yōu)區(qū)域，并賦予一個(gè)較小的初值，同時(shí)在優(yōu)選區(qū)域中，根據(jù)新的初始信息素濃度設(shè)置模型，對(duì)柵格地圖中各點(diǎn)初始信息素濃度進(jìn)行差異化設(shè)置，避免了前期搜索的盲目性，能更快地尋找最優(yōu)路徑，提高了算法的收斂速度。本文改進(jìn)的蟻群算法收斂速度要快于傳統(tǒng)蟻群算法。

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

傳統(tǒng)蟻群算法存在著收斂速度慢的不足，尋優(yōu)效果差，本文提出了一種改進(jìn)蟻群算法，通過(guò)不均勻設(shè)置初始信息濃度，使得算法在開始尋優(yōu)時(shí)，能避免尋優(yōu)盲目性，優(yōu)選區(qū)域的存在，使得尋優(yōu)初期就在一個(gè)較好的范圍內(nèi)，大大提高算法的收斂速度和尋優(yōu)效果?？紤]到研究機(jī)器人全局路徑問(wèn)題時(shí)，障礙物多是靜態(tài)的，為了降低空間復(fù)雜度，將三維空間降維為二維空間，本文采用柵格地圖對(duì)環(huán)境建模，并建立了新的模型，通過(guò)Matlab仿真實(shí)驗(yàn)，驗(yàn)證了本文改進(jìn)蟻群算法對(duì)解決機(jī)器人路徑規(guī)劃問(wèn)題的有效性和可行性。本文只是針對(duì)蟻群算法其中一點(diǎn)不足做出改進(jìn)，后期將對(duì)算法的其他性能做進(jìn)一步研究，希望本文做出的改進(jìn)能為后續(xù)工作提供幫助，同時(shí)為其他研究者提供一些參考。

Figure 4 Path planning results and convergence curves of the algorithm in 20×20 environment (1)圖4 20×20環(huán)境(1)中算法的路徑規(guī)劃結(jié)果及收斂曲線

Figure 5 Path planning results and convergence curves of the algorithm in 20×20 environment (2)圖5 20×20環(huán)境(2)中算法的路徑規(guī)劃結(jié)果及收斂曲線

Figure 6 Path planning results and convergence curves of the algorithm in 20×20 environment (3)圖6 20×20環(huán)境(3)中算法的路徑規(guī)劃結(jié)果及收斂曲線