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

94 MOTION PLANNING FOR A MOBILE ROBOT

If an obstacle is not convex but still n i = 2, the path generated by Bug2 can
be as simple as that for a convex obstacle (see, e.g., Figure 3.5, obstacle ob 2 ).
Even with more complex obstacles, such as that in Figure 3.6, the situation and
the resulting path can be quite simple. For example, in this same scene, if the
M-line happened to be horizontal, we would have n i = 2 and a very simple path.
The path can become more complicated if n i > 2 and we are dealing with
an in-position case. In Figure 3.6a, the segment of the boundary from point H 1
to point L1, (H1,L1), will be traversed three times: segments (L1,L2) and
(H2,H1), twice each; and segments (L2,L3) and (H3,H2), once each. On the
other hand, if in this example the M-line line extends below, so that point S is
under the whole obstacle (that is, this becomes an out-position case), the path
will again become very simple, with no local cycles (in spite of high n i number).

Lemma 3.3.4. Under Bug2, MA will pass any point of the ith obstacle boundary
at most n i /2 times.

Proof: As one can see, procedure Bug2 does not distinguish whether two con-
secutive obstacle crossings by the M-line (straight line (S, T )) correspond to the
same or to different obstacles. Without loss of generality, assume that only one
j
obstacle is present; then we can drop the index i. For each hit point H ,the
procedure will make MA walk around the obstacle until it reaches the cor-
j
responding leave point, L . Therefore, all H and L points appear in pairs,
j
j
(H ,L ). Because, by the model, all obstacles are of finite “thickness,” for each
j
j
j
j
j
pair (H ,L ) an inequality holds, d(H )> d(L ). After leaving L ,MAwalks
along a straight line to the next hit point, H j+1 . Since, according to the model,
the distance between two crossings of the obstacle by a straight line is finite, we
j
have d(L )>d(H j+1 ). This produces a chain of inequalities for all H and L
points,
1 1 2 2 3 3
d(H )>d(L )>d(H )>d(L )>d(H )>d(L )> ·· · (3.8)
Therefore, although any H or L point may be passed more than once, it will
be defined as an H (correspondingly, L) point only once. That point can hence
generate only one new passing of the same segment of the obstacle perimeter. In
j
j
other words, each pair (H ,L ) can give rise to only one passing of a segment
of the obstacle boundary. This means that n i crossings will produce at most n i /2
passings of the same path segment. Q.E.D.
The lemma guarantees that the procedure terminates, and it gives a limit on
the number of generated local cycles. Using the lemma, we can now produce an
upper bound on the length of paths generated by algorithm Bug2.
Theorem 3.3.3. The length of a path generated by algorithm Bug2 will never
exceed the limit
n i p i
P = D + (3.9)
2
i