应用人工势场算法的智能车路径规划

汪 波，张建勋，侯之旭

(重庆理工大学计算机科学与工程学院，重庆 400054)

基于时间最优或路径最短等准则，在已知或未知环境中规划出一条从起点到终点的无碰撞路径等路径规划问题是移动机器人研究领域的重要课题。Khatib提出了人工势场算法，将机器人的运行空间模拟成抽象势场模型，定义引力和斥力函数模型，共同引导机器人向终点运动。当引力和斥力达到平衡时，机器人会陷入局部运动，导致目标不可达。针对此类问题，许多学者对算法做了大量的改进性研究。石为人等［1］在保持引力场函数不变的情况下，在斥力场函数中引入终点与机器人的相对位置，避免势场中出现合力为零的情况，从而使算法适用于复杂室内环境中。姚婧婧等［2］在包含有大型障碍物的场景中，将大型障碍物划分成质点的集合，对质点使用人工势场法，当机器人、障碍物、终点位置由于处于同一条直线时易陷入目标不可达时，添加虚拟子目标，加大引力的作用，使机器人迅速摆脱合力为零的状况，达到避障的效果。王萌等［3］通过分析势场函数的局部最小点和该处产生的局部极小值，提出设置适当大小的控制力使机器人尽快跳出局部极小点，从而达到避障效果。罗乾又等［4］通过改进斥力场函数，考虑机器人和目标间的相对距离，在遇到局部较小值时，在原目标点处增加虚拟目标点，通过二者共同的引力帮助机器人摆脱局部极小点向着目标处前进。卢恩超等［5］引入目标与机器人的相对距离，在人工势场法中的斥力函数模型中增加距离因子，利用工作空间的几何信息对机器人的状态进行微调，应用边缘探测法引导机器人绕着距障碍物安全距离之外的区域边缘运动，该算法具有较强规划能力。针对复杂环境以及动态不确定环境，学者也应用该算法进行路径规划，并基于传统人工势场法进行了改进及验证试验［6－10］，人工势场法结合粒子群等智能算法［11－13］已被广泛应用。上述算法对解决此类路径规划问题较为有效，但实现起来较为复杂。本研究应用人工势场算法，并引入一种新的避障策略，同样可以规划出有效的避障路径。

1 传统人工势场算法

1.1 势场模型

人工势场算法中将机器人、障碍物及目标点视为质点，通过建立引力势场和斥力势场模型共同引导机器人在抽象势场中的运动，运动方向与势场下降的方向一致。运动过程中，障碍物对机器人产生斥力作用，目标对机器人产生引力作用，作用力的大小取决与机器人的的运动位置。对机器人的工作空间进行建模，斥力作用随着机器人与障碍物的不断靠近逐渐变大，

引力作用随着机器人与目标的偏离而增大。机器人运行在二维空间中，通过获取机器人、目标两点的坐标向量建立引力势函数模型:

式(1)中:Uatt为目标对机器人的引力场;katt为大于零的引力势场增益系数;X是机器人在工作空间中的位置向量;Xg是目标处的位置向量。利用该模型定义出引力大小的计算方法。引力大小是引力势场函数的负梯度:

利用障碍物、机器人二者的坐标向量，建立斥力函数模型

式(3)中:Ur为障碍物对机器人的斥力场;kr是非负的斥力场常量;ρ(X)函数描述的是障碍物与机器人的最短空间距离;ρO表示单个障碍物对机器人作用的最大空间距离。当机器人处在最大空间距离之外时，障碍物对机器人未产生任何斥力作用。斥力大小Fr是斥力场负梯度:

工作空间中，引力场、斥力场的叠加产生合力场，引导小车朝着目标行进，因此，人工势场及作用力定义为:

1.2 传统人工势场算法的缺陷

人工势场算法易适用于解决机器人路径规划问题，但在机器人行进的过程中，斥力和引力的大小随着距离的变化发生改变，且方向相反。通常会出现以下3种情形:① 当机器人、障碍物、目标处于同一条直线上时，障碍物位于机器人、目标中间，接近目标时，引力减小，斥力增大，出现合力为零的情况;②当机器人、障碍物、目标处于同一条直线上时，目标处于中间，但机器人受障碍物的斥力影响，会出现引力、斥力平衡;③ 在多障碍物环境中，多个障碍物所施加的斥力叠加和与机器人所受目标处的引力大小一致，但方向相反。这3种局部极值问题会导致机器人无法避开障碍物到达目标处。在大小为10 m×10 m的仿真环境中，随机分布着7个大小不一的障碍物，使用传统人工势场算法规划出一条路径，仿真实验结果如图1所示。

