基于改進人工勢場法的服務(wù)機器人路徑規(guī)劃

楊　娜，李漢舟，郭　靜，李瑞峰

（中國航天科技集團第十六研究所，西安710100）

基于改進人工勢場法的服務(wù)機器人路徑規(guī)劃

楊娜，李漢舟，郭靜，李瑞峰

（中國航天科技集團第十六研究所，西安710100）

人工勢場法是服務(wù)機器人路徑規(guī)劃算法中一種簡單有效的方法。針對傳統(tǒng)人工勢場法存在的目標不可達問題，通過在原來的斥力函數(shù)中加入一個調(diào)節(jié)因子的方法解決，同時采用遍歷搜索法解決局部極小值問題，并引入安全距離以及改進調(diào)節(jié)因子以提高機器人路徑規(guī)劃過程中的安全性能。最后，利用Matlab軟件將改進后的人工勢場法應(yīng)用于服務(wù)機器人路徑規(guī)劃并進行了仿真實驗。仿真結(jié)果表明，基于改進人工勢場法的服務(wù)機器人路徑規(guī)劃有效地解決了機器人不能到達目標點的問題。

服務(wù)機器人；路徑規(guī)劃；人工勢場法；遍歷

0 引言

對服務(wù)機器人進行路徑規(guī)劃的目的就是為了在機器人導航過程中，通過相應(yīng)的算法，并遵照一定的準則引導機器人避開行駛路徑中可能遇到的障礙物，順利到達目標點位置，最終完成指定任務(wù)。而服務(wù)機器人所需要遵循的準則一般是路程最短、時間最少或者機器人所消耗的能源最小等［1］。根據(jù)所得到環(huán)境信息的不同，服務(wù)機器人路徑規(guī)劃算法可以分為兩類。其中，最先出現(xiàn)的路徑規(guī)劃算法被稱為全局路徑規(guī)劃，這類算法是針對環(huán)境已知情況的，此時機器人運動空間中的障礙物信息是完全已知的。最基本的全局路徑規(guī)劃算法有結(jié)構(gòu)空間法［2］、可視圖法［2］、單元分解法［3］以及遺傳算法［4］等，之后學者們又對其進行了更深入的研究，改進后的遺傳算法［5］、神經(jīng)網(wǎng)絡(luò)［6］、蟻群算法［7］等也逐漸被用于機器人全局路徑規(guī)劃算法中。然而，只研究全局路徑規(guī)劃算法是不切實際的，因為服務(wù)機器人的工作環(huán)境通常是動態(tài)的，機器人可能需要在人群中穿梭或者繞過突然出現(xiàn)的障礙物，這時僅依靠全局路徑規(guī)劃算法就可能無法成功引導機器人無碰撞地到達目標點。因此，研究者們提出另一類路徑規(guī)劃算法——局部路徑規(guī)劃算法。這類算法需要機器人實時地探測周圍環(huán)境，通過傳感器反饋回來的信息進行路徑規(guī)劃。比較常用的局部路徑規(guī)劃方法有人工勢場法［7］、向量場矩陣法［8］等。同時學者們一直致力于研究更加高效以及可靠的局部路徑規(guī)劃算法，改進后的人工勢場法［9］、遺傳算法［10］、粒子群優(yōu)化算法［11］等均被用于局部路徑規(guī)劃中。未來服務(wù)機器人的工作環(huán)境將會更加復雜且變化迅速，因此研究者們越來越重視局部路徑規(guī)劃算法的研究［12］。

路徑規(guī)劃是服務(wù)機器人自主導航的重要環(huán)節(jié)，研究高效率、適應(yīng)性強、安全性高的路徑規(guī)劃算法是確保機器人完成安全高效導航任務(wù)的關(guān)鍵。人工勢場法相對于神經(jīng)網(wǎng)絡(luò)、遺傳算法等算法具有規(guī)劃效果安全可靠、計算量小的優(yōu)點，一直以來都受到廣泛關(guān)注，但該算法仍存在機器人在運行過程中遇到某些特殊情況而出現(xiàn)的不能到達目標點的問題。本文通過引入安全距離以提高機器人的安全性能，改進斥力場函數(shù)以解決目標不可達問題，并通過遍歷搜索法來解決局部極小值問題。在此基礎(chǔ)上，又對傳統(tǒng)的斥力函數(shù)調(diào)節(jié)因子進行了改進，進一步提高了路徑規(guī)劃的安全性能。最后，利用Matlab軟件驗證了論文改進方法的有效性。

