改进人工势场法的路径规划算法研究

刘砚菊，代 涛，宋建辉

改进人工势场法的路径规划算法研究

刘砚菊，代 涛，宋建辉

(沈阳理工大学 自动化与电气工程学院，沈阳 110159)

针对基于传统人工势场法的机器人路径规划存在局部极小点的问题，提出了一种修改斥力方向和自主建立虚拟目标牵引点相结合的路径规划算法。该算法在修改斥力方向算法中设置了一个临界值，在机器人行走的过程中，若机器人与障碍物的距离大于临界值，机器人路径规划就采用修改斥力方向的算法，当机器人与障碍物的距离小于临界值时，机器人路径规划算法就从修改斥力方向算法转入自主建立虚拟目标牵引点算法。改进后的算法很好地解决了传统人工势场法的局部极小点问题，仿真结果证明了改进后算法的有效性。

人工势场法；机器人路径规划；目标不可达；局部极小值

随着科学技术水平和人们生活水平的不断提高，机器人在人们生活中的应用[1]越来越广泛，人们对机器人应用的研究也越来越深入，其中机器人应用中一个比较重要的课题就是机器人路径规划算法的研究。路径规划就是在具有障碍物的环境中，按照一定的评价标准来寻找一条从起始状态到目标状态的无碰撞路径[2]。总的来说，机器人路径规划方法可以分为两种，它们分别是全局路径规划[3]方法和局部路径规划[4]方法，全局路径规划方法主要包括栅格法、拓扑法、可视图法等方法[5]，典型的路径规划方法主要有人工势场法[6]、沿墙走算法、模糊逻辑控制算法[7]、遗传算法[8]等。其中沿墙走算法存在路径规划速度慢的问题，模糊逻辑控制算法存在很难构造出比较全面的规则库的问题，若输入量和规则不匹配，它就无所适从，不具备适应能力，遗传算法存在计算资源消耗大、收敛速度慢的问题。与上述算法相比，人工势场法具有计算简单、实现容易、实时性好、反应速度快、规划轨迹平滑等优点，因此得到了广泛的应用。

本文在修改斥力函数的基础上，针对传统人工势场法的局部极小点问题，提出了一种修改斥力方向和自主建立虚拟目标牵引点相结合的算法。该算法结合了修改斥力方向和自主建立虚拟目标牵引点两种算法的优点，解决了传统人工势场法局部极小点问题。

1 人工势场法原理

人工势场法是由Khatib提出来的一种虚拟力法[9]，它是根据电荷间相互作用规律的理论演变而来的。人工势场法的实质就是对机器人的运行环境人为建立一个抽象的势场，机器人在这个人工势场中将会受到来自障碍物的斥力场和来自目标点的引力场的作用，在引力场和斥力场的作用下，机器人将受到引力和斥力的作用，在斥力和引力的共同作用下，机器人将会向目标点移动并最终到达目标点。传统人工势场法的定义如下:

若机器人的当前位置坐标向量为X=(x,y)，目标点的坐标向量为Xg=(xg,yg)，则定义引力势场函数如公式(1):

(1)

式中:k为大于零的引力场的系数常量；机器人到目标点的距离为ρ(X,Xg)=‖X-Xg‖，引力为引力势场函数的负梯度，则定义引力如公式(2):

F1(X)=-▽(U1(X))=k(Xg-X)

(2)

(3)

式中:m为大于零的斥力场系数常量；Xo为障碍物的位置坐标向量；机器人到障碍物的距离为ρ(X,Xo)=‖X-Xo‖；ρ0为障碍物的最大影响范围，则定义斥力如公式(4):

F2(X)=-▽(U2(X))

(4)

针对传统人工势场法存在的目标不可达问题，现在一般采用较为普遍的改进斥力函数的方法，在斥力函数中引入机器人和目标点之间的相对距离，其实现如下:

若机器人的当前位置为X=(x,y)，目标点的位置为Xg=(xg,yg)，则定义改进后的斥力势场函数如公式(5):

(5)

(6)

式中，

(7)

(8)

在实际应用中普遍采用它们各自的简化形式，形如公式(9)和公式(10):

(9)

(10)

式中δ(X-Xg)n-1=|(x-xg)n-1|+|(y-yg)n-1|。