图1 传统人工势场算法的仿真效果

图1中，起点坐标为(0，0)，终点坐标为(10，10)。由于引力和斥力的作用，小车从起点沿着势场下降的方向运动，当接近目标处时，陷入局部极值点，再往前行进会进入障碍物的影响范围，导致发生碰撞。实际上，终点处应该为势场最低值，许多专家学者为解决该问题，对算法做了进一步的改进研究。

1.3 局部极小值处理

为解决人工势场算法的缺陷，卢恩超等［5］采用了边缘探测法。边缘探测法通过引入沿边行走的思想，将障碍物的体积进行膨胀化处理，扩大成一个圆形，机器人相对于该圆形可视为质点，利用圆形的几何知识对机器人姿态进行微调。当探测到机器人运动到的下一个位置处于膨胀圆形内时，停止运行，调整方向，使机器人绕着据障碍物安全距离之外的圆弧运动，直到机器人远离危险区域。图2中当机器人到达p1位置时，预测下一个位置到达p2处，p2位于障碍物的影响范围内，若按照此路径继续行驶则发生碰撞，不符合设计要求，使用探测法到达p3处，成功避障。不断激活该方法之后使用人工势场算法，最终行驶路径是绕着圆形区域行走。在多障碍物环境中的仿真结果如图3所示。

图2 边缘探测法

图3 人工势场结合边缘探测法仿真结果

图2中的沿圆弧行走行为虽然引导机器人避免了碰撞，但圆弧在一定程度上延长了机器人的行驶距离，且经过多次转向调整，使规划出的路径并不是当前最优。当遇到局部极小值问题时可保存该位置，从该点重新规划路径。本文将障碍物处理成圆形，以局部极小值点为起点，处理起点与目标点间的障碍物，使机器人沿着圆形切线前进，少走圆弧，减少路径距离。

2 几何方法

在智能导航研究领域，基于图论原理的机器人最短路径算法通常要经过以下3个步骤实现［14］:① 利用图像处理的方法识别障碍物，并选取一定的形状(如凸多边形、圆形、椭圆、三角形)来近似描述;②利用采集的信息，建立小车工作环境模型，如栅格法;③利用相关算法在工作环境中寻找最优路径，如Dijkstra算法。

理想状况时，机器人沿着起点S到终点T的行走路径上没有任何障碍物，那么沿着直线ST行驶路径最优且平滑。在单障碍物环境中，路径ST上有一个半径大小为r的圆形障碍物，如图4所示。从几何学角度出发，以S，T为起点，针对该圆可规划出4条外切线 SA1，SA2，TE，TF，如图5所示。沿着4条路径中的任意一条都可以到达终点T处。利用数学知识可知，沿着SA1，弧A1E，ET和SA2，弧A2F，FT这两条路径所经过的路径长度是不同的。

图4 单障碍物

图5 几何切线法

几何学中，该情形分为2种:

1)连接S，T两点，直线ST过圆心O时，那么选择从 SA1，圆弧 A1E，ET到达目标处和选择从SA2，A2F，FT到达目标处的路径长度是相等的;

2)连接S，T两点的直线未过圆点O，如图4所示。从圆心O点做直线ST的垂线，垂点为D，且d(OD)＜r，根据数学知识可证明选择SA1，圆弧A1E，ET路径长度较短。

式(7)中:SA，SO 是向量;θ=arcsin(OA/SO)，θ决定着从起点出发是选择A1还是A2位置;P±θ是旋转算子。连接起点和终点的直线SF可以称作是基线，A1，A2两点离基线的距离越小，就优先选择［14］。

外切线SA1，TE必然相交于一点P，以该点为起始点，连接PT，从圆心O点做直线PT的垂线并求取最短距离，当最短距离大于r时，小车跳出障碍物的影响范围和局部极小值。再应用人工势场算法，继续行进能安全到达目标处。

3 仿真实验及分析

人工势场算法结合几何方法的实验步骤:

1)建立工作空间，并设立小车的起始点、终点位置，引力、斥力的增益系数，障碍物的个数n，障碍物半径s，小车行驶的步长l。

