1.2.2 常用的航迹规划方法

航迹规划是机器人学研究中最重要的领域之一，这方面的研究已有很长的历史。Canny在1988 年已经证明航迹规划是一个NP问题[17]，对其直接求解往往会导致组合爆炸。为了加速规划进程，近年来国外学者已提出了许多不同的规划方法。下面我们对已有的规划方法分类加以概述[2～3，18～19]。

1．基于概略图的规划方法

概略图（Skeleton）也称路线图（Roadmap）。在基于概略图的路径规划方法中，首先根据一定的规则将自由的C空间（Configuration Space）表示成一个由一维的线段构成的网络图，然后采用某一搜索算法在该网络图上进行航迹搜索。这样，路径规划问题被转化为一个网络图的搜索问题。概略图必须表示出C空间中的所有可能的路径，否则该方法就是不完全的，即可能丢失最优解。常用的概略图方法包括通视图法（Visibility Graph）、Voronoi图法、轮廓图法（Silhouette）、子目标网络法（Subgoal Network）和随机路线图法（Probabilistic Roadmap，PRM）。

（1）通视图法

通视图由规划空间中的障碍物的相互可见的顶点间的连线构成。图1-1 给出了包含三个多边形障碍物的二维规划空间的通视图，其中较粗的线表示起始点 S 和目标点 G 之间的一条最短路径。1989 年，Asano等[15]证明在具有 n 个顶点的二维规划空间中，其通视图的边数具有数量级O（n2），构造通视图所需时间的数量级也为O（n2）。

通视图法可用于求解二维规划空间中的最短路径问题。尽管它也可用于高维规划空间，但此时生成的路径将不再是最短的。由于通视图不能表达物体运动的方向性约束，除非运动物体可以按任何方向以任意角度转弯，通常很少用通视图法求解实际的路径规划问题。

（2）Voronoi图法

如果运动物体要求与障碍（或威胁）的距离越远越好，可以采用Voronoi图方法。Voronoi图由与两个或多个障碍（或威胁）的给定特征元素距离相等的点的集合构成。对Voronoi图的详细讨论可参见文献[16]。图1-2 给出了以多边形障碍物自身作为特征元素生成的Voronoi图。如果以多边形的边作为特征元素则可以得到不同的Voronoi图。对于只包含有威胁的规划空间来说，可以将威胁源的中心点作为特征元素。Voronoi图将规划空间分为多个区域，每个区域只包含一个特征元素。对于区域中的每一点，该区域的特征元素是所有特征元素中最近的。

与通视图比较，Voronoi图具有明显的优点，Voronoi图的边数只有数量级 O（n），构造Voronoi图所需时间的数量级为O（nlogn），其中n 为所选特征元素数目[21]。Voronoi图的各种构造方法可参见文献[20～25]。如果将多边形的边作为特征元素，则Voronoi图一般都包含有曲线段。1987年，Canny和Donald通过使用一种不同于欧氏距离的度量方法，构造出了一种只包含直线段的Voronoi图[26]。

对于维数大于2 的高维空间，通视图与Voronoi图将变得非常复杂，而且一般没有确定的特征元素选择方法。例如，多面体间的Voronoi图由二维曲面构成，它不再是一维的轮廓线。尽管通视图仍然可以由多面体的各顶点间的连线组成，但此时最短路径不再存在于通视图之中（如图1-3 所示）。因此，通视图与Voronoi图一般只应用于二维路径规划。

（3）轮廓线法

对于高维空间，Canny于1987 年给出了另一种构造概略图的方法[27]。该方法先将高维空间中的物体投影到一个较低维的空间中，然后在低维空间中找出其投影的边界曲线，称为轮廓。该轮廓又投影到一个更低维的空间中，如此继续下去，直到轮廓变成一维的轮廓线。对于同一障碍物其轮廓不相连的部分，需用连接线将它们连接起来（如图1-4（b）所示）。这样得到的一维轮廓线图比原始的高维空间简单得多，可以从中找到一条可行的路径。该方法通常在理论上用于分析问题的复杂性，而很少用于实际中的路径规划。使用轮廓线方法得到的路径，运动物体总是沿着障碍物边缘移动。该算法的其他变化形式可参见文献[28]。

（4）子目标网络法

子目标网络方法不直接构造明显的概略图，而是保存一个可以从起始点达到的节点列表。如果目标点出现在该表中，则规划成功结束。规划空间中两点之间的可达性由一个简单的局部规划算法来判断，该局部规划算法称为局部算子。局部算子的选择一般根据具体问题确定，例如，可以简单地在两节点之间按直线运动。

开始的时候，该算法在起始节点与目标点之间选取一个由称为子目标的中间节点组成的候选序列，并运用局部算子依次连接这些子目标。在选取子目标候选序列时可以采用某些启发式信息，也可以随机选取。如果连接过程不能到达目标点，则将已经连接的子目标保存在列表中。然后任取一个已到达的子目标，并在该子目标与目标节点之间选取一个候选序列，如此反复，直至到达目标节点。在该算法中，可到达的节点间的运动路径可以由局部算子非常容易地重新得到，因此不用保存。该算法的一个主要优点是节省内存空间。通视图可以看作是一个子目标网络，其子目标为障碍物的顶点，局部算子为“直线运动”。图1-5显示了一个“沿对角线方向运动”的局部算子生成的子目标网络。

