徐 梁，高宏力，宋興國

（西南交通大學機械工程學院，四川 成都 610031）

1 引言

移動機器人路徑規(guī)劃是機器人研究領域的重要組成部分，是指在給定的有障礙物的運動空間中，根據(jù)一定的性能指標（路徑最短、時間最少），尋找一條從初始狀態(tài)到目標狀態(tài)的最優(yōu)或近似最優(yōu)的無碰撞路徑。移動機器人路徑規(guī)劃問題是一種典型的NP-hard（非典型性多項式困難）問題[1]，針對移動機器人路徑規(guī)劃，傳統(tǒng)方法主要有柵格法[2]、模擬退火法、模糊邏輯法等，柵格法適用于結(jié)構(gòu)簡單的環(huán)境中，當空間結(jié)構(gòu)變復雜時，存在計算效率低，存儲空間大的問題；模擬退火法計算量大、效率低等問題。隨著環(huán)境復雜程度的增加，出現(xiàn)了免疫算法、遺傳算法[3]、人工魚群算法、A*算法、ACO等智能仿生算法，這類算法在移動機器人路徑規(guī)劃中取得了顯著的成果。

ACO最初是由M.Dorigo等人根據(jù)蟻群覓食行為中受到啟發(fā)提出的，用于解決旅行商問題的一種仿生智能優(yōu)化算法，最近這些年在機器人路徑規(guī)劃方面取得了很好的效果。它具有較好的魯棒性、良好的分布式計算體制、易于與其他方法相互結(jié)合等優(yōu)點[4-5]。但是ACO規(guī)劃出來的路徑收斂速度慢、易陷入局部最優(yōu)等、折線多、轉(zhuǎn)角偏大，連接不夠平滑，為了提高算法的最優(yōu)性，必須對基本蟻群算法進行改進，同時為了機器人運動的柔順性，有必要對路徑進行平滑處理。

在此，針對以上問題，給出一種將貝塞爾曲線[6-7]與ACO融合的規(guī)劃算法。仿真實驗結(jié)果表明，經(jīng)過貝塞爾曲線優(yōu)化后的路徑更適合機器人實際的運動規(guī)劃。

2 環(huán)境地圖的表示

環(huán)境地圖建模的過程就是實現(xiàn)現(xiàn)實空間到抽象空間的一個映射過程，環(huán)境中的障礙物映射成不可通過的區(qū)域。柵格法創(chuàng)建的環(huán)境地圖簡單有效，數(shù)據(jù)方便處理。假定移動機器人在二維平面RS上運動，平面上分布著隨機可數(shù)數(shù)量，形狀不確定的障礙物。柵格模型的建立采用序號法結(jié)合直角坐標法的方式。柵格地圖中柵格信息直接與環(huán)境信息相對應，其中白色柵格為可通過自由區(qū)域，黑色柵格為障礙區(qū)域。移動機器人在每個柵格中下一個可移動位置為八個相鄰柵格。

從實際環(huán)境地圖到柵格模型地圖轉(zhuǎn)換的過程中，對移動機器人和障礙物環(huán)境做出以下約定：

（1）在描述障礙物時把障礙物外擴1個機器人的最大直徑。

（2）障礙物占用不滿一個柵格時，擴充該障礙物，占滿柵格。

劃分后的機器人工作空間，如圖1所示。

圖1 柵格地圖模型Fig.1 Grid Map Model

設柵格模型為M行N列，按從左到右，從上到下的順序，左上角第一個柵格坐標為（1,1），序號為R的柵格坐標為（xR，yR），則有：

式中：mod—取余運算；int—取整運算。

3 改進蟻群算法

蟻群算法基本定義如下：

當算法完成一次搜索循環(huán)后，對相應路徑上的信息素進行更新：

式中：ρ∈（0,1）—信息素揮發(fā)系數(shù)；

（1-ρ）—信息素殘留系數(shù)；

駐τij（t）—節(jié)點i到節(jié)點j的信息素增量；

