当机器人在含有静态障碍物或动态障碍物的未知环境中工作时，突然出现的障碍物一般只会对之前路径的一部分产生影响，而剩余部分对于接下来的搜索仍然有效。若能充分利用这一部分有效信息，无疑可以加速重规划过程（类似于D*Lite算法和 AD*算法）。ERRT用之前可行路径的Waypoint进行偏置采样，但每次重新生成采样树的方式降低了算法效率。Dy⁃namic RRT（DRRT）则在ERRT的基础上融合D*算法的思想，从目标构型反向搜索可行路径，且仅丢弃发生碰撞的构型及其子节点，提高了采样树的重建速度（参见图8）。与DRRT完全删除被障碍物影响的分枝不同，Mul⁃tipartite RRT（MP-RRT）依然保留这些不连通分量，并试图将其重新连接到采样树上。Vanden Berg等结合PRM与AD*算法：首先构建一个仅考虑静态环境的路图，通过简单预测动态障碍物轨迹，以Anytime方式从目标反向搜索次优轨迹。若执行轨迹时环境发生改变，则更新路图及启发式，修复规划轨迹。Ferguson和Stentz也已将AD*的思想扩展至解决单疑问运动规划问题的RRT算法中。图8 DRRT算法流程复用之前有效的搜索信息虽然可以加速算法，但前述的反应式避障（Reactive Avoidance）方案同时也可能造成机器人在某些情况下不断地进行重规划，从而增加完成任务所需的时间。相比之下，利用感知到的信息预测动态障碍物轨迹，并与已有运动规划算法进行融合显然是一种更好的避障手段。该规划框架可以提高解路径的品质（即延长路径可行性的持续时间），降低重规划的频率。其中的关键技术是运动物体未来行为或轨迹的预测，现有文献中的解决方案可以分为基于物理定律的方法（即感知-预测方案）、基于模式的方法（即感知-学习-预测方案）和基于规划的方法（即感知-推理-预测方案）3类。前者根据牛顿运动定律显示地建立单个或多个动力学或运动学模型，并通过某种机制融合或选出一个模型进行前向仿真，以达到轨迹预测的目的；中者适用于含未知复杂动态的环境，其通过用不同的函数近似器（即神经网络、隐马尔可夫模型及高斯过程等）拟合数据来学习待预测目标的运动行为；后者则融合了理性智能体的概念，即假设智能体在长期运动过程中需最小化一个与其一系列行为相关的目标函数，并计算能使智能体达到这个目标的策略或路径猜想。其中目标函数可以预先指定，亦可通过学习得到（如利用逆强化学习技术等）。更多详细内容可参考 Lefe⁃vre和Rudenko等的综述文章，此处不再赘述。1.2.5 利用学习算法加速传统运动规划问题的求解过程机器学习方法与传统运动规划算法的结合最近已成为研究人员的关注热点，此类方法的优势主要体现在两个方面：①相较传统运动规划算法，能更有效地找到近优路径；②可直接基于原始图像进行路径规划。一些文章已将深度学习术如收缩自编码器（Contractive Auto En⁃coder，CAE）、条件变分自编码器（Condi⁃tional Variational Auto Encoder，CVAE）、卷积神经网络（Convolutional Neural Network，CNN）、图神经网络（Graph Neural Networks，GNN）及它们的变体成功应用于SBMP中，且大多数结合方式都聚焦于①用神经网络编码C-Space，并改善SBMP的采样点分布；②直接端到端地生成路径。Deep Sampling-based Motion Planner（DeepSMP）由编码器和采样点生成器构成，前者用原始点云数据作为CAE的输入以将障碍物空间编码为不变的、鲁棒的特征空间；后者用RRT*产生的近优路径训练基于Drop⁃out的统计前馈深度神经网络，使其能在给定起始构型、目标构型、障碍物空间编码信息的情况下，在包含解路径的构型空间区域内为 SBMP迭代生成采样点。Neural RRT*通过学习大量由A*算法生成的最优路径来训练CNN，该模型可为新的路径规划问题快速提供最优路径的预测概率分布，用于指导RRT*的采样过程。Ichter等认为解路径仅依赖于由C-space结构决定的几个关键构型。因此其通过图论技术识别这些关键构型，并仅用局部环境特征作为CNN的输入来学习预测关键构型，从而提升了PRM算法的性能。其在另一文章中用以往成功的规划结果和机器人经验训练CVAE，然后根据给定的初始构型、目标区域和障碍物信息，可以对CVAE的隐空间（Latent Space）进行采样，并将其投影到状态空间中更有希望包含最优路径的区域。但这种预测最短路径采样点的做法其实把所有负担都压给了 Learner，任何由近似或训练-测试不匹配造成的误差均可使算法失效。故LEGO提取多条不同近优路径上的瓶颈点，并以其作为CVAE的训练输入数据。针对CNN和全连接网络（Fully-Connected Network，FCN）容易丢失环境结构信息而引起的泛化不良问题，Khan等利用GNN的置换不变特性鲁棒地编码C-space 的拓扑结构，并计算采样分布的参数以生成采样点。实验结果表明：在学习关键采样点方面，GNN-CVAEs的表现大大优于CNN，而GNN则优于在高维空间中规划的FCN模型。除了用原始点云数据和C-space障碍物信息作为输入外，利用CNN 学习对象级语义信息产生的采样分布也可以改善未知环境中的导航结果。与上述偏置采样点分布的方法不同，MPNet则直接生成可行近优路径。其由编码网络（Enet）和规划网络（Pnet）组成，前者将机器人环境信息编码入隐空间，而后者则利用起始构型、目标构型和Enet作为输入生成路径。除深度学习外，强化学习（Reinforcement Learning，RL）在运动规划领域也有一些成功应用的案例。Q-function sampling RRT（QSRRT）根据学习到的状态-行为值函数（Qfunction），提出Softmax节点选择方法，加速了RRT的规划过程并避免陷入局部极小值。Chen等建立了一个基于Tabular Q-learning和值迭代网络（Value Iteration Networks，VIN）的可学习神经扩展算子，以为基于树的运动规划算法学习有潜力的搜索方向。Bhardwaj等将Lazy搜索中边的选择问题建模为马尔可夫决策过程（Markov Decision Process，MDP），并引模仿学习（Imitation Learning）进行求解。Zhang等利用MDP建立拒绝采样模型，并通过策略梯度方法优化采样分布以降低如碰撞检测次数和树的尺寸之类的规划代价，从而得以加速现有的最优运动规划器。综上，尽管基于学习的技术在运动规划领域取得了一些进步，但此类方法在未经历环境中的性能表现还有待验证。根据以上关于传统运动规划问题的讨论可知：相比CMP，SBMP取得成功的原因在于其以牺牲完备性为代价，换取对复杂的连通性拥有较强的表示能力（即通过“采样”的方式构建包含解路径的离散结构），而非最初版本中所带有的“采样随机性”和“搜索盲目性”。相反该特性恰恰使算法抛弃了大量可用的有效信息，阻滞了性能的进一步提升。因此针对不同场景，如何在SBMP算法的设计过程中妥善地 融入1.2.1~1.2.5节的5类信息，从而提高解路径品质并避免在无价值节点上浪费大量计算时间，将是传统运动规划研究中要考虑的重要问题。02　考虑微分约束的开环运动规划大多数运动规划问题都会涉及来自机器人运动学或动力学的微分约束。一般的处理方式是先在规划过程中忽略这些约束，并通过传统运动规划算法生成几何可行路径，然后再在问题的改进过程中利用轨迹规划/轨迹优化技术处理它们。虽然这种解耦规划在许多情况下可以节省大量计算时间，但同时也丢失了完备性和最优性保证。更好的选择是在规划过程中直接考虑微分约束，这样便可得到服从系统自然运动特性的轨迹，同时降低反馈控制器的跟踪误差。此类问题一般也被称为 Kinodynamic Motion Plan⁃ning（KMP）。本质上，KMP可被视为经典两点边值 问题（Two-point Boundary Value Prob⁃lem，TPBVP）的变体。后者通常是给定初始状态和目标状态的情况下，在状态空间中计算一条连接初末状态并满足微分约束的（最优）路径；而规划问题则牵扯到一类附加的复杂性：避免与状态空间中的障碍物发生碰撞，用控制理论的术语来讲即是为包含非凸状态约束和控制约束的非线性系统设计（最优）开环轨迹。但求解TPBVP的技术并不能很好地适用于考虑微分约束的运动规划，因为其本就不是为处理全局障碍物约束而设计的，或者说很难得到受非凸状态和控制约束的非线性系统的最优必要条件。文献中处理KMP的方式一般有基于采样的方法和基于优化的方法两类。关于前者，由于微分约束破坏了CMP所需的良好特性，故第1节中仅有SBMP可能实现较好移植。关于后者，其一般有3种应用场景：一是在前述解耦规划中，用于平滑和缩短由其它规划算法（如SBMP）生成的路径；二是直接从较差初始猜想（可能是与障碍物相交的线段）开始计算局部最优的无碰轨迹；三是在已知自由空间的凸胞腔族中规划微分约束可行的（最优）轨迹。后两类场景将在2.2节详述。而2.1节将首先介绍如何利用SBMP处理考虑微分约束的运动规划问题。2.1 基于采样方法的KMP要求一般的机器人系统在微分约束下精准到达状态空间中的某个采样点要么是不可行的（图9中的橙色区域为机器人有限时间前向可达集，其在一定时间范围内无法到达可达集之外的采样点），要么则需解决复杂的TPBVP问题（这亦是很少应用路图类算法的原因，即目前不存在有效的LPM方法），故考虑微分约束的SBMP 通过离散动作空间和时间，并进行前向仿真来递增地生成采样树。离散的动作空间和时间其实暗含着初始状态的可达图，若状态的一阶微分函数满足Lipschitz条件，则随着离散度（以概率1）趋于零，动作序列将任意接近相应动作轨迹，即可达图的节点将在可达集中（以概率1）变得稠密，这也是对基于采样方法的KMP最重要的要求。加之“系统性”搜索，便保证了算法的分辨率（概率）完备概念。图9 机器人有限时间前向可达集RRT与EST最初便是为解决含微分约束的运动规划问题而设计，而非传统运动规划。其算法流程与上一节基本相同，稍微的区别在于—此处的算法一般在固定的离散动作集中选择能最小化积分后状态与采样点间距的离散动作，作为树上新加入的边所对应的控制输入（积分时间可以固定，也可以在某个区间内随机选择）。尽管RRT为含微分约束的运动规划问题提供了较好解决方案，但它的缺点是性能对度量函数较为敏感，差的度量可能导致一些注定发生碰撞的状态和位于可达集边界的状态被重复选择，重复扩展，从而大大增加了运行时间，延缓了树的生长。如图10（a）所示：橙色为初始状态可达集，而可达集边界状态（红色）有较大的Voronoi区域，故容易被重复扩展；又如图10（b）：红色状态有较大Voronoi 区域，但其扩展结果大概率会发生碰撞。理想距离函数应是满足某种最优性的代价泛函，但除非对于像无约束、有二次形式代价的线性系统存在解析解，一般来讲设计这样的伪度量与解决原始运动规划问题一样困难。虽然也有学者提出适应于弱非线性系统的近似度量，不过一个更重要的问题是如何令算法在较差的度量函数下依然有良好的性能？或者说如何令采样树在较差的度量函数下依然能（以概率1）快速稠密地覆盖初始状态的无碰可达集？另外，引入微分约束也对RRT*提供最优性的方式构成了挑战，发展新的考虑微分约束的渐近最优算法是又一亟需解决的问题。图10 SBMP算法的度量敏感性示意

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