机器人学 —— 轨迹规划(Sampling Method)

时间:2021-07-30 09:11:34

  上一篇提到,机器人轨迹规划中我们可以在 Configuration Space 中运行A* 或者 DJ 算法。无论A* 还是DJ 算法,都必须针对邻域进行搜索,如果2*度则有4邻域,2*度则有8邻域。如果是工业上常用的6*度机器人,那么就有2^6邻域。。。。。。显然,对于轨迹规划这种串行算法而言,这么高维度的搜索空间是不合适的.......于是就有了牺牲精度,鲁棒性,但是效率较高的基于采样的轨迹规划算法。PRM(probabilistic road map)。使用PRM生成稀疏的路径图,再利用A*算法在路径图中进行轨迹规划,则可以显著提高效率。

1、生成永久map的PRM算法

  PRM算法的伪代码如下:

  机器人学 —— 轨迹规划(Sampling Method)

  其中Dist function 是计算Configuration Space中,点与点之间距离的函数。Local Planner 是检查点与点连线是否在Configuration Space 中经过非*区域的函数。

  此算法的本质是蒙特卡洛算法。所以原本很容易在GPU上实现并行化。最大的困难还是处于非*区域检查部分...

  机器人学 —— 轨迹规划(Sampling Method)

  绿色的点为随机采样点。

2、在空间中生成一次性路径的 RRT 算法

  很多时候,我们并不需要生成一整个可以反复使用的map ,我们更需要在空间中寻找到一条可以移动的路径。比如,无人汽车从A到B ,我们只需要生成一次路径即可,回头时障碍物可能已经发生变化。这时候我们使用RRT算法。

机器人学 —— 轨迹规划(Sampling Method)  机器人学 —— 轨迹规划(Sampling Method)

 其root 为起点与终点,只要最后两棵树可以合并,那么则找到了起点到终点的路径