文章来源：

原文链接：古月居

Bug算法假设机器人是在平面上运动的一个点,并且配备有接触传感器或者距离传感器.该算法有两个动作:直线行走和沿着(障碍物的)边界行走.

1 Bug1

下图中,带箭头的虚线就是Bug1算法运行时机器人的路径.

算法过程：

2 Bug2

Bug1算法每次遇到障碍物就要绕着障碍物行走一圈,这样大大降低了效率,于是在Bug1的算法上加以改进,形成了Bug2算法.

算法过程：

同Bug1一样,机器人沿着起始点和目标点连成的直线行走

遇到障碍物时,机器人沿着障碍物行走直到碰到起始点和目标点连成的直线

重复上述过程,直到走到目标位置

当然,在极端情况下,Bug2的效率不一定就会高,比如下面这种情况.

3 Tangent Bug

3.1 算法背景

假设机器人上安装有360°激光雷达(或者红外距离传感器),那么我们可以测得每束光线到达障碍物的距离.下图中 x 代表机器人的位置,细线代表发出的光线,粗线代表了光线被遮挡(说明机器人无法到达这些位置).

安装有激光雷达的机器人

我们用Oⅰ标记光线与障碍物相交的边界点.

标记出相交点

3.2 算法过程

1、机器人直接沿着目标方向按直线行走,直到激光雷达检测到了障碍物.

2、用虚线的圆表示激光雷达的检测范围.

3、标记出 Oⅰ然后机器人向着启发距离最小的Oⅰ前进

3.3 Oⅰ的选择

不同目标位置对机器人决策的影响

当然Oⅰ的值是实时更新的,这将导致最后机器人靠近障碍物时行走的轨迹是一条曲线而不是直线.

机器人的轨迹靠近障碍物时变成曲线

3.4 激光雷达半径对算法的影响

使用Tanget Bug可以有效的提升整体效率,这是激光雷达测量半径为R时形成的轨迹.

传感器测量范围为R

当测量半径退化为0时(变成了接触传感器),Tangent Bug算法就退化成了Bug2算法.

接触传感器

总结：

Bug算法是最早被提出来的路径规划算法,它符合直觉而且能取得不错的运行效果.