《1 概述》

1 概述

美国MIT著名机器人科学家认为自主机器人导航应该回答三个问题[1]，"Where am I？""Where I am going？"，"How should I go there？"，分别描述了机器人定位，规划和控制三个问题，机器人运动规划是解决机器人导航的三个核心问题之一。

对机器人运动规划的研究是20世纪60年代出现的[2]，1978年Lozano-Perez和Wesley首次引人构型空间（C-空间）的概念构造规划器[3]，对于现代的运动规划问题是一次划时代的革命。在C-空间中，每一个位姿代表着机器人在物理空间中的位置和方位，机器人被当作一个点，运动规划问题就变成在位姿空间中寻找一条从起始位姿点到目标位姿点的连续路径。1987年，J. P. Laumond[4] 将机械系统中的非完整性引人到机器人运动规划中解决自动泊车问题。自此，非完整运动规划成为一个新的研究热点一直延续到今天。

移动机器人路径规划可以当作运动规划的一个简单特例。所谓”路径”是指在位姿空间中机器人位姿的一个特定序列，而不考虑机器人位姿的时间因素；而“轨迹”与何时到达路径中的每个部分有关，强调了时间性[4,5]。机器人运动规划就是对“轨迹”的规划，按照环境建模方式和搜索策略的异同，可将规划方法大致上分成三类，分别是基于自由空间几何构造的规划，前向图搜索算法和近年兴起的以解决高维姿态空间和复杂环境中运动规划为目的的基于随机采样的运动规划。

基于几何构造的规划方法有可视图[6]、切线图[7]、Voronoi图[8]以及精确（近似）栅格分解[9.10]等方法。

路径规划是搜索的过程[11]。不管何种规划算法，最终都将归结到在某个空间中搜索一条满足某准则的连续路径问题。利用几何构造的手段描述环境的自由空间，一般都会构成图（栅格被当作一类特殊的图），最终完成轨迹的规划需要图搜索这个很重要的步骤。前向图搜索算法是从起始点出发向目标点搜索的算法，常用的包括贪心算法[12]、Dijkstra算法[13]、A.算法[14]、D*算法[15]（Dijkstra算法的变种）以及人工势场法[16]等等。

上述算法的计算复杂度与机器人自由度成指数关系，不适合于解决高自由度机器人在复杂环境中的规划[17~19]，而且都不适合于解决带有微分约束的规划。

基于随机采样的规划始于1990年Barraquand和Latombe提出的RPP（randomized potential planner）规划算法[20]，用于克服人工势场法存在的局部极小和在高维姿态空间中规划时存在的效率问题。1994年PRM（probabilistic road map）[21]和1998年RRT（rapidly-exploring random tree）[22]两种基于随机采样的运动规划方法的出现已经掀起一股对机器人运动规划研究的新热潮。这些算法适合于解决高自由度机器人在复杂环境下的运动规划问题。

笔者总结的规划算法主要面向自主移动机器人的运动规划，如足球机器人、人型移动机器人、自主地面车、自主水下机器人、无人机等，部分算法对工业机器人等也适用。

《2 规划问题的形式化描述》

2 规划问题的形式化描述

无论机器人路径规划属于哪种类别，采用何种规划算法，基本上都要遵循以下步骤：

1）建立环境模型，即将机器人所处的现实世界进行抽象后建立相关的模型；

2）搜索无碰路径，即在某个模型的空间中寻找合乎条件的路径的搜索算法。

移动机器人的运动规划问题可以形式化地描述为如下的推理机[17]：

其中X是搜索空间；是初始位置（姿态、状态等）；XgoEX是目标区域，即目标位置（姿态、状态等）的集合；对于每一个状态，U（x）是在状态x 所有备选控制输入集合；状态转换方程f 定义了状态对控制输入的响应。通常，如果时间是离散的，可以用函数f : X×U→X 表示；如果时间是连续的，状态转换方程可以定义成一个偏微分方程；是由一些不可通行的非法状态组成的集合，即C-空间中的障碍集合。

为了定义规划问题的解决方案，考虑一组行为控制序列，由此序列导出一个状态序列：

如果并且，那么称序列为规划问题的一个解决方案。机器人运动规划的目的就是要找到一组满足一定准则的行为控制序列。

