移动机器人运动规划(三)--基于采样的路径规划

本节课主要介绍基于采样的路径规划方法。

一些基本的概念总览，基于采样的方法其实就是“撒点”

完 备 ： 在 一 段 时 间 内 总 是 能 够 找 得 到 路 径 ； 例 如 A ∗ ， D ∗ ； 完备：在一段时间内总是能够找得到路径；例如A^*，D^*； 完备：在一段时间内总是能够找得到路径；例如A∗，D∗；
$概率完备：如果一个解存在，用基于采样的方法最终能够找到这个解；$
resolution complete planner：与概率完备的区别在于：采样更加确定，局限在确定的网格内。

本课的五个部分，从经典的到最近优化发展的几种基于采样的方法。

Probabilistic Road Map(概率路图)

建议参考此篇博客，将的很详细。

先随机撒点，然后将落在障碍物上的点剔除。

将这些随机点按照一些限制(太远的点不要，连接后有障碍物的点不要；也就是距离准则和障碍物准则)连接起来。

查询阶段：利用 A ∗ A^* A∗等算法得到路径。

第一幅图
第二幅图

优点：概率完备；相对于 A ∗ A^* A∗之类的图搜索要更高效；
缺点：需要解决边界值问题；在学习阶段没有把搜寻路径放在心上，还需要后期再去搜索，因此不够高效。

懒惰障碍物检测方法。

不剔除障碍物上的点，先将所有的点都连接起来。

直接做路径规划；

将不可行的线段和点都删除得到一个新的路图；

再次进行路径规划；
用这样的方式可以大大提高PRM的效率。

Rapidly-exploring Random Tree(RRT)

建议阅读这篇博客。

demo

rrt的优缺点很明显，如上图所示。

kd树对rrt的改进。

参考博客

有关此算法依然可以参考之前推荐的博客。

Optimal sampling-based path planning methods(对基于采样的路径规划算法的优化)

R R T ∗ RRT^* RRT∗：能够达到渐近最优。

参考视频

Kinodynamic-RRT*：考虑机器人的运动学约束，利用曲线取代直线连接


demo

在路径跟随中依旧会用rrt进行路径规划。

Adanced path planning methods(更高级的基于采样的算法)

Informed RRT*：把采样的范围限制在一个椭圆里。

以起点到终点的距离作为椭圆的周长，限制采样空间，随后不断缩小，最终得到一条优化过的路径。




一些参考资料。

Implementation(实际应用)

ompl库：各种关于运动规划的方法
moveit
小教程
以上的更偏向于机械臂一点，在移动机器人尤其是地面移动机器人用的较少，但原理是相通的。

这个是专门用于移动机器人规划的库。

demo

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！