2 修改斥力方向和自主建立虚拟目标牵引点的混合算法

2.1 修改斥力方向的方法

图1 改进斥力函数及修改斥力方向受力分析图

图2 修改斥力函数仿真效果图

2.2 自主建立虚拟目标牵引点的方法

自主建立虚拟目标牵引点的方法是在检测到机器人陷入传统人工势场的局部极小点时，通过自主建立虚拟目标牵引点并对原有目标点进行隔离的方法牵引机器人逐步走出局部极小点，其实现主要包括局部极小值点的检测、自主虚拟目标牵引点的建立和对原有目标点的隔离两个部分。

人工势场法局部极小值的检测一般采用一定间隔内机器人所走的距离和阀值进行比较的方法。该方法首先根据机器人移动的步长和障碍物影响范围的大小来设置一个阀值T，然后每隔一定的间隔检测一次这段间隔内机器人所走的距离并和这个阀值T进行比较。若这段间隔内机器人所走的距离小于阀值T，可以认为机器人陷入了局部极小点，反之，则没有陷入局部极小点。

当检测到机器人陷入人工势场法的局部极小点时，在与经过机器人、障碍物的直线相垂直的直线上偏移一小段距离的地方设置一个虚拟目标牵引点，并将机器人的目标点从原有目标点切换到这个虚拟目标牵引点，进而机器人将在这个虚拟目标牵引点的牵引下移动一小段距离。当机器人到达这个虚拟目标牵引点时，将机器人的目标点从虚拟目标牵引点再切换到原有的目标点。如果一个虚拟目标牵引点不能把机器人牵引出局部极小点，可以重复上述步骤继续设置更多的虚拟目标牵引点，直到把机器人牵引出局部极小点为止。

在Matlab平台上对自主建立虚拟目标牵引点的方法进行了仿真，各参数设置如下:引力场系数k为200,斥力场系数m为200,机器人移动步长l为0.1m，障碍物的最大影响范围为2m，阀值T为0.15m，仿真结果如图3所示。通过仿真结果可以看出当机器人进入凹形槽的影响范围且陷入局部极小点时，自主建立虚拟目标牵引点的方法使其顺利地绕开了障碍物并到达了目标点。

2.3 改进算法

事实上，修改斥力方向方法程序的执行效率较传统人工势场法更高，规划出的路径也较平滑，具有很多突出的优点，是一种很高效的算法，但在有凹形槽障碍物的环境中进行路径规划时该方法存在一定的局限性，如图2b所示。为解决传统人工势场法局部极小值的问题，本文在修改斥力函数的基础上，提出了一种修改斥力方向和自主建立虚拟目标牵引点相结合的算法。该算法的原理是在修改斥力方向算法中设置一个避免机器人和障碍物直接相碰撞的临界值T1，用这个临界值T1代替自主建立虚拟目标牵引点方法中的检测机器人是否陷入局部极小点的阈值T，若机器人与障碍物之间的距离始终保持大于临界值T1，机器人采用修改斥力方向的算法规划行走路径；若机器人在行走的过程中遇到机器人与障碍物之间的距离小于临界值T1的时候，机器人路径规划算法就从修改斥力方向的算法切换到自主建立虚拟目标牵引点的算法，采用自主建立虚拟目标牵引点的算法规划机器人前进的路径，其流程图如图4所示。

图3 自主建立虚拟目标牵引点仿真结果图

图4 改进后算法流程图

3 改进算法的仿真实验结果及分析

本文对改进后的算法在Matlab平台上进行了仿真，仿真在全局静态环境下进行，机器人在外界环境中是很小的，可以抽象成一个质点，把障碍物尺寸考虑进来折合成被外接圆包裹的圆形，图5中(0,0)是起始点，目标点为(28,30)，小实线圆表示包围障碍物的外接圆，虚线圆表示障碍物的最大影响范围，长线条表示机器人的前进路径，各仿真参数设置如下:引力场系数k为200；斥力场系数m为300；障碍物的最大影响范围为2m；机器人移动的步长l为0.1m；避免机器人和障碍物直接相碰撞的临界值T1为1.5m，仿真操作界面和仿真结果如图5所示。图5a为Matlab平台上的仿真操作界面，图5b和图5c为改进后算法的仿真结果。

