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

王 飛,江 明

(安徽工程大學(xué) 檢測技術(shù)與節(jié)能裝置重點(diǎn)實驗室，安徽 蕪湖 241000)

路徑規(guī)劃技術(shù)是移動機(jī)器人的關(guān)鍵技術(shù)，也是移動機(jī)器人能夠自主完成各種任務(wù)的首要前提，其任務(wù)是在環(huán)境已知或部分已知情況下，為移動機(jī)器人依據(jù)距離最短、時間最短、能耗最低等一條指標(biāo)或多條指標(biāo)規(guī)劃一條從起始點(diǎn)到目標(biāo)點(diǎn)的無碰撞最優(yōu)路徑[1]。目前，國內(nèi)外對此已經(jīng)進(jìn)行了大量研究并且提出相應(yīng)的解決方法，如A*算法[2]、人工勢場法[3]、遺傳算法[4]、粒子群優(yōu)化算法[5]、神經(jīng)網(wǎng)絡(luò)算法[6]等等，每種算法都有自己的優(yōu)勢，然而大部分研究都是基于二維空間環(huán)境，對于環(huán)境復(fù)雜、規(guī)模較大的三維空間存在一些局限性，而且由于三維環(huán)境特殊地貌的影響，路徑規(guī)劃的難度也隨之加大，難以取得理想的效果。

蟻群算法是由M.Dorigo等學(xué)者提出的一種模擬自然界螞蟻覓食行為的智能優(yōu)化算法。螞蟻在覓食過程中會分泌出一種信息素并且信息素的多少和螞蟻走過的路徑長度成反比，在路徑節(jié)點(diǎn)處螞蟻會傾向于選擇信息素較大的路徑。隨著蟻群大量體的隨機(jī)探索，最優(yōu)路徑上信息素值會越來越大，最終整個蟻群會搜索到最優(yōu)路徑，因此蟻群算法具有很強(qiáng)的魯棒性和適應(yīng)性[7]，在解決三維空間路徑規(guī)劃的問題上取得了不錯的效果，但是也存在易陷入局部最優(yōu)解、收斂速度慢等不足之處。文獻(xiàn)[8]將蟻群算法和遺傳算法相結(jié)合，提高了算法搜索效率。文獻(xiàn)[9]對死鎖螞蟻采取清零回退機(jī)制，實現(xiàn)移動機(jī)器人在三維空間中高效避障。文獻(xiàn)[10]建立模糊運(yùn)動控制系統(tǒng)，實現(xiàn)動態(tài)避障，通過模糊集合的優(yōu)化保證最優(yōu)路徑。文獻(xiàn)[11]設(shè)計了動態(tài)搜索模型，提高算法收斂速度和解的質(zhì)量。

文中研究了移動機(jī)器人在三維環(huán)境下的路徑規(guī)劃，提出一種改進(jìn)的蟻群優(yōu)化算法。針對三維環(huán)境復(fù)雜特點(diǎn)以及蟻群算法的不足，增加了避障策略，構(gòu)造新的啟發(fā)函數(shù)，增強(qiáng)算法全局搜索能力；依據(jù)起始點(diǎn)和目標(biāo)點(diǎn)位置優(yōu)化全局路徑初始信息素值分布，減少搜索初期螞蟻盲目搜索，提高算法搜索效率；提出優(yōu)質(zhì)螞蟻更新原則，自適應(yīng)調(diào)整信息素?fù)]發(fā)因子，避免算法陷入局部最優(yōu)解。

1 基本蟻群算法

螞蟻根據(jù)路徑上信息素和路徑信息來選擇路徑，在第t次迭代中，螞蟻k由節(jié)點(diǎn)i選擇下一節(jié)點(diǎn)j的轉(zhuǎn)移概率表示為：

(1)

(2)

式中,α為信息素啟發(fā)因子；β為期望啟發(fā)式因子；τij為路徑(i,j)的信息素濃度；allowk表示路徑搜索所有下一可達(dá)節(jié)點(diǎn)的集合；nij為啟發(fā)信息；dij為當(dāng)前節(jié)點(diǎn)i和待選節(jié)點(diǎn)j的歐氏距離。所有螞蟻完成一次迭代后，對殘留信息素進(jìn)行揮發(fā)處理，則t+1時刻在路徑(i,j)上信息素按式(3)、式(4)進(jìn)行更新。

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

(3)

(4)

