改進(jìn)蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用

楊樹廣,董西松

(1 山東交通學(xué)院軌道交通學(xué)院 山東 濟(jì)南 250000) (2 中國(guó)科學(xué)院自動(dòng)化研究所多模態(tài)人工智能系統(tǒng)全國(guó)重點(diǎn)實(shí)驗(yàn)室 北京 100190)

0 引言

伴隨著工業(yè)的快速發(fā)展,工業(yè)設(shè)備廣泛應(yīng)用于制造業(yè)、建筑業(yè)、物流、礦山開采等領(lǐng)域,在各種應(yīng)用場(chǎng)景中朝著自動(dòng)化、智能化等方面發(fā)展。智能工業(yè)設(shè)備可以看作一種能自動(dòng)控制、可重復(fù)編程、多功能、高度靈活的多功能機(jī)器人,它具備一些與人大腦相似的思考行為,例如:依靠傳感設(shè)備的感知能力、復(fù)雜環(huán)境下的路徑規(guī)劃能力、不同動(dòng)作的協(xié)調(diào)能力和其他設(shè)備的協(xié)同能力等。移動(dòng)機(jī)器人的路徑規(guī)劃是指機(jī)器人在其工作空間自行規(guī)劃出最優(yōu)或者較優(yōu)的安全路徑[1]。目前常被人們使用的路徑規(guī)劃方法有很多種,例如遺傳算法、人工勢(shì)場(chǎng)法、粒子群算法、Dijkstra算法、蟻群算法等,每種算法都有自己的優(yōu)缺點(diǎn)。在研究經(jīng)典算法的過程中,發(fā)現(xiàn)蟻群算法的魯棒性強(qiáng)、每次搜索相對(duì)獨(dú)立、有正反饋等特點(diǎn),但是在復(fù)雜環(huán)境下也存在尋找最優(yōu)路徑能力較差和容易陷入局部最優(yōu)等問題。

針對(duì)蟻群算法的缺點(diǎn)和問題,很多學(xué)者進(jìn)行了大量的研究。LUO Q等[2]構(gòu)造了不平等分配初始信息素,采用偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則進(jìn)行路徑選擇,自適應(yīng)調(diào)整確定選擇和隨機(jī)選擇的比例,提高了算法的全局最優(yōu)搜索能力和收斂速度;陳丹鳳等[3]提出一種基于強(qiáng)化學(xué)習(xí)和人工勢(shì)場(chǎng)改進(jìn)的蟻群算法,利用強(qiáng)化學(xué)習(xí)對(duì)蟻群算法的參數(shù)進(jìn)行配置,引入人工勢(shì)場(chǎng)算法的局部?jī)?yōu)化機(jī)制,提升算法避障能力,實(shí)現(xiàn)更快更平穩(wěn)的路徑規(guī)劃效果;劉海鵬等[4]采用一種獎(jiǎng)懲機(jī)制對(duì)路徑上的信息素進(jìn)行更新,還利用拐點(diǎn)優(yōu)化算法與分段B樣條曲線相結(jié)合的方法來進(jìn)行路徑優(yōu)化,有效地改善了路徑的平滑性;周敬東等[5]通過改變初始化信息素濃度分配、改變啟發(fā)式函數(shù)、采取螞蟻回退策略、引入螞蟻優(yōu)化排序等方法對(duì)蟻群算法進(jìn)行優(yōu)化,提高了算法的魯棒性和尋優(yōu)能力;錢平等[6]提出了蟻群算法本身參數(shù)及融合遺傳算法以及加入平滑機(jī)制,提高了路徑水下機(jī)器人路徑規(guī)劃的整體性能。

受到上述研究的啟發(fā),針對(duì)經(jīng)典蟻群算法一般容易陷入局部最優(yōu)和容易出現(xiàn)停滯現(xiàn)象等不足,本文采用以下改進(jìn)策略。

(1)將當(dāng)前步長(zhǎng)和終點(diǎn)歐氏距離結(jié)合起來的方法改進(jìn)啟發(fā)函數(shù),并且引用了前位置因子ε和終點(diǎn)位置因子μ,搜索路徑的方向性得到了加強(qiáng)。

(2)將信息素?fù)]發(fā)程度改為一個(gè)動(dòng)態(tài)的更新方式,使算法擁有了較好的收斂性。在與經(jīng)典蟻群算法比較中得出,改進(jìn)蟻群算法增大了螞蟻選擇最優(yōu)路徑的可能性,避免出現(xiàn)局部最優(yōu)解,提高了算法收斂速度的同時(shí),具有較好的全局搜索能力,使原有算法的各項(xiàng)指標(biāo)都得到提升。

1 移動(dòng)機(jī)器人的環(huán)境模型

