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

（哈爾濱工程大學(xué)自動化學(xué)院，哈爾濱150001）

0 引 言

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

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

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

1 蟻群算法基本模型

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

在t 時刻，螞蟻k 從節(jié)點i 到節(jié)點j 轉(zhuǎn)移的概率為：

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

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

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

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

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

2 人工勢場法的改進(jìn)

2.1 人工勢場算法分析

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

引力勢函數(shù)：

式中：ρ（q，qG）為移動機(jī)器人的當(dāng)前與目標(biāo)的距離；ξ為尺度因子。

目標(biāo)點對機(jī)器人的引力為目標(biāo)勢函數(shù)的負(fù)梯度，即：

斥力勢場表達(dá)式為

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

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

人工勢場法以其數(shù)學(xué)計算上的簡單明了被廣泛應(yīng)用，但是也存在很多缺陷，比如目標(biāo)不可達(dá)和在障礙物附近振動的問題。

2.2 人工勢場算法的改進(jìn)

為防止機(jī)器人距離障礙物距離過遠(yuǎn)時引力大造成容易與障礙物碰撞的問題，對引力函數(shù)進(jìn)行改進(jìn)，設(shè)置一個閾值dmax，當(dāng)機(jī)器人與障礙物之間的距離小于dmax時，引力勢場為二次函數(shù)形式，當(dāng)機(jī)器人與障礙物距離大于或等于閾值dmax時，引力勢場為距離的一次函數(shù)。

則目標(biāo)點對機(jī)器人的引力函數(shù)：

對于機(jī)器人在障礙物附近振動的問題，對斥力函數(shù)進(jìn)行改進(jìn)。障礙物對機(jī)器人產(chǎn)生的斥力場為：

式中：λ是正比例系數(shù)。

由此得出障礙物對機(jī)器人的斥力

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

圖1 未改進(jìn)人工勢場法路徑圖

圖2 改進(jìn)人工勢場法路徑圖

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

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

3 勢場蟻群算法

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

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

當(dāng)n ＞1 時，選擇其余方向的概率為

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

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

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

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

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

4 仿真分析

機(jī)器人活動的環(huán)境設(shè)置為25 ×25 的柵格區(qū)域，當(dāng)障礙物不足一個柵格時用一個柵格表示，柵格的邊長為1，機(jī)器人必須在這個柵格區(qū)域內(nèi)尋找到從起點到目標(biāo)點的無碰撞路徑。

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

由表1 和表2 的數(shù)據(jù)可見，改進(jìn)前、后的算法和改進(jìn)前的算法相比較能夠?qū)ふ业阶顑?yōu)的路徑，而且在平均路徑長度上有稍微的改善，平均運行時間有明顯的改善。

圖5 程序流程圖

表1 未改進(jìn)算法生成的路徑數(shù)據(jù)

表2 改進(jìn)后算法生成的路徑數(shù)據(jù)

圖6 仿真環(huán)境地圖1

圖7 地圖1改進(jìn)前后的路徑收斂曲線對比圖

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

圖8 仿真環(huán)境地圖2

圖9 仿真環(huán)境地圖3

圖10 仿真環(huán)境地圖4

圖11 地圖4 改進(jìn)后的路徑收斂曲線圖

5 結(jié) 語

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