2)根据引力、斥力模型计算力的大小。

3)向下一个位置移动并判断是否陷入局部极值，进入障碍物的影响距离内，若是则调到步骤4);否则调到步骤5)。

4)调用几何方法进行路径规划。

5)偏离局部极值处继续使用人工势场算法。

6)在合力作用下前进并记录行进位置、迭代次数。若到达目标处则停止路径规划;否则，重复步骤2)～5)。

应用人工势场算法结合边缘探测法解决路径规划问题时，要不断地激活沿边行走行为，并计算小车要旋转的角度用于调整位姿，结果会带来一定的路径及时间冗余。利用上述实验步骤，基于酷睿2.0GHz CPU，2Gbit内存的笔记本，在 Matlab 7.11实验平台上进行仿真实验，验证以上算法的有效性。

已知小车行驶的起始点和终点，障碍物之间不存在重叠，选取引力增益系数k=15，斥力增益系数m=5，障碍物个数n=7，小车行进步长l=0.2，最大迭代次数J=200，仿真实验结果如图6所示。从实验结果中可以看出，在局部极值点处，沿着圆的切线行进到两条切线的交点时跳出局部极小点区域，继续使用人工势场算法，可顺利避过障碍物到达指定目标处。

图6 改进方法实验结果

在栅格大小为10×10的仿真环境下，设置相同参数，对比边缘探测法和改进算法，结果如表1所示。从表1中不难看出，改进算法在较短时间、较少的迭代次数中即规划出避障路径。

表1 对比结果

4 结束语

对多障碍物环境进行建模，使用人工势场算法结合边缘探测法，解决了局部极值问题并使机器人顺利到达目标处，但绕着较长的圆弧行走路线带来了路径冗余。在局部极值处通过引进几何切线的方法，能够较快地摆脱局部极小点，可跳出障碍物影响范围并避免绕着较长圆弧行进，结合人工势场算法可顺利完成路径规划。仿真实验结果表明:该方法可有效规划出一条较优避障路径。

［1］石为人，黄兴华，周伟.基于改进人工势场法的移动机器人路径规划［J］.计算机应用，2010，30(8):2021－2023.

［2］姚婧婧，邱于兵，敖俊宇.移动机器人避障路径规划改进人工势场法［J］.科学技术与工程，2011，13(11):2953－2956.

［3］王萌，王晓荣，李春贵，等.改进人工势场法的移动机器人路径规划研究［J］.计算机工程与设计，2008，29(6):1504－1506.

［4］罗乾又，张华，解兴哲.改进人工势场法在机器人路径规划中的应用［J］.计算机工程与设计，2011，32(4):1411－1415.

［5］卢恩超，张邓斓，宁雅男，等.改进人工势场法的机器人路径规划［J］.西北大学学报:自然科学版，2012，42(5):735－738.

［6］连晓峰，刘载文，左敏.移动机器人动态人工势场路径规划方法研究［J］.计算机仿真，2011，28(1):27－31.

［7］杨放琼，谭青，彭高明.不确定环境下集矿机环境感知与实时避障研究［J］.中山大学学报:自然科学版，2010，49(4):58－63.

［8］DONG HUN KUM，SEIICHI SHIN.Local path planning using a new artificial potential function compositon and its analytical design guidelines［J］.Advanced Robotics，2006，20(1):115－135.

［9］Rimon E，Koditschek D E.Exact robot navigation using artificial potential functions［J］.IEEE Trans.Robotics Automat，2010(8):501－518.

［10］Vadakkepat P，Tan K C，Wang M.Evolutionary artificial potential fields and their application in real time robot path planning［C］//Proc.Congr.of Evolutionary Computation.San Diego，CA:［s.n.］，2000:256－263.

［11］杨柳，张洪，高忠国.基于人工势场法的移动机器人路径规划研究［J］.机床与液压，2011，39(9):68－70.

［12］Ge S S，Cui Y J.New Potential Functions for Mobile Robot Path Planning［J］.IEEE Transactions on Robotics and Automation.2009，16:615－620.

［13］Lavalle S M.Planning algorithms.Cambridge［M］.MA:Cambridge University Press，2006.

［14］Gasilov N，Dogan M.Two-stage Shortest Path Algorithm for Solve Optimal Obstacle Avoidance Problem［J］.IETE JOURNAL OF RESEARCH，2011，3(57):278－285.