基于蟻群算法的網(wǎng)球機器人路徑規(guī)劃算法研究

邱曉磊

(淮北師范大學 體育學院,安徽 淮北 235000)

0 引言

機器人具有在復雜環(huán)境中工作的優(yōu)勢,因此開發(fā)用于太空探索、建設工作的機器人成為了備受關(guān)注的焦點。網(wǎng)球機器人是一種“迷你型”機器人,由先進材料制作的外殼能夠確保其在極寒、高強紫外線輻射的惡劣環(huán)境下開展外星球表面洞穴、裂縫的勘探工作。路徑規(guī)劃是網(wǎng)球機器人開發(fā)的核心技術(shù),許多學者對機器人路徑規(guī)劃問題進行了廣泛而深入的研究。李明龍[1]對傳統(tǒng)蟻群算法的啟發(fā)信息與信息素更新機制進行改進,并通過仿真試驗驗證了改進蟻群算法所規(guī)劃的路徑在路徑長度和算法效率上均優(yōu)于傳統(tǒng)的蟻群算法。董炫良[2]針對傳統(tǒng)蟻群算法存在盲目搜索、收斂速度慢的問題,提出了以改進人工勢場法規(guī)劃路徑來啟發(fā)蟻群算法,減少了路徑規(guī)劃的盲目性,加快了算法的收斂速度。姚曉通[3]針對傳統(tǒng)蟻群算法易陷入局部最優(yōu)的問題,對傳統(tǒng)蟻群算法的信息素更新規(guī)則進行了改進,提出了一種自定義的自適應信息素揮發(fā)因子更新方法,并通過仿真模型驗證了改進的蟻群算法在最優(yōu)路徑長度和迭代次數(shù)上比傳統(tǒng)的蟻群算法表現(xiàn)更優(yōu)。本文在前人研究的基礎(chǔ)上,對傳統(tǒng)的蟻群算法進行改進,并將其應用于網(wǎng)球機器人的路徑規(guī)劃中。

1 問題描述和環(huán)境建模

網(wǎng)球機器人完成外星球表面探測,需要對周邊的環(huán)境信息進行建模,采取適當?shù)穆窂揭?guī)劃算法來完成機器人運動過程中的避障操作,最終獲得機器人運動的最佳路徑。結(jié)合網(wǎng)球機器人的工作環(huán)境,對網(wǎng)球機器人路徑規(guī)劃問題做出以下基本假設[4]:

1)網(wǎng)球機器人的運動空間是二維有限空間,同時障礙物的位置是確定的;

2)各種障礙物隨機分布在二維有限空間中,且障礙物的形狀不發(fā)生改變;

3)網(wǎng)球機器人的起始位置和目標位置是確定的。

采取蟻群算法來實現(xiàn)網(wǎng)球機器人在存在障礙物的環(huán)境下由起始位置到達目標位置,同時網(wǎng)球機器人在移動的過程中不能和已知的障礙物發(fā)生碰撞。

柵格法是環(huán)境建模的常用方法,同時考慮到網(wǎng)球機器人形狀比較小,將其作為質(zhì)點考慮。在采用柵格法所創(chuàng)建的環(huán)境模型中,白色的柵格為機器人可以行走的柵格,用1表示;黑色的柵格為障礙物柵格,機器人無法通行,用0表示[5]。構(gòu)建網(wǎng)球機器人路徑規(guī)劃的簡單環(huán)境模型與復雜環(huán)境模型,結(jié)果如圖1所示。

圖1 機器人路徑規(guī)劃環(huán)境模型Fig.1 Robot path planning environment model

2 蟻群算法及改進

2.1 蟻群算法

蟻群算法是由Marco Dorigo受到自然界螞蟻覓食行為啟發(fā)而提出的智能優(yōu)化算法,在旅行商問題上被廣泛應用。自然界中單個螞蟻的覓食行為沒有智能行為,而蟻群整體的覓食行為往往表現(xiàn)出一定的智能性。螞蟻在覓食的過程中會在經(jīng)過的路徑上釋放信息素,這樣,之后的螞蟻就可以在信息素的作用下表現(xiàn)出智能化的覓食行為。在最初覓食時,螞蟻經(jīng)過的路徑上無信息素,螞蟻選擇路徑是隨機的,伴隨著時間的推移,覓食距離短的路徑經(jīng)過的螞蟻越來越多,路徑上的信息素濃度也越來越大,最終蟻群會尋找到到達目標點的最佳路徑。

蟻群中的個體根據(jù)信息素濃度選擇下一個移動節(jié)點,同時受到當前節(jié)點和附近節(jié)點的期望信息影響。定義螞蟻k由節(jié)點i選擇節(jié)點j的轉(zhuǎn)移概率為[6]

