王 飛,江 明

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

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

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

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

1 基本蟻群算法

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

(1)

(2)

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

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

(3)

(4)

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

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

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

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

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

2.2 搜索模式

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

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

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

(5)

(6)

(7)

(8)

(9)

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

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

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

(10)

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

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

螞蟻在每一次迭代后會對所走過的路徑進行信息素更新，然而每一次迭代中，并非每只螞蟻尋得的路徑都是最優(yōu)路徑，更有一些螞蟻遇到死鎖，無法走到終點，因此合理的信息素更新是確保螞蟻快速尋到全局最優(yōu)路徑的保證?；诖颂岢鰞?yōu)質螞蟻更新規(guī)則，即每一次螞蟻迭代后，按式(11)只選擇更新達到目標點的螞蟻上的路徑信息素，拋棄陷入死鎖的螞蟻，避免信息素盲目更新，干擾螞蟻對路徑選擇的判斷。然后分別找出每次迭代中最優(yōu)螞蟻與最差螞蟻，分別按式(12)、式(13)對其路徑上的信息素進行加強與減弱。自適應調整揮發(fā)因子ρ，令ρ按式(14)進行調整，即設定在連續(xù)T次迭代內蟻群算法求得的最優(yōu)解都相同，為避免算法陷入局部最優(yōu)解，之后每次迭代都減少ρ的值，減弱當前搜索到的最優(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 改進算法步驟

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

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

圖3 算法流程圖

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

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

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

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

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

4 仿真實驗與結果分析

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

4.1 仿真實驗一

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

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

表2 仿真實驗一

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

圖6 兩種算法收斂情況

4.2 仿真實驗二

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

表3 仿真實驗二

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

圖9 兩種算法收斂情況

5 結論

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