《3 规划算法的评价标准》

3 规划算法的评价标准

在总结大量经典算法的基础上，笔者认为好的规划算法通常应该具有以下特性：

合理性——返回的任何路径都是合理的，或者说任何路径对控制机器人运动都是可执行的（也说是“可达”的）

完备性[23]——如果客观上存在一条从起点到达终点的无碰路径，该算法一定能找到；如果环境中没有路径可通行，会报告规划失败。

最优性——算法规划的结果路径在某个测度（如时间、距离、能量消耗等）上是最优的。

实时性——规划算法的复杂度（时间需求、存储需求等）能满足机器人运动的需要。

环境变化适应性——算法具有适应环境动态改变的能力，随着环境改变，不必要全部重新计算。

满足约束[17]——支持移动机器人运动时的完整性和非完整性运动约束。

《4 通用运动规划方法分类、比较及研究进展》

4 通用运动规划方法分类、比较及研究进展

机器人需要对感知到的局部外部环境或者事先已知的全局环境进行建模，一般以边表述和体表述为主[17]。前者需要写出一些方程描述某个区域，后者需要描述某个区域内包含的所有的点。它们都可以用来描述自由区域和障碍区域。搜索策略基本上分为确定搜索方式和随机搜索方式两种。

从环境模型的表示和搜索策略角度考虑，将移动机器人通用的路径规划算法分为如下几类：

《4.1 基于自由空间Cfree几何构造的规划方法》

4.1 基于自由空间Cfree几何构造的规划方法

基于自由空间几何构造的规划方法基本思想就是构造某种图来描述环境的自由空间Cfree，从图上找到满足某种准则的最优路径。此法一般包括两阶段：第一阶段构造一个描述自由空间关系图，第二阶段按照一定的准则（最短距离、最少时间等）寻找一条最优路径。其中，图的构造比较重要，搜索算法一般采用Dijkstra算法或A*算法。

可视图法  1987年就被广泛应用的算法[6]，J. C. Latombe[24]对此进行了详细描述。在C-空间中，以多边形障碍物模型为基础，任意形状障碍物用近似多边形代替，用直线将机器人运动的起始点qinit和所有C-空间障碍物的顶点以及目标点qgoal连接，并保证这些直线段不与C-空间障碍物相交，形成了一张图，称为可视图。然后采用图搜索算法寻找从起始点到目标点的最优路径，搜索最优路径就转化为从起始点到目标点经过这些可视直线的最短距离问题。可视图构造的时间复杂度是O（n2 lg n）或者O（n2），n代表障碍物的顶点总数。

Voronoi图法 计算几何中的很多技术被引用到机器人的运动规划中来，基于Voronoi图的路径规划就是一个典型的例子[8，24，25]。在C空间中，根据已知的障碍分布情况，取障碍物的顶点、边界构造出C空间中障碍分布的Voronoi图，连接机器人运动的起始点qinit以及目标点qgoal到已经构造好的Voronoi图上，构成环境中自由空间“骨架”的图，在此基础上，基于图的搜索算法可以找到连接起点和终点的最短路径。Voronoi图构造的时间复杂度是O（n lg n），实时性较好，生成的路径相对比较安全，远离障碍，并且路径比较平滑，合理性也较好，但是不能保证路径最优。

H. Choset等对广义Voronoi图（GVG，generalized Voronoi graph）在基于传感器的路径规划方面进行了深入研究[26]。

栅格分解法  是目前研究最广泛的路径规划方法之一[27]。该方法将机器人的工作空间分解为多个简单的区域，一般称为栅格。由这些栅格构成一个显式的连通图，或在搜索过程中形成隐式的连通图，然后在图上搜索一条从起始栅格到目标栅格的路径。一般，路径只需用栅格的序号表示。按照栅格划分的方式又分为确切的和不确切的两种。

确切的栅格法[9,24] 将机器人工作环境分解成一系列固定大小的栅格单元，环境被量化成具有一定分辨率的栅格序列。赋予每个栅格一个通行因子后，路径规划问题就变成在栅格图上寻求两个栅格节点间的最优路径问题。在该方法中，分辨率直接影响着环境信息存储量的大小和规划时间的长短。

