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

56 A QUICK SKETCH OF MAJOR ISSUES IN ROBOTICS

The information-theoretical (or uncertainty) aspect of the problem at hand
points to connections with other fields. In general terms the problem of sensor-
based motion planning can be seen as one of reaching a global goal using local
means. Thus presented, it becomes a fundamental problem, various formulations
of which have been studied in a number of areas. For example, in game the-
ory (differential games and macroeconomics; see, e.g., Ref. 33) one is interested
in conditions under which individualistic interests of many agents can result
in predictable behavior of the whole group. In works on collective behavior,
algorithms are designed whereby a group of individuals can organize a unified
action at a specific moment based on local interaction only, without central-
ized control. In the Firing Squad Problem [34], soldiers are requested, using
only pairwise communication, to agree on a moment when they fire all at once.
In computer science, local operations are used to study database searches with
uncertainty [35]. In geometry, attempts have been made to prove theorems of
Euclidean geometry using local input information [36]. The difficult question of
the relationship between uncertainty and algorithm complexity has been tackled
in Ref. 37.
While some considerations, such as the importance of computational proper-
ties of their methods, still served as a bridge between the Piano Mover’s and
SIM paradigms, with time many divergent issues made them harder and harder
to compare. One such issue is of course the SIM’s favoring continuous com-
putation over the Piano Mover’s one-time computation. The other issue is the
option of optimal solutions inherent in the Piano Mover’s model but inherently
impossible in the SIM model—not because of inferior algorithms, one should
add hastily, but because of the inherent lack of relevant input information. Still
another issue, as we shall see, is the difference in how both models deal with
algorithm complexity (again, not because of algorithms’ specifics but because
of the nature of uncertainty). What counts in the Piano Mover’s model is the
complexity of the whole robot scene. In contrast, what counts in the SIM model
is the amounts of robot’s “wandering” in the scene and visits to some previ-
ously visited places in the scene. Let us consider these and other factors in
more detail.
The SIM paradigm formulation includes an assumption that information about
the robot’s surroundings comes in real time, usually from its sensors. Except
perhaps for some exotic sensors (“X-ray” vision and the like), sensory information
is of local, rather than global, nature—sensors tell one something about their
surroundings. In the SIM algorithms that will be developed in the following
chapters, the only input information available to the robot at all times is its own
coordinates and those of the target location. As the robot starts moving, new
information appears from its sensors.
To exhaust the extreme case and demonstrate the algorithm completeness, we
will start the algorithm development with the “ultra-local” tactile sensor. That is,
the robot learns about an obstacle’s presence only when it touches it physically.
Later we will extend the resulting strategies to the case of proximal sensing, such
as vision.