OMPL开源轨迹规划库

下面列出的所有实现都被视为功能齐全。在OMPL中，规划器分为三类:

要了解如何对规划器进行基准测试，请单击此处。

实例图册#

部分没图就是当时没求解出来 ABITstar FMT FMT LBKPIECE1 RRT RRT SPARStwo AITstar AITstar informedRRTstar LBTRRT LBTRRT RRTsharp SST SST BFMT BFMT KPIECE1 KPIECE1 PDST PDST RRTstar RRTstar STRIDE STRIDE BiEST BiEST lazyLBTRRT PRM PRM RRTXstatic TRRT TRRT BITstar BITstar lazyPRM PRMstar PRMstar SBL SBL BKPIECE1 lazyPRMstar ProjEST ProjEST SORRTstar EST EST lazyRRT RRTconnect SPARS SPARS

几何规划器#

此类别中的规划器仅考虑系统的几何和运动学约束。假设任何可行的路径都可以变成动态可行的轨迹。这些规划器中的任何一个都可用于几何约束进行规划。此类别中的规划器可以分为几个重叠的子类别:

多查询规划器
这些规划器构建了可用于多个查询的整个环境的路线图。
- 概率路线图方法PRM
  这是基于采样的算法。我们的实现使用一个线程来构建路线图，而另一个线程检查路线图中是否存在开始状态和目标状态之间的路径。OMPL包含许多PRM的变体:
  - LazyPRM
    此计划器类似于常规 PRM，但“懒惰”地检查顶点或边的有效性，即仅当它是候选解决方案路径的一部分时。
  - PRM*
    虽然常规 PRM 尝试将状态连接到固定数量的邻居，但 PRM* 会随着路线图的增长而逐渐增加连接尝试的次数，从而向最佳路径提供收敛。
  - LazyPRM*
    具有惰性状态有效性检查的 PRM* 版本。
- SPArse 路线图扳手算法（SPARS）
  SPARS是一个计划器，它提供渐近 near 最优性（在最优解的常数因子内的解决方案），并包括一个有意义的停止准则。虽然（因为？）它不能保证最优性，但它的收敛率往往远高于PRM*。
- SPARS2
  SPARS2是SPARS算法的变体，它通过类似的机制工作，但使用不同的方法来识别接口和计算通过所述接口的最短路径。
单查询规划器
这些规划者通常会生长一棵由有效运动连接的状态树。这些规划器的不同之处在于他们用于控制 树的扩展位置 和方式的启发式方法。一些基于树的规划者种植两棵树:一棵从起点开始，一棵从目标开始。此类规划器将尝试将开始树中的一个状态与目标树中的另一个状态连接起来。
- 快速探索随机树（RRT）
  这是最早的单个查询规划器之一。该算法易于理解和实现。已经提出了许多很多RRT的变体。OMPL 包含几种 RRT 变体:
  - RRT Connect （RRTConnect）
    这个规划器是RRT的双向版本（即，它长了两棵树）。它通常优于原始的RRT算法。
  - RRT*
    RRT的渐近最优版本:算法收敛于作为时间函数的最优路径。这是第一个可证明的渐近规划器（与PRM一起）。自发布以来，已经出现了其他几种算法，这些算法提高了RRT*的收敛率，例如 RRT# 和 RRTX 。
  - 下限树 RRT （LBTRRT）
    LBTRRT是RRT的渐近最优版本:它保证收敛到最优解的常数因子内的解。
  - 稀疏稳定RRT
    SST 是 RRT 的渐近接近最优增量版本。
  - 基于过渡的 RRT （T-RRT）
    T-RRT不提供任何硬性最优性保证，但试图找到短而低成本的路径。
  - 矢量场RRT
    VF-RRT是一个基于树的运动规划器，试图最小化所谓的路径上游成本。上游成本由用户定义的向量场上的积分定义。
  - 平行RRT
    已经为基于抽样的计划者提出了许多不同的并行化方案，包括RRT。在此实现中，多个线程同时向同一树添加状态。找到解决方案后，所有线程都将终止。
  - Lazy RRT （LazyRRT）
    此计划器执行惰性状态有效性检查（类似于 LazyPRM）。它不是实验性的，但根据我们的经验，它似乎在任何类别的问题上都没有明显优于其他规划者。
  - 任务空间RRT （TSRRT）
    TSRRT是RRT的一种变体，其中探索由任务空间指导。它需要一个 ompl::geometric::TaskSpaceConfig 实例，该实例定义如何将配置空间状态投影到任务空间，以及一个将任务空间状态提升到配置空间的反向操作。