在不确切的栅格分解法[10,24] 中，所有的栅格都是预定的形状，通常为矩形。整个环境被分割成多个较大的矩形，每个矩形间都是连续的。如果大矩形内部包含障碍物或者边界，则又被分割成4个小矩形，对所有稍大的栅格都进行这种划分，然后在划分的最后界限内形成的小栅格间重复执行程序，直到达到解的界限为止。这种分解的结构称为“四叉树”。CMU已将这种不确切的栅格描述法用于越野环境下自主地面车导航，取得很好效果[28]。

切线图法  以多边形障碍物模型为基础，任意形状障碍物用近似多边形替代，在自由空间中构造切线图。文献[7]采用移动线和扫描线相结合的方法构造切线图。采用“移动线算法”检测障碍物顶点之间的所有公切线，然后利用一种“扫描线算法”测试已知公切线与障碍物之间是否存在交叉点，如果存在，滤除这些公切线，剩下的公切线构成的图被称为切线图。构造切线图在最坏情况下的时间复杂度为O（[M + R]N+ M2lg M），其中N表示障碍物顶点数，M表示个点构成的凸曲线的条数，R表示开凸曲线的滚动数。最后，搜索最优路径的问题转化为从起始点到目标点经过这些障碍物切线的最短距离问题。文献[29]在此基础上，采用跳跃式扫描技术按需扩展搜索图，使机器人能在行进中构造切线图，可以较好地适应未知和动态环境。

基于自由空间几何分解的基本规划算法的性能，在满足约束方面很差。在机器人自由度DoF<4时，实时性方面Voronoi图很好，其他算法也比较好。其他性能对比见表1。表1可见，基于自由空间几何构造的方法完备性较好，Voronoi图法和不确切的栅格分解法规划出来的路径的合理性比可视图法和切线图法好一些，不确切的栅格分解法的路径最优性比其他算法好。

《表 1》

表 1 基于自由空间几何分解的基本规划算法性能对照表

Table 1 The performance comparison of planning algorithms based on free space geometry construction

《4.2 前向图搜索算法》

4.2 前向图搜索算法

描述地形的图构造出来后，最优路径搜索显得非常重要。下面对图的常用搜索算法进行总结。

贪心算法  是最简单的图搜索算法[12,14]，是一种典型的集中考虑局部费用最小化，而忽略全局最优的搜索算法，该算法不能保证一定收敛到目标节点，就是说，该算法不完备。

Dijkstra算法[13,14]   是最短路径搜索的经典算法，首次出现在1959年，随后广泛应用在最短路径搜索问题中。该算法可以在显式图中找到从源节点到任意节点的最短路径，或者从目标节点到图中任意节点的最短路径。如果该算法在到达目标节点时结束，那么一定可以找一条从源节点到目标节点的最短路径。算法复杂度是O（n2）。多年来，研究者不断改进算法，遗传算法实现Dijkstra算法的最优时间上界是O（min{m =n lg n，m lg lg C，m + n（lg C）1/2}），其中C是满足一定属性的常数。

A*算法  A*算法[14]是应用极广的隐式图启发式搜索算法，其距离函数的定义具有启发性，在栅格结构的数据集上性能相当好。其距离函数的定义一般为，即某个栅格（节点）c处的距离f（c）定义为从起点至c的距离g（c）与从c到目标点距离的估计之和。如果启发式估计是真实路径费用的下界，只要该路径存在，A*算法的可接纳性保证它可以得到一条最优路径。J. Pearl等[30]全面研究了A*算法的平均计算量和距离函数的估计精度之间的关系，得出A*的计算量为多项式的充要条件是距离函数必须具有“对数”阶精度。但在实际应用中这个要求很难达到，A*算法基本上未能克服计算量的指数爆炸困难。已证明对于平面避障问题A*是多项式时间算法，但当环境复杂、规模较大时是低效率的，经常几乎要扩展整个规划空间才能找到目标。针对A*的这一缺陷，人们提出了许多改进措施，如采用并行机制、分层规划机制等。