(1)

式中：τij(t)為螞蟻在路徑ij上留下的信息素濃度；ηij為路徑ij上的啟發(fā)信息；α為信息啟發(fā)因子；β為期望啟發(fā)因子；dk為螞蟻可選節(jié)點集合。

啟發(fā)信息為[7]

(2)

式中：djg為待選節(jié)點j與目標節(jié)點g之間的歐式距離。

蟻群中的螞蟻個體經(jīng)過路徑時會釋放信息素，同時，隨著時間的推移信息素也會蒸發(fā)，即對路徑上信息素的更新。蟻群算法是對所有的螞蟻迭代完成之后進行信息素的更新，信息素更新規(guī)則為：

(3)

(4)

式中：Q為常量；Lk為螞蟻k訪問路徑長度。

2.2 蟻群算法改進

傳統(tǒng)蟻群算法進行路徑規(guī)劃存在盲目性且對路徑規(guī)劃目標點的逼近效果不理想,基于HOCAOGLU算法對狀態(tài)轉(zhuǎn)移規(guī)則進行改進,圖2為HOCAOGLU算法原理示意圖[8]。

圖2 HOCAOGLU算法原理示意圖Fig.2 Schematic diagram of HOCAOGLU algorithm

在圖2中,S點為起始點,G點為目標點。由幾何知識可知,兩點之間直線段距離最短,即起始點S到目標點G之間的最短路徑就是直線段SG。如果在直線段SG之間存在障礙物,那么做SG的垂直平分線ab,其中直線段Sb和直線段bG均不能與直線段SG之間的障礙物碰撞,同時設置直線段和障礙物的最短距離,要求Sb,bG和障礙物的距離均不能小于設定的最短距離,那么此時Sb,bG就是由起始點S到目標點G的最短路徑。如果在Sb之間依舊存在障礙物,那么做Sb的垂直平分線,Sc,cb,bG就是由起始點S到目標點G的最短路徑。按照這樣的方式以此類推,最終獲得由起始點S到目標點G的最短路徑。很明顯,靠近直線段SG的節(jié)點,節(jié)點和起始點S、目標點G的距離之和越小,所規(guī)劃的路徑越短。因此,構(gòu)造包含權(quán)重調(diào)節(jié)因子的引導函數(shù)

(5)

式中：dis和dig分別為當前節(jié)點和起始點、當前節(jié)點和目標點之間的距離，λ為調(diào)節(jié)因子，其表達式為

(6)

式中:Ns為當前節(jié)點次序;Nm為中間節(jié)點次序。

引入調(diào)節(jié)因子λ的作用是在搜索的前期更加側(cè)重于直線段SG附近的節(jié)點,在搜索的后期更加側(cè)重于目標點G附近的節(jié)點,使得螞蟻可以更加快速地找到目標點G。改進蟻群算法螞蟻k由節(jié)點i選擇節(jié)點j的轉(zhuǎn)移概率

(7)

式中:γ為啟發(fā)引導因子。

信息素揮發(fā)因子ρ對路徑規(guī)劃的性能影響比較大。如果信息素揮發(fā)因子ρ比較小,那么信息素揮發(fā)就比較慢,不同路徑上信息素濃度差別比較小,螞蟻個體根據(jù)信息素濃度選擇路徑比較困難,導致算法的收斂速度比較慢;如果信息素揮發(fā)因子ρ比較大,那么信息素揮發(fā)就比較快,導致不同路徑信息素濃度差別比較大,盡管會加快算法的收斂速度,但是會導致算法陷入局部最優(yōu)。基于此,提出一種自適應確定信息素揮發(fā)因子ρ的方法,即

圖3 改進蟻群算法的機器人路徑規(guī)劃算法流程Fig.3 Robot path planning algorithm flow based on improved ant colony algorithm

(8)

設定信息素揮發(fā)因子ρ的取值范圍為[0,1]，ρ的初始值為0.98，若經(jīng)過多次迭代，相鄰兩次最優(yōu)解差值小于0.1%，那么自動調(diào)整信息素揮發(fā)因子為原來信息素揮發(fā)因子的0.9倍。當信息素揮發(fā)因子的值小于0.2時，設定信息素揮發(fā)因子的數(shù)值為0.2。通過自適應確定信息素揮發(fā)因子ρ可以避免該數(shù)值過大或者過小?；诟倪M蟻群算法的機器人路徑規(guī)劃算法流程如圖3所示。

