复杂环境下改进APF的机器人路径规划

卢恩超，张万绪

西北大学信息科学与技术学院，西安 710127

复杂环境下改进APF的机器人路径规划

卢恩超，张万绪

西北大学信息科学与技术学院，西安 710127

1 引言

路径规划是移动机器人研究领域的一个基本而又极其重要的课题，灵活有效的路径规划算法能帮助机器人适应各种复杂的环境，大大扩展机器人的应用领域。路径规划的任务是机器人在具有障碍物的工作环境中，按照某一性能指标，搜索一条从起始状态到目标状态的最优或近似最优的安全、无碰撞路径[1]。目前，常用的路径规划方法主要有人工势场法（Artificial Potential Field，APF）、栅格法、神经网络法、蚁群算法[2]和粒子群算法[3]等。人工势场法是路径规划算法中较成熟且高效的方法，以其数学计算上的简单明了而被广泛使用。

人工势场法具有结构简单、计算量小、实时性高、规划轨迹平滑等优点，主要用于解决局部路径的避障规划问题，在机器人实时避障和平滑轨迹控制方面得到广泛应用，但人工势场法本身也存在着不足，主要体现在局部极值点和在大型障碍物环境中规划时间较长且避障困难的问题。在对人工势场法的深入研究中，国内外学者们对它的固有缺陷提出了各种改进方法，主要通过引入机器人与目标点的相对距离和修改斥力角度等方法对斥力势场函数进行修改，但是都没有从根本上解决上述问题。针对上述问题，本文在文献[4]的基础上采用边缘探测法并提出自适应动态步长调整算法，以确保移动机器人迅速避开障碍，顺利到达目标点。

2 人工势场法基本思想和模型

2.1 人工势场法基本思想

人工势场法（APF）是由Kathib[5]提出的一种虚拟力法。基本思想是：机器人的运动空间是二维的，目标点对机器人产生引力，障碍物产生斥力，引力和斥力的合力作为机器人的加速力，控制机器人的运动方向并确定机器人的位置。该方法通过搜索合成势场中势能的下降方向，实现机器人的无碰撞路径规划[6]。它的突出优点是所需的环境信息量较少，因此，在局部路径规划中更能显示出它的优越性。

2.2 人工势场模型

2.2.1 目标点的引力函数

设机器人在运动空间中的位置为X=(x,y)T，目标点对机器人产生的引力Fatt是引力势场函数Uatt的负梯度，则引力可以定义为：

式中，katt为引力正比例增益系数，Xgo为机器人在势场中的目标位置。当机器人到达目标的过程中，引力逐渐线性收敛于零。

2.2.2 障碍物处斥力函数

障碍物对机器人产生的斥力Frep是斥力势函数Urep的负梯度，则斥力可定义为：

式中，n为任意实数，krep为斥力势场正比例增益系数，ρ(X)为机器人与障碍物的最短距离，ρ0为单个障碍物的最大影响距离，主要取决于机器人的运动速度和减速能力。

APF容易出现局部极小值的根本原因在于：机器人无法掌握环境的全部信息，公式（3）中引入了机器人和目标点的距离因子(X-Xgo)n，从而确保整个势场仅在目标点全局最小[7]。定义Frep2(X)的方向与引力方向一致，对于机器人、目标点、障碍物在同一直线且障碍物不在中间时，定义Frep1(X)与Frep2(X)同向，其他情况定义Frep1(X)的方向与障碍物的影响范围相切，且与引力向量的内积大于等于零[8]。这样，机器人在到达目标点之前，不可能出现合力为零的情况，从而避免传统APF算法中机器人容易陷入局部极值点的问题。

在对APF路径规划进行仿真时，发现该方法在障碍物大小相同或相近的环境中，机器人能很好地从起始点绕过障碍物到达目标点，但是，对于环境中存在大型障碍物或运动空间相对狭窄的情况，机器人容易出现避障失败。为此，本文提出一种能够适应复杂环境的避障策略——边缘探测法，并加入自适应动态步长调整算法，确保机器人在大型障碍物和多障碍物的狭窄环境中能顺利绕过所有障碍物，快速到达目标点。

3 边缘探测法

