英语原文共 14 页

在障碍物环境中一种新的APF路径规划策略

摘 要

本文提出了一种在障碍物环境下求解路径规划问题的通用方法。该方法一方面可以应用于移动机器人，另一方面也可以用于解决高冗余多体系统在其对应空间中的规划问题。该方法基于人工势场(APF)的概念，通常与环境中定义的障碍物和目标位置相关。首先，根据一个与距离n次幂成反比的势密度，构造了一个新的APF形状。在此基础上，提出了一种全新的路径规划策略——“准测地线法”。该方法适不仅适用于二维环境同样也适用于三维环境，无论环境是静态的还是动态的，这种算法的工作方式都是相同的。

1.简介

自从尼尔森^[1]在1969年提出移动机器人路径规划的可见图方法以来，机器人和机械手臂的路径规划几乎每天都有新的发展。参考文献[2-5]包括近期路径规划参考书目的一小段摘录。

多年来，已经发展了若干种用于路径规划的方法。在[6]中可以看到路径规划的短暂发展，Latombe列出了1990年以前路径规划的标志性方法。此外，名为Zomaya^[7]的作者在他们的论文中汇编了关于这些方法的信息，并将它们分组。在避障方面，博士论文[8,9]和报告[10]对不同的方法进行了详尽的分类和描述。

利用人工势场(APF)来进行路径规划是最普遍、最简单的方法之一。这个概念是Oussama Khatib提出的，他在[11]中提出了一种实时避障方法。一方面，该方法基于对障碍物周围的势函数(FIRAS函数)的构造，推导出机器人规避障碍物的斥力。另一方面，用规划终点的中心定义了一个吸引势函数。此后，许多作者，如Volpe和Khosla^[12-14]，致力于寻找一个与障碍物相关的势场函数，使机器人具有更好的行为去规避障碍物并且接近目标。这些势函数的新公式避免了局部极小^[11]的一些问题。

这个概念也被用于路径规划。Koditscheck在[15]中引入了“导航函数”的符号，这是一个无局部极小值的势能函数。Faverjon和Tournassoud利用势场方法的一种变体，在[16]中实现了一个实际的系统，该系统能够规划具有八个关节的机械手在垂直管道中移动的运动。Barraquand和Latombe^[17]将势场方法与随机技术相结合，从局部极小值中逃逸，实现了一个多自由度机器人自主规划路径的方式。

目前发展起来的基于人工势场的路径规划方法，是基于设置与障碍物相关联的排斥势函数和与目标点相关联的吸引势函数。这两个函数的和就是所谓的APF。路径规划问题包括寻找初始位置和目标位置之间的最小势能路径。本文提出了一种新的基于APF的路径规划方法，不需要定义一个吸引势场。

2.问题一建模:一个新的势函数

如上所述，只有排斥力场与障碍物相关联。在[18,19]中，提出了一种新的势函数模型，该模型是将障碍物对其几何形状用点进行离散化后建立的。与超二次势场的复杂性相比，这种定义势函数的方法可以很容易地对任何几何障碍物进行建模[13,14]。超二次势场无法对任意的障碍物进行建模，此外它们的分析表达式更为复杂。

在本文中，我们提出了一种更精确的扩展方法，基于沿着障碍物几何形状建立势密度，如图1所示。

在式(1)中对于势密度的表达式，是基于[18]中成功开发的势函数的势密度表达式

其中KR和N为常数值(如在[18]中)，d为特定面积或长度的差值，电势中的点是通过计算得到的，d0是标准化的距离。因此，势函数可以由下面的二维积分给出，其中曲线可以用参数u表示:

在三维情况下，如果曲面由参数u和v参数参数表示，则表达式为：

其中：

这样做的目的是得到任意形状的障碍物的势函数解析表达式。然而，积分(2)和(3)在一般情况下不适用于符号解法。

无论如何这些积分对于二维的直线和三维的三角形都可以很容易地求出来，障碍物的轮廓应该近似为直线还是三角形，这样将会得到比[18]中更好的近似函数。

