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

MOTION PLANNING WITH INCOMPLETE INFORMATION 61

medieval churches and castles in Europe had mazes in their gardens or as inside
mosaics on the floor. Many mazes are built even today for public amusement and
contemplation. Some labyrinth builders tried to emulate the famous labyrinth of
the Chartres cathedral in France; one Chartres-type labyrinth appears in the Grace
Cathedral in San Francisco. Even Washington, D.C., the United States capital,
has its own tiny labyrinth in the small pretty St. Thomas Parish Park located in
the heart of Dupont Circle.
Most collections of puzzles contain labyrinth problems. A “Bible” of labyrinths
that is monumental in coverage, unique, and marvelously written is the book by
Hermann Kern, Through the Labyrinth: Designs and Meanings over 5000 Years
(originally published in Germany in 1983 [40] and translated into English in
2000 [41]).
A simple labyrinth is a set of corridors lying in the plane and connected
in intricate ways. A labyrinth can be described by a graph whose edges rep-
resent corridors and vertices (vertices are the points where the corridors meet).
Figure 2.19a shows the famous labyrinth in the garden at Hampton Court in
London; the corresponding graph is shown in Figure 2.19b.
The problem is as follows: Given two points in a labyrinth, start S and target T ,
can a method be designed that would guarantee a path from S to T ? It is usually
assumed that the traveler has no beforehand knowledge about the labyrinth and
has a way to mark the corridors and corridor intersections. In graph terms, this is
a graph-searching problem: Given two graph vertices S and T , design a method
to generate a path from S to T if one exists.
A general maze does not have to have explicit corridors and intersections.
An arbitrary scene with obstacles presents a kind of maze. Any motion planning
task for a robot in the plane can therefore be seen as a maze search. Such tasks
can be naturally reduced to a graph search. Consider the scene in Figure 2.20a.
Suppose a point robot plans to start at point S and reach point T . Suppose the
robot knows its own location and that of T but has no beforehand knowledge
about obstacles on its way. Then, it would be reasonable for the robot to take the
shortest route to T , a straight line. Let us call this line the Main line,or M-line.
If M-line happens to be free, the robot reckons, this would be the fastest route
to T ; if there are obstacles on the way, it will deal with them somehow. (The
notion of Main line will appear often in the following chapters.)
Together with the scene, this strategy defines a graph that, although unknown
to the robot, relates to the physical reality. Vertices of the graph are points S
and T , as well as intersection points between M-line and obstacle boundaries;
its edges are segments of M-line outside the obstacles and segments of obstacle
boundaries (Figure 2.20b). The graph is called the connectivity graph of the
maze. It has a simple structure: Vertices S and T are of degree one, and all other
vertices are of degree three. Note that since each vertex has an odd number of
edges incident to it, this is not a Euler graph, and so traversing the whole graph
will result in at least some edges being traversed more than once. The graph can
be easily transformed into a Euler graph—for example, by replacing with two
segments each M-line segment that connects two obstacles.