文章目录
- 简介
- 原理
- 算法
- 运动规划的变体和改进
简介
快速探索随机树(RRT)是一种算法,旨在通过随机构建空间填充树来有效搜索非凸高维空间。该树是从搜索空间随机抽取的样本中逐步构建的,并且本质上偏向于向问题的大型未搜索区域生长。RRT 由 Steven M. LaValle 和 James J. Kuffner Jr. 开发。它们可以轻松处理障碍物和微分约束(非完整和动力学)问题,并已广泛用于自主机器人运动规划。
RRT可以看作是一种为具有状态约束的非线性系统生成开环轨迹的技术。RRT 也可以被视为一种蒙特卡洛方法,用于将搜索偏置到配置空间中图的最大 Voronoi 区域。有些变化甚至可以被认为是随机分形。
RRT 可用于计算近似控制策略,以控制具有状态和动作约束的高维非线性系统。
原理
RRT 通过使用搜索空间中的随机样本,来生长植根于初始配置的树。 在绘制每个样本时,会尝试与树中最近的状态之间建立连接。 如果连接是可行的(完全通过自由空间并服从任何约束),则新状态添加到树中。 通过对搜索空间进行均匀采样,扩展现有状态的概率与其 Voronoi 区域的大小成正比。 由于最大的Voronoi地区属于搜索前沿的state,这意味着这棵树优先向大片未搜索区域扩展。
树与新状态之间的连接长度通常受到生长因子的限制。 如果随机样本离树中的最近状态比此限制允许的更远,则使用从树沿线到随机样本的最大距离处的新状态,而不是随机样本本身。 然后,随机样本可以被视为控制树木生长的方向,而生长因子决定其生长速度。 这保持了RRT的空间填充偏差,同时限制了增量增长的大小。
通过增加从特定区域采样状态的概率,可以对RRT增长产生偏差。 RRT 的大多数实际实施都利用这一点来指导对规划问题目标的搜索。 这是通过在状态抽样过程中引入对目标进行小概率抽样来实现的。 这种概率越高,树就越贪婪地朝着目标生长。
算法
对于通用配置空间 C,伪代码中的算法如下:
在上面的算法中,“RAND_CONF”在 C 中获取随机配置 q r a n d q_{rand} qrand。这可以替换为函数“RAND_FREE_CONF”,该函数使用 C