復雜環境下改進APF的機器人路徑規劃

盧恩超，張萬緒

西北大學信息科學與技術學院，西安 710127

復雜環境下改進APF的機器人路徑規劃

盧恩超，張萬緒

西北大學信息科學與技術學院，西安 710127

1 引言

路徑規劃是移動機器人研究領域的一個基本而又極其重要的課題，靈活有效的路徑規劃算法能幫助機器人適應各種復雜的環境，大大擴展機器人的應用領域。路徑規劃的任務是機器人在具有障礙物的工作環境中，按照某一性能指標，搜索一條從起始狀態到目標狀態的最優或近似最優的安全、無碰撞路徑[1]。目前，常用的路徑規劃方法主要有人工勢場法（Artificial Potential Field，APF）、柵格法、神經網絡法、蟻群算法[2]和粒子群算法[3]等。人工勢場法是路徑規劃算法中較成熟且高效的方法，以其數學計算上的簡單明了而被廣泛使用。

人工勢場法具有結構簡單、計算量小、實時性高、規劃軌跡平滑等優點，主要用于解決局部路徑的避障規劃問題，在機器人實時避障和平滑軌跡控制方面得到廣泛應用，但人工勢場法本身也存在著不足，主要體現在局部極值點和在大型障礙物環境中規劃時間較長且避障困難的問題。在對人工勢場法的深入研究中，國內外學者們對它的固有缺陷提出了各種改進方法，主要通過引入機器人與目標點的相對距離和修改斥力角度等方法對斥力勢場函數進行修改，但是都沒有從根本上解決上述問題。針對上述問題，本文在文獻[4]的基礎上采用邊緣探測法并提出自適應動態步長調整算法，以確保移動機器人迅速避開障礙，順利到達目標點。

2 人工勢場法基本思想和模型

2.1 人工勢場法基本思想

人工勢場法（APF）是由Kathib[5]提出的一種虛擬力法?；舅枷胧牵簷C器人的運動空間是二維的，目標點對機器人產生引力，障礙物產生斥力，引力和斥力的合力作為機器人的加速力，控制機器人的運動方向并確定機器人的位置。該方法通過搜索合成勢場中勢能的下降方向，實現機器人的無碰撞路徑規劃[6]。它的突出優點是所需的環境信息量較少，因此，在局部路徑規劃中更能顯示出它的優越性。

2.2 人工勢場模型

2.2.1 目標點的引力函數

設機器人在運動空間中的位置為X=(x,y)T，目標點對機器人產生的引力Fatt是引力勢場函數Uatt的負梯度，則引力可以定義為：

式中，katt為引力正比例增益系數，Xgo為機器人在勢場中的目標位置。當機器人到達目標的過程中，引力逐漸線性收斂于零。

2.2.2 障礙物處斥力函數

障礙物對機器人產生的斥力Frep是斥力勢函數Urep的負梯度，則斥力可定義為：

式中，n為任意實數，krep為斥力勢場正比例增益系數，ρ(X)為機器人與障礙物的最短距離，ρ0為單個障礙物的最大影響距離，主要取決于機器人的運動速度和減速能力。

APF容易出現局部極小值的根本原因在于：機器人無法掌握環境的全部信息，公式（3）中引入了機器人和目標點的距離因子(X-Xgo)n，從而確保整個勢場僅在目標點全局最小[7]。定義Frep2(X)的方向與引力方向一致，對于機器人、目標點、障礙物在同一直線且障礙物不在中間時，定義Frep1(X)與Frep2(X)同向，其他情況定義Frep1(X)的方向與障礙物的影響范圍相切，且與引力向量的內積大于等于零[8]。這樣，機器人在到達目標點之前，不可能出現合力為零的情況，從而避免傳統APF算法中機器人容易陷入局部極值點的問題。

在對APF路徑規劃進行仿真時，發現該方法在障礙物大小相同或相近的環境中，機器人能很好地從起始點繞過障礙物到達目標點，但是，對于環境中存在大型障礙物或運動空間相對狹窄的情況，機器人容易出現避障失敗。為此，本文提出一種能夠適應復雜環境的避障策略——邊緣探測法，并加入自適應動態步長調整算法，確保機器人在大型障礙物和多障礙物的狹窄環境中能順利繞過所有障礙物，快速到達目標點。

3 邊緣探測法