構(gòu)建環(huán)境地圖的目的在于幫助移動(dòng)機(jī)器人在建立好的含有障礙的環(huán)境模型中規(guī)劃出一條從起點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑。建立適用于移動(dòng)設(shè)備路徑規(guī)劃的環(huán)境模型已經(jīng)有了許多成熟的方法,現(xiàn)有的基本的環(huán)境模型主要包括柵格分解圖、四叉分解圖、可視圖、Voronoi圖。其中柵格分解圖的代表性強(qiáng),構(gòu)建方法較為簡(jiǎn)單和后期維護(hù)成本低。柵格分解圖就是假設(shè)移動(dòng)機(jī)器人的工作環(huán)境是在一個(gè)二維空間,將空間按照單位大小的正方形劃分為大小相同的單元。一般情況下,在柵格分解圖建模中,0表示可以自由移動(dòng)的區(qū)域,1表示的是存在障礙物的區(qū)域,0和1分別對(duì)應(yīng)了白色和黑色區(qū)域。本文不考慮障礙物的形狀,如果障礙物所占面積不足一個(gè)柵格面積時(shí),也按照一個(gè)柵格的面積進(jìn)行計(jì)算。

移動(dòng)機(jī)器人的環(huán)境地圖建模如圖1所示,柵格分解圖中的x、y坐標(biāo)軸和一般的坐標(biāo)軸遞增順序是一樣的。柵格分解圖共有i行m列,單個(gè)柵格邊長(zhǎng)為1,則每個(gè)柵格中心坐標(biāo)可以表示為式(1)所示:

圖1 移動(dòng)機(jī)器人環(huán)境模型

(1)

式(1)中xi、yi表示此點(diǎn)中心位置的橫坐標(biāo)、縱坐標(biāo);mod(*)表示除后的余數(shù);ceil(*)表示每個(gè)元素四舍五入到大于或等于此元素的最接近的數(shù)。

2 經(jīng)典蟻群算法

2.1 算法基本原理

我們所熟知的螞蟻在大自然中尋找食物時(shí),會(huì)留下類似于信息素之類的物質(zhì),其他螞蟻可能感知到先前螞蟻留下的這種物質(zhì)。我們用信息素濃度的表征此路徑的長(zhǎng)短,所以在較短的路徑上的信息素濃度較高。信息素的濃度也會(huì)影響螞蟻選擇路徑的概率,再加上蟻群在路程中也會(huì)留下信息素,最終會(huì)形成一個(gè)正反饋,不斷引導(dǎo)著蟻群尋找出最短的路徑。

2.2 算法公式

(2)

ηij=1/dij

(3)

式(2)中,τij(t)表示t時(shí)刻i到j(luò)上的信息素濃度;ηij(t)為啟發(fā)函數(shù),表示螞蟻從i到j(luò)的期望程度;allow表示屬于可以行進(jìn)的地圖點(diǎn);α表示信息素重要因子;β表示啟發(fā)函數(shù)重要因子。

在蟻群經(jīng)過某個(gè)路徑會(huì)留下信息素的同時(shí),原有的信息素濃度也會(huì)慢慢下降,設(shè)定參數(shù)ρ(0<ρ<1)表示信息素的揮發(fā)程度。所以,當(dāng)循環(huán)一次后,已經(jīng)走過的每個(gè)路徑上的信息素濃度會(huì)產(chǎn)生變化,其公式如式(4)所示:

(4)

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

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

蟻群算法中的啟發(fā)函數(shù)只是將下個(gè)節(jié)點(diǎn)與終點(diǎn)之間的歐氏距離考慮進(jìn)去,考慮的因素太單一,容易陷入局部最優(yōu)解。如果在原有公式加入當(dāng)前位置到下個(gè)選擇可選擇位置的歐氏距離,路徑的搜索的方向性被增強(qiáng)。在計(jì)算中加入位置因子可以調(diào)整兩個(gè)距離的權(quán)重,這樣能使算法的調(diào)整變得靈活。其公式如式(5)所示:

(5)

式(5)中,dis表示從當(dāng)前節(jié)點(diǎn)和下一個(gè)待選節(jié)點(diǎn)之間的歐式距離;djE從下一個(gè)待選節(jié)點(diǎn)到E終點(diǎn)的距離的歐式距離;ε表示當(dāng)前位置因子;μ表示終點(diǎn)位置因子。

3.2 改進(jìn)信息素?fù)]發(fā)程度

蟻群算法中的螞蟻是依靠信息素來做去強(qiáng)化最優(yōu)路徑的選擇,隨著時(shí)間額推移,以前留下的信息素會(huì)逐漸消失。信息素的揮發(fā)程度會(huì)直接影響算法收斂快慢和對(duì)全局路徑的搜索,它表示了螞蟻群中的每個(gè)螞蟻之間會(huì)相互影響路徑的選擇,是螞蟻獲取外界信息的途徑。將信息素?fù)]發(fā)程度改為一個(gè)動(dòng)態(tài)的更新方式會(huì)讓蟻群搜索更多的可行路徑,隨著迭代次數(shù)的增加ρ逐漸減小,螞蟻將朝著信息素濃度增高的路徑集中,因此會(huì)增快收斂速度。其公式如式(6)所示:

(6)

