您当前的位置: 首页 >  算法

RuiH.AI

暂无认证

  • 7浏览

    0关注

    274博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

路径规划算法1.3抽样算法——PRM与RRT算法

RuiH.AI 发布时间:2021-10-27 11:21:08 ,浏览量:7

路径规划算法1.3抽样算法——PRM和RRT算法
  • 前言
  • 抽样算法的完备性
  • PRM概率路图
    • 思想
    • 方法
  • RRT快速扩展随机树
    • 思想
    • 基本方法
    • 改进随机搜索策略
    • 其他改进
  • 后记

前言

由于图搜索算法在三维空间中的计算量陡增,因此抽样算法(sample based planning)更适合在三维中使用。最经典的两个算法是PRM(Probabilistic Road Map)概率路图法,RRT(Rapidly-explorring Random Tree)快速扩展随机树法,及其优化方法RRT*。

抽样算法的完备性

基于图搜索的方法,只要规划时间充足就肯定能找到路径,因此是完备的。

基于抽样的算法,由于采样数量是一定的,因此当采样次数越多,找到解的概率越大,但寻路时间越长;采样点少就可能找不到路径,是概率完备的

PRM概率路图 思想

寻路空间中随机采样,形成路图,搜索路径。

方法
  1. 在寻路空间中随机撒点,剔除落在障碍物上的采样点。
  2. 将每个采样点与其附近一定距离内的采样点连接,剔除与障碍物碰撞的边,形成路图。
  3. 采用图搜索算法(如A*)寻找最优路径。

PRM是概率完备的,但碰撞检测耗时较长,效率低。 在这里插入图片描述 在这里插入图片描述

在这里插入图片描述

RRT快速扩展随机树 思想

通过抽样点引导路径树在寻路空间中生长,形成路径(有增量式搜索的意味)。

基本方法
  1. 初始化起点,终点,路径树T={起点}。
  2. 在寻路空间中随机抽样一个点R,从路径树T中找到距离点R最近的节点N。
  3. 由N向R扩展一段距离到达点S,如果边NS无碰撞,则将S加入路径树T中。
  4. 循环步骤2和3,直到加入路径树的点S与终点间的距离小于一定阈值。

这就是最简单的RRT算法,但是由于搜素策略是随机抽样,因此搜索效率不高。

另外,抽样算法获得的路径大多都不是最优的。

改进随机搜索策略

将基本方法步骤2进行修改:

  1. 随机抽取 q ∈ ( 0 , 1 ) q\in(0, 1) q∈(0,1),当 q < t h r e s h o l d qthreshold q>threshold时,在寻路空间中随机抽样一个点R,从路径树T中找到距离R最近的节点N。

t h r e s h o l d threshold threshold靠近1时,路径树偏好向终点生长,但容易被障碍物阻挡; t h r e s h o l d threshold threshold靠近0时,路径树类似于随机生长,容易越障但效率低。

这种搜索策略的改进提升了搜索策略的目的性(朝向终点),也保持了一定的越障能力。

在这里插入图片描述

在这里插入图片描述 在这里插入图片描述 在这里插入图片描述

其他改进

RRT能够改进的地方有:

  • 随机搜索策略
  • 扩展树的方法
  • 近邻节点的定义
  • 双向树生长(bidirectional RRT)
后记

下一次会再总结RRT*等sample based算法。

关注
打赏
1658651101
查看更多评论
立即登录/注册

微信扫码登录

0.0506s