图5 混合修改斥力方向和自主建立虚拟目标牵引点算法的仿真结果图

实验结果分析:图5中起始点为(0,0)，目标点为(28,30)，按照传统人工势场法进行路径规划，在遇到位置为(7,7.5)障碍物时，机器人必将陷入局部极小点而无法到达目标点，但通过图5b和图5c仿真结果可以看出，修改斥力方向的算法使机器人顺利走出了传统人工势场法的局部极小点。在进入凹形槽区域时，检测到机器人和障碍物的距离小于设定的临界值T1，机器人路径规划算法就从修改斥力方向的算法自动切换到自主建立虚拟目标牵引点的算法，在虚拟目标牵引点的作用下，避免了修改斥力方向算法中机器人撞上凹形槽的情况，使机器人顺利地绕过了凹形槽并到达了目标点。本文改进的算法可以把机器人从凹形槽的不同方向牵引出来，如图5b和5c所示，然后进行比较选择一条较好的路径作为机器人的前进路径。通过比较可以发现，图5c的前进路径更加光滑，是一条较好的前进路径。综合上述分析可知，本文对基于人工势场法的路径规划算法的改进方法是可行的。

4 结束语

对传统人工势场法的原理、实现方法进行了分析，并对改进传统人工势场法的修改斥力方向方法和自主建立虚拟目标牵引点方法进行了研究，提出了一种修改斥力方向和自主建立虚拟目标牵引点相混合的算法，该算法很好地解决了传统人工势场法的局部极小值问题，仿真结果证明了改进后算法的有效性。

[1]廖爽,许勇,王善超.智能汽车自动驾驶的控制算法研究[J].计算机测量与控制,2014,22(8):2472-2474.

[2]石为人,黄兴华,周伟.基于改进人工势场法的移动机器人路径规划[J].计算机应用,2010,30(8):2021-2023.

[3]黄静,陈汉伟.移动机器人全局路径规划算法的研究[J].仪表技术与传感器,2014(12):80-83.

[4]黄炳强,曹广益.基于人工势场法的移动机器人路径规划研究[J].计算机工程与应用,2006,42(27):26-28.

[5]Park M G,Jeon J H,Lee M C.Obstacle avoidance for mobile robots using artificial potential field approach with simulated annealing[J].IEEE International Symposium on Industrial Electronics,2001,3(6):1530-1535.

[6]吴正平,唐念,陈永亮,等.基于改进人工势场法的AUV路径规划[J].化工自动化及仪表,2014,41(12):1421-1423.

[7]潘洲,万衡,李嘉琦.基于模糊人工势场法的移动机器人路径规划[J].制造业自动化,2015,37(7):4-8.

[8]曲志坚,张先伟,曹雁锋,等.基于自适应机制的遗传算法研究[J].计算机应用研究,2015,32(11):176-182.

[9]KHATIB O.Real-Time obstacle avoidance for manipulators and mobile robots[J].The International Journal Robotics Research,1986,5(1):90-98.

(责任编辑:马金发)

Research of Path Planning Algorithm Based on Improved Artificial Potential Field

LIU Yanju,DAI Tao,SONG Jianhui

(Shenyang Ligong University,Shenyang 110159,China)

In path planning of the mobile robot,the problem of local minimum points exists based on the traditional artificial potential field method.A path planning algorithm is proposed,which is based on combination of modifying the repulsive force direction and determines the virtual target point.In this algorithm,a critical value is set in the modified repulsion direction algorithm.In the process of the robot moving,when the distance between the robot and the obstacle is larger than the critical value,the path planning of the robot turns to the modified repulsive direction algorithm.When the distance between the robot and the obstacle is less than the critical value,the robot path planning algorithm is transferred from the modified repulsive direction algorithm to the autonomous virtual target traction point algorithm.The improved algorithm solves the problem of local minimum points,and the effectiveness of the improved algorithm is verified by simulation.

artificial potential field;robot path planning;goal non-reachable;local minimum point

2016-05-05

刘砚菊(1965—)，女，教授，博士，研究方向:多传感器信息融合、目标识别、智能检测技术。

1003-1251(2017)01-0061-05

TP391.9

A