本文作为论文The Gaussian Sampling Strategy for Probabilistic Roadmap Planners的阅读笔记。
        这篇论文出自荷兰乌徳勒支大学的研究人员之手，发表在1999年的ICRA上。其中一位作者算是运动规划领域响当当的人物——Mark H. Overmars。这人名字很有意思哈，“火星人”！他主要研究的是计算机图形学、计算几何，由于这些东西与运动规划紧密相关，使得他在运动规划领域也相当游刃有余。这种模式我很欣赏，因为我对图形学也非常感兴趣。
        闲话少说。这篇论文的主要贡献在于给出了一种能够在困难区域产生较多采样点的策略，而这个策略的灵感竟然来自数字图像处理中的高斯平滑，于是该策略被称为高斯采样（Gaussian sampling）。相对于经典PRM而言，这种采样策略必然造成采样时间的增加——经典PRM是随机采样，这几乎是最简单的采样策略了，而高斯采样已经不是“原生态”的了，因为它经过了有目的的人工干预。然而，下面的分析将得出结论：尽管采样时间增加了，但是采样点更加“精炼”了，使得构建地图的时间不升反降！
        先来看看经典PRM的地图构建算法：

        两个最耗时的步骤是第3步和第8步，因为他们需要几何操作。令$T_{s}$表示产生一个无碰撞采样点所需时间（第3步），$T_{a}$表示将其加入地图所需时间（第4-9步），那么上述算法的总时间为$T=n \left (T_{s}+T_{a} \right )$，其中n是采样点总数。在PRM的标准实现中，$T_{s}$远小于$T_{a}$，这提示我们考虑通过更“认真”地采样来提升算法的时间效率，即通过增加$T_{s}$来减少n。
        有些采样算法是这样工作的：生成一个采样点，检测它是否位于自由空间F，如果是，就将它添加到地图中。注意，这里没有对直线路径进行碰撞检测，因此，一个很好的例子就是Lazy PRM。这种算法的总时间可以表示为$T=n_{t}T_{t}+n_{a}T_{a}$，其中$n_{t}$是尝试过的采样点总数，$n_{a}$是成功加入地图的采样点数目，$T_{t}$是对一个采样点进行碰撞检测的时间，$T_{a}$如前所述，是将一个采样点加入地图所需时间。同样地，$T_{t}$远小于$T_{a}$。道理很简单：对一个点进行碰撞检测远远简单于对很多直线路径进行碰撞检测。这提示我们可以尝试更多的采样点（增加$n_{t}$ ），但是在保留采样点时必须“挑剔”（减少$n_{a}$ ）。这样，虽然在采样的时候花费了更多的时间，但是由于“精选”出的点较少，使得最终的规划时间减少。
        图像处理中有一个著名的“高斯平滑”，这里就借用了它的思想。首先，在d维C-Space中定义高斯分布：$\phi \left (c;\sigma \right )= \frac {1}{\sqrt{2\pi\sigma^{2}}^{d}}e^{-\frac {c^{2}}{2\sigma^{2}}}$。定义函数$Obs \left (c \right )$，当c有碰撞时，$Obs \left (c \right )=1$；否则，$Obs \left (c \right )=0$。函数$f \left (c,\sigma \right )= \int Obs \left (y \right )\phi \left (c-y;\sigma \right )\mathrm{d}x$使用高斯分布平滑C障碍物。为了避免采样点与障碍物碰撞，定义$g \left (c;\sigma \right )= \mathrm{max} \left (0,f \left (c;\sigma \right )-Obs \left (c \right ) \right )$。这就是我们想要的概率分布。在障碍物内部，$g\left (c;\sigma \right )=0$；否则，$g\left (c;\sigma \right )=f \left (c;\sigma \right )$。
        $\sigma$是一个重要参数，它指出了我们想让采样点离障碍物有多近。下面的三幅图示意了利用上述分布在2维C-Space中的采样结果。在每一幅图中，颜色越浅，表示采样点出现于此的概率越高。由图可见，当$\sigma$ 选取适当时，障碍物周围被采样的概率很高。三幅图从左到右，$\sigma$依次减小。

        是时候给出传说中的高斯采样算法了！

        称该算法为高斯采样（Gaussian sampler）的原因在于它产生的采样点遵从$g\left (c;\sigma \right )$ 分布。该算法避免了在C-Space中的一些计算，而只使用了一种操作，即采样点的碰撞检测，这样可以提高算法效率。该算法对采样点是“挑剔”的：只有当一个采样点本身无碰撞且周围有障碍物时，该采样点才会被添加到地图中。这恰好反映了先前讨论的策略，即每一个采样点在加入地图之前都应该精挑细选。高斯采样比随机采样慢的原因在于前者测试两个点却最多只能向地图中加入一个点。乍一看，算法的最后一步要舍去两个刚刚辛辛苦苦测试完的采样点，好像有悖常理，但是这一步却是至关重要的，它避免了在大片的空旷区域添加采样点。
        如前所述，标准差$\sigma$的选择大有讲究。如果我们选择了一个小$\sigma$，则大部分的采样点会很靠近障碍物；如果我们选择了一个大$\sigma$，采样点就几乎均匀分布在自由空间F中了。在本论文中，机器人既能平移（translate）又能旋转（rotate），如果能够选择一个适当的$\sigma$，使得大部分位姿到障碍物的距离最多不超过机器人本身的长度，这样既保能证位姿靠近障碍物，又能允许机器人绕轴旋转。当然，旋转自由度（rotational degrees of freedom）和平移自由度（translational degrees of freedom）本应以不同的方式处理。该算法只是使第二个采样点$c_{2}$的位置（position）遵从高斯分布，而它的方向（orientation）则为任意。不过，实验结果依然不错。
        实验部分和总结部分在此略过。


转载本文请联系原作者获取授权，同时请注明本文来自王彦科学网博客。
链接地址：https://wap.sciencenet.cn/blog-795645-628000.html

上一篇：读书笔记——一种在障碍物周围产生采样点的随机地图方法
下一篇：读书笔记——桥测试，一种解决PRM中窄道问题的好方法