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

74 MOTION PLANNING FOR A MOBILE ROBOT

algebraic and semialgebraic sets; representation of the scene with intermediate
structures such as connectivity graphs; reduction of the scene to a discrete space;
and so on. Our robot will treat obstacles as they are, as they are sensed by its
sensor. It will deal with the real continuous space—which means that all points
of the scene are available to the robot for the purpose of motion planning.
The approach based on this model (which will be more carefully formalized
later) forms the sensor-based motion planning paradigm, or, as we called it above,
SIM (Sensing–Intelligence–Motion). Using algorithms that come out of this
paradigm, the robot is continuously analyzing the incoming sensing information
about its current surroundings and is continuously planning its path. The emphasis
on strictly local input information is somewhat similar to the approach used
by Abelson and diSessa [36] for treating geometric phenomena based on local
information: They ask, for example, if a turtle walking along the sides of a
triangle and seeing only a small area around it at every instant would have
enough information to prove triangle-related theorems of Euclidean geometry. In
general terms, the question being posed is, Can one make global inferences based
solely on local information? Our question is very similar: Can one guarantee a
global solution—that is, a path between the start and target locations of the
robot—based solely on local sensing?
Algorithms that we will develop here are deterministic. That is, by running
the same algorithm a few times in the same scene and with the same start and
target points, the robot should produce identical paths. This point is crucial: One
confusion in some works on robot motion planning comes from a view that the
uncertainty that is inherent in the problem of motion planning with incomplete
information necessarily calls for probabilistic approaches. This is not so.
As discussed in Chapter 1, the sensor-based motion planning paradigm is dis-
tinct from the paradigm where complete information about the scene is known
to the robot beforehand—the so-called Piano Mover’s model [16] or motion
planning with complete information. The main question we ask in this and the
following chapters is whether, under our model of sensor-based motion plan-
ning, provable (complete and convergent are equivalent terms) path planning
algorithms can be designed. If the answer is yes, this will mean that no matter
how complex the scene is, under our algorithms the robot will find a path from
start to target, or else will conclude in a finite time that no such path exists if
that is the case.
Sometimes, approaches that can be classified as sensor-based planning are
referred to in literature as reactive planning. This term is somewhat unfortunate:
While it acknowledges the local nature of robot sensing and control, it implicitly
suggests that a sensor-based algorithm has no way of inferring any global char-
acteristics of space from local sensing data (“the robot just reacts”), and hence
cannot guarantee anything in global terms. As we will see, the sensor-based
planning paradigm can very well account for space global properties and can
guarantee algorithms’ global convergence.
Recall that by judiciously using the limited information they managed to get
about their surroundings, our ancestors were able to reach faraway lands while