改進(jìn)蟻群算法的移動機(jī)器人三維路徑規(guī)劃

李志錕

(1.廣東科技學(xué)院 機(jī)電工程學(xué)院，廣東 東莞 523083；2.安徽工程大學(xué) 高端裝備先進(jìn)感知與智能控制教育部重點實驗室，安徽 蕪湖 241005)

0 引言

科學(xué)技術(shù)的高速發(fā)展帶來了移動機(jī)器人性能的不斷提升，作為集成了動態(tài)決策與路徑規(guī)劃[1-5]、環(huán)境感知、可編程及模塊可拓展等特點的移動機(jī)器人，其應(yīng)用領(lǐng)域不斷拓寬。比如農(nóng)業(yè)、醫(yī)療服務(wù)、科學(xué)實驗和空間探測等，這些領(lǐng)域的應(yīng)用場景不局限于二維環(huán)境，而且大量應(yīng)用于三維環(huán)境。移動機(jī)器人的種種應(yīng)用也基本上都基于三維環(huán)境展開，因此，從未來的發(fā)展前景以及日常實用性角度出發(fā)，研究三維環(huán)境下的移動機(jī)器人路徑規(guī)劃具有十分重要的意義。

目前，由于在三維空間中，三維地圖環(huán)境較為復(fù)雜，移動機(jī)器人可移動方向大幅增加，加上目前有關(guān)移動機(jī)器人路徑規(guī)劃的研究成果較少，因此，移動機(jī)器人在三維環(huán)境下的路徑規(guī)劃難度高于二維環(huán)境下的路徑規(guī)劃。據(jù)此，本文將研究移動機(jī)器人應(yīng)用改進(jìn)蟻群算法[6-13]的問題以及在三維環(huán)境下的路徑規(guī)劃問題。

移動機(jī)器人三維路徑規(guī)劃是指移動機(jī)器人在三維地圖環(huán)境中尋找出一條從起始點到終點的最優(yōu)路徑[14-16]，所規(guī)劃出的最優(yōu)路徑必須滿足與所有障礙物安全無碰撞。目前，路徑規(guī)劃算法主要是基于二維地圖環(huán)境運行，由于應(yīng)用在三維地圖環(huán)境下的路徑規(guī)劃算法信息量存儲較大，同時要考慮三個維度導(dǎo)致計算復(fù)雜。因此，已有的三維路徑規(guī)劃算法較少，主要有：遺傳算法、A*算法、蟻群算法等。蟻群算法具有分布計算、收斂速度相對較快的優(yōu)勢，非常適合移動機(jī)器人路徑規(guī)劃，通過對蟻群算法進(jìn)行改進(jìn)，不僅適用于移動機(jī)器人二維路徑規(guī)劃，而且適用于移動機(jī)器人三維路徑規(guī)劃。

1 三維環(huán)境的抽象建模

對移動機(jī)器人進(jìn)行三維路徑規(guī)劃前，需要通過對三維地圖構(gòu)造出三維空間模型。模型構(gòu)造方法：在三維地圖中挑選合適的頂點作為坐標(biāo)原點，對該坐標(biāo)原點建立三維直角坐標(biāo)系A(chǔ)-XYZ，A點為坐標(biāo)原點，確定柵格地圖的最大長度AB，最大寬度AD，最大高度AE，構(gòu)造出了容納三維地圖的立方體ABCD-EFGH，如圖1所示，將直角坐標(biāo)系上的三維地圖劃分為獨立的立方體，再對立方體柵格化為體積相等的小柵格。然后將三維地圖空間沿著X軸方向進(jìn)行等分，得到(n+1)個長方體，接著對(n+1)個長方體沿著Y軸方向進(jìn)行m等分，得到了(n+1)×(m+1)個長方體；后沿著Z軸方向?qū)θS地圖空間進(jìn)行l(wèi)等分，得到了(n+1)×(m+1)×(l+1)個正方體，這些正方體就是組成三維地圖的獨立柵格。

圖1 三維環(huán)境模型