駐τkij（t）—第k只螞蟻在路徑上留下的信息素。

信息素更新有三種模型，蟻周（Ant-Cycle）模型、蟻量（Ant-Quantity）模型、蟻密（Ant-Density）模型。這里擬采用蟻周（Ant-Cycle）模型：

式中：Q—正整數(shù)；Lk—第k只螞蟻在一次循環(huán)中走的路徑總長度。

為了避免算法陷入局部最優(yōu)解和提高算法的收斂性，對算法做出以下改進：

3.1 信息素取值范圍

在算法完成一次迭代后，最優(yōu)路徑上的信息素做出如下改變：

通過將信息素限制在一個確定的范圍內(nèi)，可減少算法的過早收斂和保證每個路徑點上的信息素差異不會比較大。

3.2 揮發(fā)系數(shù)

在經(jīng)典蟻群算法中，揮發(fā)系數(shù)是一個恒定不變的值，信息素揮發(fā)系數(shù)跟蟻群算法的全局搜索能力和算法的收斂速度有著緊密的聯(lián)系；因為ρ的存在，從未被搜索到的路徑上的信息素會逐漸減為0，當ρ較大時，再一次選擇之前搜索到的路徑的可能性較大，算法的全局搜索能力和隨機搜索性能也會受到影響；雖然減小ρ可以通過提高算法的全局搜索能力和隨機搜索性能，但同時會使得算法的收斂速度降低。

通過以上分析結(jié)果，提出了一種自適應改變信息素揮發(fā)系數(shù)的蟻群算法改進方略，意在通過自適應調(diào)整信息素揮發(fā)因子ρ來提高算法的全局性。在蟻群算法初期，算法的全局搜索能力需要提高，ρ需要比較大，隨著算法的執(zhí)行，為了提高算法的收斂速度，ρ的取值需要比較小。

式中：ρmin—ρ的最小值，可以避免ρ過小從而降低算法的收斂速度，a和b為系數(shù)。

4 路徑平滑處理

在柵格環(huán)境下蟻群算法規(guī)劃出來的路徑轉(zhuǎn)折次數(shù)多，折線多，路徑不夠平滑，機器人實際運動效率低。所以有必要對規(guī)劃后的路徑進行平滑處理。

貝塞爾曲線是基于伯恩斯坦多項式發(fā)展而來的，由于控制簡單卻有極強的圖形描述能力，位置點連接平滑，貝塞爾曲線在工業(yè)上得到了廣泛的應用。

一條n次貝塞爾曲線表達式為：

式中：P（u）—貝塞爾曲線的運動控制點；u—獨立變量；P（i）—位置點；P（0）、P（1）—起點和終點。所有位置點 P（i）構(gòu)成了一個特征多邊形；Bi，n（u）—n 次伯恩斯坦多項式，并且滿足：

當n=1時，一階貝塞爾曲線為一條直線，位置點有兩個；當n=2時，二階貝塞爾曲線為拋物線，位置點有三個；當n≥3時，曲線為高階貝塞爾曲線，位置點有n+1個。

對貝塞爾曲線求導有：

貝塞爾曲線具有以下性質(zhì)：

（1）貝塞爾曲線的起點和終點也是特征多邊形的起點和終點。

（2）貝塞爾曲線的起點和終點的切線與特征多邊形的起始線和結(jié)尾線方向一致。

（3）貝塞爾曲線起始于 P（0）結(jié)束于 P（1）。

（4）貝塞爾曲線特征多邊形一旦確定，曲線的形狀也就唯一確定，不依賴選取的參考系。

通過以上兩個算法的分析，下面將融合貝塞爾曲線和改進蟻群算法完成移動機器人的路徑規(guī)劃。

5 基于平滑蟻群算法的路徑規(guī)劃

具體的機器人平滑路徑規(guī)劃算法基本步驟如下：

（1）柵格法建立環(huán)境地圖，確定初始化蟻群算法參數(shù)以及移動機器人起始點S和目標點T。

