一種基于改進人工勢場法的路徑規劃技術

摘 要：針對傳統人工勢場法在路徑規劃中出現的局部最小值問題和振蕩問題，提出了引入虛擬局部目標，修改斥力場函數的解決方案。為增強算法的實用性，提出了一種考慮障礙物體積的方案。最后文章還使用了另一種方法來優化改進的APF算法規劃出的路徑。在該方法中，最優路徑由盡可能少的直線組成，節省了機器人運動的時間。仿真實驗結果表明文章所提算法能夠較好的實現移動機器人的路徑規劃任務。

關鍵詞：移動機器人；路徑規劃；人工勢場法

1 人工勢場法概述

人工勢場法（APF）首先被Khatib提出[1]。APF可以快速地計算出一條高質量的路徑并響應動態環境。然而，該算法被廣泛證明存在不可避免的缺點，該算法容易將機器人引入局部最小值和在障礙物前振蕩。有文獻提出了一種混合算法，該算法整合了環境信息的先驗知識以便于執行更加有效和安全的任務分配[2]。結果表明該方法能保證機器人即使在未知的動態環境中操作，也不會陷入死鎖。盡管該方法有良好的特性，但該文獻所描述導航系統的典型缺點是系統依賴先驗知識和導航策略。另一種改進型APF算法也被提出，該算法使用粒子群優化快速全局搜索和確定最佳路徑規劃[3]。為了處理傳統APF的局部最小值問題，還有研究者提出了一種由機器回歸和勢場填充的方法[4]。類似的方法也在其它文獻中提到，在計算最終的結果前，把一個對象放入勢場中，建立其到最近障礙物之間的連接來優化路徑規劃[5]。其他改進勢場法的方法也被研究過，比如有研究者將機器人和目標位置之間的相對距離引入斥力函數，然后修改斥力方向確保全局最小值在目標位置[6]。

然而上述所有的APF和它的改進算法仍然會遇到一些缺點，比如在高時間復雜度和高維度情況下，有些算法能處理實時路徑規劃，有些算法無法完全解決局部最小值和振蕩問題，使他們在實踐中效率低下。因此，上述算法下的路徑不是最優路徑，僅僅是可行路徑。在文章中展示了一種有效的改進APF算法，該方法能在已知環境中獲得一個沒有局部最小值問題和振蕩問題的全局最優或次優路徑。

2 傳統人工勢場法介紹

APF的基本思路是假設機器人是抽象的人造勢場范圍中一個移動的質點。環境中的人工勢場由目標產生的引力勢場和障礙物產生的斥力勢場組成。引力勢場由目標產生，方向指向目標點，斥力場由不同障礙物共同產生，方向為遠離障礙物點。因此，勢場函數（1）就是機器人的APF算法，該函數的結果為引力勢場和斥力勢場相加。機器人沿著APF的方向控制其運動到目標點。在APF算法下，機器人能通過搜索沿勢場函數方向下降的路線找到一條無碰撞的路徑。

機器人的坐標是q=（x，y）T，因此APF定義為：

盡管傳統的APF算法能規劃出一條光滑的路徑，但其仍存在一些問題。在機器人向目標位置移動的過程中，當引力和斥力相等或幾乎相等，且互為反向時，機器人勢場力為0，這將會導致陷入局部最小值和在障礙物前振蕩。當目標的位置與障礙物十分接近時，機器人可能會出現目標不可達。

3 改進的人工勢場法

機器人與目標之間引力勢場的值取決于？籽goal（q）的距離，如式（3）。當？籽（q）非常大時，引力同樣也很大，容易導致機器人移動時離障礙物太近。為避免碰撞，當機器人與障礙物的距離小于一定值時，讓斥力顯著增加，斥力函數修改如式（10）。

其中，系數d是斥力函數的影響因子，為指數形式，在下一節中給出。

對于上一節提到的局部最小值問題，通過引入虛擬局部目標來指導機器人逃離局部最小值，該方法也能解決振蕩問題。此外，利用函數（11）和（12）來解決機器人目標不可達的問題，我們稱其為斥力抵消法。一旦機器人探測到目標和障礙物之間的距離小于dob，目標和機器人的距離小于dgr，機器人就僅沿著引力勢場前進，不考慮引力勢場和斥力勢場的疊加。

U（q）=Uatt（q）+Urep（q） ，otherwisedUatt（q） ，？籽（q）？燮dob and ？籽goal？燮dgr （11）

F（q）=Fatt（q）+Frep（q） ，otherwiseFatt（q） ，||qg-qc||？燮dob and ||q-qg||？燮dgr （12）

前面提到的APF算法和改進的APF算法都沒有明確定義多邊形障礙物的斥力場。在傳統APF的描述中，將人工勢場源看做質點，即將目標、障礙物和移動機器人都看做質點。若障礙物的體積過大，有可能導致APF算法規劃出的路徑穿過障礙物內部，這樣機器人在沿著規劃好的路徑運動過程中會與障礙物發生碰撞。如圖1，虛線圓是障礙物的實際邊界，按照傳統的勢場法，機器人沿著路徑行走會穿過障礙物，這顯然是不合理的。因此，為增強APF算法的實用性，文章針對此問題提出了改進措施。