D*算法  上述的图搜索算法只限于在静态图上的搜索，Stentz发展一种D*算法[14,31]可以在动态图上搜索到最短路径。通常，该算法能够在搜索动态图目标节点的过程中处理变动弧的费用，假设弧的费用在遇到障碍时可能会发生变化。需要指出，D*在静态图中的搜索情况将退化为Dijkstra算法，时间复杂度为O（n2），Stentz表示，“若D*算法在搜索结果的过程中，费用参数可以随之改变的情况下，它可以处理任意的路径优化问题"。而且它还说[31]，"当参数的变更发生在起始点附近时，算法效率最高”。该算法在CMU的越野环境导航实验中取得了很多成果[28]。

人工势场法  物理学中的场的概念也被引进来描述机器人在空间中的几何结构，引导机器人向目标行进。这些场包括常见的势场，还有距离场[32]以及来自于水力分析的基于流函数[33]的规划算法。国内对后两种算法研究甚少。人工势场法[34]最初由Khatib[16]提出，其基本思想是引入一个称为势场的数值函数来描述机器人空间的几何结构，通过搜索势场的下降方向来完成运动规划。势场分为两部分，即目标位姿产生的吸引势和障碍物产生的排斥势。吸引势使机器人向目标位姿靠近，排斥势使机器人绕开障碍物，二者的叠加构成机器人运动的虚拟势场，势场的负梯度作为作用在机器人上的虚拟力，该力“推动”机器人向着目标作无碰运动。文献[35]通过引入虚拟障碍物使搜索过程逃脱局部极小点，但该措施可能引人新的局部极小点，同时增加了算法的复杂度。文献[20]采用随机运动逃脱局部极小点，该算法称为“随机势场法”。诸如此类的启发式搜索算法还有很多，如爬山算法[36]、波传播算法[37]等等。主要的常见前向图搜索算法，在满足约束方面，人工势场法较差其他都很差，而在DoF<4时环境变化适时性都较好，其他部分性能对照情况见表2。

《表 2》

表 2 前向图搜索算法性能对照表

Table 2 The performance comparison of forward graph search algorithms

Dijkstra算法适合于静态显式图的搜索，A*算法适合于静态隐式图的最短路径搜索，D*算法适合于解决动态图的最优搜索，人工势场法适合于解决局部规划问题。图的前向搜索算法和图的后向搜索算法结合，可以构成图的双向搜索算法[17]。

《4.3 基于随机采样的运动规划方法》

4.3 基于随机采样的运动规划方法

前面介绍的规划算法基本上属于相对确定的方法，就是说对于同一环境任意两次不同规划，结果都相同。但是即使一类简单的规划问题，比如一个点机器人在三维多边形障碍环境中运动，其规划复杂度在1988年就已经被J. F. Canny证明是NP复杂度[38,39]。通常，规划问题的复杂度与机器人的自由度成指数关系，与环境中障碍物的规模成多项式关系，规划问题随着机器人自由度增多会出现“维数灾难（dimension curse）"问题，因而以上确定性算法不适合解决高自由度机器人在复杂环境中的实时规划[17~19]。为了解决存在的问题，科学家们采用基于在规划空间（如位置空间、姿态空间、状态空间等）中随机采样的方法，以损失完备性为代价提高算法的执行效率[40,41]。

随机路规器  1990年，Barraquand和Latombe设计一种随机路径规划器（RPP）[20]被认为是基于随机采样的运动规划的开端[41]。该算法在人工势场法的基础上通过执行随机步骤使其摆脱局部极小。定义h（v）代表吸引势和排斥势合成的启发式势函数（从某节点至目标点的费用估计）。对于RPP规划器来说，定义三种模式：DESCEND，ESCAPE和BACKTRACK，最初时，规划器处于DESCEND模式，从vint开始按照梯度下降的原则产生新节点。在DESCEND模式下，在图G中产生一个新节点，在的邻域内且使得h（v）最小的方向上产生一个新节点作为规划的下一个节点。如果陷入局部极小，通过梯度下降产生新节点的操作会失败。此时，规划器转入ESCAPE模式，试图摆脱局部极小。在ESCAPE模式下，执行一个随机步骤创建新节点，结束后转向DESCEND模式。如果在ESCAPE模式下，一定步数内，连续随机产生新节点失败，规划器将转A BACKTRACK模式。在此模式下，在图G中，从上次产生的最新节点到图G的起始节点之间随机选择一个节点，从该节点开始规划器进入ESCAPE模式。该算法[17]在陷入局部极小时通过执行随机步骤能有效地克服局部极小的限制，能解决高维自由度机器人的规划问题，但是该算法的正确运行需要调整很多参数，如果部分参数设置不当，容易导致算法陷入局部极小，如果次数太多，也极大地影响算法性能。

