具有勢場啟發因子的蟻群路徑規劃仿真

王 輝， 于立君， 胡羽坤， 王瑩瑩

（哈爾濱工程大學自動化學院，哈爾濱150001）

0 引 言

移動機器人路徑規劃指在存在障礙物的環境中尋找一條從起點到終點的無碰撞的路徑［1-3］。大量的算法被應用于機器人的路徑規劃之中，如人工勢場法［4，5］、遺傳算法［6，7］、粒子群算法及蟻群算法［8-10］等，每一種算法各有優劣。

螞蟻系統（Ant System，AS）是由M. Dorigo 于20世紀90 年代提出的一類仿生算法，算法開始被成功應用于旅行商問題（Traveling Salesman Problem，TSP）等組合優化問題，之后也被用來解決移動機器人路徑規劃問題［11-13］。文獻［14］中提出了最大、最小螞蟻系統（MAX-MIN Ant System，MMAS），將信息素限制在一個區間內，有效避免了搜索過程中的早熟現象。文獻［15］中提出了基于蟻群遺傳算法的移動機器人路徑規劃方案，該方案能夠減小蟻群算法搜索初期的盲目性，提高搜索效率，在具有較強的全局搜索能力和魯棒性等優點的同時，也存在搜索效率低且容易陷入局部最優的缺陷。

針對蟻群算法存在收斂速度慢及復雜環境下收斂差的問題，本文提出了一種改進的勢場蟻群算法，引入勢場啟發因子，并控制整個搜索過程的不同階段兩種算法的重要程度，快速找到從起始點到目標點的無碰撞路徑。

1 蟻群算法基本模型

螞蟻會在走過的路上潑灑信息素，而這種信息素又會影響后續的螞蟻對路徑選擇，螞蟻趨向選擇信息素濃度高的路徑這種正反饋機制使得螞蟻可以發現長度短的路徑。

在t 時刻，螞蟻k 從節點i 到節點j 轉移的概率為：

式中：Pkij為螞蟻k從節點i到節點j的轉移概率；dij為節點i和節點j之間的距離；ηij為啟發因子，表示螞蟻從節點i轉移到節點j的期望程度；C為螞蟻下一步可選擇節點的集合；S 為節點變量；τij為節點i 與節點j之間的信息素濃度；α 為信息素濃度τij在求取轉移概率時所占的比例；β為啟發因子ηij在計算轉移概率時所占的比例。

信息素的改變有兩種方式，隨著時間流逝會有一部分信息素揮發掉，螞蟻走過的路徑會釋放一部分信息素。待全部螞蟻都到達目標位置或完成軌跡搜索后信息素的更新策略為：

式中：Δτkij（t，t ＋1）為第k 只螞蟻在時刻（t，t ＋1）留在路徑（i，j）上的信息量；Δτij（t，t ＋1）為一次迭代完成后，軌跡（i，j）上的信息素增量；φ為信息素衰減系數，防止信息素無限累積。Δτkij（t，t ＋1）的更新存在3 種模型，分別為蟻密模型、蟻量模型和蟻周模型。文獻［16，17］中通過實驗對比3 種模型的效果，表明蟻周模型在機器人路徑規劃方面優于其余兩種，該模型為：

式中：Lk為第k只螞蟻完成搜索形成路徑的總長度；Q為信息素強度系數。

選擇最大、最小螞蟻系統算法，最大、最小蟻群算法是將信息素濃度控制在一個范圍內，即ηij∈［min，max］，將不在此范圍內的信息素強制設置為min 或max，設置方法為：當ηij＜min 時，令ηij＝min，當ηij＞max時，令ηij＝max，最大、最小螞蟻系統可以有效防止螞蟻陷入局部最優路徑。

2 人工勢場法的改進

2.1 人工勢場算法分析

人工勢場法是一種虛擬力法。通過目標位置產生的引力勢場和障礙物產生的斥力勢場的疊加控制移動機器人的運動，搜索一條無碰撞的路徑。

引力勢函數：

式中：ρ（q，qG）為移動機器人的當前與目標的距離；ξ為尺度因子。

目標點對機器人的引力為目標勢函數的負梯度，即：

斥力勢場表達式為

式中：δ為斥力尺度因子，ρ（q，qo）是機器人距離障礙物的最短距離，ρ0是障礙物的影響半徑。則障礙物對機器人的斥力：Δ

機器人受到的合力為引力和斥力之和，即：

人工勢場法以其數學計算上的簡單明了被廣泛應用，但是也存在很多缺陷，比如目標不可達和在障礙物附近振動的問題。

2.2 人工勢場算法的改進

為防止機器人距離障礙物距離過遠時引力大造成容易與障礙物碰撞的問題，對引力函數進行改進，設置一個閾值dmax，當機器人與障礙物之間的距離小于dmax時，引力勢場為二次函數形式，當機器人與障礙物距離大于或等于閾值dmax時，引力勢場為距離的一次函數。