1 傳統(tǒng)的人工勢場法

1.1傳統(tǒng)人工勢場法模型

傳統(tǒng)的人工勢場法是一種典型的梯度勢場法，假設(shè)機器人在運動空間中具有一定的抽象勢能，這種抽象勢能的負梯度方向指向機器人所受抽象力的方向，而這種抽象力就可以引導機器人繞過影響范圍內(nèi)的障礙物，朝目標前進并最終到達目標點。該方法的具體實現(xiàn)過程是，首先在機器人的運動空間中創(chuàng)建一個虛擬勢場，機器人在該勢場的勢能由引力勢能和斥力勢能兩部分組成，其中引力勢能由目標提供，斥力勢能由障礙物提供。之后分別對兩部分勢能求負梯度得到引力與斥力，引力指向目標方向，斥力指向遠離障礙物方向。最終機器人所受到的抽象力由引力部分和斥力部分的疊加得到，機器人將沿著合成的抽象力方向運動，繞開障礙物，向目標點運動。在勢場中機器人的受力分析如圖1所示。

圖1　傳統(tǒng)人工勢場法模型Fig.1 The model of traditional artificial potential field method

假設(shè)機器人的二維工作空間為W=［x y］T，勢場的構(gòu)造是應(yīng)用引力與斥力共同對機器人產(chǎn)生作用為:

其中，Ua（W）為引力勢能，Uo（W）為斥力勢能。故此，勢場中機器人的合力表示為:

其中，引力Fa=-grad［Ua（W）］，斥力Fo= -grad［Uo（W）］。

1.2機器人引力與斥力計算

目標對機器人的引力勢能函數(shù)為:

其中，α為引力增益系數(shù)，W和Wa分別為當前機器人與目標點在二維空間中的坐標，ρa=為機器人與目標之間的相對距離，則相應(yīng)的引力可轉(zhuǎn)化為:

障礙物的斥力勢能函數(shù)定義為:

其中，β為斥力增益系數(shù)，ρ0是障礙物的影響距離，ρ為機器人與障礙物的最短距離。則相應(yīng)的斥力為:

傳統(tǒng)的人工勢場法通過對已知障礙物與目標點信息進行建模，同時在機器人運行過程中對障礙物進行實時檢測，得到上述公式中的各項參數(shù)信息，并最終求得機器人每一時刻所受到抽象力的方向，引導機器人避開障礙物，安全到達目標點。

1.3傳統(tǒng)方法不足分析

本文在對傳統(tǒng)的人工勢場法進行分析后，發(fā)現(xiàn)該算法在某些方面存在不足，需要對其進行后續(xù)的分析以及改進。當目標點在某一個或多個障礙物的影響范圍內(nèi)時，機器人向目標逼近，障礙物對機器人產(chǎn)生的斥力勢能將快速增加，從而使得機器人所受斥力快速增大，同時目標點對機器人產(chǎn)生的引力勢能快速減小，則斥力有可能會大于引力，導致機器人只能在目標點附近移動，這就造成了目標不可達問題。而機器人在運行過程中，還可能會遇到另外一種情況，即陷入局部極小值點。這種情況是當機器人與目標之間出現(xiàn)一個或多個障礙物時，障礙物對機器人產(chǎn)生的斥力與目標所產(chǎn)生的引力大小相等且方向相反，這就使得機器人所受到的勢場合力F=Fa+Fo=0，此時機器人就會停止前進，從而陷入局部極小值點，導致路徑規(guī)劃失敗。

2 改進的人工勢場法

2.1改進思路

為了找出這種問題的解決方案，對傳統(tǒng)的人工勢場法進行分析發(fā)現(xiàn)，傳統(tǒng)的人工勢場法是用虛擬力控制機器人運動的，而這種方法就會導致上述情況發(fā)生。而當我們將每個路徑點的勢場強度之和作為判據(jù)，通過遍歷搜索算法比較路徑點勢場大小，選擇勢場和最小點為下一路徑點時，這樣機器人總是朝著勢能下降的方向運動，最終到達勢能為0的目標點位置。同時為了解決傳統(tǒng)算法的目標不可達問題，本文對傳統(tǒng)人工勢場法的斥力勢場函數(shù)進行改進，將機器人與目標之間的距離引入斥力場函數(shù)中，并通過引入安全距離將障礙物影響距離進行分段，在障礙物影響距離內(nèi)加入安全距離，確保機器人在障礙物安全距離內(nèi)所產(chǎn)生的斥力勢場比引入之前所產(chǎn)生勢場值更大，這樣可以提高機器人原理障礙物的趨勢，從而提高機器人路徑規(guī)劃過程中的安全性。