用直线的参数表示：

以及三角形

如图2所示，对于N的每一个值，都可以求出积分(2)和(3)。例如，在二维情况下，取N = 3，势函数的表达式为如下:

其中n是直线的总数，Li是直线i的长度。

对于参数N值较大的三维情况，势函数的表达式更为复杂。

在图3中，为二维几何绘制了势函数的形式

3.问题二:路径规划的拟测地线曲线建模。

利用传统的APF公式，在以障碍物最终位置为中心的排斥势阱中加入一个吸引势阱。因此，在二维情况下，路径是在XY平面上的投影，在势函数的表面上定义了有限长度的曲线。必须考虑到这里使用的势函数在障碍物的轮廓处趋于无穷。

最明显的路径规划方式是定义通过初始位置的最大梯度曲线(图4)，由于与所谓的优化技术相似，该方法可称为“梯度下降法”。由于吸引势井，曲线可能经过最终位置。然而，我们可以在其中很容易地找到局部极小值。此外，如果考虑到最小长度，规划的路径可能也不是最优的。

综上所述，考虑到最小长度准则，最合适的曲线可能是初始位置与最终位置之间测地线曲线的投影，如图5所示。然而，对于具有复杂解析表达式的曲面，测地线曲线的精确表达是不可能的。此外，这条曲线似乎不适用于依赖于时间的环境。为此，利用“快进法”对曲面进行多面体离散，得到测地线曲线，开展了[20,21]等工作。一些作者提出了在[22]曲面上寻找近似最短路径的方法，并将其应用于路径规划。然而，这些方法似乎很难扩展到三维情况和障碍物位置和最终位置随时间变化的情况。

本文提出了一种新的曲线代替测地线路径。对于二维情况，势函数可以表示为式(7)的曲面F(x,y,v) = 0

这条曲线从曲线表面的一个起始点到曲线表面的终点,并满足以下性能:对于任何点p (x,y,v)在曲线表面上的行进,沿着最大限度地减少点p(x,y,v) 和点f(xf,yf,vf)的直线距离的方向。这意味着，从给定的起始点到终点的剩余的最短路径(如测地线路径)近似为一条从p到f的直线，这就是为什么称这条曲线为拟测地线,图6描述了曲线的几何排列。下面是曲线的微分方程。

首先将曲线的方向向量推导为点坐标(x,y, v)的函数，然后考虑方向向量的表达式，整理曲线的微分方程。

方向向量可以在曲面F(x,y,v) = 0的切平面上测量。它的方向是点p(x,y, v)到点f(xf,yf,vf)在切平面上投影直线的方向。

所以曲面F(x,y,v)的法向量是(非标准化)：

所以切平面是：

点f在切平面上的坐标为:

式中：

曲线的方向向量与向量成正比，它的组成部分为：

对向量进行标准化，方向向量的分量是：

引入参数s(弧长)，对微分方程组用曲线进行验证为：

在初始条件下：

以四阶方程组为例，可以一步一步地精确求解方程组的解。

4.问题三:拟测地线的推广

拟测地线的概念可以推广到超曲面。最复杂的路径规划中可以提出的问题是具有时变障碍物和时变最终位置的三维规划问题。对于这个问题，定义拟测地线曲线的超曲面的形式为F(x,y,z,t,v) = 0。在本例中，时间作为一个附加变量。因此，法向量与切平面有如下表达式:

最后一个超点在相切超平面上的投影的坐标，有以下表达式:

式中：

其中是到达终点所需要的时间。

而超曲线的方向向量与x、y、z、v的分量成正比:

变量“t”(时间)是一个连续的变量，其增量必须严格地正相对于以前的位置。因此，方向向量的组成部分即关于变量t的分量必须与下面的向量成比例

并对向量进行标准化，得到了一个类似于(13)的方程。由此得到的微分方程组为:

在初始条件下：