- 膨胀空间树（EST）
  该规划器与RRT大约同时出版。根据我们的经验，它对良好的距离测量并不敏感，这对于复杂的高维状态空间可能很难定义。EST实际上有三个版本: 原始接近第一次发布的版本，双向版本和基于投影的版本。低维投影用于跟踪状态空间的探索方式。大多数情况下，OMPL可以自动确定合理的投影。我们已经实施了一些规划器，这些规划器不一定是EST的简单变体，但确实具有相同的扩展策略:
  - 单查询双向延迟碰撞检查计划（SBL）
    此计划器本质上是具有惰性状态有效性检查的 EST 的双向版本。
  - 并行单查询双向延迟碰撞检查计划（pSBL）
    此规划器在 SBL 中并行使用多个线程增长两棵树。
- 通过内部和外部细胞探索（KPIECE）进行运动学规划
  KPIECE是一个基于树的规划器，它使用离散化（通常是多个层次）来指导（连续）状态空间的探索。OMPL的实现是简化的，使用单一级别的离散化:一个网格。网格被强加于 projection 状态空间的投影上。在探索空间时，优先考虑到目前为止已探索的网格部分的边界。边界定义为 在 n 维投影空间中具有少于 2 n 个非对角线非空相邻格网像元的格网像 _n_元集。KPIECE有两种变体:
  - 双向 KPIECE （BKPIECE）
  - Lazy Bi-directional KPIECE （LBKPIECE）
- 具有分辨率独立密度估计（STRIDE）的搜索树
  这位规划器的灵感来自 EST。STRIDE 不使用投影，而是使用几何近邻访问树直接在状态空间中估计采样密度。STRIDE 对于高维系统非常有用，在这些系统中，自由空间无法通过低维（线性）投影轻松捕获。
- 路径导向细分树（PDST）
  PDST 是一个规划器，它完全消除了对距离度量的依赖，这在难以定义良好距离度量的情况下很有用。PDST保持二进制空间分区，以便运动完全包含在分区的一个单元格中。每个单元格的运动密度用于指导树的扩展。
- 快速行进树算法（FMT∗）
  FMT∗ 算法对一组概率绘制的样本执行“惰性”动态规划递归，以生长路径树，该路径树在成本空间中向外移动。与所有其他规划器不同，需要事先选择有效样本的数量。
- 双向快速行进树算法（BFMT∗）
  执行两个 FMT* 树，一个从起点开始，另一个从目标开始，从而在探索更少的空间时使规划器更快。
