随着应用场景的日益复杂，机器人对旨在生成无碰撞路径（轨迹）的自主运动规划技术的需求也变得更加迫切。虽然目前已产生了大量适应于不同场景的规划算法，但如何妥善地对现有成果进行归类，并分析不同方法间的优劣异同仍是需要深入思考的问题。以此为切入点，首先，阐释运动规划的基本内涵及经典算法的关键步骤；其次，针对实时性与解路径（轨迹）品质间的矛盾，以是否考虑微分约束为标准，有层次地总结了现有的算法加速策略；最后，面向不确定性（即传感器不确定性、未来状态不确定性和环境不确定性）下的规划和智能规划提出的新需求，对运动规划领域的最新成果和发展方向进行了评述，以期为后续研究提供有益的参考。机器人学是研究如何通过计算机控制装置感知并操纵客观世界的学科，现今已被应用于各个领域，如行星探索中的移动平台、空间机械臂、无人机、自动驾驶汽车等（图1）。设想这样的场景：一架无人机正在高楼耸立的城市中穿行，未知环境要求其应利用新接收到的信息不断修正它的运动；杂乱的障碍物要求其应避免与众多物体发生碰撞；传感器误差、阵风干扰、模型误差、控制约束等则要求真实运动与规划运动间的误差应尽量小。因此为了能在充满未知性和不确定性的真实世界中可靠地完成任务，机器人必须具有自主感知、快速决策、运动规划与控制的能力。其中运动规划作为上层决策与底层控制的连接模块，负责将决策序列转化为控制器可执行的参考路径（轨迹），在机器人研究中占有重要地位。图1 典型的机器人系统运动规划领域早期侧重于处理有障碍物的二维或三维世界中的开环运动规划问题，其结果可以是一条无碰路径，也可以是一条无碰轨迹。前者是几何意义上的连续（光滑）曲线，后者则是这一曲线的时间参数化表达。对机器人而言，路径规划（本文称其为传统运动规划）一般在构型空间（Configuration Space，C-space）内进行，轨迹规划（本文称其为考虑微分约束的开环运动规划）则在状态空间（即构型空间或相空间）内进行。但无论构型空间亦或相空间，都是无限不可数的，故开环运动规划的一个中心主题是将连续空间离散化，进而借助人工智能领域的离散搜索思想，将求解运动规划问题视为在高维自由构型空间（,）或自由相空间中的搜索过程。除一般的可行性问题外，满足某类性能指标最优（如时间最优、路径长度最优等）的开环运动规划问题亦是学者们的关注焦点。一条最优路径往往可参数化为许多条轨迹，它们的速度时间历程各不相同，而最优轨迹仅是其中一条。不幸的是，计算最优路径（轨迹）的时间复杂度往往较高（甚至对某些问题来讲，计算可行路径就已十分困难），很难满足机器人实时规划的需求，这便促使研究人员不断开发新的算法以实现两者间的平衡。另外，经典控制理论的发展历史表明：反馈是应对不确定性的有效手段。但开环运动规划过程常常忽略了这一点，从而容易造成机器人沿规划路径（轨迹）运动时意外碰撞的发生（图2）。反馈运动规划则通过对不确定性进行建模，并将该模型融入规划过程，为机器人的实际运动提供了安全保障。虽然近年关于反馈运动规划的研究取得了一系列进展，但鲜有文章对这一主题进行归纳总结。即使有所提炼，包括反馈运动规划在内的各类内容也已稍显陈旧，而且将运动规划的研究范围局限于基于采样的运动规划（Sampling-based Motion Planning，SBMP）算法的做法无疑限制了读者的视野。图2 运动规划与控制的解耦可能造成意外碰撞根据是否考虑微分约束和反馈，Lavalle的经典专著将运动规划问题分为表1中的4 项子课题，本文则不区分最右侧2项，并将其统称为反馈运动规划。进而在这种分类方式的基础上以单机器人为研究对象，依次总结了现有的传统运动规划、考虑微分约束的开环运动规划和反馈运动规划相关算法，形成了类似于“谱”的运动规划算法归类，便于读者对比分析各种方法间的区别与联系。其中针对解路径（轨迹）品质与求解效率间存在的矛盾，重点详述了如何利用已有信息来加速渐近最（近）优算法。另外则对不确定性建模方式、动态环境中的规划、学习算法与运动规划算法的融合等先进课题的最新成果进行了总结，以期为后续研究提供思路。表1 运动规划问题分类01  传统运动规划设为映射到的拓扑图（可参考图3~图6），其中为图中节点的集合，每个节点相对应一个构型。为图中边的集合，每条边相对应两个构型 间的无碰撞路径。对于所有，定义式中：表示路径的像；为可以通过）到达的所有构型的集合。解决传统运动规划问题的思路正是用包含可数个节点的图结构捕捉的连通信息，并基于此离散结构搜索解路径。由于 的构建过程显然受障碍物形状及其位置分布的影响，故一般可根据是否在中显式表示障碍物区域（），将处理传统运动规划问题的算法分为组合运动规划（Combina⁃torial Motion Planning， CMP）算法和基于采样的运动规划算法两类。1.1 组合运动规划基于显式表示的障碍物，CMP首先构造满足下列条件：1）可达性（Accessibility）：对于任一，可以简单高效地计算一条以其为起点，以中任一点为终点的路径，即，。2）确保连通性（Connectivity-Preserving）：对于起始构型、目标构型及它们在中的连接点、，如果存在一条路径，使得，，那么也将存在一条路径，使得的路图，其或由的胞腔剖分间接生成，如垂直胞腔剖分、圆柱代数剖分等；或通过其他方法直接构造，如可视图法、广义维罗尼图法、轮廓法等。进而利用图搜索算法如Dijkstra算法、A*算法、ARA*算法、D*Lite算法、AD*算法及Theta*算法等寻找解路径。后四者都是A*的变体：ARA*通过放松对启发式的一致性要求并重复使用先前的搜索信息，可快速产生因子可控的次优路径，具有Anytime特性，适用于计算时间受限的静态环境；D*Lite是一种递增搜索算法，其先用A*算法从目标顶点反向计算相关节点的最优路径代价，待环境发生改变后，再以此有效信息为基础进一步调整相关节点的最优路径代价，适用于含动态障碍物的场景；AD*则是结合了ARA*和D*Lite的优点，既具有Anytime特性，又有递增特性，真正实现了动态场景中的实时规划。另外由于A*算法找出的解路径角度往往被网格划分方式所限制，因而其并非真实地形中的最优路径，Theta*通过解除这一约束，可在相同时间复杂度下得到更高质量的解路径。条件1）其实保证了内的任一起始、目标构型对（）均可被连接到中，条件2）则保证了在解路径存在的情况下，搜索总是可以成功。而这正是CMP 完备性的来源，即在有限时间内，算法要么找到一条解路径，要么正确地报告无解。虽然其几乎能解决任何运动规划问题，而且在一些简单情形（如二维世界中，为多边形，机器人仅进行平移运动）下可以高效地得到较好解，但对于大多数具有高维C-space且障碍物数量巨大的问题，较长的运行时间和执行困难使此类方法失去了吸引力。1.2 基于采样的运动规划与CMP不同，SBMP通过碰撞检测模块来避免显式构建，并且利用可数的采样点集或采样序列及满足一定条件的连接方式近似捕捉无限不可数的Cfree的连通特性。尽管其永远不可能知晓的精确形状，但却节省了大量计算时间，是一种行之有效的折中方式，可用于高维空间中的运动规划。不过与此同时也牺牲了算法的完备性，并代之以更弱的概念：使用随机采样方法的运动规划算法是概率完备（Probabilistically Complete）的，使用确定性采样方法的运动规划算法是分辨率完备（Resolution Complete）的。为满足弱完备性要求：①中的采样序列必须稠密；②算法的搜索过程应具备“系统性”。更多关于 SBMP产生的历史原因和早期发展过程可参考Lindemann和Lavalle的综述文章。对于给定数个起始-目标构型对的多疑问（Multiple-Query）运动规划问题，如果环境结构不发生改变，则非常有必要花费时间对模型进行预计算以生成路图，从而提高后续搜索效率。概率路图法（Probabilistic Roadmap，PRM）是其中的典型代表，它最初是为应对高自由度运动规划问题而发展的，算法流程如图3所示。PRM构建的路图可看作是对CMP所导出路图的一种近似，因此也常被与CMP共同归入基于图搜索的运动规划算法中。Kavraki等通过对简化的PRM（Simplified PRM，s-PRM）进行分析，建立了算法失败概率与路径长度、路径和障碍物间距、采样点数量之间的函数关系，其中随的增加而线性增加，随的增加而指数减小到0，从而证明了PRM的概率完备性。但由于路径特性很难提前得知，故该完备性分析方法不易使用。另一分析方法则借助ε-goodness、β-lookout和（ε，α，β）-expansive的概念，证明算法失败概率为图3 PRM算法流程式中：为正常量。从式（2）不仅能得出与的指数关系，而且可以发现如果暗含可视特性的越大，那么完成求解所需的采样点就越少，算法运行时间就越短。因为引起可视特性下降的狭窄通道不可能偶然出现，故实际中遇到的许多都具有良好的可视特性，即相应的较大。另外可视特性是用体积比率定义的，而不直接依赖于C-space维数，这便解释了为什么当维数在一定范围内增加时，PRM仍能较好地运行。

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。