局部算子的选择确定了规划算法的实现。一种极端的情形是采用“直线运动”，但当两个节点之间的距离很远时，该方法通常很难找到可行的路径。因此，相邻的两个子目标间的距离一般很近，这势必增加子目标的数目，从而增加内存空间。另一个极端就是采用一种精确的全局规划算法作为局部算子，此时仅有一个包含有起始点和目标点的候选序列需要连接。这种方法将一个全局规划问题分解成若干个比较简单的局部规划问题[29，30]。

（5）随机路线图法

随机路线图法是近年发展起来的一种针对多自由度问题的路径规划方法，由Overmars等于1992年率先提出[31]。该方法通过在规划空间中随机进行采样生成路线图，然后在该路线图中搜索路径。随机路线图的构造如下：如果最新的采样点与路线图中的某一节点间存在可行路径，则将该采样点加入到路线图中，同时找出该节点与路线图中的近邻节点间可能存在的路径，并将可行路径作为节点间的边加入到路线图中。该方法的详细讨论可参见文献[31～34]。

该方法的优点之一就是可以在规划时间和路径的质量之间进行权衡，构造随机路线图的时间越长，得到最优路径的可能性就越大。在确定环境下，随机路线图一般可以事先构造。然而，如果规划环境一旦发生变化，随机路线图并不能通过局部更新以适应新的环境，因此，该算法一般不适于在线实时应用[35]。

2．基于单元分解的规划方法

基于单元分解（Cell Decomposition）的规划方法首先将自由的C空间分解成为一些简单的单元，并判断这些单元之间是否是连通的（存在可行路径）。为了寻找从起始点到目标点之间的路径，首先找到包含起始点和目标点的单元，然后寻找一系列连通的单元将起始单元和目标单元连接起来即可。单元的分解过程可以是对象依赖的，也可以是对象独立的。

在对象依赖的单元分解中，障碍物的边界被用作单元的边界，这样所有单元并在一起恰好与自由空间重合，如图1-6 所示。对象依赖单元分解的另一个优点就是分解得到的单元数目较少，节省存储空间。但其分解过程较为复杂，各单元之间是否存在包含、交叉、连接、相邻关系的判断比较困难。Keil和Sack于1985 年证明，对于具有缺口的多边形，如何将它分解成凸多边形的组合是一个NP问题[36]。

在对象独立的单元分解过程中，首先将C空间分解为规则形状的单元（通常为正方形），然后检查各单元是否被障碍物覆盖或与障碍物相交。由于所有单元都是预先划分的，其形状和位置不随对象的形状和位置而改变，单元的边缘与对象的边缘也不一定重合，但其误差随着单元的细化而不断减少。与对象依赖单元分解相比，在实际应用中该方法的计算量要小得多。栅格法和四叉树法是最常用的两种对象独立单元分解方法，如图1-7所示。

3．人工势场法

人工势场法最先由Khatib于20世纪80年代中期提出[37]，它不需要利用图形的形式表示规划空间，而是将物体的运动看成是两种力作用的结果：一种是吸引力，它将运动物体拉向目标点；一种是排斥力，它使运动物体远离障碍物和威胁源。这样，物体总是沿着合力的方向运动。人工势场法最初是为机器人的在线导航而提出的，后来它被用于离线路径规划中。该方法的一个显著优点就是规划速度快，但它可能找不到路径，从而导致规划失败，其原因是在吸引力和排斥力相等的地方存在局部最小点。许多学者提出了各种不同的势函数，以克服局部最小的问题[38，39]。

没有局部最小的势函数称为导航函数。传统的势函数一般取为与运动物体最近的障碍物的距离，这种基于最近障碍物的距离的势函数一般都不满足导航函数的要求[40，41]。尽管传统的势函数方法通常很难彻底消除局部最小，但可以通过在其基础之上附加一些混合机制，以逃离局部极小值点。这些方法已成功地用于解决多达10个自由度的路径规划问题。

1991年，Barraquand和Latombe采用一种巧妙的机制给出了两种路径规划方法[3，42]。他们在运动物体上给出多个控制点，对每个控制点定义一个势场。C空间中的每一点的势场值根据运动物体在物理空间所处对应位置时各控制点的势场值来定义。尽管在物理空间上各点的势场值没有局部极小点，各控制点的势场值之和可能导致C空间中势场值的局部极小点。Barraquand和Latombe给出了两种方法克服这一问题。

第一种方法是采用最优优先搜索策略在C空间中进行路径搜索，并以链表的形式保存搜索过的路径点。如果发现一个局部最小值点，则标志出该点，并将它从路径点链表中剔除，然后重新进行路径搜索。这种方法可以有效地“填起”局部最小值点。一般地，位于局部极小值“洼地”中的点数按C空间的维数呈指数上升，因此，该方法不适用于高维空间中的路径规划。

