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

12 MOTION PLANNING—INTRODUCTION

(e) They are exceedingly complex computationally in more or less complex
practical tasks.
2. Topological Approaches. Humans and animals rarely face situations where
one can approach the motion planning problem based on complete informa-
tion about the scene. Our world is messy: It includes shapeless hard-to-describe
objects, previously unseen settings, and continuously changing scenes. Even if
faced with a “geometric”-looking problem, say, finding a path from point A to
point B in a room with 10 octagonal tables, we would never think of com-
puting first the whole path. We take a look at the room, and off we go. We
are tuned to dealing with partial information coming from our sensors. If we
want our robots to handle unstructured tasks, they will be thrown in a similar
situation.
In a number of ways, topological approaches are an exact opposite of the
geometrical approaches. What is difficult for one will be likely easy for the other.
Consider the above example of finding a path from point A to point B in a
room with a few tables. The tables may be of the same or of differing shapes; we
do not know their number, dimensions, and locations. A common human strategy
may look something like this: While at A, you glance at the room layout in the
direction of point B and start walking toward it. If a table appears on your way,
you walk around it and continue toward point B. The words “walking around”
mean that during this operation the table is on the same side from you (say, on
the left). The table’s shape is of no importance: While your path may repeat the
table’s shape, “algorithmically” it is immaterial for your walk around it whether
the table is circular or rectangular or altogether highly nonconvex. Why does
this strategy represent a topological, rather than geometric, approach? Because it
relies implicitly on the topological properties of the table—for example, the fact
that the table’s boundary is a simple closed curve—rather than on its geometric
properties, such as the table’s dimensions and geometry.
We will see in Chapter 3 that the aforementioned rather simplistic strategy is
not that bad—especially given how little information about the scene it requires
and how elegantly simple is the connection between sensing and decision-making.
We will see that with a few details added, this strategy can guarantee success in
an arbitrarily complex scene; using this strategy, the robot will find a path if one
exists, or will conclude “there is no path” if such is the case.
On the negative side, since no full information is available in this process, no
optimality of the resulting path can be guaranteed. Another minus, as we will see,
is that generalizations of such strategies to arm manipulators are dependent on
the robot kinematics. Let us summarize the properties of topological approaches
to motion planning:
(a) They are suited to unstructured tasks, where information about the robot
surroundings appears in time, usually from sensors, and is never complete.
(b) They rely on topological, rather than geometrical, properties of space.
(c) They cannot in principle deliver an optimal solution.