APF法是通過環境勢場模型進行路徑規劃的，合理的環境模型能夠極大提高路徑規劃的速度和準確度。文獻[4]中環境模型的建立是將障礙物視為同等大小，但是當復雜環境中存在大型障礙物時，如果仍按照上述方法，機器人將在較小的障礙物周圍繞很遠的路，甚至直接與障礙物碰撞而導致路徑規劃失敗。針對上述情況，本文提出一種新的環境模型的建立方法，并結合邊緣探測法，確保機器人更好地適應大型障礙物的復雜環境需求。

3.1 環境模型的建立

機器人環境模型的建立：擬在靜態環境下，利用勢場的概念在二維平面上對機器人工作環境進行建模。為方便對移動機器人在規劃過程中的處理，將機器人模型簡化為一個很小的質點，同時將障礙物（T形和桿形障礙物除外）進行膨脹化處理。

具體做法：利用機器人攜帶的多種傳感器（如視覺、超聲、紅外傳感器等）通過傳感器信息融合技術來獲取障礙物的尺寸、形狀和位置等局部環境信息。首先，將機器人的實際尺寸折算進障礙物的面積內，同時根據機器人的實際尺寸將障礙物的邊界向外擴展，其次，再將邊界外擴后的障礙物膨脹化為一個包含該障礙物的最小圓，這樣，就簡化了APF算法中距離的計算和問題的描述。

3.2 邊緣探測法步驟

如圖1所示：假定實線圓O（半徑為R）代表膨脹化障礙物，以O為圓心，OXk為半徑的虛線圓與直線OXk+1'相交的點記為Xk+1，該點稱為引導點。則邊緣探測法的步驟如下：

（1）當機器人進入障礙物的影響范圍內時，不斷探測下一步將要到達的位置，若機器人探測到下一步的位置在障礙物膨脹化邊界內時，就停止向前運動，并及時調整自身姿態向Xk+1處移動。

（2）當機器人到達Xk+1點后退出邊緣探測法，進入APF路徑規劃繼續探測下一步的位置Xk+2，若Xk+2不在障礙物的膨脹化區域內，則說明機器人已成功避開該大型障礙物，否則，繼續按照步驟（1）逐步進行探測，直到機器人預探測的下一步位置Xk+m不在障礙物區域內為止。一般來說，m只需一步或者幾步即可。

圖1 邊緣探測法示意圖

邊緣探測法的實質是利用引導點引導機器人離開障礙物區域。當檢測到障礙物時，機器人就按照給定的避障策略完成避障任務，它的激活條件是OXk+m≤R。

本文在勢場環境模型下結合邊緣探測法，引導機器人沿著距障礙物一定距離的邊緣運動，以達到避障和平滑路徑的作用。但是，該方法存在規劃時間長的問題，尤其在環境信息部分未知的局部路徑規劃中，機器人在向目標邁進的過程中通常是一步一步試探前進，然后根據傳感器采集到的信息更新局部環境信息，最后經過計算在得到下一步的前進方向θ后，機器人就沿著該方向以固定步長l向前移動。因此，為了提高APF算法的收斂速度和路徑規劃的效率，從步長入手，提出自適應動態步長調整算法對APF路徑規劃加以改進。

4 自適應動態步長調整算法

4.1 自適應動態步長調整算法原理

在APF模型下，通過對機器人受力分析可知，機器人的運動軌跡如圖2所示，其規律可總結如下：

（1）當ρ(X)＞ρ0時，只受目標點的吸引力，機器人將沿引力方向直線運動。

（2）當ρ(X)≤ρ0時，機器人在合力作用下，將沿著障礙物的邊緣做圓弧狀運動。

圖2 固定步長路徑規劃圖例

一般來說，整個環境中，自由空間占據絕大部分，在這些自由空間中，如果步長取值太小，必然會降低算法的性能。尤其在障礙物分布不均勻和大型多障礙物的復雜環境中，如果步長太小，不但使機器人到達目標點所消耗的時間變長，還容易陷入死鎖狀態使機器人在局部區域不斷徘徊，甚至無法前進。同時，過多的姿態調整將導致許多機械方面的問題（例如輪子滑動誤差等）。但是，如果步長太大，會大大增加機器人與障礙物的碰撞機率，而且機器人很有可能錯過一些比較隱蔽的入口，從而繞了許多彎路，沒有達到路徑優化的目的[9-10]。

