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

BASIC ALGORITHMS 93

L 3

T

H 3

L 2
H 2

L 1

H 1
S
Figure 3.8 Robot’s path in an in-position case; here point S is outside of the obstacle,
and T is inside.

Moreover, the only obstacles that can be met by MA are those that intersect the
M-line (straight line (Start, Target)).

Definition 3.3.1. For the given local direction, a local cycle is created when MA
has to pass some point of its path more than once.

In the example in Figure 3.5, no local cycles are created; in Figures 3.6 and 3.8
there are local cycles.

Definition 3.3.2. The term in-position refers to a mutual position of points (Start,
Target) and a given obstacle, such that (1) the M-line crosses the obstacle bound-
ary at least once, and (2) either Start or Target lie inside the convex hull of the
obstacle. The term out-position refers to a mutual position of points (Start, Target)
and a given obstacle, such that both points Start and Target lie outside the convex
hull of the obstacle. A given scene is referred to as an in-position case if at least
one obstacle in the scene creates an in-position situation; otherwise, the scene
presents an out-position case.

For example, the scene in Figure 3.3 is an in-position case. Without obstacle
ob 3 , the scene would have been an out-position case.
We denote n i to be the number of intersections between the M-line (straight
line (S, T ))and the ith obstacle; n i is thus a characteristic of the set (scene, Start,
Target) and not of the algorithm. Obviously, for any convex obstacle, n i = 2.