在一般的家庭環境中，障礙物形狀多樣，給路徑規劃帶來一定難度。文章提出了將障礙物邊界離散化的方法，即根據障礙物的實際形狀，在其邊界上離散的取若干個點，使用若干個點的勢場代替原先將障礙物看做質點時的勢場，如圖2所示。上述改進有效的解決了穿過障礙物的問題。然而在某些情況下，改進的勢場法規劃出的路徑仍然會出現穿過障礙物的情況，此時邊界上的點會對障礙物產生斥力，方向指向障礙物中心，這會導致機器人向著障礙物行走。如圖3所示，A點是機器人的下一步路徑點，由于目標對障礙物的引力太大導致A點在障礙物內部，此時由于障礙物邊界點對其存在斥力，導致機器人進一步進入障礙物，即B點。這是因為算法中步長參數太大，導致所規劃的路徑一步就跨入障礙物內部，因此障礙物邊界點間距的設定應小于機器人的步長。上述方法雖然增加了計算量，但能有效解決某些情況下與障礙物發生碰撞的問題。

盡管上述改進的APF能成功的解決局部最小值問題和振蕩問題，但仍不能規劃出一條在實際應用中最優或次優的路徑。APF算法為路徑規劃設置了步長，即APF算法會根據給定的步長計算下一個路徑點，直到下一個路徑點為目標點。在這種情況下，APF算法所規劃出來的路徑會有很多不必要的彎曲，這會使得機器人頻繁調整方向導致時間的浪費和能耗的增加。文章使用了另一種方法來優化改進的APF算法規劃出的路徑。在該方法中，最優路徑由盡可能少的直線組成，節省了機器人運動的時間。

改進的方法如下：從機器人的當前位置到目標位置，起始點連接了其后的路徑點成為一條直線。如果這條直線沒有穿過任何障礙物，起始點將重新連接下一個路徑點成為新的直線，直到這條線穿過障礙物，或這條線離障礙物的距離小于D0。將這條線保存為機器人的局部最優路徑。然后系統將上一條直線的終點作為下一條直線的起點，使用同樣的方法生成新的直線。

使用圖4來舉例說明改進的APF算法。假設Ti∈{T1，T2，T3，...，Ti，Ti+1，...，Tn}是一系列由人工勢場法規劃出的路徑點，機器人沿著這些路徑點移動就能無碰撞的到達目標點。首先，初始點T1作為開始點連接下一個點T2，成為直線L1-2。然后判斷L1-2是否已經越過障礙物，或其與障礙物的最短距離D是否小于D0。如果L1-2沒有越過障礙物，或D大于D0，則重新連接T1和T3成為直線L1-3。重復前面的步驟，直到L1-i穿過障礙物，那么可行的局部最優路徑是L1-i，即Ti是該直線的終點。因為Ti+1不是目標點，所以下一個初始點是Ti，類似的連接Ti+1。因此在這個例子中，最優路徑是L1-i和Li-n。換句話說，機器人沿著L1-i和Li-n行走將最大化節省時間，并且距離最短。

綜合前面幾項改進，完整的改進APF算法如下：

（1）計算機器人當前坐標與各障礙物點之間的距離；（2）計算引力：根據式（4）計算引力；（3）計算斥力：根據式（7），若當前坐標與障礙物距離？籽（q）小于？籽0，計算斥力。否則忽略該障礙物斥力，即將斥力置為0。根據式（12），若目標和障礙物的距離小于dob，目標和機器人的距離小于dgr，將斥力置為0；（4）計算機器人所受的合力；（5）根據設定的步長，使用合力計算下一步坐標點；（6）將坐標保存為Ti；（7）重復前兩步，直到到達目標；（8）依次搜索Ti；（9）連接初始點Ti到Tj，作為直線Li-j；（10）如果Li-j不符合條件，則連接Ti和Tj+1；（11）否則保存Li-j，然后將點Tj作為下一條直線的初始點；（12）返回第六步直到找到最后的目標點；（13）獲取最優路徑，機器人按照該路徑移動。

4 結束語

仿真實驗表明：文章所提出的改進APF算法克服了傳統APF算法局部最小值和在障礙物前振蕩的缺點，在算法中考慮障礙物的體積使其實用性更強，最后對路徑進行了優化使得算法規劃出的路徑在路程長度和機器人轉向時間上都有縮短。綜上文章所提出的改進APF算法能夠較好的實現移動機器人的路徑規劃任務。

參考文獻

[1]Khatib O. Real-time Obstacle Avoidance for Manipu-lators and Mobile Robots[J].International Journal of Robotics Research，1985，1（5）：500-505.

[2]Sgorbissa A，Zaccaria R. Planning and Obstacle Avoidance in Mobile Robotics[J].Robotics Autonomous Systems，2012，60（4）： 628-638.

[4]Zhang H，Yang L，Gao Z， et al. The Dynamic Path Planning Research for Mobile Robot Based on Artificial Potential Field[C]//Consumer Electronics， Communications and Networks （cecnet），2011 International Conference on， [S.l.]： [s.n.]，2011：2736-2739.

[4]Qi N，Ma B，Liu X， et al. A Modified Artificial Potential Field Algorithm for Mobile Robot Path Planning[J].World Congress on Intelligent Control Automation， 2008：2603-2607.

[5]Automation SOMEA，University TP，Tianjin， et al. An Optimized Method for Path Planning Based on Artificial Potential Field[C]//Null， [S.l.]： [s.n.]，2006：35-39.

[6]He B，Liu G，Gao J， et al. A Route Planning Method Based on Improved Artificial Potential Field Algorithm[C]//Communication Software and Networks （iccsn），2011 Ieee 3rd International Conference on， [S.l.]： [s.n.]，2011：550-554.