式中，ρ為信息素?fù)]發(fā)系數(shù)，ρ∈(0,1)；Δij(i,j)表示本次迭代螞蟻在路徑(i,j)上的信息素增量；Q為信息素強(qiáng)度；Lk表示第k只螞蟻在本次迭代所走路徑的總長度。

2 三維環(huán)境路徑規(guī)劃

2.1 三維環(huán)境建模

環(huán)境模型建立的好壞直接影響到路徑規(guī)劃算法的精確度，因此合理的將三維環(huán)境抽象表達(dá)出來是移動機(jī)器人在三維環(huán)境中自主作業(yè)的關(guān)鍵[12]。采用柵格法將二維空間擴(kuò)展到三維空間，如圖1所示，構(gòu)造三維空間ABCD-EFGH，以A點(diǎn)為原點(diǎn)建立空間坐標(biāo)系，ABCD平面在XOZ平面上，以原點(diǎn)O沿Y軸方向?qū)E進(jìn)行n等分，沿X軸方向?qū)B進(jìn)行m等分，沿Z軸方向?qū)D進(jìn)行l(wèi)等分，即得到n個平面，每個平面劃分為m×l個柵格。至此ABCD-EFGH空間可由n×m×l個柵格來表示，空間中任一個柵格都對應(yīng)一個路徑節(jié)點(diǎn)，蟻群算法則在這些節(jié)點(diǎn)中進(jìn)行路徑規(guī)劃設(shè)計與仿真研究。

圖1 三維空間模型 圖2 三維空間搜索模式

2.2 搜索模式

在三維空間中，由于選擇節(jié)點(diǎn)范圍的擴(kuò)大，導(dǎo)致算法搜索變得異常復(fù)雜，而且很容易出現(xiàn)死鎖現(xiàn)象，使得算法收斂性差，全局搜索性低。為此，采用一種分層前進(jìn)與柵格平面法相結(jié)合的搜索模式如圖2所示。設(shè)定移動機(jī)器人起始點(diǎn)為PS，目標(biāo)點(diǎn)為PG，選取X軸為主前進(jìn)方向，規(guī)定機(jī)器人最大橫向移動距離ymax，最大縱向移動距離Zmax，即螞蟻對下一個節(jié)點(diǎn)的搜索存在可達(dá)區(qū)域。首先螞蟻從起始點(diǎn)PS出發(fā)，在第一個平面搜索到可行節(jié)點(diǎn)P1(x1,y1,z1)，接著在第二個平面搜索到第二個可行節(jié)點(diǎn)P2(x2,y2,z2)，螞蟻依次在各個平面選擇路徑節(jié)點(diǎn)，直到搜索到目標(biāo)點(diǎn)PG結(jié)束，即可搜索到一條最優(yōu)路徑。

2.3 啟發(fā)函數(shù)設(shè)計

啟發(fā)函數(shù)是整個蟻群算法重要組成部分，其作用是利用距離信息引導(dǎo)移動機(jī)器人選擇最短路徑，直接影響到算法的收斂性、穩(wěn)定性以及最優(yōu)性[13]。但是螞蟻搜索節(jié)點(diǎn)時往往容易貪婪選擇與當(dāng)前節(jié)點(diǎn)最近的節(jié)點(diǎn)而忽視了下一節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離，且在算法搜索前期盲目地選擇節(jié)點(diǎn)，而忽視節(jié)點(diǎn)周圍障礙物因素，易陷入死鎖狀態(tài)。為此增加避障策略構(gòu)造新的啟發(fā)函數(shù)，轉(zhuǎn)移概率式如式(5)所示:

(5)

(6)

(7)

(8)

(9)

式中，τa,a+1為路徑信息素。Ha,a+1為啟發(fā)函數(shù)信息；D1為當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)的距離的倒數(shù)；D2為下一節(jié)點(diǎn)到目標(biāo)點(diǎn)距離的倒數(shù)；(ia,ja,ka)為當(dāng)前節(jié)點(diǎn)坐標(biāo)；(ia+1,ja+1,ka+1)為下一節(jié)點(diǎn)坐標(biāo)；(iG,jG,kG)為目標(biāo)點(diǎn)坐標(biāo)；N為當(dāng)前節(jié)點(diǎn)可探索區(qū)域內(nèi)節(jié)點(diǎn)總數(shù)量；Na+1為當(dāng)前節(jié)點(diǎn)可探索區(qū)域內(nèi)不可行節(jié)點(diǎn)的數(shù)量；w1、w2、w3為相應(yīng)的權(quán)值。通過引入避障策略以及對啟發(fā)信息函數(shù)的改進(jìn)，能夠有效提高算法的全局搜索能力。