概率路标算法  自1994年开始，Lydia Kavraki和Jean-Claude Latombe发表了一系列在位姿空间中随机采样进行预处理的快速路径规划算法，即概率路标算法（PRM）[21,42]。其主要思想是用一个随机路标图来表示机器人系统运行的自由空间Cfree，然后在此图中为机器人系统搜索到一条可行的路径，它是一个多重查询算法。这一随机路标图即是为机器人系统所建立的地图，该网络中节点代表在Cfree中为机器人随机选取的位姿节点之间的连线，即图中的边，代表机器人不同位姿之间的可行路径。

一般的PRM规划方法的操作过程大体可分为学习阶段（预处理阶段）和搜寻阶段[21]。学习阶段的主要目的是在Cfree中为机器人建立一张地图。在该阶段，首先以随机的方式在Cfree中选取大量的机器人位姿，构成地图中的节点集N，然后由一个局部规划器来为N中的每个节点寻找它们的近邻节点，并为它们建立连接，从而构成地图中的边集E。经过学习阶段建立起来的地图是一张较大的无向图R=（N，E）。在搜索阶段，首先将规划任务的起始点qinit和目标点qgoal加入节点集N，并由局部规划器为其寻找近邻节点并建立连接，从而在地图R中形成了若干个连通图。如果起始点和目标点在同一个连通图中，则存在机器人运动的可行路径，然后在地图R中采用某种搜索算法在起始点qinit和目标点qgoal之间搜索一条通路，即为机器人的可行路径。如果起始点和目标点不处于同一个连通图中，则回到学习阶段进行节点扩充操作，来增加地图在Cfree的“困难地区（如狭窄通道等）”的连通性。上述的两个阶段，可以交错反复进行，以提高效率。

PRM算法因为在处理狭窄通道处的完备性太差等缺陷，很多学者对其进行改进，产生很多变种，如 MAPRM[43]，OBPRM[44]，Lazy-PRM[45]，Visiblity PM[46]等等。该算法在动态障碍物、高维状态空间的环境中的运动规划已经得到广泛的应用[48]，但该算法未能解决移动机器人运动中存在微分约束等问题，导致其结果路径合理性较差[17]。

Emmanuel Mazer提出的Ariadne线索法（Ariadne's clew algorithm）[47]对路径规划中运用随机采样技术产生极大的推动作用。该算法生成一棵从起始节点至目标节点搜索树的单一查询算法，在生成树的每一次迭代过程中总是尽可能多的探测新的区域。该算法规划器设置两种工作模式，分别为SEARCH和EXPLORE，它们在每次迭代过程中交替出现。首先检测在SEARCH模式下能否找到一条从qinit到qgoal的简单路径；如果简单路径不存在，那么就在EXPLORE模式下随机产生一个新节点，在SEARCH模式下从此节点到目标节点寻找一条简单路径，并采用高并行性的遗传算法解决中间的优化问题。如此循环下去，直至到达目标点结束。如果环境中路径是存在的，Ariadne's clew算法可以找到它，也就是说，该算法是确切的，而且采用EXPLORE模式可以防止算法陷入局部极小。但是在EXPLORE模式下，采用了遗传算法产生新节点的优化问题非常费时，而且该算法也需要人为调整参数[17,41]。

