快速搜索随机树 (Rapidly exploring Random Trees, RRT)是一种通过随机构建空间填充树高效搜索非凸高维空间的算法。

Agreement

相关术语

1. xxx

快速搜索随机树

Description

快速搜索随机树（Rapidly exploring Random Trees, RRT）通过构建空间填充树（space-filling tree）来高效搜索非凸高维空间。

RRT路径搜索

Algorithm

算法通过对搜索空间随机采样来生长节点树。

  1. 随机树初始化后仅包含一个根节点 $p_{init}$
  2. 在整个搜索空间随机采样得到一个点 $p_{rand}$
  3. 确定随机树中距离 $p_{rand}$ ”最近“的节点 $p_{nearest}$
  4. 在 $p_{nearest}$ 与 $p_{rand}$ 之间”生长“得到新的节点 $p_{new}$
  5. 确认从 $p_{nearest}$ 到 $p_{new}$ 的生长符合规则（碰撞等），如符合则将 $p_{new}$ 加入随机树，否则放弃本次生长
  6. 在允许迭代次数内重复 2-5 步，直到 $q_{nearest}$ 到目标 $p_{goal}$ 的距离小于阈值，生长结束

Variants & Improvements

  1. 以概率 $P$ 确定生长方向是随机点还是最终目标，如小于某个概率直接向最终目标生长，否则向一个随机方向生长

Summary

  1. 随机树保存前驱节点索引，则可以由后往前一次索回所有路径点
  2. 算法中的最近标准和生长方法可以灵活定义

Appendix

Reference
  1. RRT路径规划算法
Archive