2.4 初始信息素分布優(yōu)化

在蟻群算法搜索前期，由于各路徑信息素初始值相同，算法的正反饋作用不明顯，螞蟻會在搜索過程中盲目搜索，甚至朝著相反的道路探索，極大降低算法的搜索效率[14]。改進(jìn)蟻群算法在信息素初始化時，設(shè)定前進(jìn)方向中起始點(diǎn)和目標(biāo)點(diǎn)之間的區(qū)域為全局有利區(qū)域，規(guī)定其信息素初始值大于其他區(qū)域信息素初始值，即

(10)

式中，τ0為信息素初始值；C為大于τ0的常數(shù)；R為全局有利區(qū)域。依據(jù)全局地圖信息可知，最優(yōu)路徑往往是一條從起始點(diǎn)朝著目標(biāo)點(diǎn)方向出發(fā)并逐漸靠攏的路徑，因此不均勻分配信息素，有利于減少蟻群搜索時間，提高搜索效率。

2.5 信息素更新規(guī)則

螞蟻在每一次迭代后會對所走過的路徑進(jìn)行信息素更新，然而每一次迭代中，并非每只螞蟻尋得的路徑都是最優(yōu)路徑，更有一些螞蟻遇到死鎖，無法走到終點(diǎn)，因此合理的信息素更新是確保螞蟻快速尋到全局最優(yōu)路徑的保證。基于此提出優(yōu)質(zhì)螞蟻更新規(guī)則，即每一次螞蟻迭代后，按式(11)只選擇更新達(dá)到目標(biāo)點(diǎn)的螞蟻上的路徑信息素，拋棄陷入死鎖的螞蟻，避免信息素盲目更新，干擾螞蟻對路徑選擇的判斷。然后分別找出每次迭代中最優(yōu)螞蟻與最差螞蟻，分別按式(12)、式(13)對其路徑上的信息素進(jìn)行加強(qiáng)與減弱。自適應(yīng)調(diào)整揮發(fā)因子ρ，令ρ按式(14)進(jìn)行調(diào)整，即設(shè)定在連續(xù)T次迭代內(nèi)蟻群算法求得的最優(yōu)解都相同，為避免算法陷入局部最優(yōu)解，之后每次迭代都減少ρ的值，減弱當(dāng)前搜索到的最優(yōu)路徑上信息素對螞蟻搜索路徑的影響，ρmin為ρ的最小值，防止ρ過小降低算法收斂速度。γ為信息素衰減系數(shù)，為一個小于1的正數(shù)，同時限定信息素值上下限τ(t)∈[τmax,τmin]，防止算法因信息素過大或過小陷入局部最優(yōu)值[15]。

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

(11)

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

(12)

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

(13)

(14)

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

步驟1：對機(jī)器人工作環(huán)境建立抽象模型，選擇起始點(diǎn)和目標(biāo)點(diǎn)，根據(jù)全局地圖信息劃定有利區(qū)域，對初始信息素值進(jìn)行不均勻分配。

步驟2：初始化螞蟻數(shù)量m、最大迭代次數(shù)Nmax、信息素?fù)]發(fā)因子ρ、信息素衰減系數(shù)γ等參數(shù)，選擇起始節(jié)點(diǎn)，根據(jù)轉(zhuǎn)移概率式(5)尋找下一個可達(dá)路徑節(jié)點(diǎn)，直到螞蟻搜索結(jié)束。

圖3 算法流程圖

步驟3：所有螞蟻完成一次迭代搜索后，拋棄陷入死鎖的螞蟻，只對所有走到目標(biāo)點(diǎn)上的螞蟻進(jìn)行路徑上信息素更新，另外按式(12)、式(13)分別加強(qiáng)最優(yōu)螞蟻與減弱最差螞蟻所經(jīng)過路徑上的信息素，同時限定信息素上下限濃度τ(t)∈[τmax,τmin]。

步驟4：設(shè)定迭代閾值T，即連續(xù)T次求得最優(yōu)解沒有變化時，則按式(14)自適應(yīng)調(diào)整信息素?fù)]發(fā)因子。

步驟5：判斷迭代次數(shù)是否達(dá)到上限，如果沒有，則跳轉(zhuǎn)步驟2，如果迭代次數(shù)到達(dá)上限結(jié)束搜索，保存最優(yōu)路徑信息。