APF法是通过环境势场模型进行路径规划的，合理的环境模型能够极大提高路径规划的速度和准确度。文献[4]中环境模型的建立是将障碍物视为同等大小，但是当复杂环境中存在大型障碍物时，如果仍按照上述方法，机器人将在较小的障碍物周围绕很远的路，甚至直接与障碍物碰撞而导致路径规划失败。针对上述情况，本文提出一种新的环境模型的建立方法，并结合边缘探测法，确保机器人更好地适应大型障碍物的复杂环境需求。

3.1 环境模型的建立

机器人环境模型的建立：拟在静态环境下，利用势场的概念在二维平面上对机器人工作环境进行建模。为方便对移动机器人在规划过程中的处理，将机器人模型简化为一个很小的质点，同时将障碍物（T形和杆形障碍物除外）进行膨胀化处理。

具体做法：利用机器人携带的多种传感器（如视觉、超声、红外传感器等）通过传感器信息融合技术来获取障碍物的尺寸、形状和位置等局部环境信息。首先，将机器人的实际尺寸折算进障碍物的面积内，同时根据机器人的实际尺寸将障碍物的边界向外扩展，其次，再将边界外扩后的障碍物膨胀化为一个包含该障碍物的最小圆，这样，就简化了APF算法中距离的计算和问题的描述。

3.2 边缘探测法步骤

如图1所示：假定实线圆O（半径为R）代表膨胀化障碍物，以O为圆心，OXk为半径的虚线圆与直线OXk+1'相交的点记为Xk+1，该点称为引导点。则边缘探测法的步骤如下：

（1）当机器人进入障碍物的影响范围内时，不断探测下一步将要到达的位置，若机器人探测到下一步的位置在障碍物膨胀化边界内时，就停止向前运动，并及时调整自身姿态向Xk+1处移动。

（2）当机器人到达Xk+1点后退出边缘探测法，进入APF路径规划继续探测下一步的位置Xk+2，若Xk+2不在障碍物的膨胀化区域内，则说明机器人已成功避开该大型障碍物，否则，继续按照步骤（1）逐步进行探测，直到机器人预探测的下一步位置Xk+m不在障碍物区域内为止。一般来说，m只需一步或者几步即可。

图1 边缘探测法示意图

边缘探测法的实质是利用引导点引导机器人离开障碍物区域。当检测到障碍物时，机器人就按照给定的避障策略完成避障任务，它的激活条件是OXk+m≤R。

本文在势场环境模型下结合边缘探测法，引导机器人沿着距障碍物一定距离的边缘运动，以达到避障和平滑路径的作用。但是，该方法存在规划时间长的问题，尤其在环境信息部分未知的局部路径规划中，机器人在向目标迈进的过程中通常是一步一步试探前进，然后根据传感器采集到的信息更新局部环境信息，最后经过计算在得到下一步的前进方向θ后，机器人就沿着该方向以固定步长l向前移动。因此，为了提高APF算法的收敛速度和路径规划的效率，从步长入手，提出自适应动态步长调整算法对APF路径规划加以改进。

4 自适应动态步长调整算法

4.1 自适应动态步长调整算法原理

在APF模型下，通过对机器人受力分析可知，机器人的运动轨迹如图2所示，其规律可总结如下：

（1）当ρ(X)＞ρ0时，只受目标点的吸引力，机器人将沿引力方向直线运动。

（2）当ρ(X)≤ρ0时，机器人在合力作用下，将沿着障碍物的边缘做圆弧状运动。

图2 固定步长路径规划图例

一般来说，整个环境中，自由空间占据绝大部分，在这些自由空间中，如果步长取值太小，必然会降低算法的性能。尤其在障碍物分布不均匀和大型多障碍物的复杂环境中，如果步长太小，不但使机器人到达目标点所消耗的时间变长，还容易陷入死锁状态使机器人在局部区域不断徘徊，甚至无法前进。同时，过多的姿态调整将导致许多机械方面的问题（例如轮子滑动误差等）。但是，如果步长太大，会大大增加机器人与障碍物的碰撞机率，而且机器人很有可能错过一些比较隐蔽的入口，从而绕了许多弯路，没有达到路径优化的目的[9-10]。

图3 （a）动态步长调整法路径规划图例