圖3 （a）動態步長調整法路徑規劃圖例

由于機器人運動軌跡比較簡單且有一定的規律，所以面對比較復雜的環境，機器人需要有根據障礙物的分布情況自動調整步長的能力?；谏鲜龇治?，本文提出自適應動態步長調整算法，該算法隨著搜索方向的變化動態調整搜索步長，從而實現較快的搜索，以提高復雜環境中APF算法的收斂速度和路徑規劃的實時性。

式中，θ為機器人的合力方向，γ為動態步長，表示機器人每步行走的相對距離。λ為步長增益系數且0≤λ≤1，α為合力方向與環境坐標系x軸之間的夾角且α∈[0,π]。δ為步長增益補償量且lmin≤δ≤lmax，此處α是為了防止步長為零而設置的。lmax和lmin分別為固定步長路徑規劃時步長的最大值和最小值，是動態步長γ的一個參考約束范圍，其值與環境大小和障礙物的分布情況密切相關。

在程序運行過程中，λlmax和δ都是相對固定的。由前面對機器人的受力分析可知，當ρ(X)≤ρ0時，機器人開始進入避障狀態，步長γ將隨著α的增大而逐漸變?。划敠?X)＞ρ0時，機器人運動方向固定，步長γ可以取一個較大的固定值。由于α的變化直接反映了機器人是否進入避障狀態，因此，公式（6）選取了α作為動態步長γ的變量。

4.2 自適應動態步長調整算法策略分析

機器人由于受自身（如慣性、機械摩擦等）以及外界環境（如地面情況、障礙物分布等）影響，在避障過程中很容易與大型障礙物碰撞，因此，機器人在實際運動時其速度設定應與動態步長γ成正比。

如圖3（a）所示，當機器人在障礙物的影響范圍之外時，機器人做直線運動，此時，步長γ的值（對應于圖3（b）中直線段a和c）相對圖3（b）中的固定步長（虛線）來說比較大，機器人可以快速運行；當機器人進入障礙物的影響范圍內時，為避免機器人與障礙物碰撞，在避障初期，由于運動方向θ的變化比較大，此時，步長γ的值（對應于圖3（b）中的曲線段b）應該適當減小，機器人慢速運行，直到安全避開障礙物為止，之后機器人再以較大的步長（對應于圖3（b）中直線段c）加快速度向目標點運動。這樣，就在局部提高機器人避障精度的同時也全面提高了路徑規劃的速度和效率。

圖3 （b）固定步長和動態步長曲線圖

總之，根據空間中障礙物的分布信息來自動調整步長的大小，不僅可以優化路徑，降低陷入局部極值點的機率，縮短到達目標點的時間，而且還能提高APF算法的收斂速度以及路徑規劃的效率和機器人的安全性。

5 仿真結果與分析

在改進APF機器人路徑規劃中，假設機器人的運動速度是可變的，在APF環境模型中，障礙物大小和分布情況可根據傳感器獲得的局部環境信息抽象出來，在運動初期應合理設定機器人的避障范圍（略大于障礙物的影響范圍）。

采用改進前后的APF路徑規劃，在相同環境和參數（不包括初始步長）條件下，分別對機器人路徑規劃進行仿真，結果如圖4和圖5所示。表1為機器人在環境中障礙物的個數分別為7和8時，利用傳統APF和改進APF（IAPF）路徑規劃經過多次實驗所得的實驗數據對比。

圖4 基于APF的機器人路徑規劃

圖5 改進APF的機器人路徑規劃

表1 改進前后APF路徑規劃參數對比

從仿真結果可以看出，圖4中機器人的運動步長是固定的，并且機器人在運動過程中遇到大型障礙物7時，直接與障礙物碰撞，而圖5在邊緣探測法的基礎上加入自適應動態步長調整算法后，機器人不僅能夠順利避開所有障礙物到達預定目標點，而且在整個規劃過程中，步長隨著障礙物的分布呈動態變化趨勢。表1中實驗數據表明，改進APF路徑規劃所需的步數和規劃過程中消耗的時間明顯減少，并且步數的減少幅度分別為35%和36.8%。結果表明，加入自適應動態步長調整算法后APF路徑規劃的效率得到較大的提高，并且環境空間越大，該方法的優勢就會越明顯。

6 結束語