式(6)中,T代表總迭代次數(shù);t代表當(dāng)前迭代次數(shù)。

4 仿真實(shí)驗(yàn)驗(yàn)證及分析

為了驗(yàn)證改進(jìn)蟻群算法加快了收斂速度的同時(shí)具有較高的全局搜索能力等方面的優(yōu)化效果,在MTALAB2022a上選用20×20規(guī)模和30×30規(guī)模的柵格分解圖對(duì)于改進(jìn)后的蟻群算法進(jìn)行仿真。實(shí)驗(yàn)運(yùn)行電腦的操作系統(tǒng)為Windows10,處理器為Intel i7-7700HQ CPU,內(nèi)存為16 GB,起始點(diǎn)和終點(diǎn)分別設(shè)置在柵格分解圖的左上方與右下方。算法基本參數(shù):迭代次數(shù)K=100次;螞蟻的數(shù)量M=50只;信息素重要程度因子α=1.2;起點(diǎn)位置因子ε=0.4;終點(diǎn)位置因子μ=0.6;啟發(fā)函數(shù)重要因子β=8;信息素的揮發(fā)程度ρ=0.6。

4.1 20×20柵格分解圖仿真

基于表所給的參數(shù)指標(biāo),首先使用20×20的固定障礙物的柵格分解圖分別對(duì)經(jīng)典蟻群算法和改進(jìn)蟻群算法進(jìn)行仿真實(shí)驗(yàn),結(jié)果如圖2、圖3所示,并對(duì)結(jié)果進(jìn)行對(duì)比。

圖2 20×20經(jīng)典蟻群算法收斂曲線變化趨勢(shì)和運(yùn)動(dòng)軌跡圖

圖3 20×20改進(jìn)蟻群算法收斂曲線變化趨勢(shì)和運(yùn)動(dòng)軌跡圖

從本次仿真結(jié)果得出改進(jìn)蟻群算法的最優(yōu)路徑長(zhǎng)度和迭代次數(shù)為31.799 m和15次,比經(jīng)典蟻群算法的路徑長(zhǎng)度減少了10.58%,迭代次數(shù)減少了51.61%。仿真結(jié)果表明,改進(jìn)蟻群算法的收斂速度遠(yuǎn)高于經(jīng)典蟻群算法,同時(shí)容易看出其各項(xiàng)指標(biāo)更加優(yōu)越。

4.2 30×30柵格分解圖仿真

為進(jìn)一步驗(yàn)證本文算法的優(yōu)越性,在30×30的固定障礙物的柵格分解圖中將兩種算法再次進(jìn)行對(duì)比仿真實(shí)驗(yàn),各個(gè)參數(shù)設(shè)置和4.1中保持一致。結(jié)果如圖4、圖5所示,并對(duì)結(jié)果進(jìn)行分析。

圖4 30×30經(jīng)典蟻群算法收斂曲線變化趨勢(shì)和運(yùn)動(dòng)軌跡圖

圖5 30×30改進(jìn)蟻群算法收斂曲線變化趨勢(shì)和運(yùn)動(dòng)軌跡圖

從本次仿真結(jié)果來看經(jīng)典蟻群算法前期路徑搜索方向較差,容易陷入局部最優(yōu)和選擇方向錯(cuò)誤,這是因?yàn)樾畔⑺氐膿]發(fā)程度在迭代開始時(shí)分布均勻,信息素的揮發(fā)程度的正反饋不強(qiáng),啟發(fā)式信息的方向變?nèi)?。?jīng)典蟻群算法在30×30的仿真實(shí)驗(yàn)中穩(wěn)定性很差,直到最后也沒有能迭代收斂,甚至在搜尋路徑的過程中還出現(xiàn)了方向的混亂。改進(jìn)蟻群算法在第28次迭代時(shí)就能夠收斂,此時(shí)的路徑長(zhǎng)度僅為46.769 6 m,并且沒有出現(xiàn)方向混亂。

5 結(jié)語(yǔ)

綜上所述,本文通過兩組對(duì)比實(shí)驗(yàn)在20×20和30×30的柵格分解圖中路徑規(guī)劃的最優(yōu)路徑長(zhǎng)度、找到最優(yōu)路徑的迭代次數(shù)等數(shù)據(jù),說明了改進(jìn)蟻群算法能有效減少最優(yōu)路徑的迭代次數(shù),加快收斂速度,增加規(guī)劃軌跡的平滑度等方面均優(yōu)于蟻群算法,此外經(jīng)典蟻群算法在處理較為復(fù)雜的地圖時(shí)會(huì)出現(xiàn)各種問題,證明本次算法在路徑規(guī)劃問題求解上的實(shí)用性。移動(dòng)機(jī)器人屬于大型設(shè)備,對(duì)于路徑的平滑程度、穩(wěn)定性和迭代次數(shù)都有較高的要求。改進(jìn)蟻群算法能滿足設(shè)備運(yùn)行的同時(shí)也提高了設(shè)備的安全性,使用戶的使用變得更加高效便捷。