利用以上三維地圖的構(gòu)建方法，三維地圖的立方體區(qū)域ABCD-EFGH被切割成三維點集合，集合中的每一個點a都將擁有兩個坐標(biāo),分別為序號坐標(biāo)a(1)(i,j,k)(i=0,1,…，n;j=0,1,…,m;k=0,1,…,l)與位置坐標(biāo)a(2)(xi,yi,zi)，其中：i是當(dāng)前位置點a沿著AB方向的劃分序號，j是當(dāng)前位置點a沿著AD方向的劃分序號，k是當(dāng)前位置點a沿著AE方向的劃分序號。令A(yù)B=h，則在三維地圖環(huán)境下的任意一點p(i,j,k)與三維坐標(biāo)A-XYZ中的點p(x,y,z)的對應(yīng)關(guān)系如下：

2 三維環(huán)境下移動機(jī)器人路徑規(guī)劃

2.1 信息素更新策略

蟻群算法利用信息素的分布來吸引蟻群進(jìn)行路徑尋優(yōu)，因此，信息素的初始化分布以及信息素的更新策略對于蟻群最終搜索到的最優(yōu)路徑至關(guān)重要。本研究已經(jīng)介紹了如何將三維地圖離散為一系列的三維柵格節(jié)點，這些三維柵格節(jié)點組成了蟻群算法可以移動的柵格集合。通過信息素的初始化，在蟻群搜索路徑前，在每個三維柵格節(jié)點設(shè)定初始信息素值，經(jīng)過一次迭代后，每個三維柵格節(jié)點進(jìn)行信息素更新。

蟻群在路徑尋優(yōu)時，通過螞蟻信息素的分泌起到正反饋作用，因此，在三維柵格節(jié)點合理分布初始信息素對于蟻群后期尋優(yōu)至關(guān)重要。設(shè)定螞蟻從起始點到終點移動時的方向所指向的區(qū)域為有利通行區(qū)域，增加該區(qū)域的信息素初始值，利用信息素的正反饋作用激勵蟻群快速到達(dá)終點，設(shè)定初始信息素值為τ1，初始信息素不均勻分布公式為

(4)

其中：τ0為信息素初始值；C為大于1的常數(shù)；R為有利通行區(qū)域。根據(jù)三維地圖的復(fù)雜程度，合理調(diào)整C值的大小，吸引蟻群朝向最優(yōu)路徑靠攏，既保證了蟻群的搜索效率，又兼顧了全局路徑搜索的目的，有利于提高蟻群算法收斂速度。

通過全局信息素更新和局部信息素更新兩種方式，實現(xiàn)改進(jìn)信息素更新策略，當(dāng)螞蟻到達(dá)某個三維柵格時，通過降低該柵格的信息素值，增加螞蟻搜索其他三維柵格的概率，達(dá)到全局路徑搜索的目的。局部信息素隨著螞蟻的移動動態(tài)調(diào)整，局部信息素更新公式為

τijk=(1-ζ)τijk+τ1,

(5)

其中：τijk為三維柵格(i,j,k)上已有的信息素值；ζ為信息素值的衰減系數(shù)。

為了避免信息素值過高或過低，導(dǎo)致蟻群算法過快的收斂于非最優(yōu)路徑，限制信息素值τijk∈[τmin,τmax]。當(dāng)螞蟻從起始點到終點完成一次路徑尋優(yōu)時，篩選出所有最優(yōu)路徑，增加最優(yōu)路徑所涉及的三維柵格信息素值，全局信息素更新公式為

τijk=(1-ρ)τijk+ρΔτijk,

(6)

其中：l(m)表示第m只螞蟻完成一次路徑尋優(yōu)所爬行的路徑長度；ρ為信息素更新系數(shù)；K為常數(shù)。

2.2 多元化啟發(fā)函數(shù)設(shè)計

蟻群算法利用啟發(fā)函數(shù)計算可視區(qū)域內(nèi)下一步可到達(dá)節(jié)點的概率，通過螞蟻當(dāng)前位置與終點位置的距離信息吸引螞蟻選擇最優(yōu)路徑。因此，啟發(fā)函數(shù)的設(shè)計對于螞蟻能否找到最優(yōu)路徑至關(guān)重要，設(shè)計后的啟發(fā)函數(shù)為

