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

98 MOTION PLANNING FOR A MOBILE ROBOT

j
that after having defined a point H , MA will never define this point again as
an H or an L point. Therefore, on each of the subsequent local cycles (if any),
j
point H will be passed not along the M-line but along the obstacle boundary.
j
After having left point H , MA can expect one of the following to occur:
j
MA will never return again to H ; this happens, for example, if it leaves the
current obstacle altogether or reaches the Target T .
j
MA will define at least the first pair of points (L ,H j+1 ), ... , and will then
j
return to point H , to start a new local cycle.
j
j
MA will come back to point H without having defined a point L on the
previous cycle. This means that MA could find no other intersection point
j
Q of the line (H ,T ) with the current obstacle such that Q would be
j
closer to the point T than H , and the line (Q, T ) would not cross the
current obstacle at Q. This can happen only if either MA or point T are
trapped inside the current obstacle (see Figure 3.10). The condition is both
necessary and sufficient, which can be shown similar to the proof in the
target reachability test for algorithm Bug1 (Section 3.3.1).
Based on this observation, we now formulate the test for target reachability for
algorithm Bug2.

T

T

S

S

(a) (b)

Figure 3.10 Examples where no path between points S and T is possible (traps), algo-
rithm Bug2. The path is the dashed line. After having defined the hit point H 2 , the robot
returns to it before it defines any new leave point. Therefore, the target is not reachable.