由于机器人运动轨迹比较简单且有一定的规律，所以面对比较复杂的环境，机器人需要有根据障碍物的分布情况自动调整步长的能力。基于上述分析，本文提出自适应动态步长调整算法，该算法随着搜索方向的变化动态调整搜索步长，从而实现较快的搜索，以提高复杂环境中APF算法的收敛速度和路径规划的实时性。

式中，θ为机器人的合力方向，γ为动态步长，表示机器人每步行走的相对距离。λ为步长增益系数且0≤λ≤1，α为合力方向与环境坐标系x轴之间的夹角且α∈[0,π]。δ为步长增益补偿量且lmin≤δ≤lmax，此处α是为了防止步长为零而设置的。lmax和lmin分别为固定步长路径规划时步长的最大值和最小值，是动态步长γ的一个参考约束范围，其值与环境大小和障碍物的分布情况密切相关。

在程序运行过程中，λlmax和δ都是相对固定的。由前面对机器人的受力分析可知，当ρ(X)≤ρ0时，机器人开始进入避障状态，步长γ将随着α的增大而逐渐变小；当ρ(X)＞ρ0时，机器人运动方向固定，步长γ可以取一个较大的固定值。由于α的变化直接反映了机器人是否进入避障状态，因此，公式（6）选取了α作为动态步长γ的变量。

4.2 自适应动态步长调整算法策略分析

机器人由于受自身（如惯性、机械摩擦等）以及外界环境（如地面情况、障碍物分布等）影响，在避障过程中很容易与大型障碍物碰撞，因此，机器人在实际运动时其速度设定应与动态步长γ成正比。

如图3（a）所示，当机器人在障碍物的影响范围之外时，机器人做直线运动，此时，步长γ的值（对应于图3（b）中直线段a和c）相对图3（b）中的固定步长（虚线）来说比较大，机器人可以快速运行；当机器人进入障碍物的影响范围内时，为避免机器人与障碍物碰撞，在避障初期，由于运动方向θ的变化比较大，此时，步长γ的值（对应于图3（b）中的曲线段b）应该适当减小，机器人慢速运行，直到安全避开障碍物为止，之后机器人再以较大的步长（对应于图3（b）中直线段c）加快速度向目标点运动。这样，就在局部提高机器人避障精度的同时也全面提高了路径规划的速度和效率。

图3 （b）固定步长和动态步长曲线图

总之，根据空间中障碍物的分布信息来自动调整步长的大小，不仅可以优化路径，降低陷入局部极值点的机率，缩短到达目标点的时间，而且还能提高APF算法的收敛速度以及路径规划的效率和机器人的安全性。

5 仿真结果与分析

在改进APF机器人路径规划中，假设机器人的运动速度是可变的，在APF环境模型中，障碍物大小和分布情况可根据传感器获得的局部环境信息抽象出来，在运动初期应合理设定机器人的避障范围（略大于障碍物的影响范围）。

采用改进前后的APF路径规划，在相同环境和参数（不包括初始步长）条件下，分别对机器人路径规划进行仿真，结果如图4和图5所示。表1为机器人在环境中障碍物的个数分别为7和8时，利用传统APF和改进APF（IAPF）路径规划经过多次实验所得的实验数据对比。

图4 基于APF的机器人路径规划

图5 改进APF的机器人路径规划

表1 改进前后APF路径规划参数对比

从仿真结果可以看出，图4中机器人的运动步长是固定的，并且机器人在运动过程中遇到大型障碍物7时，直接与障碍物碰撞，而图5在边缘探测法的基础上加入自适应动态步长调整算法后，机器人不仅能够顺利避开所有障碍物到达预定目标点，而且在整个规划过程中，步长随着障碍物的分布呈动态变化趋势。表1中实验数据表明，改进APF路径规划所需的步数和规划过程中消耗的时间明显减少，并且步数的减少幅度分别为35%和36.8%。结果表明，加入自适应动态步长调整算法后APF路径规划的效率得到较大的提高，并且环境空间越大，该方法的优势就会越明显。

6 结束语

