勢場改進蟻群算法的移動機器人路徑規劃研究

李林喜 李衛國 任超群 王利利

摘 要：在復雜環境中工作的移動機器人，針對其避障及路徑優化問題，對傳統人工勢場法和基本蟻群優化算法進行了分析研究，提出了改進的人工勢場蟻群算法，并利用仿真實驗進行了分析。結果表明，改進后的人工勢場法能夠得到最優的路徑，提高了算法的收斂性，且速度快、過程穩定，可用于解決移動機器人路徑規劃問題。

關鍵詞：移動機器人;路徑規劃;蟻群算法;人工勢場

近年來，隨著人工智能技術的發展，移動機器人作為當前機器人領域的一個重要分支，在工業制造、海洋探測、家庭服務、醫療護理、資源開發、巡檢排險、航空航天和國防等諸多領域得到了成功的應用。

路徑規劃是移動機器人完成各種自主移動任務的關鍵環節之一，是機器人領域的一個重要研究課題。路徑規劃簡單的理解，就是讓機器人從初始位置到達目標位置，作出最優行走路徑應遵循的某種性能指標（如距離，時間等）。目前，路徑規劃的求解方法主要有人工勢場法和基于人工智能的啟發式方法，如蟻群算法、遺傳算法和粒子群等。蟻群算法是一種受到生物界蟻群覓食行為的啟發式搜索算法，本文為校級科研項目，在項目開展過程中，對上述各種算法進行反復比對實驗，最終提出一種移動機器人路徑規劃算法——勢場改進的蟻群算法，并測試了其有效性和優越性。

1 建立足球機器人路徑規劃模型

移動機器人的路徑規劃模型如圖1所示，起始點為當前移動機器人的位置，當機器人遇到障礙物時，在避開障礙物，避免發生碰撞的前提下，找到一條從起始位置到目標位置長度最優的路徑。

2 基本蟻群算法的缺點

基本的蟻群算法具有其不足和局限性： 相對于其他方法它的搜索時間更長;容易出現停滯（算法結束在不是最優解或次優解）;描述復雜問題的能力還不夠強等等。對于復雜環境存在的缺陷之處主要在于：

（1）參數α、β的選擇對算法的影響。

在蟻群算法中，信息素因子α反映的前面的螞蟻所釋放的信息素對后面螞蟻尋找路徑的影響程度，如果α過大則后面螞蟻選擇其路徑的可能性過小，會導致搜索的隨機性喪失太多，反之則容易過早陷入局部最優的問題;期望啟發式因子β，是對于前期的信息對螞蟻的指導程度，值的大小反映尋徑過程中的預先確定因素的作用強度，過大會導致螞蟻收斂速度加快，搜索隨機性削弱，尋到局部最優的概率增大。由于α和β在通常情況下都是給的定值，它們的影響在從整個算法的執行過程中都是一直保持和開始一樣的影響效果。在比較小的柵格規模下還可以滿足算法需要，但如果到了規模很大的柵格環境時，螞蟻能經過的位置點會成倍上漲，這時螞蟻需要經過的位置點更多，開始給定的信息素因子可能已經蒸發了很多，不能保證螞蟻走過柵格中的任何一個位置點都獲得該點的信息素。當再經歷數次迭代，能獲得的信息素位置點越來越少，這時的蟻群算法不僅更有可能出現次優解，也更容易進入局部最優。

（2）存在不可逆柵格情況。

當在柵格模型下的障礙物，出現下圖2（a）的情況時，螞蟻可能會按照圖上指出方向選擇可行的自由柵格，結果就會進入無法繼續行動的狀態，如果在算法前期出現這種狀態的螞蟻增多，相當于m減小，會出現停滯狀態。

解決的方法就是在已知全局信息的情況下將其中的自由柵格作障礙柵格處理如圖2（b）所示。

3 基本蟻群算法的改進

本文針對參數α和β的給定值進行改進。在算法執行的開始階段，對依靠信息素因子α的尋找路徑的方式的依賴程度還比較低，到了算法后期對其的依賴程度增高;相反的，對于期望啟發因子β，前期依賴程度較高，到算法后期主要依靠螞蟻之間的信息素傳遞來尋找路徑，對期望啟發因子的需求降低。經上面的分析可知，我們在算法前期讓β升高而讓α降低，以解決前期更多位置點得不到足夠信息素問題;同樣道理，到算法后期，讓啟發值β降低而α升高，也就是后期讓算法利用更具有優勢的信息素的方式尋找最佳路徑。通過上述分析，我們就是要設計一個規則讓基本蟻群算法的參數α和β在算法運行過程中實行動態變化的形式，在隨時間執行的過程中，α逐漸遞增至最大值;而β則逐漸遞減至最小。我們將這個過程用數學公式敘述如下式（1）和（2）：

在上兩個式子中，m為臨界迭代次數（即螞蟻個數），NC為最大迭代次數。在本論文中取值分別為m=10;NC=100。

4 人工勢場的改進蟻群算法

結合人工勢場法在未知環境下局部搜索的優勢和蟻群算法在全局路徑規劃中的特點，用聯合啟發因子來進一步提高機器人在路徑規劃中的效率。

蟻群中一共有m只螞蟻，當其中的螞蟻k在第n位置Pn=r轉移到下一步位置Pn+1=s的概率依據是由下面的式子決定的

當0≤q0≤1是一個常數，S是按照概率確定的下一個到達的位置，其概率分布是按照（2）式來確定的

