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

78 MOTION PLANNING FOR A MOBILE ROBOT

computational savings: There is no need to know objects’ shapes and dimensions
in advance, and there is no need to describe and store object descriptions once
they have been visited.
In Section 3.1 below, the formal model for the sensor-based motion planning
paradigm is introduced. The universal lower bound on paths generated by any
algorithm operating under this model is then produced in Section 3.2. One can see
the bound as the length of a path that the best algorithm in the world will gener-
ate in the most “uncooperating” scene. In Sections 3.3.1 and 3.3.2, two provably
correct path planning algorithms are described, called Bug1 and Bug2, one from
Class 1 and the other from Class 2, and their convergence properties and perfor-
mance upper bounds are derived. Together the two are called basic algorithms,
to indicate that they are the base for later strategies in more complex cases. They
also seem to be the first and simplest provable sensor-based planning algorithms
known. We will formulate tests for target reachability for both algorithms and
will establish the (worst-case) upper bounds on the length of paths they generate.
Analysis of the two algorithms will demonstrate that a better upper bound on
an algorithm’s path length does not guarantee shorter paths. Depending on the
scene, one algorithm can produce a shorter path than the other. In fact, though
Bug2’s upper bound is much worse than that of Bug1, Bug2 will be likely
preferred in real-life tasks.
In Sections 3.4 and 3.5 we will look at further ways to obtain better algorithms
and, importantly, to obtain tighter performance bounds. In Section 3.6 we will
expand the basic algorithms—which, remember, deal with tactile sensing—to
richer sensing, such as vision. Sections 3.7 to 3.10 deal with further extensions
to real-world (nonpoint) robots, and compare different algorithms. Exercises for
this chapter appear in Section 3.11.

3.1 THE MODEL

The model includes two parts: One is related to geometry of the robot (automaton)
environment, and the other is related to characteristics and capabilities of the
automaton. To save on multiple uses of words “robot” and “automaton,” we will
call it MA, for “moving automaton.”

Environment. The scene in which MA operates is a plane. The scene may be
populated with obstacles, and it has two given points in it: the MA starting
location, S, and the target location, T . Each obstacle’s boundary is a sim-
ple closed curve of finite length, such that a straight line will cross it in
only finitely many points. The case when the straight line is tangential to an
obstacle at a point or coincides with a finite segment of the obstacle is not a
“crossing.” Obstacles do not touch each other; that is, a point on an obstacle
belongs to one and only one obstacle (if two obstacles do touch, they will be
considered one obstacle). The scene can contain only a locally finite number
of obstacles. This means that any disc of finite radius intersects a finite set of