针对RRT对度量函数的敏感性问题，Resolution-Complete RRT（RC-RRT）利用Constraint Violation Function（CVF）描述每个顶点发生碰撞的概率，并通过记录已成功应用的动作，在避免重复扩展的同时可以寻找到更有价值的顶点。RRT-blossom选择待扩展节点的方式与RC-RRT类似，不同的是RRTblossom同时应用所有可能的行为，并移除碰撞轨迹和回退轨迹。Reachability-Guided RRT（RG-RRT）的显著特点是为采样树上各顶点计算离散可达集，通过位于可达集Voronoi区域内的采样点来引导搜索，从而在不需要特殊启发式的情况下缓解了对距离度量的敏感性。但由于RG-RRT算法在狭窄通道环境中可能持续发生碰撞，而RC-RRT则可能偏向选择那些有较小CVF和较大Voronoi 区域面积的无价值顶点，因此促使Environmentally Guided RRT（EGRRT）算法将两种策略合并。Path-Directed Subdivision Tree（PDST）用路径段表示“采样点”，并将“采样点”按优先扩展顺序排列，同时用状态空间的非均匀细分来估计覆盖率，从而避免了度量敏感问题。GRIP（Greedy，Incre⁃mental，Path-directed）通过用简单度量代替路径细分过程而进一步改进了PDST算法，并以此偏置采样，加之DRRT重复使用先前信息的优势，实现了未知环境中含微分约束的重规划。另一种与PDST类似的方法是 KPIECE（Kinodynamic Planning by Interior-Exterior Cell Exploration），其用网格离散低维投影空间，并标记为外胞腔和内胞腔两类。因为前者较好捕捉了采样树的边界，故为实现更快的空间探索，文章以75%的概率选择外胞腔进行扩展。其次算法也将更偏爱于覆盖率较低、相邻胞腔较少、扩展次数较少等有利于采样树生长的胞腔。实验结果表明：KPIECE的运行时间和内存消耗显著下降。最近一些机器学习方法也被用来离线学习度量函数和Steering函数，它们通过最优控制算法提供数据集，以有监督的方式近似两状态间的尚需代价函数和对应的控制输入，从而为RRT的在线执行提供有价值的信息。2.1.2 最优性问题正如前文所指出：为了获得渐近最优性，RRT*要求精确且最优地连接状态对，但其实这仅适用于完整系统和存在较好Steering方法的非完整系统。Karaman和 Frazzoli再次将RRT*算法扩展至含微分约束的运动规划问题中，并在存在局部最优Steering方法的前提下，针对局部可控系统，提出了保证算法渐进最优性的充分条件。同样假设存在局部最优Steering方法，满足动态环境中实时Kinodynamic 重规划的RRTX算法也已被提出。类似于Kim等的工作，LQR-RRT*将基于线性二次调节器（Linear Quadratic Regulators， LQR）的启发式应用于RRT*，即用 LQR代价函数作为度量函数来选择邻近顶点，用LQR控制策略生成轨迹。但因为每次都是在新的采样点处进行系统线性化，所以代价函数各不相同，而且此类轨迹无法准确到达目标状态，也就无法确定结果的最优性。Kinodynamic RRT*针对能控线性系统，利用fixed-final-state-free-final-time控制器来精确且最优地连接状态对，从而满足了上述充分条件，使算法有了渐进最优性保证，类似工作还包括 Goretkin等关于LQR-RRT*算法的改进。与传统运动规划类似，如何利用已有信息改善采样分布以求加速算法，已经成为研究人员关心的一个问题。Xie等以欧式距离与最大速度的商做为BIT*的保守启发式，用序列二次规划（Sequential Quadratic Programming，SQP）的变体求解局部BVP，提出了一种有较好性能提升的KMP方法。同时FMT*的Kinody⁃namic 版本见于Schmerling等的工作。不考虑微分约束的系统的信息集形成了一个参数化的椭圆，直接在该椭圆中采样可有效降低算法运行时间。但对含微分约束的系统来讲，显式表示信息集非常困难，而一般的拒绝采样方法在高维情况下又效率低下。故针对存在局部Steering方法的系统，Kunz等提出分层拒绝采样（Hier⁃archcal Reject Sampling，HRS）技术来缓解这一问题。Yi等则将其重新定义为在隐非凸函数的子水平集内的均匀采样问题，从而使蒙特卡罗采样方法得以应用：给定信息集中先前的一个采样点，HNR-MCMC（Hit-and-Run Markov Chain Monte-Carlo）首先对某个随机方向进行采样，然后通过拒绝采样找到最大步长，使新采样点位于信息集内。Joshi等利用椭球工具箱离线求解并保存线性系统的初始构型前向可达集和目标构型后向可达集，导出时间信息集（Time-Informed Set， TIS）。一旦找到初始解，后续搜索将被限定在TIS中，从而加速KMP的收敛。对含有更复杂微分约束的系统，RRT*类方法获得渐进最优性的方案很难继续应用。因此只通过模型前向仿真以收获最优性的思路便吸引了研究人员的注意力。AO-X算法将最优KMP问题表述为可行KMP问题。首先利用任意可行的KMP算法（文中为RRT和EST）在State-Cost空间中生成可行轨迹，再通过逐次缩小轨迹代价的上界以满足渐近最优性要求。且可以证明算法的期望运行时间为，其中是述解轨迹次优性的参数。SST（Stable Sparse RRT）和SST*通过蒙特卡洛前向传播（Monte-Carlo Forward Propagation）建立采样树，以修剪树上的局部次优分枝并维持稀疏结构，分别保证了算法的渐近几乎最优性和渐进最优性。另外，一些不要求Steering方法的加速方案也已被提出：Dominance-Informed Re⁃gion Tree（DIRT）引入Dominance Informed Region来谋求Voronoi偏置与路径质量间的平衡，并采用类似于RRT-blossom的边扩展策略和图修剪技术以缩短找到高质量解轨迹所需的时间。同样在类似于RRT-blossom的边扩展策略的基础上，Informed SST（iSST）模仿A*引入启发式来起到有序选择待扩展顶点和修剪的作用，提高了有限时间内的求解成功率和相同时间内的路径质量。除上述两类获得渐进最优性的方法外，状态栅格（State Lattice）方法也可获得分辨率下的最优性。其由离线计算的运动基元库（Motion Primitives Library）在线导出，是对初始状态无碰可达集的近似。通过在状态栅格上的搜索过程，可求得符合要求的解轨迹。2.1.3 考虑微分约束的基于学习的运动规划方法与传统运动规划类似，基于学习的方法也被应用于考虑微分约束的运动规划问题，现有文献中的改进措施主要集中于：①端到端地生成轨迹；②学习在无碰可达集内生成稠密（最优）的采样点分布；③在不考虑障碍物的情况下，学习针对复杂系统的LPM；④学习有关NSM的度量函数。Huh等提出的c2g-HOF（cost to goHigh Order Function）神经网络架构以工作空间为输入，输出给定构型空间和目标构型的连续cost-to-go函数，而据其梯度信息便可直接生成轨迹。MPC-MPNet （Model Prective Motion Planning Network）是MPNet在KMP领域的进一步扩展，算法框架包括神经网络生成器（Neural Generator）、神经网络鉴别器（Neural Discriminator）和并行模型预测控制器（Parallel⁃izable Model Predictive Controller）。前者迭代生成批量采样点，中者选出有最小代价的采样点并通过后者进行最优连接（也可为所有批量采样点在树上找出最近点，并用MPC并行计算局部最优轨迹，即文中的MPC-MPNet Tree算法），实验结果表明MPC-MPNet相较现有算法在计算时间、路径质量和成功率方面有较大提升。为研究任务约束、环境不确定性和系统模型不确定性场景中的长范围路图构建问题，Francis等和Faust等合并了PRM 的规划效率和RL的鲁棒性，并提出由深度确定性策略梯度（Deep Deter⁃ministic Policy Gradient， DDPG）或连续动作拟合值迭代（Continuous Action Fitted Value It⁃eration， CAFVI）训练的RL agent决定路图连通性。结果表明无论相比RL agent自身还是传统的基于采样的规划器，PRM-RL的任务完成度都有所提高。RL-RRT仍将RL agent作为局部规划器，同时训练一个有监督的可达性估计器作为度量函数。该估计器以激光雷达等局部观测数据为输入，预测存在障碍物时RL agent连接两状态所需的时间，以起到偏置采样分布的作用。L-SBMP（Latent Sampling-based Motion Planning）方法由自编码网络、动力学网络和碰撞检测网络构成（分别模仿基于采样算法中的状态采样、局部Steering 和碰撞检测），前者隐式地编码了嵌入在状态空间的系统动力学低维流形，并提供了对隐空间直接采样的能力，加之动力学网络和碰撞检测网络，使L2RRT（Learned La⁃tent Rapidly-exploring Random Trees）可以有效地、全局地探索学习到的流形。CoMPNet（Con⁃strained Motion Planning Networks）针对操作规划和有运动学约束的规划问题而提出，由环境感知和约束编码器组成，它的输出作为神经规划网络的输入，并与双向规划算法一起，在约束流形上生成起始构型和目标构型间的可行路径。经过2.1节的讨论，可以直观地觉察到引入微分约束后SBMP算法所面临的新困难：首先算法的搜索范围发生了变化，即局部无碰可达集的概念代替了传统运动规划中可视区域的概念，用局部无碰可达集外的构型引导采样树的生长显然浪费了宝贵的计算时间。但在可达集中直接采样的思路目前却仍存在2个难点：一是高维非线性系统可达集的实时计算，二是可达集形状的不规则；其次更一般的TPBVP问题的求解很难逾越，即使代之以采样树的前向仿真方案，过长的运行时间也将使算法在实际应用中很难获得最优性，甚至变得不可行。综上，如何像传统运动规划那样，借助已有或学习到的信息限制搜索范围、安排搜索次序、设计度量函数，以加速考虑微分约束的运动规划算法，将是未来的发展方向。另外，前述SBMP的加速策略或解品质提升策略已被总结在表2中。表2 SBMP的加速策略或解品质提升策略2.2 基于优化的运动规划算法虽然考虑微分约束的基于采样的运动规划算法具有全局搜索特性且不需要初始猜想，但其在高维空间中的应用确需消耗较长计算时间，这使得一些研究人员诉诸于局部最优的基于优化的运动规划算法受益于最优控制直接法，即显式考虑障碍物约束。其将函数空间中的无穷维优化问题转化为有限维非线性参数优化问题，在一定意义上可被统一至模型预测控制（Model Predic⁃tive Control，MPC）的框架下（参见图11，其根据当前测量到的系统状态反复解一个开环最优控制问题，这里为控制量，为系统模型，为扰动，和分别为可行的状态集合和控制集合，为目标状态集合，为优化指标。上标“”表示最优值，“~”表示标称量，“·”表示导数）。文献中目前大致存在类基于优化的运动规划算法：图11 标称MPC的一般框架1）无约束优化方法，其目标函数被由障碍物表示的人工势场所增强，或通过确定性协变方法，或通过概率梯度下降方法减小目标函数值。虽不需要高质量的初始猜想，但并未从理论上提供收敛保证，而且在有杂乱障碍物的环境中的失败率较高，不适用于实时运动规划问题。2）序列凸规划方法，对有约束的非凸优化问题来讲，通用类非线性规划算法的收敛表现严重依赖于初始猜想，无法提供收敛保证并提前预知所需的计算时间，很难应用于实时任务。而凸优化问题可保证在多项式时间内可靠地得到全局最优解，为借助这一优势，必须将非凸的最优运动规划问题进行凸化。其中的代表性方法包括 TrajOpt、SCvx、GuSTO，且后两者提供了理论证明，促进了其在实时任务中的 应用。此类方法的详细介绍可参考Malyuta等的文章，这里不再展开。除问题的凸化外，该类方法面临的另一困难则在于如何建立恰当的避障约束。3）凸分解方法，为了避免由避障需求带来的非凸约束的影响，凸分解方法通常将已知自由空间分解为一系列重叠的凸胞腔，并保证数个插值曲线片段分别位于各凸胞腔内以满足机器人运动过程的安全性要求（参见图12，其中紫色为障碍物区域，绿色为已知自由空间分解后的凸胞腔，蓝色为规划的轨迹）。Deits和 Tedrake用IRIS（Iterative Regional Inflation by Semidefi⁃nite Programming）计算安全凸区域，由混合整数优化完成多项式轨迹分配，最后利用一种基于平方和（Sums-of-Squares，SOS）规划的技术确保了整个分段多项式轨迹不发生碰撞。相比于IRIS，Liu等根据由JPS（Jump Point Search）算法求得的初始分段路径建立安全飞行走廊（Safe Flight Corridor， SFC），减少了凸分解的时间。同时SFC为二次规划（Quadratic Program，QP）过程提供了一组线性不等式约束，允许进行实时运动规划。Chen等逐步构建基于八叉树的环境表示，并通过在八叉树数据结构中的有效操作来在线生成由大型重叠三维网格组成的自由空间飞行走廊。Gao等则在环境点云地图的基础上，将SFC的构建交付于SBMP。除此之外的另一个关键问题是区间分配（Interval Al⁃location）方式和时间分配（Time Allocation）方式，前者决定每个凸胞腔内的轨迹间隔，而后者则处理在每个间隔上所花费的时间。图12 凸分解方法示意虽然基于优化的运动规划算法采用了3种不同的处理思路，但其本质上都是建立在有约束的非线性优化问题的基础上的，所以优化技术未来可预见的重大进展将是此类算法性能提升的主要渠道。表3对本文所讨论的几种开环最优路径（轨迹）规划算法进行了总结，其中和分别代表在路图上选取邻域点时的半径和数量，为采样点数量，为的维数，为体积测度，为维单位球的体积，为最优误差。对于为最优路径代价，，而含微分约束的运动规划不需要几何邻域的定义。表3 考虑微分约束的最优算法总结

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