改進后的機器人斥力勢場函數(shù)如式（7）所示:

式中，β為初始算法中的斥力增益系數(shù)，ρ0為傳統(tǒng)算法中的障礙物影響距離，而ρ1即為論文中引入的安全距離，δ為安全距離所對應(yīng)的斥力增益系數(shù)。分別對引入安全距離前后的斥力勢能函數(shù)進行數(shù)據(jù)分析，得到障礙物附近斥力勢能示意圖如圖2所示。圖2中，橫坐標為機器人運行空間的x軸，目標點在（10，10）處，障礙物坐標分別為（3，3）、（5，7）、（8，7），縱軸為斥力勢能值。從圖2中可以看出，改進后的斥力勢場值在障礙物附近升高的趨勢更快，這是因為引入安全距離后，當機器人與障礙物之間的距離小于安全距離時，改進方法所產(chǎn)生的斥力勢能值比改進前斥力勢場值大，這也就提高了機器人的安全性能。

而圖3、圖4又分別給出了改進前后算法在運行空間中所產(chǎn)生的總勢能平面圖與立體圖。在機器人運行空間中，設(shè)定目標點坐標為（10，10），障礙物坐標分別為（3，3）、（5，7）、（8，7）。從圖3和圖4中可以看出，兩種方法目標點的勢能為0，距離目標物越遠，勢能越大，而障礙物附近的勢能值有突變。當障礙物離目標物越近時，所產(chǎn)生的勢場值也就越小，這也就避免了當障礙物距離目標太近時目標點勢能不為0的情況。而同樣還可以看出，改進后障礙物附近所產(chǎn)生的勢能升高的趨勢更加明顯，在安全距離影響范圍內(nèi)機器人所產(chǎn)生的斥力勢能也更大。

圖2　改進前后斥力勢場強度側(cè)面示意圖Fig.2 Lateral schematic diagram of the intensity of the repulsive potential field before and after improvement

圖3　改進前后總勢場強度平面示意圖Fig.3 Complanate schematic diagram of the intensity of the total potential field before and after improvement

圖4　改進前后總勢場強度立體示意圖Fig.4 Stereoscopic schematic diagram of the intensity of the total potential field before and after improvement

2.2對斥力勢場函數(shù)調(diào)節(jié)因子的改進

在先前的研究基礎(chǔ)上，本文又將改進方法中的調(diào)節(jié)因子改為（eρ2a-1），則改進后的斥力場函數(shù)為:

為了驗證論文提出方法的優(yōu)越性，針對傳統(tǒng)改進方法中不同n值的調(diào)節(jié)因子與論文改進后的調(diào)節(jié)因子進行了數(shù)據(jù)分析對比，得出的數(shù)據(jù)規(guī)律基本相同。圖5（a）、圖5（b）分別給出了當n=4與n=12時本文方法與傳統(tǒng)改進法中調(diào)節(jié)因子系數(shù)項的曲線示意圖。

圖5　改進方法調(diào)節(jié)因子對比圖Fig.5 Comparison of adjustment factor of improved method

從圖5中可以看出，本文提出的調(diào)節(jié)因子較傳統(tǒng)改進方法中調(diào)節(jié)因子收斂速度快。而在基于人工勢場法的路徑規(guī)劃算法中，機器人所受到的斥力勢場與調(diào)節(jié)因子值成正比。因此，從圖中曲線走勢可以得出:當機器人與目標物距離較遠時，本文提出方法得到的斥力勢場值要遠遠高于傳統(tǒng)改進方法的斥力勢場值，也就是說遠離目標物時機器人所受到的斥力更大，也就提高了機器人路徑規(guī)劃的安全性；而當機器人逐漸靠近目標物時，本文方法的斥力勢場函數(shù)值迅速下降，逐漸小于傳統(tǒng)改進法的值并趨于0，這在解決了傳統(tǒng)方法中目標不可達問題的同時，提高了機器人向目標方向運動的趨勢。因此，可以得出結(jié)論，本文改進方法相比傳統(tǒng)改進方法具備一定的優(yōu)越性。

3 仿真分析

