Open Source Robotics

精选高质量开源机器人项目、工具和软件，推动机器人社区发展。

Rapidly-exploring random tree

  • 又称: RRT
  • 类别: Planning & manipulation › Motion planning
  • 标签: motion-planning, sampling-based-planning, path-planning, kinodynamic-planning, collision-avoidance

一种基于采样的运动规划器，它从起始状态生长一棵树，反复随机采样一个状态，并把最近的树节点朝它扩展，从而快速探索大空间。

定义

快速探索随机树（Rapidly-exploring random tree，RRT）是一种基于采样的算法，用于找到一条从起始状态到目标区域的可行路径。它由 Steven LaValle 于 1998 年提出。该算法生长一棵以起点为根的树：每次迭代时，它在构型空间或状态空间中随机采样一个状态，找到树中最近的节点，并从该节点朝着样本扩展一小段距离。如果扩展没有碰撞，新状态就被加入树中。当树到达目标区域时搜索结束，再通过每个节点的父节点回溯读出路径。

关键性质是 Voronoi 偏置。位于树前沿的节点拥有最大的 Voronoi 区域，因此它们最有可能成为离随机样本最近的节点，于是树被拉向未探索的空间，而不是填充已经覆盖的区域。这使得 RRT 在高维空间中很有效，例如机械臂的关节空间。RRT 是概率完备的：如果存在解，随着样本数增加，找到它的概率趋近于 1。常见的改进包括目标偏置，即一部分样本直接取在目标处，以及 RRT-Connect，它同时从起点和目标生长两棵树，并尝试以贪心方式把它们连接起来。

由于扩展步骤只需要一种从一个状态朝另一个状态移动的方法，RRT 也能处理运动动力学规划（kinodynamic planning），即机器人无法在其状态空间中沿直线运动的情况。这时扩展步骤会施加采样得到的或优化得到的控制量并向前模拟动力学，如 LaValle 和 Kuffner 的运动动力学 RRT，或者把预先计算好的运动基元串联起来。这使它适用于车辆、足式机器人和富接触操作，在这些场景中，距离度量和扩展步骤必须围绕动力学来设计。RRT 的路径通常是曲折的且不是最优的，而且一旦找到路径，增加更多样本并不会改善它。RRT\ 增加了选择父节点的步骤和重连步骤，只要存在代价更低的路线，就重新连接附近的节点，这使它具有渐近最优性，代价是每个样本需要更多计算。当需要快速得到可行路径时，普通 RRT 或 RRT-Connect 加上捷径化和平滑处理仍然是常见的选择。

为何重要

RRT 使运动规划在多自由度机器人和带动力学的系统上变得实用，并且至今仍是 OMPL 和 MoveIt 等库中的默认规划器。许多后来的规划器，包括 RRT*，都建立在它的结构之上。

主要应用

  • 杂乱工作空间中的机械臂运动规划
  • 汽车、无人机和足式机器人的运动动力学规划
  • 使用自定义距离度量的富接触操作规划
  • 在运动基元图上为步行运动进行规划
  • 探索未知环境

实际应用

一个团队为从货架上拣取物品的七轴机械臂配置 MoveIt，把 OMPL 的 RRT-Connect 用作默认规划器。碰撞检测使用机器人模型和由深度相机构建的八叉树。他们根据货架开口的间隙设定规划时间上限和扩展步长，然后对每条路径进行捷径化和时间参数化后处理，使机械臂平稳运动。当规划难以深入狭窄的货架格口时，他们会加大目标偏置，或尝试一种在狭窄通道中表现更好的规划器；而对于静态工作单元中的重复查询，他们会考虑改用概率路线图。

常见误解

  • RRT 能找到最短路径 — 它找到的是一条可行路径；要获得好的路径质量，需要 RRT* 或后处理
  • RRT 保证在设定时间内找到路径 — 它是概率完备的，因此随着采样继续，找到路径的概率趋近于 1，而狭窄通道可能需要很长时间
  • RRT* 总是更好的选择 — 它会随时间改进路径，但得到第一个解更慢；当速度重要时，通常更倾向于使用 RRT-Connect 加平滑处理

谁需要了解

  • 运动规划工程师
  • 使用 MoveIt 或 OMPL 的操作和移动机器人开发人员
  • 自动驾驶车辆和无人机规划工程师
  • 机器人专业学生

相关技术

  • OMPL
  • MoveIt
  • RRT-Connect
  • 运动动力学 RRT（Kinodynamic RRT）
  • Informed RRT*
  • 路径捷径化（Path Shortcutting）

相关术语

  • Configuration Space
  • Motion Planning
  • Obstacle Avoidance
  • RRT*
  • Probabilistic Roadmap
  • Motion Primitive

相关项目

  • Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
  • ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
  • OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
  • MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
  • PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
  • mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms

视频

  • Motion Planning: Rapidly Exploring Random Trees (RRT): Algorithm Implementation Step by Step!: VDEngineering

本网站需要 JavaScript 才能正常运行。请启用 JavaScript 以浏览我们的开源机器人项目。