（2）螞蟻k從點S開始運動，將S放置在禁忌表tabuk中，根據(jù)（2）式得到下個移動位置，添加到相應禁忌表中。

（3）判斷目標點T是否到達，如果已到達，則令k=k+1，然后轉(zhuǎn)到（2），直到這次迭代過程所有的螞蟻都完成路徑搜索任務。

（4）根據(jù)禁忌表tabuk中相關(guān)信息，可以計算蟻群的路徑長度，進而比較得到最短路徑。調(diào)整最短路徑上各個節(jié)點全局信息素值。

（5）判斷算法是否滿足退出條件，如果滿足條件，輸出最短路徑，否則轉(zhuǎn)至（2）。

（6）對規(guī)劃的路徑進行平滑處理。

對應的流程圖，如圖3所示。

圖2 蟻群算法流程圖Fig.2 Flow Chart of Ant Colony Algorithm

6 仿真實驗及其分析

本課題用Matlab 2014a對算法進行仿真研究，硬件條件為CPU 2.6 GHz、內(nèi)存 8 GB。

在仿真環(huán)境中中各個參數(shù)設定如下，實驗環(huán)境地圖柵格模型為15×15，蟻群算法螞蟻數(shù)目為40，最大迭代次數(shù)為50，揮發(fā)因子中系數(shù)a和b與分別為-0.8，25，改進蟻群算法中重要參數(shù)α=1，β=7。當機器人起始序號S為211，終點序號G為15時，仿真圖中坐標系的x軸方向正向向右，y軸方向向上，黑色方塊為障礙物?；诟倪M蟻群算法的移動機器人路徑規(guī)劃的仿真過程路徑圖，如圖4所示。

圖3 改進蟻群算法最終尋優(yōu)路徑Fig.3 Final Path of Improved ACO

算法均采用運行50次的平均值，對基本的蟻群算法和改進后的蟻群算法做了仿真實驗比較，兩種算法的尋優(yōu)路徑長度和迭代次數(shù)，如表2所示。

表1 算法性能比較Tab.1 Algorithm Performance Comparison

由仿真對比結(jié)果可知，和基本蟻群算法相比，改進優(yōu)化后的蟻群算法能避免搜索陷入局部最優(yōu)，收斂速度也更快。通過貝塞爾曲線平滑過后的路徑，如圖5所示。

圖4 路徑平滑F(xiàn)ig.4 Path Smoothing

通過平滑過后的路徑可知，優(yōu)化過后的路徑轉(zhuǎn)折次數(shù)大幅減少，更有利于機器人實際的運動，機器人運動更加平滑，對移動機器人自身的沖擊也越小。

在隨機生成的（20×20）的地圖中運行改進蟻群算法規(guī)劃出的最優(yōu)路徑，如圖6所示。通過大量仿真實驗結(jié)果證明了該改進算法能夠有效的解決機器人的路徑規(guī)劃問題。

圖5 尋優(yōu)路徑Fig.5 Optimization Path

6 結(jié)論

針對移動機器人路徑規(guī)劃問題上，提出了一種基于改進蟻群算法的方法，主要結(jié)論如下。（1）通過限制信息素的取值范圍，擴大了搜索結(jié)果，從而避免了路徑陷入局部最優(yōu)。（2）同時還提出了一種自適應調(diào)節(jié)信息素揮發(fā)因子的蟻群算法改進方針，通過自適應的信息素揮發(fā)因子來提高算法的全局性和算法的收斂速度，設置禁忌柵格，防止搜索時路徑死鎖。（3）針對蟻群算法在柵格環(huán)境中規(guī)劃出來的路徑為折線圖，提出了用貝塞爾曲線優(yōu)化路徑的方法，優(yōu)化后的路徑更有利于實際機器人運動情況。最后利用本研究提出的算法完成了路徑規(guī)劃任務，仿真實驗驗證了該方法具有可行性和有效性。