步驟6：輸出最優(yōu)路徑長度，算法結(jié)束。

算法執(zhí)行流程圖如圖3所示。

4 仿真實驗與結(jié)果分析

隨機(jī)生成31m×31m×31m環(huán)境模型，在安全避障的前提下，以最短路徑為評價指標(biāo)。采用改進(jìn)蟻群算法和經(jīng)典蟻群算法進(jìn)行實驗對比，算法運(yùn)行環(huán)境為：Windows 7 64 bit； Matlab 2016a；處理器i5-4590 CPU；內(nèi)存4 GB。實驗參數(shù)取值如表1所示。

4.1 仿真實驗一

設(shè)定起始點(diǎn)為(1,15,8)，目標(biāo)點(diǎn)為(31,16,9)，路徑規(guī)劃結(jié)果如圖4、圖5、圖6所示，實驗數(shù)據(jù)如表2所示，可以看出經(jīng)典蟻群算法迭代了14次才找到了全局最優(yōu)路徑37.877 6 m，而改進(jìn)蟻群算法在第8次就找到了全局最優(yōu)路徑33.949 4 m。改進(jìn)蟻群算法相比經(jīng)典蟻群算法迭代次數(shù)減少43%，路徑長度減少10%，極大減少了收斂次數(shù)，并且啟發(fā)函數(shù)和信息素更新規(guī)則的改進(jìn)，使得改進(jìn)算法搜索到的最優(yōu)路徑長度小于經(jīng)典蟻群算法。

表1 實驗參數(shù)設(shè)置

表2 仿真實驗一

圖4 經(jīng)典蟻群算法路徑規(guī)劃 圖5 改進(jìn)蟻群算法路徑規(guī)劃

圖6 兩種算法收斂情況

4.2 仿真實驗二

設(shè)定起始點(diǎn)為(1,1,5)，目標(biāo)點(diǎn)為(31,8,5)，路徑規(guī)劃結(jié)果如圖7、圖8、圖9所示。實驗數(shù)據(jù)如表3所示?？梢钥闯鼋?jīng)典蟻群算法迭代了15次才找到了全局最優(yōu)路徑37.192 0 m，而改進(jìn)蟻群算法在第10次就找到了全局最優(yōu)路徑35.599 7 m。改進(jìn)蟻群算法相比經(jīng)典蟻群算法迭代次數(shù)減少了33%，路徑長度減少4%。盡管在算法運(yùn)行時間上改進(jìn)蟻群算法耗時稍微多點(diǎn)，這是因為在搜索前期對初始信息素處理，增加避障策略以及信息素更新等方面的改進(jìn)而增加了一些程序代碼，但是從路徑規(guī)劃結(jié)果對比分析，算法搜索策略的改進(jìn)使得改進(jìn)蟻群算法有效提高算法搜索能力和收斂速度，充分表明了其優(yōu)越性和可行性。

表3 仿真實驗二

圖7 經(jīng)典蟻群算法路徑規(guī)劃 圖8 改進(jìn)蟻群算法路徑規(guī)劃

圖9 兩種算法收斂情況

5 結(jié)論

文中研究了移動機(jī)器人在三維環(huán)境下路徑規(guī)劃的問題，提出一種改進(jìn)的蟻群優(yōu)化算法。采用柵格法擴(kuò)展建立三維抽象環(huán)境模型，依據(jù)起始點(diǎn)和目標(biāo)點(diǎn)位置信息，優(yōu)化初始信息素值分布，避免算法前期螞蟻盲目搜索，提高算法的搜索效率。引入避障策略并且利用當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離信息來改進(jìn)啟發(fā)函數(shù)，提高算法全局搜索能力。提出優(yōu)質(zhì)螞蟻更新策略，自適應(yīng)調(diào)節(jié)信息素?fù)]發(fā)因子，防止算法陷入局部最優(yōu)值。實驗結(jié)果表明，在復(fù)雜的三維環(huán)境下，改進(jìn)蟻群算法相比經(jīng)典蟻群算法有效縮短了最優(yōu)路徑長度，降低了收斂次數(shù)，具有較高的全局搜索能力。算法是在全局靜態(tài)環(huán)境下展開研究的，后續(xù)研究將重點(diǎn)放在動態(tài)避障上，進(jìn)一步提高算法的實用性、有效性。