膨胀空间法  D. Hsu和J. C. Latombe等介绍了一种用于扩展姿态空间的单一查询规划算法——膨胀空间法（EST，expansive spaces）[48]。EST规划器从初始节点开始生成一棵树，树中每一个节点x有相应的权值，被定义成Nd（x），表示以节点x为中心，d为半径的邻域内顶点的数目。在每一次迭代过程中，该树以一定的概率选择一个节点进行扩展。节点x被选中的概率是1/w（x），w（x）代表权函数。对于给定的节点x，在其邻域Nd（x）内有K个节点被采样到，这样每一个节点的权函数就可以计算出来。每一个新节点y以概率1/w（x）被保持，并且规划器会试图将每一个被保持的节点连接到x。这样，该算法和Ariadne's clew算法中的EXPLORE模式相似，都试图将搜索树扩展到自由空间中未被探测到的区域。主要的缺点在于算法需要d和K参数，在不同的环境中，对它们的选择受主观因素影响较大[17,41]。

快速随机搜索树算法  1998年美国伊利诺斯大学（UIUC）的科学家S. M. LaValle 在最优控制理论、非完整规划和随机路径规划的基础上提出了一种单一查询的快速随机搜索树算法（RRT）[17,22,49]。基本RRT算法是一种增量式前向搜索算法。

搜索树构造阶段，从初始位姿（状态）点Xinit出发构造搜索树T，在位姿空间中随机选择一个位姿（状态）点Xrand，遍历T，依据距离ρ，找到T上离Xrand最近距离的节点Xnear，然后在控制输入集U里选择一个控制输入（如转向角、速度等）作用在Xnear上，机器人沿着Xnear到Xrand依照状态转换方程产生满足全局约束的候选路径集合，经历时间，到达一个新状态构成Xnew集合，依据距离ρ，选择使得Xnew到达Xrand距离最近的控制输入u作为最佳控制输入。依次产生新状态，直至到达目标状态，搜索树构造结束。

路径产生阶段，从目标状态点出发，找到父亲节点，依此直至到达起始状态点，即树根，就规划出从起始状态点到达目标状态点满足全局和微分约束的路径以及在每一时刻的控制输入参数。因为在搜索树的生成过程中充分考虑了机器人客观存在的微分约束（如非完整约束、动力学约束、运动动力学约束等），因而算法规划出来的轨迹合理性非常好，但算法的随机性导致其只能概率完备。

为了提高算法的效率和性能，不断对该算法进行改进。如为了提高搜索效率采用双向搜索树（Bi-RRT）[4.49]，从起始点和目标点并行生成两棵RRT，直至两棵树相遇，算法收；Kuffner和LaValle 又提出RRT-connect [50]，使得节点的扩展效率大大提高；运动规划中，距离的定义非常复杂，Peng Cheng[51]研究了在RRT生长过程中距离函数不断学习的算法以降低距离函数对环境的敏感性；考虑到基本RRT规划器得到的路径长度一般是最优路径的1.3~1.5倍，英国的J. de Smith [52]研究了变分法技术使其达到最优。该算法在动态障碍物、高维状态空间和存在运动学、动力学等微分约束的环境中的运动规划已经得到广泛的应用[53,17]。

Kostas E. Bekris和Lydia E. Kavraki等在综合PRM以及RRT优缺点的基础上，提出一种组合多重查询与单一查询相结合的PRT算法[54]。采用与PRM类似的方法在环境中随机采样，使用功能强大的Bi-RRT作为局部规划器连接采样点构成路标图。该算法在一个有狭窄通道的环境中，其规划性能相对于PRM和RRT都有显著提高。

随机算法以损失完备性为代价来提高执行效率，适合于解决高自由度（DOF>6）机器人在复杂环境中的运动规划，合理性较好[49]。基于随机采样的运动规划方法的部分性能对比见表3。

《表 3》

表 3 基于随机采样的运动规划方法性能对照表

Table 3 The performance comparison of random sampling based motion planning algorithms

表3可见，基于随机采样的运动规划算法都不是完备的，但是算法收敛的时间往往与采样点的个数有关，并不简单地只与自由度成指数关系。

上述基于随机采样的运动规划方法大体上可分为多重查询算法和单一查询算法。前者的典型代表是PRM算法，RRT算法是后者的典范。在MSL运动规划库上运行这两种算法，在同一环境下针对狭窄通道均具有良好的性能。但PRM算法未考虑约束，轨迹的合理性明显不如RRT算法。

《4.4 其他智能化规划方法》

4.4 其他智能化规划方法