H(i,j,k)=D(i,j,k)w1×S(i,j,k)w2×Q(i,j,k)w3,

(8)

其中：D(i,j,k)表示當(dāng)前位置與下一步可到達(dá)節(jié)點位置之間的路徑長度，其吸引螞蟻選擇可視區(qū)域內(nèi)路徑更短的節(jié)點位置；S(i,j,k)表示安全因素；Q(i,j,k)表示下一步到達(dá)節(jié)點距離終點的路徑長度，其吸引螞蟻向距離終點更近的節(jié)點移動；w1,w2,w3均為系數(shù)。

其中：a表示當(dāng)前節(jié)點；b表示下一節(jié)點；d表示終點；N(i,j,k)代表點(i,j,k)擁有的所有可視節(jié)點的個數(shù)；UN(i,j,k)代表所有可視節(jié)點內(nèi)不可到達(dá)區(qū)域的節(jié)點的個數(shù)。

2.3 蟻群搜索策略

三維空間環(huán)境下，螞蟻可以選擇的柵格節(jié)點大幅增加，蟻群算法的計算量也變得更復(fù)雜，蟻群從起始點到終點的路徑尋優(yōu)也變得更難，蟻群甚至在路徑尋優(yōu)中陷入死鎖現(xiàn)象而無法找到最優(yōu)路徑。因此，對于蟻群在三維空間環(huán)境下的路徑搜索，采取柵格平面和分層前行兩種方案互相結(jié)合的搜索策略。如圖2所示，Ps為螞蟻出發(fā)的起始點，設(shè)定螞蟻每次橫向移動的最大距離為xmax，每次縱向移動的最大距離為ymax，則螞蟻下一步可到達(dá)的柵格節(jié)點為一個可視區(qū)域，簡化了蟻群的搜索空間。螞蟻離開起始點ps后，將在第一個可視區(qū)域內(nèi)找到可到達(dá)節(jié)點p1(x1,y1,z1)，離開節(jié)點p1后，將在第二個可視區(qū)域內(nèi)找到可到達(dá)節(jié)點p2(x2,y2,z2)，螞蟻每次離開當(dāng)前節(jié)點位置后，都將在下一個可視區(qū)域內(nèi)尋找可達(dá)到節(jié)點位置，直到搜索到終點pg，則蟻群算法的三維路徑規(guī)劃結(jié)束。

圖2 三維環(huán)境搜索模式

螞蟻從平面Pi上的節(jié)點pi搜索到下一平面Pi+1上的節(jié)點pi+1的步驟如下：首先，利用抽象環(huán)境找到平面Pi+1上螞蟻可視區(qū)域內(nèi)的所有節(jié)點的集合，其次，利用啟發(fā)函數(shù)公式算出節(jié)點pi到平面Pi+1上螞蟻可視區(qū)域內(nèi)所有節(jié)點集合的啟發(fā)信息值Ha+1,u,v，同時，計算出平面Pi+1上的任意一點(i+1,u,v)被選擇的概率P(i+1,u,v)，其結(jié)果為

其中τ(a+1,u,v)表示平面Pi+1上的點p(a+1,u,v)的信息素值。最后，通過公式(12)計算出各點被選擇的概率來確定下一個到達(dá)的節(jié)點。

2.4 算法流程

改進(jìn)后的蟻群算法運行流程如圖3所示。

圖3 三維環(huán)境下蟻群算法流程圖

三維路徑尋優(yōu)步驟如下：

步驟1：對蟻群所在的三維環(huán)境抽象建模，初始化信息素，信息素按照節(jié)點位置的重要程度不均勻分布；

步驟2：蟻群從起始點開始搜索路徑，根據(jù)式(12)計算可視區(qū)域內(nèi)到達(dá)各點的概率，確定螞蟻下一步要到達(dá)的節(jié)點位置；

步驟3：螞蟻在搜索路徑時，進(jìn)行局部信息素更新，當(dāng)蟻群算法完成一次迭代后，更新全局信息素；