3.1算法思路

改進算法的實現(xiàn)思路為:在建立了勢場模型的前提下，給定機器人每一步所走的步長，設(shè)定初始化勢場值。以機器人為圓心，步長為半徑的圓即為機器人下一路徑點范圍。從起點開始，通過在每一個圓上取均勻的若干個點，分別計算這若干個點的勢能值，遍歷整個路徑點范圍得到唯一一個勢能值最小點即為機器人下一路徑點。該路徑規(guī)劃算法具體的程序流程如下:

1）建立勢場模型。確定引力場和斥力場的增益系數(shù)α和β、障礙物影響距離ρ0、安全距離ρ1、極限步數(shù)s（防止程序無限循環(huán)）以及移動步長R（假設(shè)機器人是勻速前進的）。設(shè)定初始化勢能值U以及初始化的角度θ，同時確定機器人起始位置x0、y0。

2）判斷機器人是否到達目標點，如果到達目標點則終止規(guī)劃過程。

3）在第k時刻時，根據(jù)機器人當前位置（xk，yk）以及步長計算若干個點與機器人連線與x軸的夾角，從起點開始，根據(jù)已經(jīng)建立的勢場模型以及初始化后的參數(shù)計算機器人在若干個點的勢能值，與初始化勢場值進行比較，若小于初始值則取代，并將該點的夾角值賦給θ，之后按照同樣的步驟遍歷完整個路徑點范圍，最終得到的U以及θ即為機器人下一路徑點的勢場值和運行角度θk。

4）通過式（9）計算第k+1時刻的位置。

5）機器人移動至下一路徑點，同時置k=k+1為當前點。

6）判斷機器人當前運行的步數(shù)是否達到極限步數(shù)，如果達到則表明無法到達目標點，可能需要重新調(diào)整模型參數(shù)，若沒有達到則返回第二步繼續(xù)執(zhí)行。

3.2仿真結(jié)果以及分析

按照以上程序流程，通過Matlab平臺分別對改進前的人工勢場法以及改進后的人工勢場法進行了仿真。程序中設(shè)定引力場和斥力場的增益系數(shù)α和β均為10，障礙物影響距離ρ0為1.5、ρ1為0.5，極限步數(shù)s為500以及移動步長R為0.05。并設(shè)定初始化勢場值U為10000以及初始化的角度θ為0，同時確定機器人起始位置（x0，y0）為（0，0）。

同時在機器人運動空間中設(shè)置了3個障礙物，分別單個或2個障礙物距離設(shè)置在機器人運行路徑前方或目標點附近，仿真結(jié)果如圖6、圖7和圖8所示。其中，圖6（a）、圖7（a）和圖8（a）為改進前的人工勢場法仿真結(jié)果，圖6（b）、圖7（b）和圖8（b）為改進后的人工勢場法仿真結(jié)果，方塊為機器人初始位置，圓圈為障礙物位置，倒三角為目標點位置，空間中的曲線即為程序運行完之后所得機器人在運動空間中的運行軌跡。

圖6　對單個障礙物局部最小值問題的改進結(jié)果Fig.6 The results of the improvement of the local minimum value problem for a single obstacle

圖7　對多個障礙物局部最小值問題的改進結(jié)果Fig.7 The results of the improvement of the local minimum value problem for multiple obstacles

圖8　對目標不可達問題的改進結(jié)果Fig.8 The results of the improvement of the target's non reachable problem

從仿真結(jié)果可以看出，改進前后方法都可以控制機器人開始都朝著目標點運行。然而傳統(tǒng)的方法在遇到單個或多個障礙物與目標所產(chǎn)生的合力為0時會在障礙物附近徘徊，而改進后的方法在機器人遇到同種情況時可以控制機器人成功地繞過了障礙物，繼續(xù)朝目標點前進，由此也證明了改進后的路徑規(guī)劃算法的有效性。因此得出結(jié)論，將機器人下一路徑點范圍的勢場值作為判據(jù)并采用遍歷搜索法進行路徑規(guī)劃的算法很好地解決了局部極小值問題，能夠引導機器人到達目標點。采用傳統(tǒng)人工勢場法時，機器人并不能到達目標點，而是在目標點附近徘徊，而采用改進方法卻可以順利到達目標點，由此也證明了改進后的路徑規(guī)劃算法的有效性。

4 結(jié)論