由圖3可知,先創(chuàng)建柵格環(huán)境地圖,并且將關(guān)聯(lián)坐標加入到禁忌表中,設定網(wǎng)球機器人的初始位置和目標位置。采用HOCAOGLU算法對狀態(tài)轉(zhuǎn)移規(guī)則進行改進,根據(jù)改進的規(guī)則來選擇下一個節(jié)點,同時更新節(jié)點和禁忌表,判斷網(wǎng)球機器人是否到達設定的目標位置,如果沒有到達目標位置,則繼續(xù)選擇下一個節(jié)點;如果到達了目標位置,那么對該路徑上的信息素進行更新。同時,采用自適應確定信息素揮發(fā)因子的方法來改變路徑上的信息素,判斷是否達到設定的最大迭代次數(shù),如果沒有達到,則繼續(xù)設定新的起始位置和目標位置;如果達到,那么輸出最優(yōu)規(guī)劃的路徑。

3 網(wǎng)球機器人路徑規(guī)劃仿真

在MATLAB R2020a環(huán)境下,搭建網(wǎng)球機器人路徑規(guī)劃仿真環(huán)境,分別為大小為10×10的簡單障礙物環(huán)境和大小為20×20的復雜障礙物環(huán)境。設定簡單障礙物環(huán)境和復雜障礙物環(huán)境的網(wǎng)球機器人起始位置均為(1, 1),簡單障礙物環(huán)境的目標點位置為(10, 10),復雜障礙物環(huán)境的目標點位置為(20, 20),具體如圖4所示。

圖4 網(wǎng)球機器人起始點與目標點Fig.4 Starting point and target point of tennis robot

調(diào)節(jié)因子λ設置為:當前節(jié)點次序Ns小于中間節(jié)點次序Nm時,調(diào)節(jié)因子λ取值0.75;當前節(jié)點次序Ns大于中間節(jié)點次序Nm時,調(diào)節(jié)因子λ取值0.25。分別采用傳統(tǒng)蟻群算法和改進蟻群算法對簡單環(huán)境模型下的網(wǎng)球機器人進行路徑規(guī)劃仿真,其路徑規(guī)劃結(jié)果和算法收斂結(jié)果如圖5所示。

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

由圖5可知,在簡單環(huán)境模型下,改進蟻群算法所規(guī)劃的路徑長度明顯比傳統(tǒng)蟻群算法所規(guī)劃的路徑長度短,同時,改進蟻群算法在迭代28次就開始收斂,而傳統(tǒng)蟻群算法在迭代52次才開始收斂,即改進蟻群算法對網(wǎng)球機器人的路徑規(guī)劃克服了收斂速度慢、易陷入局部最優(yōu)的缺陷。

分別采用傳統(tǒng)蟻群算法和改進蟻群算法對復雜環(huán)境模型下的網(wǎng)球機器人進行路徑規(guī)劃仿真,其路徑規(guī)劃結(jié)果和算法收斂結(jié)果如圖6所示。

(a) 傳統(tǒng)蟻群算法圖6 復雜環(huán)境模型下仿真結(jié)果對比Fig.6 Comparison of simulation results under the complex environment model

由圖6可知,在復雜環(huán)境模型下,改進蟻群算法所規(guī)劃的路徑長度依舊優(yōu)于傳統(tǒng)蟻群算法所規(guī)劃的路徑長度,同時改進蟻群算法在迭代42次開始收斂,而傳統(tǒng)蟻群算法在迭代68次才開始收斂。

不論是簡單環(huán)境模型,還是復雜環(huán)境模型,改進蟻群算法通過引入引導函數(shù)對轉(zhuǎn)移概率公式進行改進,同時對信息素揮發(fā)因子進行自適應調(diào)節(jié),使得改進蟻群算法的全局尋優(yōu)能力增強,同時收斂速度加快,所規(guī)劃的路徑更優(yōu),路徑規(guī)劃所用時間大大縮短。

4 結(jié)論

網(wǎng)球機器人是開展外星球表面洞穴、裂縫勘探的重要工具,路徑規(guī)劃是網(wǎng)球機器人開發(fā)的核心技術(shù)。本文針對傳統(tǒng)蟻群算法應用于路徑規(guī)劃存在的收斂速度慢、易陷入局部最優(yōu)的缺陷,受到HOCAOGLU算法的啟示,在轉(zhuǎn)移概率中引入引導函數(shù),同時采取自適應方法確定信息素揮發(fā)因子,從而對傳統(tǒng)的蟻群算法進行改進,并將改進的蟻群算法應用于簡單和復雜兩種環(huán)境模型中進行仿真分析。仿真分析結(jié)果表明,改進蟻群算法相對于傳統(tǒng)蟻群算法,所規(guī)劃的路徑大大縮短,同時算法收斂速度大大提升,對網(wǎng)球機器人的開發(fā)具有一定的參考價值。