多层次规划器
可以利用多个抽象级别的规划算法。如果要使用它们，则应使用 [ompl::base::SpaceInformationPtr](https://ompl.kavrakilab.org/core/classompl_1_1base_1_1SpaceInformationPtr.html "ompl::base::SpaceInformation 的共享指针包装器。").然后，所有规划器都保证概率完整性，如果提供的抽象是可以接受的。有指南 guide，教程和演示形式的大量文档。
- 快速探索随机商空间树（QRRT）
  RRT的推广，以在不同的抽象级别上进行规划。
- 快速交货率*
  QRRT 的渐近最优版本
- 商空间路线图规划器（QMP）
  PRM的泛化，用于在不同的抽象级别上进行规划。
- QMP*
  QMP 的渐近最优版本
优化规划器
近年来，已经提出了几种基于抽样的计划算法，这些算法仍然提供了一些最优性保证。通常，假定最优解是最短路径。在OMPL中，我们有一个更通用的框架来表示状态和路径的成本，例如，允许您最大化沿路径的最小间隙，最小化机械功或一些任意用户定义的优化标准。有关详细信息，请参阅最佳规划。下面的一些规划者使用这种一般成本框架，但请记住，当优化路径长度以外的其他内容时，不能保证收敛到最优。
- PRM*
  PRM的渐近最优版本; 使用一般成本框架。
- 懒惰PRM*
  PRM*的惰性版本; 使用一般成本框架。
- RRT*
  RRT的渐近最优版本; 使用一般成本框架。
- RRT#
  RRT* 的一种变体，收敛率更高。 它使用一般成本框架。
- RRTX
  RRT* 的一种变体，收敛率更高。 它使用一般成本框架。
- 知情的RRT*
  RRT* 的一种变体，它使用启发式方法来绑定对最佳解决方案的搜索。 它使用一般成本框架。
- 批处理通知树（BIT*）
  一种随时渐近最优算法，它使用启发式算法对最优解的搜索进行排序和绑定。 它使用一般成本框架。
- 高级位* （阿比特*）
  BIT* 的扩展，它使用高级图形搜索技术更快地找到初始解决方案。 它使用一般成本框架。
- 自适应通知树（AIT*）
  一种随时渐近优化的算法，可同时估计和利用特定于问题的启发式方法。 它使用一般成本框架。
- 下限树 RRT （LBTRRT）
  RRT 的渐近接近最优版本。
- 稀疏稳定RRT
  SST 是 RRT 的渐近接近最优增量版本。
- 基于过渡的 RRT （T-RRT）
  T-RRT不提供任何硬性最优性保证，但试图找到短而低成本的路径。 它使用一般成本框架。
- 梁
  基于渐近最优路线图的规划器。
- SPARS2
  基于渐近最优路线图的规划器。
- FMT*
  渐近最优的基于树的规划器。
- ST-RRT*
  用于时空规划的双向时间优化规划器。
- 首席财务官
  一个元规划器，它在不同的线程中运行多个渐近最优规划器实例。当一个线程找到更好的求解路径时，路径上的状态将传递给其他线程。
- 随时缩短路径（APS）
  APS 是围绕一个或多个几何运动规划器的通用包装器，它反复将快捷方式和混合应用于一组解决方案路径。可以指定任何数量和计划器的组合，每个计划器都在单独的线程中运行。

Attention OMPL 如何选择几何规划器
如果使用 ompl::geometric::SimpleSetup 类（强烈推荐）来定义和解决运动规划问题，则 OMPL 将自动选择合适的规划器（除非您明确指定了一个）。如果状态空间具有默认投影（如果您使用任何内置状态空间，情况就是如此），那么使用 LBKPIECE 如果可以则它将使用双向规划器，否则它将使用 KPIECE 。这些规划器已被证明在许多现实世界的运动规划问题上都能很好地工作，这就是为什么这些规划器是默认选择的原因。如果状态空间没有默认投影，则将使用 RRTConnect 或常规 RRT ，具体取决于是否可以使用双向规划器。目标的概念在 OMPL 中非常笼统:甚至可能无法对满足目标的状态进行采样，在这种情况下，OMPL 无法在目标状态生长第二棵树。可行性和最优性
在实践中，可行和最佳规划者之间的界限并不是那么黑白分明。它们之间的界限可以用适当的 ompl::base::PlannerTerminationCondition 来模糊。例如， ompl::base::exactSolnPlannerTerminationCondition 函数返回一个终止条件，该条件导致优化计划程序在找到第一个解决方案后终止。作为另一个示例，使用 ompl::base::CostConvergenceTerminationCondition 和参数 solutionsWindow=10 和 epsilon=1，导致优化计划程序 _exactly_在找到 10 个解决方案时终止。您可以使用 ompl::base::p lannerOrTerminationCondition 和 ompl::base::p lannerAndTerminationCondition 来组合计划程序终止条件（例如，“在找到 10 个解决方案或 超过 10 秒的时间限制时终止”）。有关详细信息，请参阅 Planner 终止条件。

其他工具:#

基于控制的规划器#

如果所考虑的系统受到差异约束，则使用基于控制的规划器。这些规划者依靠状态传播而不是简单的插值来生成运动。这些规划器不需要转向功能，但如果用户实现它，它们（KPIECE除外）都将使用它。下面的前两个规划器是对上面相应几何规划师的基诺动力学改编。

快速探索随机树（RRT）
稀疏稳定RRT
SST 是 RRT 的渐近接近最优增量版本。
膨胀空间树（EST）
通过内外细胞探索（KPIECE）进行Kinodynamic规划
顾名思义，基于控件的KPIECE版本首先出现，几何版本是从中派生出来的。
路径导向细分树（PDST）
基于控制的PDST版本实际上出现在几何版本之前。鉴于基于控件的版本，也很容易实现几何版本。
Syclop，一个元规划器，在较低级别使用其他规划器
Syclop 是一个元规划器，它将通过状态空间分解计算的高级指南与低级规划算法相结合。低级规划人员所做的进度将反馈给高级规划员，高级规划师使用此信息来更新指南。Syclop 有两种不同版本：
- Syclop使用RRT作为低级规划器
- Syclop 使用 EST 作为低级规划器
线性时态逻辑规划器（LTLPlanner）
LTLPlanner 为运动规划问题找到解决方案，其中目标由线性时态逻辑（LTL）规范指定。

OMPL 如何选择基于控件的计划员
如果使用 ompl::control::SimpleSetup 类（强烈推荐）来定义和解决运动规划问题，则 OMPL 将自动选择适当的规划器（除非您明确指定了一个）。如果状态空间具有默认投影（如果使用任何内置状态空间，情况就是如此），则它将使用 KPIECE。该规划器已被证明在许多现实世界的运动规划问题上都能很好地工作，这就是为什么它是默认选择的原因。如果状态空间没有默认投影，则将使用 RRT 。请注意，没有基于双向控制的规划器，因为我们不假设有一个转向功能可以精确地连接两个状态 exactly。

基于多层次的规划器#

为了解决涉及高维状态空间的问题，我们通常可以使用多级抽象来简化状态空间，从而使专门的规划者能够更快地找到解决方案。此类中的规划器支持状态空间序列，可用于具有几何和动态约束的状态空间。有指南 guide，教程和演示形式的大量文档。

快速探索随机商空间树（QRRT）
RRT的推广，以在不同的抽象级别上进行规划。
快速交货率*
QRRT 的渐近最优版本
商空间路线图规划器（QMP）
PRM的泛化，用于在不同的抽象级别上进行规划。
QMP*
QMP 的渐近最优版本
稀商空间路线图规划器（SPQR）*
SPARS向多层次规划的推广。