基于改進人工勢場模型的移動機器人路徑規劃

摘要:針對傳統人工勢場模型在移動機器人路徑規劃中存在局部極值的問題，提出了一種改進方法。該方法首先將傳統勢場模型轉換成解空間中尋優的問題，再加入罰因子建立罰函數數學模型。新的勢場模型能夠有效的使得機器人成功逃逸局部極值點。最后通過MATLAB進行仿真實驗，仿真實驗結果證明該方法的有效性。

關鍵詞:移動機器人;人工勢場;路徑規劃;罰函數;函數優化

中圖分類號:TP242文獻標識碼:A文章編號:1009-3044(2010)11-2708-03

Research of Path Planning for Mobile Robot Based on Evolutionary Artificial Potential Field

ZHU Jun1， WANG Yu-jun1， CHANG Guang-hua2， XU Fang1

(1.College of Computer and Information Science， SouthWest University， Chongqing 400715， China; 2.Department of Computer Science and Technology， Beijing Information Science and Technology University， Beijing，100101， China)

Abstract: This paper propose an improved method for local extremum problems exist in path planning of mobile robot used traditional APF model.The method uses penalty function model to solve the problem of local constraints.Firstly，converting potential field models into optimization problems of the solution space. Secondly，adding penalty factor to establish a mathematical model.The new model can effectively makes the robot to escape local maximum point. At last， using MATLAB tool to simulate this method.The final simulation results show that the method is effective.

Key words: mobile robot; artificial potential field; path planning; penalty function; function optimize

路徑規劃問題是移動機器人研究領域的重要技術之一，一直以來很多的學者將這個問題視為移動機器人研究的熱門。路徑規劃可以分為兩個大類:第一是全局路徑規劃，就是環境信息已知，其中環境中障礙物幾何形狀，以及分布坐標均已知，第二是局部路徑規劃，這是建立在環境信心未知或者部分未知，移動機器人需要通過傳感器實時的感知外界環境并通過自身的控制策略在線規劃移動路徑。全局規劃方法包括環境建模和路徑搜索兩個子問題，是一種事前規劃一般情況下要先對環境信息進行建模，然后采用某種搜索方法搜索最優路徑[1] 。局部路徑規劃是要求移動機器人具備對環境的建模和搜索同時進行的能力，這就需要移動機器人的核心處理運算能力較強，并且還要具備設備噪聲處理算法。局部規劃由于缺少環境的信息，以及移動機器人傳感設備工作范圍有限，可能規劃的路徑不是全局最優路徑，甚至在某些情況下，移動機器人不能規劃完整的路徑，陷入某些局部“死”點。路徑規劃作為移動機器人的重要技術之一，對于移動機器人有著重要的意義，機器人如果要成功的完成任務，必須完成路徑規劃。

1 人工勢場模型

人工勢場法是一種傳統的路徑規劃方法，該方法最先由Khatib在其博士論文中提出，作為工業機械手臂的路徑規劃研究方法，取得很好的成果，多年以來人工勢場得到廣大學者的大量研究，并對其做了很多的改進，形成了目前人工勢場的兩個主要研究方向:第一種是選擇更好的勢場函數，使得勢場中出現極小值的概率減小;另一種是將人工勢場法和別的方法融合來克服人工勢場的缺點[2] 。

人工勢場法的基本思想是將機器人視為在環境空間中的受到一種虛擬的力場的運動，該力場主要由目標物對機器人的引力和障礙物對機器人的斥力構成，這兩個力的合力就是移動機器人的運動方向，我們把移動機器人簡化成二維空間中的一質點，它的運動空間是二維的它在運動空間中任意位置X(X=[x y]T)的移動方向由障礙物的斥力場和目標物的引力場總場強的方向指定[1] 。

引力勢場函數可以定義為:

(1)

該式中，X與Xg代表機器人和目標物在二維運動空間中的坐標位置，ρ(X，Xg)=||Xg-X||代表機器人與目標物之間的距離，k為正比例位置增益系數，則引力Fattr是勢場函數的負梯度[1] :

(2)

斥力勢場函數:

(3)

該式中，η為正比例位置增益系數，ρ(X，X0)為機器人在空間中的位置與障礙物之間的最短距離，ρ0為障礙物的影響距離，在該距離范圍內，機器人才會受到斥力的影響，該值一般視具體情況而定，通常選擇的參考標準是障礙物之間距離的一半以及障礙物到目標物之間的最小的距離[1] 。

機器人沒到到達目標處，受到的斥力可以用下式定義:

(4)

則機器人受到的合力為:

F=Fattr+Frep(5)

該力決定了機器人的運動方向，如圖1所示。

2 改進人工勢場的方法設計

由于傳統人工勢場模型進行路徑規劃的時候，當環境模型為圖2所示時，機器人將出現在局部點死機，不能繼續規劃路徑，處理該局部約束的情況，可以借鑒優化方法跳出局部約束采納的懲罰函數的辦法，對傳統的人工勢場模型加入懲罰因子，使其跳出局部死機點。

罰函數法主要有簡單罰函數法，內點罰函數法和乘子法。罰函數的主要思想是構造適當的罰函數，將約束優化問題轉化成一系列的無約束優化問題。對函數在不可行的點即外點處進行懲罰，讓函數跳出約束限制。

其中f(x)，gi(x)，i=1，…，m，hj(x)，j=1，…，p是連續函數。

記:

(6)

(7)

則(CNP1)的可行域S={x∈Rn|c(x)=0}。

引入罰函數可以定義為:

F(x)=f(x)+H(x) (8)

其中f(x)為優化的目標函數，H(x)為罰因子，可以定義為[3] :

(9)

式中φi(x)max{0，gi(x)} ，gi(x)為約束函數，而h(#8226;)， μ(#8226;)， δ(#8226;)依賴具體的問題而定[3] 。本文的約束條件為機器人能夠順利通過局部極小值點。

因此首先應將人工勢場進行路徑規劃的問題轉化為優化求解問題，機器人路徑規劃其實就是尋找環境中某點處的勢場下降最快的方向。而機器人處于環境中某一點的勢場跟它與障礙物的距離和目標物的距離相關。

移動機器人可以用傳感設備，如全景視覺探知周圍的環境信息，并且判斷距離，根據這些信息，可以求出該點的勢場。

為了轉化路徑求解問題成函數優化問題，在這個時候可以采用候選解的方案[4]。即機器人在某一時刻的可能運動方向作為它的一個候選解，所有的運動方向可以組成解空間θ=(θ1，θ2，…，θN) [4] 。這樣移動機器人的路徑規劃問題就可以轉化成了解空間內的尋優求解過程。

在移動機器人的運動空間中，有各種未知邊界障礙物等等環境因素，因此上述的優化求解的過程是有約束限制的，該約束求解的方程如下[4-5] :

(10)

該式中， Pi(xi，yi)為機器人第i步的坐標，向量CM_D=[cos(θT)，sin(θT)]為梯度方向θT的向量表示，向量CMi=[cos(θi)，sin(θi)]為候選解的向量表示，OB=[ob1，…，obn]障礙物集合表示， Goal=[xg，yg]為目標的坐標，XLeft，XRight，Yleft，YRight為環境的上下邊界[2] 。

由于機器人陷入局部極小值點，將會在該點附近震蕩，來回徘徊，這種情況可以用下式表達:

(11)

該式中，ξ為無窮小量，該式表達了機器人在第n步和第n+m-1步上的m個位置來回振蕩，無法繼續前進搜索目標[6] 。此時為了跳出局部極小值，應當選擇丟棄掉目標物的引力，讓機器人只收到障礙物的斥力影響，執行調轉車向策略，這樣罰函數法中的罰因子可以定義為:

(12)

如果||Δpi+1-Δpi||

式中λi為罰常數取值-1，m1，m2為設定的局部極值的判斷閾值常數，m為經過Pi點后行走的步數。該方法的可行性是建立在勢場連續性的基礎上的，機器運動過程中，通過三個坐標點的位置來判斷機器人的路徑，這三點為機器人的當前所處的位置Pi，下一步要到達的位置Pi+1，以及之前上一步所處的位置Pi-1。

3 算法實現步驟

1)首先要初始化環境參數，確定環境的起點坐標，目標點坐標，以及障礙物的坐標，建立起勢場模型。

