Bug避障算法简介
移动机器⼈智能的⼀个重要标志就是⾃主导航，⽽实现机器⼈⾃主导航有个基本要求——避障。避障是指移动机器⼈根据采集的障碍物的状态信息，在⾏⾛过程中通过传感器感知到妨碍其通⾏的静态和动态物体时，按照⼀定的⽅法进⾏有效地避障，最后达到⽬标点。实现避障与导航的必要条件是环境感知，在未知或者是部分未知的环境下避障需要通过传感器获取周围环境信息，包括障碍物的尺⼨、形状和位置等信息，因此传感器技术在移动机器⼈避障中起着⼗分重要的作⽤。避障使⽤的传感器主要有超声传感器、视觉传感器、红外传感器、激光传感器等。 ⽬前移动机器⼈的避障根据环境信息的掌握程度可以分为障碍物信息已知（global knowledge of the environment）、障碍物信息部分未知或完全未知（local knowledge of the environment）两种。实际⽣活中，绝⼤多数的情况下，机器⼈所处的环境都是动态的、可变的、未知的。在⼀系列避障算法中Bug算法是最简单的机器⼈避障⽅法，其基本思想是让机器⼈朝着⽬标前进，如果遇到障碍则先环绕障碍物移动，然后绕离它，继续驶向⽬标。为完成避障需要机器⼈能实现两种功能：沿直线⾏⾛和跟踪障碍物的边界。Bug算法的优势之⼀就在于其只需要使⽤触觉传感器获得周围环境的局部信息⽽不必了解全局情况。
Bug1算法
花龄盛会如图2.1所⽰，起始点和⽬标点分别为q start和q goal. 初始时刻i = 0，令q L0 = q start，并称连接q L i和q goal的线段为m-line. 没有遇到障碍时，机器⼈沿着m-line朝⽬标q goal直线移动. 如果遇到障碍，则称点q H1为第⼀次遇到障碍时的撞击点（hit point）. 接着，机器⼈环绕障碍物移动直⾄返回q H1点。然后判断出障碍物周边上离⽬标最近的点，并移到这个点上，该点称为离开点（leave point），由q L1表⽰。从q L1开始机器⼈再次沿直线驶向⽬标，如果这条线与当前障碍物相交，则不存在到达⽬标的路径（如图2.2所⽰）。 Bug1算法的效率很低，但可以保证机器⼈能到达任何可达的⽬标。 Bug2算法
机器⼈先跟踪障碍物的轮廓，与Bug1不同的是，当它能直接移动到⽬标点时，就⽴即离开。如图2.3所⽰，Bug2算法中的m-line连
接q start和q goal，为⼀条固定不变的直线。遇到障碍物时机器⼈会进⼊轮廓跟踪模式，当其到达m-line上⼀个接近⽬标点的位置后（⽽⾮初次遇到障碍物的撞击点），继续沿m-line驶向⽬标。如果机器⼈再次在m-line遇到上之前的撞击点，则到达⽬标的路径不存在（如图2.3中第⼆种情况所⽰）。
Bug2算法在⼀般情况下具有很短的移动路径，然⽽这种策略并⾮完美。如图2.4所⽰的螺旋形障碍物，其边界与m-line多次相交，我们可以根据上述Bug2算法的伪代码确定其运动路径：
1.qstart→qgoal，遇到障碍物，到达撞击点qH1；
刘秀发明了共享2.qH1开始环绕障碍物，直到与m-line相交到达m点（此时进⾏判断：没有到达⽬标；没有再次遇到qH1；相⽐qH1点m点离⽬标更近；继续朝⽬标前进不会碰到障碍），则qL1=m，i=2。机器⼈从qL1沿着m-line继续朝⽬标前进；
3.再次遇到障碍物，到达撞击点qH2，然后沿着障碍物边界移动，直到再次与m-line相交到达m点（此时进⾏判断：没有到达⽬标；没有再次遇到qH2；但继续朝⽬标前进会碰到障碍），由于不满⾜离开点的条件，则继续环绕；
4.机器⼈环绕边界到达qH1点，与m-line相交（此时进⾏判断：没有到达⽬标；没有再次遇到qH2；但继续朝⽬标前进会碰到障碍），由于不满⾜离开点的条件，则继续环绕⽬标；
5.机器⼈继续环绕边界到达qL1点，与m-line相交（此时进⾏判断：没有到达⽬标；没有再次遇到qH2；继续朝⽬标前进不会碰到障碍；但此
时相⽐qH2机器⼈离⽬标位置更远），因此也不满⾜离开点条件，则继续环绕；
6.机器⼈环绕边界，与m-line相交到达m点（此时进⾏判断：没有到达⽬标；没有再次遇到qH2；继续朝⽬标前进不会碰到障碍；但此时相⽐qH2机器⼈离⽬标位置更远），因此也不满⾜离开点条件，则继续环绕；
7.机器⼈环绕边界，与m-line相交到达m点（此时进⾏判断：没有到达⽬标；没有再次遇到qH2；继续朝⽬标前进不会碰到障碍；相⽐qH2机器⼈离⽬标位置更近），满⾜离开点条件，则qL2=m，i=3；战时兵员动员
8.机器⼈从qL2沿着m-line继续朝⽬标前进，到达⽬标位置。
经济研究导刊
Bug1 VS Bug2
• Bug1 is an exhaustive search algorithm——it looks at all choices before commiting
• Bug2 is a greedy algorithm—— it takes the first thing that looks better
• In many cases, Bug2 will outperform Bug1, but Bug1 has a more predictable performance overallanchorfree
对外贸易增长的原因
In fact, Bug1 and Bug2 illustrate two basic approaches to search problems. For each obstacle that it encounters, Bug1 performs
an exhaustive search（穷举搜索） to find the optimal leave point. This requires that Bug1 traverse the entire perimeter of the obstacle, it is certain to have found the optimal leave point. In contrast, Bug2 uses an opportunistic（投机取巧的）approach. When Bug2 finds a leave point that is better than any it has seen before, it commits to that leave point. Such an algorithm is also called greedy, since it opts for the first promising option that is found. When the obstacles are simple, the greedy approach of Bug2 gives a quick payoff, but when the obstacles are complex, the more conservative approach of Bug1 often yields better performance. 即障碍物的“复杂度”越⼤的情况下，Bug1算法相⽐Bug2算法更有优势。
参考：
Principles of Robot Motion: Theory, Algorithms, and Implementation
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议