Page 115 - Sensing, Intelligence, Motion : How Robots and Humans Move in an Unstructured World

90 MOTION PLANNING FOR A MOBILE ROBOT

point L. The robot then walks to L by the shortest route (which it knows from
the information it now has) and establishes on it the leave point L. At this point,
algorithm Bug1 prescribes it to move toward T . While performing the test for
target reachability, however, the robot will note that the line (L, T ) enters the
obstacle at L and hence will conclude that the target is not reachable.

3.3.2 Second Basic Algorithm: Bug2

Similar to the algorithm Bug1, the procedure Bug2 is executed at every point of
the robot’s (continuous) path. As before, the goal is to generate a path from the
start to the target position. As will be evident later, three important properties
distinguish algorithm Bug2 from Bug1: Under Bug2, (a) MA can encounter the
same obstacle more than once, (b) algorithm Bug2 has no way of distinguishing
between different obstacles, and (c) the straight line (S, T ) that connects the
starting and target points plays a crucial role in the algorithm’s workings. The
latter line is called M-line (for Main line). In imprecise words, the reason M-line
is so important is that the procedure uses it to index its progress toward the target
and to ensure that the robot does not get lost.
Because of these differences, we need to change the notation slightly: Subscript
i will be used only when referring to more than one obstacle, and superscript j
will be used to indicate the jth occurrence of a hit or leave points on the same
0
or on a different obstacle. Initially, j = 1; L = Start. Similar to Bug1, the Bug2
procedure includes a test for target reachability, which is built into Steps 2b and
2c of the procedure. The test is explained later in this section. The reader may
find it helpful to follow the procedure using an example in Figure 3.5.

ob 2 T

L 2

H 2

L 1
ob 1
H 1

S

Figure 3.5 Robot’s path (dashed line) under Algorithm Bug2.