基于改進智能算法的機器人路徑規劃問題研究

代婷婷

(昭通學院 數學與統計學院,云南 昭通 657000)

0 引 言

目前，機器人在眾多領域發揮著重要的作用，人們可通過編程設計讓機器人完成很多危險復雜的工作.關于機器人路徑規劃問題，科研人員提出了很多解決方案，例如，遺傳算法、粒子群算法、人工勢場法、蟻群算法等[1-4].雖然相關的智能算法比較多，但仍存在一些不足[5].其中，蟻群算法雖然在理論上能夠找到最優解，在機器人路徑規劃方面的性能不錯，但其仍存在如何快速有效地在全局范圍內搜索出最優解的問題，對此，學者們對蟻群算法進行了各種改進.例如，Deng等[6]提出了動態搜索誘導算子，通過閾值p的動態變化極大地提高了算法解的質量和收斂速度；Cai等[7]通過人工勢場法對蟻群算法信息素的揮發系數進行改進，提高了算法的最優解質量；趙靜等[8]對蟻群算法的啟發函數表達式進行了改進，在啟發函數中加入了下一節點到目標節點之間的歐氏距離，使得當前節點與目標節點的聯系更加緊密，從而提高了算法的求解效率；顧軍華等[9]對于蟻群算法的信息素濃度更新提出了新的方案，從相反的方向對每次迭代中的最優最差路徑上的信息素釋放量進行干擾，避免了收斂過快而導致局部最優解的出現.在此基礎上，本研究將文獻[8]與文獻[9]中相關的改進蟻群算法巧妙地融合而得出一種新的改進蟻群算法，并將其用于解決機器人路徑規劃問題，取得了較好的效果.

1 路徑規劃問題的環境建模方法

針對機器人的路徑規劃問題，通常需要對機器人所處的環境進行模擬建模.對此，本研究選擇最常用的柵格法進行環境建模，此方法具有建立、表示與保存簡單等優點.其思路是：將機器人所處的模擬環境分割成大小相同的一些正方形柵格，一個柵格表示一個單位，而每個柵格邊長是環境最小行走單元，柵格內的情況可以忽略不計.具體步驟包括：首先，規定使用中心點來表示機器人的柵格坐標，并對柵格進行標記和編號，其可采用坐標法和序號法;其次，按照柵格所具有的屬性，使用2種顏色將安全區域和障礙區域區別開，即機器人曾經走過的柵格劃掉，其他安全的區域可以任意行走.圖1為20×20柵格示例.

圖1 20×20柵格示例圖

2 基本蟻群算法

基本蟻群算法的思路是：在尋找食物的過程中，螞蟻會在自己走過的搜索路徑上釋放信息素，而信

息素會對其他螞蟻產生吸引作用.正是有這種相互作用的正反饋，使得螞蟻搜索到的最短路徑的概率和該路徑上的信息素濃度成正比.按照此機制，就可以達到尋找到最短路徑的目的.其具體的模型為：設i為外出覓食螞蟻的出發點，則其到達覓食終點j的隨機行進概率可表為，

(1)

式(1)表明:螞蟻覓食過程中最容易被選到的那條路徑具有較高的信息素濃度且距離螞蟻較近；每一次每一只螞蟻經過某一條路徑后都會馬上按照式(2)和式(3)更新該路徑上的信息素[10].

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

(2)

(3)

3 改進蟻群算法與流程圖

3.1 改進啟發函數

基于基本蟻群算法的原理分析以及結合相關的文獻，本研究認為，不但節點之間的概率轉移能影響最短路徑的計算結果，而且行走路徑上的信息素濃度的更新對最短路徑的影響也較為明顯.一般情況下，可使用相鄰節點i和j間的歐氏距離的倒數來表示轉移概率中的啟發函數.但事實上，開始搜索的最初階段，由于螞蟻數量不多，釋放的信息素濃度較少使得更多螞蟻偏離正確尋找路徑的概率加大，從而形成局部最優解或無效解.對此，文獻[8]在啟發函數中引入了下一節點和目標節點之間的歐氏距離，從而加強了當前節點與目標節點的聯系，其數學表達式為，

(4)

式中，dij表示當前節點i與下一個可行節點j之間的歐氏距離，djE是下一可行節點j到目標節點E的歐氏距離.

式(4)表明，由于加強了搜索路徑的方向性，相應的運算時間可大為縮短，提高了算法的計算效率.

3.2 更新信息素濃度

研究表明，蟻群算法的效率受信息素濃度更新的影響極大[10].影響信息素濃度更新的主要因素包括：第一，行走路徑的長度與信息素濃度的更新關系非常地密切，為了防止其積累過多而使算法過早局部收斂，信息素濃度進行更新是必不可少的；第二，由于大自然的固有特性，螞蟻行走路徑上的信息素濃度會隨著時間的推移而揮發掉一部分，即濃度會不斷降低；第三，經過行走路徑的所有螞蟻都會釋放信息素，即最短路徑上的螞蟻最多，信息素濃度也最強；最后，要在全部路徑中凸顯出最優路徑[11].對此，文獻[9]的主要做法是沿相反的方向對當次迭代的最優和最差路徑上的信息素進行改變，即最優的加強，最差的減弱，并將其按照式(5)的方式更新，防止算法收斂過快而陷入局部最優，