隨著計算機技術(shù)、傳感技術(shù)等的飛速發(fā)展，未來服務(wù)機器人將成為一個巨大的產(chǎn)業(yè)，而路徑規(guī)劃算法作為服務(wù)機器人研究領(lǐng)域的一項關(guān)鍵技術(shù)，受到了越來越多的重視。本文對基于人工勢場法的路徑規(guī)劃算法進行了研究，該方法具有計算量小、可靠性高等優(yōu)點，然而利用人工勢場法進行路徑規(guī)劃時，可能會存在某些情況下機器人無法到達目標點的問題。本文采用遍歷搜索算法解決了局部極小值的問題，并引入安全距離提高了機器人路徑規(guī)劃的安全性能，同時對斥力場函數(shù)的調(diào)節(jié)因子進行了改進，從而解決目標不可達問題。仿真分析結(jié)果證明了論文算法的有效性。然而，未來服務(wù)機器人的工作環(huán)境將會越來越復雜，需要應(yīng)對多變的動態(tài)環(huán)境，這就需要我們對路徑規(guī)劃算法不停地完善以適應(yīng)未來服務(wù)機器人對路徑規(guī)劃技術(shù)的更高要求。

［1］Raja P，Pugazhenthi S.Optimal path planning of mobile robots:a review［J］.International Journal of Physical Sciences，2012，7（9）:1314-1320.

［2］Lozano-Pérez T，Wesley M A.An algorithm for planning collision-free paths among polyhedral obstacles［J］.Communications of the ACM，1979，22（10）:560-570.

［3］Lozano-Pérez T.Spatial planning:a configuration space approach［J］.IEEE Transactions on Computers，1983，32（3）:108-120.

［4］Khatib O.Real time obstacle avoidance for manipulators and mobile robots［J］.International Journal of Robotics Research，1986，5（1）:90-98.

［5］Hu J，ZhuQB.Multi-objectivemobilerobotpath planning based on improved genetic algorithm［C］.International Conference on Intelligent Computation Technology and Automation，2010:752-756.

［6］Jung I K，Hong K B，Hong S K，et al.Path planning of mobile robot using neural network［C］.IEEE International Symposium on Industrial Electronics，Bled，Slovenia，1999，3:979-983.

［7］Buniyamin N，Sariff N，Wan Ngah W A J，et al.Robot global path planning overview and a variation of ant colonysystem algorithm［J］.International Journal of Mathematics and Computers in Simulation，2011，5（1）:9-16.

［8］Latombe J C.Robot motion planning［J］.Academic Publisher，Boston，1991.

［9］Vadakkepat P，Tan K C，Liang W M.Evolutionary artificial potential fields and their application in real time robot path planning［C］.Proceedings of the Congress on Evolutionary Computation，2000:256-263.

［10］Yun S C，Parasuraman S，Ganapathy V.Dynamic path planning algorithm in mobile robot navigation［C］.IEEE Symposium on Industrial Electronics and Applications， 2011:363-369.

［11］Zhang Q R，Gu G C.Path planning based on improved binary particle swarm optimization algorithm［C］.Proceedings of the IEEE International Conference on Robotics，Automation and Mechatronics，2008:462-466.

［12］Savkin A V，Wang C.Seeking a path through the crowd: robot navigation in unknown dynamic environments with moving obstacles based on an integrated environment representation［J］.RoboticsandAutonomousSystems，2014，62（10）:1568-1580.

Path Planning of Service Robot Based on Modified Artificial Potential Field Method

YANG Na，LI Han-zhou，GUO Jing，LI Rui-Feng
（The 16thInstitute，China Aerospace Science and Technology Corporation，Xi'an 710100）

The artificial potential field method is a simple and effective method for the path planning algorithm of the service robot.A regulation factor was joined in the original repulsion function to resolve the presence of target accessibility issues of the traditional artificial potential field method，and the traversal search method was adopted to solve the local minimum value problem，and then the safe distance and improvement of the adjustment factor were introduced to improve the safety performance in robot path planning process.The improved artificial potential field method is applied to the path planning of the service robot，and the simulation experiment is carried out by using the Matlab software.The simulation results show that the path planning of the service robot based on the improved artificial potential field method can effectively solve the local minimum problem.

service robot；path planning；artificial potential field algorithm；ergodic

TP24

A

1674-5558（2016）01-01227

10.3969/j.issn.1674-5558.2016.05.008

楊娜，女，碩士，研究方向為服務(wù)機器人導航技術(shù)。

2016-01-06