路径规划是环境模型和搜索算法相结合的一种技术，规划过程既是搜索的过程，也是推理的过程。人工智能中的很多优化、推理技术也被运用到移动机器人运动规划中来，如遗传算法、模糊推理以及神经网络等在移动机器人运动规划中起到很大的作用[55]。

遗传算法规划器  遗传算法作为一类重要的进化算法在移动机器人运动规划方面的应用获得了大量的成果[56~58]。遗传算法求解路径规划问题是将路径个体表达为路径中的一系列中途点，并转换为二进制串。首先初始化路径群体，然后进行遗传操作，如选择、交叉、复制、变异。经过若干代的进化以后，停止进化，输出当前最优个体作为路径下一个节点。该算法的优点是，路径可以收敛到全局最优或者近似最优；缺点是进化速度难以控制，难以满足实时需要，需要的经验参数太多，不利于自动处理。

模糊规划器  模糊逻辑[59]运用近似自然语言方式，可以很好地处理数据的不确定性和非精确性，克服噪声和误差，实现输入输出之间的映射关系。模糊规划器利用反射式导航机制[60,61]，将当前环境障碍信息作为模糊推理机的输入，推理机输出机器人期望的转向角和速度等。该方法在环境未知或发生变化的情况下，能够快速而准确地规划机器人局部路径，对于要求有较少路径规划时间的机器人是一种很好的导航方法。但是，其缺点是当障碍物数目增加时，该方法的计算量较大，影响规划结果，而且该规划器只利用局部信息作出快速反应，较容易陷入局部极小。

神经网络规划器  近年来，科学家一直致力于将机器学习的技术运用到机器人中来[62]，或者说致力于依靠智能机器人技术来推动机器学习的发展，事实上，它们是密不可分的。神经网络在机器导航中曾经取得过辉煌的成就[63,64]，在机器人运动规划中也有大量的研究成果[65~68]。其基本原理是将环境障碍等作为神经网络的输入层信息，经由神经网络并行处理，神经网络输出层输出期望的转向角和速度等，引导机器人避障行驶，直至到达目的地。优点是并行处理效率高，具有学习功能，能收敛到最优路径。

这些智能化推理方法与基于几何构造的方法类似，随着机器人自由度的增加和环境复杂度增强，都存在效率问题。

《5 结语》

5 结语

移动机器人的运动规划算法是伴随着移动机器人的发展为满足机器人的需要而发展，当今无人地面、水下、空中机器人发展迅速，足球机器人比赛如火如茶，并且机器人正朝着微小型化和多机器人协作方向发展。随着星球探测和无人战争的需要，对机器人的研究也越来越注重于在崎岖地形和存在着运动障碍的复杂环境中自主导航[69,70]。为了满足移动机器人发展的需要，运动规划正在并且将会向高维自由度机器人、多机器人协调、动态未知环境中的规划发展[17]。基于随机采样的运动规划方法联合其他运动规划方法的智能化规划方法将是研究的重点和热点。

对通用规划算法的比较可见，对移动机器人运动规划的研究和应用，应着重注意以下几个方面：

1）自由度较少的机器人在简单环境，如室内、室外平地、平直道路等，或者长程起伏的越野环境中低速导航时，可不必考虑机器人的动力学特征，基于自由空间几何构造和图搜索相配套的算法效率更高，实用性较强，算法在合理性方面的缺陷可通过控制策略弥补[28]。

2）自由度较少的机器人在复杂环境，比如崎岖的越野地形、复杂的水下环境中，高速导航时，比如军事应用、野外营救等，对导航的实时性要求很高，而且必须考虑机器人的运动动力学特征[70]。

3）自由度较高的机器人，比如火星车[71]、航天飞机[17,49]等，在复杂环境中自主导航时，对算法的完备性要求相对不高，在规划失败时，可以允许重新规划。为了保证算法的执行效率，确定性算法并不适用，基于随机采样的规划算法解决此类问题的能力更强。但在保证算法效率的前提下，尽可能提高算法的完备性，以实现更加可靠的规划。

4）应该寻求智能规划器与基于几何构造和随机采样算法相结合的策略，以减少规划算法的参数选择和规划过程的人工干预，并且优化算法使其达到或接近某项指标（如时间、距离、能量消耗等）的最优。