The Bug2 strategy

An alternative to Bug1 is the Bug2 strategy, which is illustrated in Figure 12.22. The robot always attempts to move along a line that connects the initial and goal positions. When the robot is on this line, the goal direction will be either the same as from the initial state or it will differ by $ \pi $ radians (if the robot is on the other side of the goal). The first step is the same as for Bug1. In the second step, the robot follows the perimeter only until the line is reached and it is able to move in the direction toward the goal. From there, it goes to Step 1. As expressed so far, it is possible that infinite cycles occur. Therefore, a small modification is needed. The robot remembers the distance to the goal from the last point at which it departed from the boundary, and only departs from the boundary again if the candidate point that is closer to the goal. This is applied iteratively until the goal is reached or it is deemed to be impossible.

Figure 12.23: A bad case for Bug2. Only part of the resulting path is shown. Points from which the robot can leave the boundary are indicated.
\begin{figure}\centerline{\psfig{figure=figs/bug2c.eps,width=5.0in} }\end{figure}

For the Bug2 strategy, the total distance traveled is no more than

$\displaystyle d + \frac{1}{2} \sum_{i=1}^{M} n_i p_i ,$ (12.26)

in which $ n_i$ is the number of times the $ i$th obstacle crosses the line segment between the initial position and the goal position. An example that illustrates the trouble caused by the crossings is shown in Figure 12.23.

Figure 12.24: An illustration of the VisBug strategy with unlimited radius.
\begin{figure}\centerline{\psfig{figure=figs/visbug.eps,width=5.0in} }\end{figure}

Figure 12.25: The candidate motions with respect to the range sensor are the directions in which there is a discontinuity in the depth map. The distances from the robot to the small circles are used to select the desired motion.
\begin{figure}\centerline{\psfig{figure=figs/visbugb.idr,width=3.0in} }\end{figure}

Steven M LaValle 2012-04-20