第二种方法是采用随机搜索的方法避开局部极小值点。首先，执行最佳优先策略，找到一个局部最小值点，然后，从当前局部最小值点执行随机运动（Brownian运动），脱离该局部最小值点，并找到下一个局部最小值点，这样逐渐构成局部最小值图。然后根据该图执行深度确定优先搜索策略，找到目标位置点，产生路径。该方法被成功应用于多达31 个自由度的路径规划问题求解。这种方法的缺陷是由于它是概率完备解，如果找不到路径，算法会一直进行下去，而无法给出解不存在的答案；同时，对同一个问题，每次求解可能会得到不同的结果。

以上方法的问题主要是找不到没有局部极小值的势函数。一种可能的方法是通过数值解法计算出一个没有局部极小值的势函数，这种导航函数只在规划空间的各网格点上求出它的值。由于需要计算各网格点的势函数的值，因此一般只适用于维数相对较低的空间的路径规划。这类方法主要包括波传播法[42～44]和调和函数法[45]。

（1）波传播法

波传播法通常采用各网格点与目标点之间的距离为导航函数。1991年，Barraquand给出了一种简单的计算导航函数的算法[42]。几乎同一时间，Lemmon和Glasious描述了一种神经网络的方法计算距离函数[43，46]。Muraca于1996年将距离函数应用于两节机械臂的避障规划，取得了较好的效果[44]。

（2）调和函数法

Connolly等于1991 年利用各种不同类型的调和函数作为导航函数进行了一系列的研究[45，47，48]。调和函数是拉普拉斯（Laplace）方程的解，可以通过简单的迭代过程求出。该方法通过将路径规划问题转化为一个拉普拉斯方程，障碍物和目标位置表示成边界条件。1994 年Stan等证明其迭代计算过程可通过并行计算显著缩短时间，并给出了它的分析解[48～50]。Cannolly在路径规划的基础之上还研究了生物的驱动控制与调和函数之间的关系[45]。

尽管调和函数易于计算，并且没有局部极小值点，但它也存在一些问题。例如，在梯度很小的地方，如果数值算法的迭代过程有限，或者由于环境噪声的影响，很可能丢失最优路径。如果将障碍物表示为Neumann边界条件而不是Dirichlet边界条件时，梯度会有所增加。

4．数学规划方法

数学规划方法通常将避障问题表示成一系列不等式约束，这样，路径规划问题就可以表示成带有约束条件的最优化问题。这类方法的一大优点就是除距离和障碍之外，可以综合考虑多种与路径相关的其他要素，如路径的安全性、可执行性等。由于该最优化问题通常是非线性的，并且带有多个不等式约束，一般需用数值方法进行求解。数学规划方法用于求解路径规划一般计算量都很大，而且受局部最小值的影响，通常只用于局部路径规划，并且借助于神经网络、模拟退火等方法加速计算，避免陷入局部最小值点[51～53]。

5．基于进化计算的规划方法

基于进化计算的规划方法本质上包含在上述的几类方法之中。但由于近年来出现的基于进化计算的路径规划方法较多[54～64]，而且本书的许多工作都是以进化计算为基础，因此把它单独列出来加以讨论。

早期的进化规划算法一般都是直接采用传统的遗传算法，而很少考虑路径规划的特定领域知识[59，60]。随后，文献[58]和[63]主要考虑移动机器人二维路径规划问题；文献[64]和[65]将基于学习的遗传算法应用于机器人路径跟踪和局部导航；Bessiere等采用并行实现方法给出了一种用于动态环境中的进化规划器[62]。所有这些算法采用的都是定长的基因编码方式。

Xiao等于1997 年针对二维空间中的点状机器人提出了一种基于进化的路径规划和导航算法[54]。他们将路径规划和导航结合在一起，既可用于离线路径规划，也可用于实时在线导航。该算法考虑了路径规划的特定领域知识，可以适应于不同的优化准则。同时，通过调整不同进化算子的使用概率，可以自适应于不同的使用环境。

1997年，Chen和Zalzala将遗传算法应用于具有距离和安全等多个准则的移动机器人近似最优路径搜索，成功地解决了多准则的优化问题[63]。他们采用栅格的单元分解方法表示规划环境，用两个栅格化的势场域分别表示目标和障碍。该算法也主要应用于二维路径规划。

2001年，Hocao+和Sanderson针对高维空间的机器人多路径规划问题提出了一种多分辨率表示的进化路径规划器[55，66，67]。该算法直接在工作空间中进行路径搜索，省却了构造C空间的计算。通过采用最小表达规模原理和种群进化技术，该算法可以一次性生成多条路径。

在UAV航迹规划方面，Yi等于1997年利用Fourier级数拟合UAV的航迹，并用遗传算法求解它的系数[68]。2003年，Nikolos等采用B样条曲线模拟UAV的三维飞行航迹，利用进化算法优化B样条曲线的控制点[69]。两种算法都可以生成光滑的三维航迹，但不能处理有关航迹的约束条件。