其中”s”是超曲线的弧长

解决这个问题

计算拟测地线曲线的函数，在二维情况下为式(7)，在三维情况下为较复杂的表达式。在第一种情况下，用四阶龙格-库塔法可以很容易地得到方向矢量的解析表达式，并且可以很容易地解决问题。然而，在三维情况下，得到的解析表达式及其导数(需要求解(22))太大。因此，虽然进行了(3)的初始积分，但是花在计算上的时间过多。这里有两个选择:第一个可以建立在(3)及其导数的数值积分上。这是一种合理的方法，因为用龙格-库塔法求解(22)时，不需要分析方向向量的表达式。此外，每次迭代都需要求解一个数值积分步长。第二种选择考虑了使[18]成为障碍物的模型，其中势函数的表达要容易得多，尽管障碍物表面的近似性不是很好。

示 例

例1。考虑含有静止障碍物(Oi)的二维环境如图7所示，以及初始点和终点。计算得到的路径为KR = 0.01, N = 3, d0 = 1。龙格-库塔分辨率的步长取haverage = 0.01

例2。现在考虑图8中的二维环境，在一秒钟内，有动态障碍物和动态终点。计算路径Kr = 0.1, N = 3, d0 = 1。龙格-库塔分辨率的步长取haverage = 0.01。

在图9中，展示了障碍物的连续位置和终点位置，以及每一瞬间终点的轨迹。

三维的例子很难画出二维的图形。然而，静态和动态情况都要求同样好的结果

图9。例二中的连续位置(a) 0.1 s，(b) 0.2 s，(c) 0.3 s，(d) 0.4 s，(e) 0.5 s，(f) 0.6 s，(g) 0.7 s，(h) 0.8 s，(i) 0.9 s，(j) 1.0 s

结 论

本出了一种新的基于APF的路径规划方法，重点研究了一个新的势函数的形式，以及在该函数上定义路径的一条新曲线(拟测地线曲线)的生成。势函数建立在沿障碍物轮廓的势密度上，势密度与障碍物点和空间点之间标准化距离的n次幂成反比。quasi-geodesic曲线被定义为一个势函数曲线,它满足以下属性，即曲线上的任何一点在曲线表面的前进方向是沿着最大限度地减少这个点和终点的直线距离的方向，该路径将作为拟测地线曲线的投影。这条路径的定义，使它成为一个非常可行的方法，用于静态或动态和二维或三维问题。实验结果验证了该方法的有效性。在动态情况下，如果能够对环境进行实时检测，则该方法易于修改，计算所需的导数可通过外推法计算。

参考文献

[1] N.J. Nilsson, A mobile automaton: an application of artificial intelligence techniques, in: Proceedings of the 1st International Joint Conference on Artificial Intelligence, Washington, DC, 1969, pp. 509–520.

[2] C. Lin, C.K. Chen, C.L. Chen, Path planning and dynamic control of a redundant robot manipulator for conveyor tracking, International Journal of Systems Science 30 (5) (1999）491–503.

[3] R. Kindel, D. Hsu, J.C. Latombe, S. Rock, Kinodynamic motion planning amidst moving obstacles, in: IEEE International Conference on Robotics and Automation, 2000.

[4] P. Vadakkepat, K. Chen Tan, W. Ming-Liang, Evolutionary artificial potential fields and their application in real time robot path planning, in: Proceedings of Congress of Evolutionary Computation (CEC2000), San Diego, 2000.

[5] S. Yang, M. Meng, An efficient neural network method for real-time motion planning with safety consideration,Robotics and Autonomous Systems 32 (2000) 115–128.

[6] J.C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991.

[7] A.Y. Zomaya, M.R. Wright, T.M. Nabham, On the path planning problem in the vicinity of obstacles,Cybernetics and Systems: An International Journal 29 (1998) 807–868.

[8] T.A. Harden, The implementation of artificial potential field based obstacle avoidance for a redundant manipu

资料编号：[5006]