為克服APF自身的缺陷，本文通過分析APF機器人路徑規劃及所生成的路徑軌跡的特點，提出在邊緣探測法的基礎上加入自適應動態步長調整算法，并采用APF加以實現，確保機器人在有大型障礙物和運動空間相對狹窄的復雜環境中，不僅能從給定起始點安全、無碰撞地繞過所有障礙物到達預定目標點，而且還縮短了路徑規劃的時間，提高APF算法的收斂速度和機器人的避障精度。經過多次實驗及仿真結果表明：改進APF路徑規劃克服了傳統勢場法中存在的局部極值點、規劃時間長以及大型障礙物附近避障困難的缺點，同時保留了傳統勢場法計算簡單的優點。因此，改進APF機器人路徑規劃具有較強的路徑規劃能力和實際意義。

當然，在實際應用中環境是復雜多變的，對于桿形和T形障礙物的處理以及如何改進勢場函數，確保APF算法能夠適應動態未知環境下的路徑規劃，是下一步將要研究的重點。

[1]姚靖靖，邱于兵，敖俊宇.移動機器人避障路徑規劃改進人工勢場法[J].科學技術與工程，2011，11（13）：2953-2956.

[2]何少佳，劉子揚.基于慣性蟻群算法的機器人路徑規劃[J].計算機工程與應用，2012，48（15）：245-248.

[3]馬千知，雷秀娟.改進粒子群算法在機器人路徑規劃中的應用[J].計算機工程與應用，2011，47（25）：241-244.

[4]沈文君.基于改進人工勢場法的機器人路徑規劃算法研究[D].廣州：暨南大學，2009.

[5]Kathib O.Real-time obstacle avoidance for manipulators and mobile robots[C]//The International Journal of Robotics Research，1986，5（1）：90-98.

[6]曲道奎，杜振軍，徐殿國，等.移動機器人路徑規劃方法研究[J].機器人，2008，30（2）：97-101.

[7]石為人，黃興華，周偉.基于改進人工勢場法的移動機器人路徑規劃[J].計算機應用，2010，30（8）：2021-2023.

[8]孟蕊.基于改進人工勢場法的足球機器人路徑規劃研究[D].北京：北京工商大學，2010.

[9]梁軻.移動機器人在未知環境下的自適應路徑規劃[D].上海：復旦大學，2005.

[10]黃凱，周永權.一種改進的變步長自適應GSO算法[J].計算機工程，2012，38（4）：185-187.

LU Enchao,ZHANG Wanxu

School of Information Science and Technology,Northwest University,Xi’an 710127,China

When the obstacles are large,or the complex environment space is relatively narrow,Artificial Potential Field method（APF）is prone to appear repeated shocks,long time planning and obstacle avoidance of difficulty nearby the large obstacles. This paper presents an adaptive dynamic step length adjustment method based on the APF path planning which is combined with the edge detection method to overcome the proposed defects of APF,achieving mobile robot smooth path planning in the complex environment.Hence it can not only improve APF algorithm convergence speed and the safety of path planning,but at the same time ensure the approximate optimum path.Experiments are carried out by simulation to verify the effectiveness of the aforementioned methods.

Artificial Potential Field（APF）;path planning;edge detection;adaptive dynamic step length adjustment

針對移動機器人在有大型障礙物和運動空間相對狹窄的復雜環境中，人工勢場法（APF）容易出現反復震蕩、路徑規劃時間較長以及大型障礙物附近避障困難的問題，提出了在結合邊緣探測法的APF路徑規劃基礎上，加入自適應動態步長調整算法來克服APF的上述缺陷，實現移動機器人在復雜環境下的平滑路徑規劃，在確保路徑近似最優的同時提高APF算法的收斂速度和路經規劃的避障性能。實驗結果證明了上述方法的有效性。

人工勢場法；路徑規劃；邊緣探測；自適應動態步長調整法

A

TP242

10.3778/j.issn.1002-8331.1207-0287

LU Enchao,ZHANG Wanxu.Path planning for mobile robot based on improved Artificial Potential Field method in complex environment.Computer Engineering and Applications,2013,49（24）：45-48.

盧恩超（1985—），女，碩士研究生，研究領域為智能控制與測試；張萬緒（1964—），男，博士，副教授，研究領域為智能控制與測試和電視信號處理。E-mail：luenchao_666@163.com

2012-07-20

2012-09-06

1002-8331（2013）24-0045-04

CNKI出版日期：2012-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20121011.1019.021.html