步驟4：蟻群算法達(dá)到最大迭代次數(shù)時，螞蟻結(jié)束路徑尋優(yōu)，保存最優(yōu)三維路徑，當(dāng)蟻群算法沒有達(dá)到最大迭代次數(shù)，繼續(xù)搜索路徑；

步驟5：輸出最優(yōu)三維路徑，結(jié)束蟻群算法。

為解決移動機(jī)器人在三維地圖環(huán)境中尋找出一條從起始點到終點的最優(yōu)路徑問題，提出一種改進(jìn)蟻群算法，將三維地圖離散成一系列的三維柵格節(jié)點，這些三維柵格節(jié)點組成了蟻群算法可以移動的柵格集合，通過全局信息素更新和局部信息素更新兩種方式，對柵格集合實現(xiàn)改進(jìn)信息素更新策略，設(shè)計多元化啟發(fā)函數(shù)，吸引蟻群選擇最優(yōu)路徑，提高算法的收斂速度。

3 實驗與結(jié)果

本研究對改進(jìn)蟻群算法以及傳統(tǒng)蟻群算法分別進(jìn)行仿真實驗并作對比分析，兩次實驗的三維地圖環(huán)境保持一致，起始點坐標(biāo)均為(1,3,1)，終點坐標(biāo)均為(21,10,10)，螞蟻數(shù)量取值為100，蟻群算法的最大迭代次數(shù)取值為100，對兩種算法分別運行3次，選擇其中最佳實驗結(jié)果。傳統(tǒng)蟻群算法的三維路徑軌跡如圖4所示，改進(jìn)蟻群算法的三維路徑軌跡如圖5所示，傳統(tǒng)蟻群算法、改進(jìn)蟻群算法的收斂曲線圖分別如圖6和圖7所示。

圖4 傳統(tǒng)蟻群算法三維路徑軌跡 圖5 改進(jìn)蟻群算法三維路徑軌跡

圖6 傳統(tǒng)蟻群算法收斂曲線 圖7 改進(jìn)蟻群算法收斂曲線

實驗結(jié)果顯示，應(yīng)用傳統(tǒng)蟻群算法進(jìn)行三維路徑尋優(yōu)搜索的最優(yōu)路徑長度為77.78 m，應(yīng)用本文改進(jìn)蟻群算法進(jìn)行三維路徑尋優(yōu)搜索的最優(yōu)路徑長度為71.36 m，改進(jìn)蟻群算法在搜索最優(yōu)路徑長度方面相比于傳統(tǒng)蟻群算法提高了8.3%；改進(jìn)蟻群算法迭代16次搜索到全局最優(yōu)路徑，同時達(dá)到穩(wěn)定狀態(tài)，傳統(tǒng)蟻群算法迭代44次搜索到最優(yōu)路徑，同時達(dá)到穩(wěn)定狀態(tài)，在收斂速度方面，改進(jìn)蟻群算法比傳統(tǒng)蟻群算法提高了63.7%。以上數(shù)據(jù)表明，本文改進(jìn)蟻群算法要明顯優(yōu)于傳統(tǒng)蟻群算法，能更快更穩(wěn)定的完成三維路徑規(guī)劃。

4 結(jié)論

本研究通過分析傳統(tǒng)蟻群算法的不足，對該蟻群算法進(jìn)行改進(jìn)。首先，通過對三維空間環(huán)境進(jìn)行建模，改進(jìn)信息素更新策略，利用初始化信息素的不均勻分布，吸引蟻群每次搜索路徑時優(yōu)先選擇距離終點更近的柵格位置。然后采用信息素全局更新及局部更新兩種方式，達(dá)到全局路徑搜索的目的。最后通過多元啟發(fā)函數(shù)計算出螞蟻選擇三維可視區(qū)域內(nèi)各點的概率，促進(jìn)螞蟻能完成起點到終點的路徑搜索，提高算法收斂速度。在三維空間下進(jìn)行傳統(tǒng)蟻群算法與改進(jìn)蟻群算法的仿真實驗并作對比分析，結(jié)果顯示，改進(jìn)后的蟻群算法在路徑搜索速度方面及最優(yōu)路徑軌跡方面均優(yōu)于傳統(tǒng)蟻群算法。

(責(zé)任編輯：潘姝靜)