(5)

3.3 改進蟻群算法與計算流程

本研究根據以上2種文獻相關算法改進的優點，將文獻[8]中的啟發函數改進和文獻[9]中的信息素濃度更新的方案融合起來構成一種新的改進蟻群算法，即對啟發函數進行改變，把與最終節點的距離加入其中，同時，增加或減少在信息素更新時找到的最優和最差解的信息素濃度，從而提高算法的性能.本研究的改進蟻群算法的具體計算流程如圖2所示.

圖2 改進蟻群算法的計算流程示意圖

4 實證分析

為了驗證本改進蟻群算法的實際效果，本研究選用MATLAB分析軟件進行仿真實驗，具體做法是分別使用基本的蟻群算法和本改進蟻群算法來進行測試.其步驟是，將機器人處于圖1所示中的柵格障礙環境中，讓機器人在該環境中尋找無碰撞的最短路徑.在實驗的過程中，設定找到一條從起點到終點的沒有碰撞的最短路徑是機器人工作的目的，從而比較使用2種算法使機器人在這個尋找最短路徑的過程中找到最優路徑用時最短的方法.

在測試中，對本改進蟻群算法在實驗中的參數做表1所示的具體設置.

表1 實驗過程中改進蟻群算法的參數設置

通過MATLAB分析軟件的仿真試驗，2種算法的測試結果如圖3、圖4所示.

圖3 20×20柵格最優路徑

圖4 20×20柵格環境下基本蟻群算法與改進蟻群算法的收斂曲線

由圖3可知，基本蟻群算法和本改進蟻群算法都尋找到了長度為29.21的最優路徑，即2種算法找到的最優路徑相同.盡管2種算法得到的最優路徑是一樣的，但從圖4可以看出，這2種算法所使用的時間是完全不同的，基本蟻群算法找到最優路徑需要18次迭代，而本改進的蟻群算法僅迭代到第3次的時候就已經找到了最優路徑.此也表明，本研究的改進蟻群算法收斂速度很快，其搜索效率與基本蟻群算法相比有較大提升，可以在極短時間內搜索到最優解.

為了進一步顯示本改進蟻群算法的特點，本研究將其與文獻[8]和文獻[9]所提算法的性能進行了對比，結果如圖5所示.

圖5 20×20柵格環境下3種算法的收斂曲線

由圖5可知，由于同時對啟發函數和信息素濃度的更新方式進行了改進，使得本研究所提算法具有明顯的優勢.與其他2種算法相比，本算法在搜索初期所走的路線更短.文獻[8]算法在迭代第12次時，得到的路徑長度為29.21，但收斂速度較慢.雖然文獻[9]算法在迭代第8次時就得到長度為30.36的最優路徑，擁有較快的收斂速，但得到的卻是局部最優解.本算法在迭代第3次時就獲得了長度為29.21的最短路徑，明顯地在大幅度提升收斂速度的同時獲得了最短路徑.

為更直觀地展現本文算法與其他2種算法的對比優勢，在表2中列出了上述3種算法運行10次的仿真結果.

表2 20×20柵格環境下3種算法仿真結果對比

根據表2的仿真結果對比可知:從搜索路徑的長度上看，本文算法在迭代次數內僅有一次陷入了局部最優，其余幾次均能快速地找到全局最優解，且在距離啟發函數和自適應揮發因子的共同作用下擁有極強的逃離局部最優解的能力;文獻[8]算法有數次找到了最優解，但還是有幾次未能很好地實現尋優;文獻[9]算法出現了幾次搜尋路徑較長，其尋優能力弱于上述2種算法.在迭代次數上，本文算法與文獻[9]算法次數相差不大，與文獻[8]算法相比大幅降低.在運算時間上，本文算法稍優于文獻[9]算法，但均優于傳統算法.據此可知，本文的相關改進使蟻群算法的缺點得到了較大改善，避免了算法易陷入局部最優的難題,同時收斂速度提升明顯.

5 結 語

針對機器人路徑規劃問題，本研究根據文獻[8]和文獻[9]中的相關算法，提出了一種新的改進蟻群算法，具體改進體現為：第一，對啟發函數中的2段距離之和做了平方處理，加強了搜索的方向性，使得搜索時間有所減少；第二，對信息素濃度的更新方式做了改變，避免了出現局部最優的情況.利用MATLAB分析軟件對相關算法進行了仿真測試，結果表明：本改進蟻群算法與基本蟻群算法相比，雖然在相同的柵格環境中尋找的最優路徑完全相同，但所需要的迭代次數較少；與文獻[8]與文獻[9]的2種算法相比，在尋找最優解和收斂速度方面都有比較明顯的提升.