郭江1,2，肖宇峰1,2，劉欣雨1，陳麗1
(1.西南科技大學 信息工程學院，四川 綿陽 621010；2.西南科技大學 特殊環境機器人技術四川省重點實驗室，四川 綿陽 621010)
摘要：移動機器人路徑規劃一直是移動機器人領域里的重要技術問題。A*算法在最優路徑搜索上有著比較成功的運用，但在柵格環境下的A*算法也存在著折線多、轉折角度大等問題。在考慮移動機器人的實際工作環境及相關運動參數后，這些問題都將大大地影響移動機器人的工作效率。在對以上問題進行分析后提出了一種基于Bezier曲線與A*算法融合的方法來實現移動機器人的路徑規劃，再通過MATLAB、VREP仿真工具來實現Bezier_A*融合算法與平滑A*算法及A*算法的對比。通過Bezier_A*融合算法使得機器人在工作中的尋優能力、路徑規劃效率都得到較大的提高。
關鍵詞：移動機器人；路徑規劃；A*算法；Bezier曲線；融合算法
中圖分類號：TP391文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.02.017
引用格式：郭江，肖宇峰，劉欣雨，等.Bezier曲線與A*算法融合的移動機器人路徑規劃［J］.微型機與應用，2017,36（2）：52-55，59.
0引言
*基金項目：國家自然科學基金(61601381);四川省科技支撐計劃項目(2015GZ0035);四川省教育廳重點項目(14ZA0091)移動機器人路徑規劃問題一直以來都是移動機器人研究的熱點和難點［1］。在近年的發展中，越來越多的學者和專家已經致力于結合智能控制算法來解決移動機器人的路徑規劃問題。例如遺傳算法［2］、蟻群算法［3］、禁忌搜索算法［4］等智能算法及其混合形式都被用來解決路徑規劃問題。但這些智能算法目前還不太完善，存在著一些缺點，例如遺傳算法編碼長度變化范圍大，求解規模小；Dijkstra算法［5］直接搜索全局而不考慮目標信息，導致路徑求解時間長，難以滿足快速規劃路徑的需求；D*算法［6］主要解決局部的動態路徑規劃問題。
A*算法［7］作為一種比較成功的全局路徑規劃算法，已成功應用于機器人的路徑尋優和規劃方面，并且取得良好的路徑規劃效果。但由于A*算法本身的計算特點，在柵格環境下A*算法規劃出的移動機器人路徑一般存在著折線多、累計轉角大等問題。在對A*算法進行平滑［8］處理方面，最近幾年也出現了不少的研究成果。但絕大多數的平滑處理方法都是著眼于障礙物與移動機器人交匯處來進行處理。這種平滑方式有著很大的局限性，平滑算法在對路徑平滑時，都是遍歷所有的節點，當某一個節點前后節點連線上無障礙物時，就將延長線路的這一中間節點刪除，當遍歷到路徑上從起始點到終止點的所有節點時，平滑算法終止，路徑平滑規劃結束。這樣的平滑方式由于是遍歷所有的節點，將大大影響算法的運行效率。本文主要處理兩個問題：其一，因A*算法在柵格地圖中生成的路徑折線多、轉折多而影響機器人工作效率的問題；其二，現行的路徑平滑算法效率不高的問題。針對以上兩個問題，本文提出一種將Bezier曲線［9］與A*算法融合的規劃算法，并通過MATLAB、V_REP仿真工具來實現與平滑A*算法、A*算法的性能對比分析。
1環境建模
移動機器人的路徑規劃在實際應用上主要是面對兩個問題：一是環境建模；二是路徑搜索生成及處理策略［10］。本節主要討論環境建模，在下一小節將對路徑搜索算法及處理策略進行分析。
移動機器人路徑規劃的環境建模有很多種，例如柵格法、拓撲圖、幾何信息法等。柵格法在許多機器人系統中得到應用，是比較成功的一種環境建模方法，且柵格地圖容易創建和維護，因此本文采用柵格法。常用的環境地圖表示中柵格地圖的特點是容易創建和維護，創建成本和使用成本都比較低。移動機器人所了解的每個柵格信息直接與環境區域相對應，且移動機器人可以根據柵格地圖進行導航與定位。在本文中所創建的柵格環境模型是根據實驗室環境及障礙物映射生成的，最終柵格通過機器人仿真工具VREP畫出，如圖1所示。VREP柵格地圖中，黑色區域表示實驗室中的障礙物區域，灰白色區域表示可安全行走區域。
2Bezier曲線與A*算法原理分析
2.1A*算法原理分析
A*算法是建立在Dijkstra和BFS(廣度優先搜索)算法基礎上的搜索算法。它的整體框架采用遍歷搜索法，但是它采用了啟發函數來估計地圖上任意點到目標點的費用，從而可以很好地選擇搜索方向。
A*算法引入了當前節點x的啟發函數f(x)，當前節點x的啟發函數定義為：
f(x)=g(x)+h(x)(1)
其中g(x)是從起點到當前節點x的實際費用度量，h(x)是從當前節點x到終點的最小費用估計。h(x)只要滿足相容性條件：不能高于節點x到終點的實際最小費用，則原問題存在最優解，并且A*算法一定能夠求出最優路徑。A*算法的優點是利用啟發函數，使搜索方向更加智能地趨向于終點，所以其搜索深度較小，搜索的節點數少，這樣將大大提高算法的運行效率。
A*算法是廣泛使用的移動機器人路徑規劃上的一類算法，同時它也適用于全局環境信息已知的路徑規劃。但是目前A*算法在實際的工程運用中還是存在折線多、轉折次數多、累計轉角大等問題，給機器人運行造成較大的麻煩，例如，轉角多時，必須準確計算出機器人和障礙物間距，否則就會發生碰撞；當累計角度大、轉角多時，機器人的工作效率也會下降。考慮上述問題，本文首先采用A*算法實現路徑的初步規劃，再采用Bezier曲線實現融合處理。
2.2Bezier曲線分析
n次曲線的定義式有多種形式,目前使用最廣泛的是由英國學者Forrest于1972年給出的定義：
P(u)=∑niPiBi,n(u),u［0,1］(2)
其中，pi(0≤i≤n) 被稱為曲線的第i個控制點，順次連接從p0到pn的折線被稱為Bezier曲線的控制多邊形。Bi,n(u)為n次Bernstein多項式,其表達式為：
在坐標系xoy中，對于給定已知的四個控制點(x0,y0),(x1,y1),(x2,y2),(x3,y3)可以由公式（4）、（5）確定一個3次Bezier曲線。
通過分析3次曲線的定義式可知，0次Bezier曲線是其唯一的控制點P0，1次Bezier曲線是連接P0至P1的線段，2次或者2次以上的Bezier曲線則具有以下性質：
（1）端點性質：Bezier曲線的起點P0和終點Pn與特征多邊形的起點和終點重合。
（2）切矢量性：Bezier曲線的起點和終點處的切線方向和特征多邊形的第一條邊及最后一條邊走向一致。
（3）凸包性：曲線落在特征多邊形各頂點構成的凸包之中。
（4）幾何不變性：Bezier曲線的幾何特性不隨坐標變化而變化，Bezier曲線的位置和形狀與特征多邊形頂點的位置有關，而不依賴坐標的選擇。
通過以上兩個算法的分析，下面將設計Bezier曲線與A*算法的融合方案。
2.3Bezier曲線與A*算法融合的路徑規劃方案
移動機器人路徑規劃的最終目標是：在保證機器人能達到目標點的同時，找到一條平滑可行的最短路徑。移動機器人路徑規劃的一切設計方案都應該遵循這個宗旨。A*算法能夠保證機器人在充滿障礙物的地圖中找到一條最短路徑。但找到這一條最短的路徑還是遠遠不夠的，A*算法本身存在著許多的不足：在柵格環境下A*算法規劃出的移動機器人路徑往往存在著折線多、轉折次數多、累計轉折角度大、運行效率低等許多問題。
在分析了A*算法的突出問題后，提出了一種A*算法與Bezier曲線融合的路徑規劃方法，通過融合算法的實現，將有效地解決A*算法及平滑A*算法所存在的折線多、轉折次數多、轉折角度累計大等問題。整個融合算法大體分以下步驟完成：第一步，實現A*算法對移動機器人路徑的初步規劃；第二步，將所規劃的路徑進行Bezier曲線再規劃處理；第三步，對Bezier曲線融合后的分段曲線進行拼接并最終輸出融合路徑。在以上的三個處理步驟中主要的難點問題是如何解決A*算法初次規劃后，對初步路徑的節點信息進行再處理。當得到初步的路徑節點信息后，不可能對所有節點都采取一致的3次Bezier曲線或者2次Bezier曲線優化，單調地使用2次或者3次以及更高次的Bezier曲線處理往往會使移動機器人陷入障礙物死區,如圖2所示，在對4個節點進行Bezier曲線優化時，觸碰到了障礙物，讓機器人陷入了工作死區。但對于障礙物死區問題，結合2次或者3次的處理后，問題將得到很好的解決，能使移動機器人成功地避開障礙物死區。對于2次的Bezier曲線，由公式（2）可得：
結合2次曲線和3次曲線的處理，即可避免移動機器人陷入死區等問題。再對每一段k(k=1,2,3)次曲線按照公式（8）進行拼接:
S(u)=∑ki=0(Pi－Bi(ui))2(8)
如圖3所示，通過分段的Bezier處理，有效地避免了障礙物死區問題。整個融合算法實現偽代碼如下：
OPEN表 = 起始點start；
CLOSED 表 = 空；
BEZIER 表 = 空；
圖3融合算法避開死區
While(OPEN != NULL)
{
從OPEN表中取估價函數f最小節點n;
If(n==目標節點){
Break；
}
For(當前節點n的每個子節點X){
算X的估價值；
If(X in OPEN){
If(X的估價值小于OPEN的估價值){
把n設置為X的父節點；
更新OPEN表中的估價值；
}}
If(X in CLOSE){
If(X的估價值小于CLOSE表估價值){
把n設置為X的父節點；
更新CLOSE表中的估價值；
把X節點放入OPEN；
}}
If(X not in both){
把n設置為X的父節點；
求X的估價值；
并將X插入OPEN表中
}}//end for
將n節點插入CLOSE表中；
按估價值將OPEN表中的節點排序；
BEZIER 表 = 初次規劃的路徑節點；
}//end while(OPEN != NULL)
While(BEZIER != NULL){
For(對路徑所有節點進行Bezier處理){
If(4節點處理無障礙){
3次bezier曲線處理；
更新此4節點為一段Bezier曲線；
}
If(3節點處理無障礙){
2次Bezier曲線處理；
更新此3節點為一段Bezier曲線；
}
If(2節點處理無障礙){
1次Bezier曲線處理；
更新此2節點為一段Bezier曲線；
}}//end for
對每段Bezier曲線實現拼接處理；
輸出融合處理后的路徑
}//end while(BEZIER !=NULL)
3實驗仿真分析
本仿真實驗計算機采用處理器為Intel(R) Core(TM) i54595,內存為4 GB；算法分析工具為MATLAB；路徑規劃仿真工具為VREP。
通過機器人仿真工具VREP，編寫相關代碼實現了A*算法及Bezier_A*融合算法的路徑規劃如圖4、圖5所示。從兩個圖中可以很清晰地看到，A*算法規劃路徑的折線較多、轉折次數也較多，但在圖5中由Bezier_A*融合算法生成的路徑上折線和轉角已經大大減少。
在V-REP中將A*算法及融合算法的節點數據導出到數據表格，在MATLAB中，得到圖6所示的規劃路徑。
圖6路徑規劃對比效果為同其他的路徑規劃算法形成性能分析對比，本文將文獻［7］和［8］中給出的A*算法、平滑A*算法兩種算法的分析結果與本文算法進行對比分析，對比環境為：40×40的柵格地圖。表1是Bezier_A*融合算法與A*算法性能對比，表2是Bezier_A*融合算法與平滑A*算法的性能對比。
降低率/%累計
轉折數折線
減少率/%A*45.873 636Bezier_A*43.234 65.75683.33
表2Bezier_A*融合算法與平滑A*算法算法累計
轉折角轉折
降低率/%運行
時間/s時間
減少率/%平滑A*456.873 60.362 1Bezier_A*326.811 528.460.291 619.47
通過仿真實驗可以得出，與A*算法、平滑A*算法相比，使用Bezier_A*融合算法所規劃的移動機器人路徑各方面性能得到了較大的提升。對比A*算法，Bezier_A*融合算法有效地減少路徑距離6%左右，將累計的轉折數減少了85%左右；對比平滑A*算法，Bezier_A*融合算法能更加有效地減少累計轉折角30%左右，并且將算法的運行效率提升了20%左右。
4結論
本文主要針對柵格環境中的移動機器人路徑規劃實現，分析了A*算法、平滑A*算法在移動機器人路徑規劃上所存在的缺點，如轉折角度大、轉折數多等問題，這些問題都將大大影響移動機器人的實際工作效率。針對以上問題，本文提出A*算法與Bezier曲線融合的路徑規劃算法，融合算法大大改善了移動機器人的運動性能。最后通過仿真實驗證明，融合算法減少了累計轉折角30%左右，減少累計轉折數85%左右，相比于一般的平滑A*算法，融合算法還提升了運行效率。實際運用中Bezier_A*融合算法在障礙物分布廣泛的柵格環境下具有轉折次數少、累計轉折角度小等優點，更能滿足移動機器人在工作時的運動需求。
參考文獻
［1］ ZAMIRIAN M,KAMYAD A V,FARAHI M H. A novel algorithm for solving optimal path planning problems based on parametrization method and fuzzy aggregation［J］.Physics Letter A,2012,373(38)：34-39.
［2］ PANDA R K, CHOUDHURY B B. An effective path planning of mobile robot using genetic algorithm［J］.IEEE International Conference on Computational Intelligence & Communication Technology,2015,145(15)：287-291.
［3］ 張琦，馬家辰，謝偉，等. 基于改進蟻群算法的移動機器人路徑規劃［J］. 東北大學學報，2013,34（11）：1522-1527.