其中τrsn與ηrsn分別為從Pn=r到Pn+1=s的路徑所在邊的信息素的濃度和啟發期望信息;a與β代表信息素因子和啟發期望因子的相對重要性;第k個螞蟻到下步所能允許到達的位置用allowedkn集合表示，機器人只能倒退到來時的柵格Pn-1，則說明Pn位置是一個死路，這種情形在之后Pn這個位置將會作為障礙柵格處理，也就是上邊的凹柵格的“凸”處理方式。

第k只螞蟻在搜索路徑的過程中，對走過的邊的局部信息素更新遵照下式：

當0<ψ≤1為一個常數;τ0=mCnn為初始信息素的值;Cnn為相鄰的啟發規則產生的路徑的長度。這個蒸發過程是為了避免對其它的螞蟻的過于強的吸引力，以避免迭代過早的收斂，讓螞蟻對其他路徑搜索的可能。當m只螞蟻都已經走完，完成一次迭代后，對所有螞蟻的路徑進行比較從中找出最短路徑，并對這條路徑進行一次全局信息素更新，如下式：

當0<ρ≤1為控制信息素衰減速度的常數;其中Δτrs=1Lgb，Lgb為本次迭代所找到的全局最優路徑。

上述將人工勢場法和蟻群算法的改進分別作了詳述。下面將兩種算法融合到一起，讓它們共同構成完整的規劃過程，可得該勢場改進蟻群算法的啟發信息ηrs為：

從式中得出，當勢場的合力，也就是機器人處于勢場的局部穩定點處，這時若只在人工勢場中，將陷在局部最優中。但在本算法中，由于蟻群算法的加入，在這時啟發信息會為ηrsn=ηdn=1d2P，G，也就是說當某一位置合力Ftot=0時，ηd的啟發信息會引導機器人跳出局部最優這個陷阱，繼續進行全局最優路徑的搜索。

以上介紹了人工勢場法和蟻群算法的改進分別作了詳述。下面就要介紹一下這兩種算法如何融合到一起，讓它們共同構成完整的規劃過程。這里就要對啟發信息ηrsn進行構造。

在路徑搜尋過程中，螞蟻尋找到下一個位置的啟發性信息是由兩個部分構成，其中之一是螞蟻受環境中的勢場的合力，形成讓螞蟻能沿著合力的方向接近目標的啟發信息，這部分信息為

式子里，a是大于零的常數，θ為螞蟻可行進的方向和勢場的合力Ftot方向的夾角，如圖3-4所示。這是可知螞蟻會在這個合力的影響下向著與勢場合力方向的夾角θ較小的邊移動到下一個自由位置。該啟發信息可以幫助機器人避碰，選擇合適路徑接近目標位置。

剩下的一部分就是由螞蟻距目標所在位置距離提供的。定義這一部分的啟發信息如下

再將兩者綜合在一起，便可得該勢場改進蟻群算法的啟發信息ηrs為：

從式子中我們可以了解到，當勢場的合力，也就是機器人處于勢場的局部穩定點處，這時若只在人工勢場中，將陷在局部最優中。但在本算法中，由于蟻群算法的加入，在這時啟發信息會為ηrsn=ηdn=1d2P，G，也就是說當某一位置合力Ftot=0時，ηd的啟發信息會引導機器人跳出局部最優這個陷阱，繼續進行全局最優路徑的搜索。

5 仿真與實驗分析

5.1 人工勢場蟻群算法

如圖3、圖4為人工勢場蟻群算法仿真圖，在迭代30次后，算法趨于穩定，最優路徑長度在33.9258，并且在最優路徑上。但從圖上可以看出，0-30次之間收斂曲線波動較大，表明在收斂上存在可以改進之處。

5.2 人工勢場改進蟻群算法

如圖5、圖6所示，在迭代15次后，算法就趨于穩定，最優路徑長度是33.9053，進一步提高了其收斂效率，而且收斂曲線也平滑了很多，收斂效果改進明顯。

綜上所述，人工勢場法的改進蟻群算法，在收斂效率上有了明顯的提高，搜索最優路徑時間更快更加趨于合理。該算法克服了人工勢場法遇到的局部最優和目標不可達等問題，而且提高了算法的收斂性。

6 算法驗證

利用此算法，機器人在實際運行中的路徑比較平滑，但機器人行進過程中，當挪動障礙物形成動態規劃時，機器人在靠近障礙物時會出現震蕩前進，但最后依然可以到達目的地。這也為以后的進一步研究提出了改進方向。

7 結語

本文針對基本蟻群算法和人工勢場法存在的不足，整合兩者的優點，提出了人工勢場改進的蟻群算法，并通過仿真實驗和真實室內環境下實驗，均驗證了其可行性。同時，也發現了對于動態規劃的不足，有些地方還需要改進。

參考文獻

[1]周明秀，程科，汪正霞.動態路徑規劃中的改進蟻群算法[J].計算機科學， 2013，40（1）：314-316.

[2]吳晨光.基于改進人工勢場法的機器人路徑規劃及其在RobCup中的應用[D].南京郵電大學，2012.

[3]曲寶福，王利利等. 基于勢場改進蟻群算法的足球機器人路徑規劃研究[D].現代商貿工業，2018.

[4]高田田，張莉等.基于改進粒子群算法的足球機器人路徑規劃[J].西安工程大學學報，2016，30（5）：609-615.