【机器人规划】Bug解析_bug1和bug2算法的优势场景

参考文献

自动驾驶决策规划算法 - Bug Algorithms Bug算法
Robotic Motion Planning: Tangent Bug and Sensors
Introduction to Robotics Bug Algorithms
Bug Algorithms autorob.org
Principles of Robot Motion
Bug updated - annotated.pptx

简介

本文所有图片均来自以下这本书:

Principles of Robot Motion: Theory, Algorithms, and Implementations[M]. MIT Press, 2005.

BUG算法（Bug Algorithms）是一种最简单的避障算法。其算法原理类似昆虫爬行的运动决策策略。在未遇到障碍物时，沿直线向目标运动；在遇到障碍物后，沿着障碍物边界绕行，并利用一定的判断准则离开障碍物继续直行。这种应激式的算法计算简便，不需要获知全局地图和障碍物形状，具备完备性。但是其生成的路径平滑性不够好，对机器人的各种微分约束适应性比较差。

Bug1算法

该算法的基本思想是在没有障碍物时，沿着直线向目标运动可以得到最短的路线。当传感器检测到障碍物时，机器人绕行障碍物直到能够继续沿直线向目标运动。BUG1算法只有两个行为：向目标直行和绕着障碍物的边界走。

Bug2算法

Bug2算法伪代码：

BUG1和BUG2算法提供了搜索问题的两种基本方法：比较保守的BUG1算法进行详细的搜索来获得最佳的离开点。这需要机器人环绕整个障碍物的边界。而BUG2算法使用一种投机的方法。机器人不环绕完整的障碍物，而选择第一个可用的点作为离开点。对于一般的环境，BUG2算法的效率更高；而对于复杂形状的障碍物，保守的BUG1算法性能更优。

Bug2算法在一般情况下具有很短的移动路径，然而这种策略并非完美。如图2.4所示的螺旋形障碍物，其边界与m-line多次相交，我们可以根据上述Bug2算法的伪代码确定其运动路径：

Tangent Bug算法

下图中x代表机器人的位置,细线代表发出的光线,粗线代表了光线被遮挡(说明机器人无法到达这些位置)。

我们用$O_i$标记光线与障碍物相交的边界点:

关于O_i的选择

如上图所示，当机器人探索到障碍物上的 M点后，探索距离就不再减小，即 M点是机器人探索距离在障碍物边界上的局部极小点。机器人开始沿着障碍物边界进行环绕，图中虚线路径就是机器人环绕障碍物时所走的路径。当机器人探测到与目标距离相比 M MM点更近的点时，重新开始接近目标的运动。

Tangent Bug算法伪代码如下：

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

使用Tanget Bug可以有效的提升整体效率,这是激光雷达测量半径为$R$时形成的轨迹,当测量半径退化为0时(变成了接触传感器),Tangent Bug算法就退化成了Bug2算法：

总结

Bug算法是最早被提出来的路径规划算法，很符合直觉，尤其是在完全一无所知的环境下，Bug算法往往能够取得非常不错的效果！