則目標點對機器人的引力函數：

對于機器人在障礙物附近振動的問題，對斥力函數進行改進。障礙物對機器人產生的斥力場為：

式中：λ是正比例系數。

由此得出障礙物對機器人的斥力

改進前后的人工勢場法在障礙物附近的振蕩情況分別如圖1、2 所示，圖中左上角為起始點，右下角為目標點。

圖1 未改進人工勢場法路徑圖

圖2 改進人工勢場法路徑圖

經過改進的人工勢場算法解決了障礙物附近抖動的問題和目標附近有障礙物導致的目標不可達問題，但還存在易陷入局部最小點的問題（見圖3），本文中的蟻群算法可以彌補人工勢場法在這個問題上的缺陷。

圖3 人工勢場法陷入極值點

3 勢場蟻群算法

蟻群算法在搜索初期由于信息素均勻分布使得蟻群算法花費的搜索時間長。針對這一情形，使用人工勢場法對蟻群算法進行改進。改進如下：將人工勢場的勢場力信息作為蟻群算法的啟發信息，蟻群算法的概率轉移表達式修改為

式中：μ ＝α；ν ＝β；γ 為人工勢場法在方向選擇上占的比重；σij為根據人工勢場法計算出的8 個方向的選擇概率，規定和勢場合力F 夾角最小的方向的選擇概率為

當n ＞1 時，選擇其余方向的概率為

式中：n為螞蟻下一步可以選擇的方向的個數。圖4給出了螞蟻可能會遇到的一種環境情形，a、b、c、d、e、f為下一步可以選擇的方向及各個方向選擇概率值。

圖4 螞蟻下一步選擇概率分布圖

對于普通的實驗環境，使用式（15）總能快速找到一條最優或次優的無碰撞道路，但是對于特殊的實驗環境，如圖3 則可能出現失敗的情況，因為在這種環境中人工勢場法失效，此時要去除人工勢場算法的影響，即將式（15）中的參數γ 設置為0，此時改進的算法變成了單純的蟻群算法。為了使算法能夠適應各種環境，將算法進行以下修改。

設置算法的循環次數LoopMax，循環次數閾值LoopFlag，當前循環次數為Loop，當LoopFlag ＜Loop時，使用式（15）計算轉移概率，當LoopFlag≥Loop 時，令γ等于0，即單純的蟻群算法。在算法開始的時候使用單純的蟻群算法找到起點到目標點的路徑，這時信息素會出現差異，這些信息會被后續螞蟻使用，解決了特殊環境下機器人找不到路徑的問題。

程序的流程如圖5 所示，其中：

4 仿真分析

機器人活動的環境設置為25 ×25 的柵格區域，當障礙物不足一個柵格時用一個柵格表示，柵格的邊長為1，機器人必須在這個柵格區域內尋找到從起點到目標點的無碰撞路徑。

采用幾個不同的環境進行仿真實驗，進行10 次的獨立仿真實驗，數據取平均值，路徑圖為隨機選取的一次生成路徑。實驗對比了未改進的蟻群算法和改進之后的算法的路徑長度和程序運行時間兩項，表1 為未改進的算法生成的路徑數據，表2 為改進后的算法生成的路徑數據。仿真實驗使用環境地圖如圖6、8 ～10所示。

由表1 和表2 的數據可見，改進前、后的算法和改進前的算法相比較能夠尋找到最優的路徑，而且在平均路徑長度上有稍微的改善，平均運行時間有明顯的改善。

圖5 程序流程圖

表1 未改進算法生成的路徑數據

表2 改進后算法生成的路徑數據

圖6 仿真環境地圖1

圖7 地圖1改進前后的路徑收斂曲線對比圖

圖7 為地圖1 改進前、后的路徑收斂曲線對比圖，其中藍色點劃線為地圖1 改進之后的收斂曲線，紅色線為未改進的蟻群算法的收斂曲線，圖11 為地圖4 改進后的路徑收斂曲線圖，可見，改進之后的算法收斂的速度明顯加快。

圖8 仿真環境地圖2

圖9 仿真環境地圖3

圖10 仿真環境地圖4

圖11 地圖4 改進后的路徑收斂曲線圖

5 結 語

本文首先對人工勢場算法進行改進，提出引力勢場采用分段函數的方法來解決人工勢場法造成的一些問題，如機器人在障礙物附近抖動問題、機器人和目標點距離過大時容易和障礙物發生碰撞的問題，并定義了勢場啟發因子。將改進后的算法嵌入蟻群路徑規劃算法中，在找到最優或次優路徑的基礎上，提高了蟻群算法的收斂速度，實驗室環境下的仿真實驗證明了改進方法的合理性。學生通過仿真平臺對移動機器人路徑算法進行仿真對比分析，大大提高了學生實驗興趣。