2)為了降低復雜性，提高實時性，勢場解空間的選取由粗到精的策略，先在機器人全景視覺中選取周圍8個45度等分圓的方向進行判斷。計算出這8個方向上的位置的勢場值，并比較大小，選擇最小值為移動機器人的下一運動點，并且將改點保存為路徑點數組中，其中步距以全景視覺的測量范圍為準。

4)機器人執行對比判斷該點是不是機器人的目標點，如果是目標點，則規劃結束。

5)如果經過判斷后，該點不是目標坐標，機器人再判斷，運動過程中的步數有沒有超過規定步數，如果超過，則機器人認為路徑規劃結束，目標為無法到達的點，這時機器人需重新設計路徑規劃策略。

6)機器人計算此步移動的步距與上次移動的步距進行對比，如果小于設定的極小值閾值m1即若||Δpi+1-Δpi||5則計算Δp(i+5)-Δpi有沒有超過設定的閾值m2。如果超過閾值，則判定機器人陷入極小值狀態，需要機器人受罰因子的調節執行調轉車向，逃離極小值操作，并將count=0。

4 仿真實驗

本文使用MATLAB工具進行仿真實驗，路徑規劃結果圖見圖3所示:

(a)(b) (c)

圖3實驗結果圖

圖(a)是用改進后的模型進行路徑規劃的結果圖，從圖可以看出該改進后的模型可以從起始點規劃一條完整的到達目的的路徑。圖(b)中顯示的使用傳統模型進行路徑規劃時在環境中遇見局部極值的情形，移動機器人受到的引力與斥力為0進入局部極小值處，陷入困境，不能繼續規劃路徑。圖3(c)顯示的使用改進后的模型進行規劃能夠順利的逃逸局部極值點。成功到達目的地，完成路徑規劃。

通過實驗分析得出改進后的模型能夠有效的避免傳統人工勢場模型的局部極值缺陷。但是該模型仍然有不足的地方，就是當移動機器人進入局部極值處，采用新模型的逃逸策略，導致機器人大角度轉向，規劃出的路徑抖動較為嚴重，不夠圓滑。這有待于進一步改進。

5 結論

罰函數法在解決優化函數模型的局部約束問題有很好的效果，本文針對傳統人工勢場模型應用在移動機器人路徑規劃中的局部極值情形，采用罰函數法要將傳統人工勢場轉換成優化函數模型。當機器人陷入局部極值點的時，選用懲罰因子，讓機器人只受障礙物斥力影響，調轉車向逃逸局部極值點。最后通過仿真實驗，驗證該方法。對實驗結果分析得知，該方法一定的實用性，對移動機器人的路徑規劃方法研究有一定的參考價值。該方法也有不足之處，采用罰因子使得機器人轉向角度過大，路徑不夠圓滑，且路徑出現抖動現象，因此后續的研究中要解決如何消除路徑的抖動問題，使得規劃的路徑盡量圓滑。

參考文獻:

[1] 王麗.移動機器人路徑規劃方法研究[D].西安: 西北工業大學，2007.

[2] 肖本賢.逃逸人工勢場法局部極小值策略的研究[J].系統仿真學報，2007，19(19):4495-4498.

[3] 雷開友.粒子群算法及其應用研究[D].重慶:西南大學，2006.

[4] Khatib O. Real time obstacle avoidance for manipulators and mobile robots[J].Int.JRobotics，1986，5(1):90-98.

[5] Dozier G， Homaifar A Bryson S. Artificial potential field based robot navigation，dynamic constrained optimization and simple genetic hill-climbing[C].Proceeding of 1998 IEEE World Congress on Computational Intelligence，The 1998 IEEE International Conference on Evolutionary Computation，1998:189-194.

[6] 熊博.基于模糊神經網絡的移動機器人路徑規劃技術研究[D].南京:南京理工大學，2006.