为克服APF自身的缺陷，本文通过分析APF机器人路径规划及所生成的路径轨迹的特点，提出在边缘探测法的基础上加入自适应动态步长调整算法，并采用APF加以实现，确保机器人在有大型障碍物和运动空间相对狭窄的复杂环境中，不仅能从给定起始点安全、无碰撞地绕过所有障碍物到达预定目标点，而且还缩短了路径规划的时间，提高APF算法的收敛速度和机器人的避障精度。经过多次实验及仿真结果表明：改进APF路径规划克服了传统势场法中存在的局部极值点、规划时间长以及大型障碍物附近避障困难的缺点，同时保留了传统势场法计算简单的优点。因此，改进APF机器人路径规划具有较强的路径规划能力和实际意义。

当然，在实际应用中环境是复杂多变的，对于杆形和T形障碍物的处理以及如何改进势场函数，确保APF算法能够适应动态未知环境下的路径规划，是下一步将要研究的重点。

[1]姚靖靖，邱于兵，敖俊宇.移动机器人避障路径规划改进人工势场法[J].科学技术与工程，2011，11（13）：2953-2956.

[2]何少佳，刘子扬.基于惯性蚁群算法的机器人路径规划[J].计算机工程与应用，2012，48（15）：245-248.

[3]马千知，雷秀娟.改进粒子群算法在机器人路径规划中的应用[J].计算机工程与应用，2011，47（25）：241-244.

[4]沈文君.基于改进人工势场法的机器人路径规划算法研究[D].广州：暨南大学，2009.

[5]Kathib O.Real-time obstacle avoidance for manipulators and mobile robots[C]//The International Journal of Robotics Research，1986，5（1）：90-98.

[6]曲道奎，杜振军，徐殿国，等.移动机器人路径规划方法研究[J].机器人，2008，30（2）：97-101.

[7]石为人，黄兴华，周伟.基于改进人工势场法的移动机器人路径规划[J].计算机应用，2010，30（8）：2021-2023.

[8]孟蕊.基于改进人工势场法的足球机器人路径规划研究[D].北京：北京工商大学，2010.

[9]梁轲.移动机器人在未知环境下的自适应路径规划[D].上海：复旦大学，2005.

[10]黄凯，周永权.一种改进的变步长自适应GSO算法[J].计算机工程，2012，38（4）：185-187.

LU Enchao,ZHANG Wanxu

School of Information Science and Technology,Northwest University,Xi’an 710127,China

When the obstacles are large,or the complex environment space is relatively narrow,Artificial Potential Field method（APF）is prone to appear repeated shocks,long time planning and obstacle avoidance of difficulty nearby the large obstacles. This paper presents an adaptive dynamic step length adjustment method based on the APF path planning which is combined with the edge detection method to overcome the proposed defects of APF,achieving mobile robot smooth path planning in the complex environment.Hence it can not only improve APF algorithm convergence speed and the safety of path planning,but at the same time ensure the approximate optimum path.Experiments are carried out by simulation to verify the effectiveness of the aforementioned methods.

Artificial Potential Field（APF）;path planning;edge detection;adaptive dynamic step length adjustment

针对移动机器人在有大型障碍物和运动空间相对狭窄的复杂环境中，人工势场法（APF）容易出现反复震荡、路径规划时间较长以及大型障碍物附近避障困难的问题，提出了在结合边缘探测法的APF路径规划基础上，加入自适应动态步长调整算法来克服APF的上述缺陷，实现移动机器人在复杂环境下的平滑路径规划，在确保路径近似最优的同时提高APF算法的收敛速度和路经规划的避障性能。实验结果证明了上述方法的有效性。

人工势场法；路径规划；边缘探测；自适应动态步长调整法

A

TP242

10.3778/j.issn.1002-8331.1207-0287

LU Enchao,ZHANG Wanxu.Path planning for mobile robot based on improved Artificial Potential Field method in complex environment.Computer Engineering and Applications,2013,49（24）：45-48.

卢恩超（1985—），女，硕士研究生，研究领域为智能控制与测试；张万绪（1964—），男，博士，副教授，研究领域为智能控制与测试和电视信号处理。E-mail：luenchao_666@163.com

2012-07-20

2012-09-06

1002-8331（2013）24-0045-04

CNKI出版日期：2012-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20121011.1019.021.html