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

MOTION PLANNING FOR A MOBILE ROBOT 77

Class 1. Algorithms in which the robot explores each obstacle that it encounters
completely before it goes to the next obstacle or to the target.
Class 2. Algorithms where the robot can leave an obstacle that it encounters
without exploring it completely.

The distinction is important. Algorithms of Class 1 are quite “thorough”—one may
say, quite conservative. Often this irritating thoroughness carries the price: From the
human standpoint, paths generated by a Class 1 algorithm may seem unnecessarily
long and perhaps a bit silly. We will see, however, that this same thoroughness
brings big benefits in more difficult cases. Class 2 algorithms, on the other hand,
are more adventurous—they are “more human”, they “take risks.” When meeting
an obstacle, the robot operating under a Class 2 algorithm will have no way of
knowing if it has met it before. More often than not, a Class 2 algorithm will win
in real-life scenes, though it may lose badly in an unlucky scene.
As we will see, the sensor-based motion planning paradigm exploits two
essential topological properties of space and objects in it—the orientability and
continuity of manifolds. These are expressed in topology by the Jordan Curve
Theorem [57], which states:

Any closed curve homeomorphic to a circle drawn around and in the vicinity of a
given point on an orientable surface divides the surface into two separate domains,
for which the curve is their common boundary.

The threateningly sounding “orientable surface” clause is not a real constraint. For
our two-dimensional case, the Moebius strip and Klein bottle are the only examples
of nonorientable surfaces. Sensor-based planning algorithms would not work on
these surfaces. Luckily, the world of real-life robotics never deals with such objects.
In physical terms, the Jordan Curve Theorem means the following: (a) If our
mobile robot starts walking around an obstacle, it can safely assume that at some
moment it will come back to the point where it started. (b) There is no way for
the robot, while walking around an obstacle, to find itself “inside” the obsta-
cle. (c) If a straight line—for example, the robot’s intended path from start to
target—crosses an obstacle, there is a point where the straight line enters the
obstacle and a point where it comes out of it. If, because of the obstacle’s com-
plex shape, the line crosses it a number of times, there will be an equal number of
entering and leaving points. (The special case where the straight line touches the
obstacle without crossing it is easy to handle separately—the robot can simply
ignore the obstacle.)
These are corollaries of the Jordan Curve Theorem. They will be very explic-
itly used in the sensor-based algorithms, and they are the basis of the algorithms’
convergence. One positive side effect of our reliance on topology is that geome-
try of space is of little importance. An obstacle can be polygonal or circular, or
of a shape that for all practical purposes is impossible to define in mathematical
terms; for our algorithm it is only a closed curve, and so handling one is as easy
as the other. In practice, reliance on space topology helps us tremendously in