基于Bug算法的移动机器人路径规划研究

赵文瑜

摘   要：當移动机器人具有有限的计算能力时，Bug算法是最简单有效的路径规划算法，适用于环境地图未知或环境快速变化的情况，这些算法从机器人传感器，如激光雷达传感器来获得的本地信息和全局目标信息，以朝向目标的直线运动和沿着障碍的边界运动这两种简单的运动方式来到达目标点。文章对此展开了分析。

关键词：路径规划;Bug算法;机器人

基于Bug的路径规划算法有3种，分别为Bug0，Bug1，Bug2。使用这些算法的移动机器人可以避开障碍物并朝着目标前进。其需要使用的内存低，并且获得的路径通常远非最佳。Lumelsky等[1-2]首先实现Bug算法，然后进行了一些改进[3-4]。文章在下面内容主要描述了Bug算法中的3个基本算法，并使用Bug0算法在Matlab中进行仿真，验证其算法的有效性。

1    Bug1算法

与Bug0相比，Bug1算法需要使用更多内存来运行更多计算。在每次迭代中，其需要计算到目标点位置的欧几里德距离并记住障碍物圆周上与目标的最近点。其操作流程如下：

（1）沿直线向目标移动，直到遇见障碍物或达到目标。

（2）如果检测到障碍物，则向左转并沿着障碍物的整个边界运动并测量到目标的欧几里德距离。当再次到达最初检测到障碍物的点时，沿着最接近目标轮廓上点的方向跟随障碍物的轮廓，然后恢复直线向目标移动。

用Bug1算法时，机器人首先完全地围绕障碍物，然后从距离目标最短的点离开。当然这种方法效率很低，但是可保证机器人会到达任何可达的目标。Bug1算法操作的一个例子如图1所示。

根据图1中Bug1算法做出的路径规划，在最坏的情况下，其路径长度为障碍物轮廓的长度中的1.5倍，而不是从开始到目标的欧几里德距离。这个距离远比从起始点到目标点的欧几里德距离长很多。对于从开始到目标在其路径上检测到的每个障碍物，算法从障碍物的边界轮廓上找到一个起始点和一个离开点，因此不会多次检测到障碍物，更不会在同一障碍物的边界轮廓上走重复的路线。当算法不止一次检测到同一障碍物时，知道在障碍物内捕获了起点或目标点，并且可以终止路径搜索。因为没有可行的目标路径，也就是图1中最右边的情况，因此该算法可以有效地识别无法达到的目标点。

2    Bug2算法

用Bug2算法时，机器人开始跟踪物体的轮廓，但当它能直接移动至目标时，就立即偏离障碍物的边缘。这个改进的算法，使机器人行走具有非常短的总路径。Bug2算法总是尝试在主线上移动，该主线则为连接起始点和目标点的直线，如图2所示。

Bug2算法流程如下：

（1）遇到障碍物之前在主线上运动，直到到达目标点时停止。

（2）如果检测到障碍物，则沿着障碍物轮廓运动，直到到达主线。

从Bug1和Bug2算法的比较可以得到以下结论：Bug1是更彻底的搜索算法，因为会评估所有的搜索算法在做出决定之前的可能性。Bug2是贪婪的算法，因为其选择了看起来很有希望的第一个选项。在大多数情况下，Bug2算法比Bug1更有效。但是，Bug1算法的操作更容易预测。

3    基于Bug0的路径规划算法

Bug0算法的基本流程：

（1）向目标移动，直到检测到障碍物或达到目标。

（2）如果检测到障碍物，则向左（或向右，但始终在同一方向）左转并跟随障碍物的轮廓，直到再次朝向目标的直线运动。Bug0路径规划算法结果如图3所示。

Bug0算法成功找到左侧环境中目标的路径，而右侧环境中则不成功。通过对比可以看出以上3种Bug算法中，Bug0算法的路径规划其距离最短、效率最高。

4    仿真实验

用Bug0算法进行移动机器人进行路径规划仿真实验，根据Bug0算法，如果移动机器人距离障碍物足够远（>0.2 m），机器人直接向目标点运动。如果其靠近障碍物，则机器人沿着障碍物的边界运动。在Matlab中对Bug0算法的进行仿真实验验证，移动机器人在10×10 m的有障碍环境中运动，将障碍物膨胀为圆型，起始点坐标和目标点坐标分别设置为（0.5，0.5）和（9.5，9.5）。其获得的机器人路径如图4所示。

通过实验结果可以看出，机器人可以准确有效地到达目标位置，能够缩短机器人路径冗余并提高机器人的运动效率。

[参考文献]

[1]LUMELSKY V，STEPANOV P.Dynamic path planning for a mobile automaton with limited information on the environment[J].IEEE Transactions on Automatic Control，1986（11）：1058-1063.

[2]SANKARAN A A，VIDYASAGAR M.A new path planning algorithm for moving a point object amidst unknown obstacles in a plane[C].Honolulu：IEEE Conference on Robotics and Automation，1990.

[3]KAMON I，RIVLIN E.Sensory-based motion planning with global proofs[J].IEEE Transactions on Robotics and Automation，1997（6）：814-821.

[4]LAUBACH S，BURDICK J.An autonomous sensor-based path-planner for planetary microrovers[C].Detroit：IEEE Conference on Robotics and Automation，1999.

Research on mobile robot path planning based on Bug algorithm

Zhao Wenyu

（School of Electronic & Information Engineering， North China Institute of Science and Technology， Sanhe 065201， China）

Abstract：Bug algorithms are the simplest path planning algorithms that assume only local knowledge and do not need a map of the environment. Therefore， they are appropriate in situations where an environment map is unknown or it is changing rapidly and also when the mobile platform has very limited computational power. These algorithms use local information obtained from their sensors （e.g.， distance sensor） and global goal information. Their operation consists of two simple behaviors： motion in a straight line toward the goal and obstacle boundary following. This paper analyzes it.

Key words：path planning; Bug algorithm; robot