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

58 A QUICK SKETCH OF MAJOR ISSUES IN ROBOTICS

be independent of the length of paths, in the following sense. We can say, for
example, that the algorithm A is better than the algorithm B because their n
numbers are 2 and 3.5, respectively. That is, under algorithm A the robot will
visit the same piece of its path at most twice, whereas under algorithm B it can
visit a piece of its path at most 3.5 times.
One inherent weakness in algorithms with incomplete information is that the
problem dimensionality cannot be made arbitrarily high. This drawback, again,
comes from the nature of dealing with uncertainty, not from the lack of good algo-
rithms. Consider, for example, a point robot flying in the three-dimensional space,
like a fly. If the robot meets an obstacle, it has an infinite number of possibilities
for passing around it. Given the robot’s limited knowledge about the scene, its
difficulty is unsurmountable: While good sensing will often help, in the worst
case the robot may have to search an infinite number of paths to find one accept-
able path. Luckily, for the cases of practical interest—mobile robots moving on
a 2D surface and 3D arm manipulators—the situation is inherently easier.
The lack of information about the robot environment dictates a shift of empha-
sis in the SIM paradigm from objects’ geometry to their topology. Relying on
geometric properties of objects, as in the Piano Mover’s model, would make
SIM algorithms too brittle. We will see that a more sensible approach is to rely
on the scene’s topological properties; this allows one to tolerate uncertainty in
objects’ geometry. Hence there is a corresponding shift in the SIM paradigm
from computational geometry tools to those from topology.
There are two other factors that have not been mentioned yet and that are
often neglected in both the Piano Mover’s and SIM algorithms. One is the robot
dynamics. If the robot is heavy and moves relatively fast, no strategy in the
world will prevent it from collisions unless this strategy is capable of handling
the relation between the robot dynamics, its speed, its sensing, and of course the
robot’s goal. A submarine cannot stop on a dime: Its motion control system has
to process an impending collision in advance; how it avoids collision will also
depend on what it plans to do next. In other words, a realistic motion planning
system may well need to account for the system dynamics. This factor will be
considered in Chapter 4.
The second factor relates to the robot’s shape and dimensions. There is always
a question of how an algorithm that assumes a point robot will work for a real
robot with blood and flesh. A small robot can pass where a big robot will not.
One can pass a narrow corridor with folded arms, but won’t be able to do it
with outstretched arms. Besides accounting for the robot dimensions, this also
suggests the effect of robot kinematics on motion planning.
We will see in the next section that the first serious approaches to the motion
planning problem started with an abstract problem of searching a graph. The
major actors in the events had no idea that their work would be a contribution
to robotics. Some formulated it as a maze-searching problem, in a rather narrow
way, where a maze is defined as something that would be practically equivalent
to a graph. We will see in the sequel that something is lost when replacing a
scene by a graph: A graph may lose some information from the original problem.