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

MOTION PLANNING WITH INCOMPLETE INFORMATION 59

Below we first review those first graph-searching approaches, switching then to
the proper prior work on robot motion planning.

2.9.1 The Beginnings

Leonhard Euler, perhaps the most famous mathematician of all time, was born
on April 15, 1707, in Basel, Switzerland, and spent most of his career, between
1727 and 1741 and then from 1766 until his death on September 18, 1783, in
St. Petersburg, Russia, holding a prestigious position of academician—that is,
a full member of Russian Academy of Sciences. As his fame grew, in 1733 he
succeeded Daniel Bernoulli to the chair of mathematics in the Academy. It was
at this first period of his St. Petersburg career, in 1736, that Euler proposed and
solved a problem that was to become famous under the name K¨oenigsberg Bridge
Problem. This work marked the beginning of two new mathematical disciplines,
graph theory and topology. It also gives an important insight into the robot motion
planning problem.
The city of K¨ oenigsberg (called today Kaliningrad and being a part of Russia)
was divided into two parts by the Pregel River, with the Island of Kneiphof
in the middle. Seven bridges connected the island with the rest of the city (see
Figure 2.18a). The question posed to Euler by the city’s residents was this: Can a
pedestrian, starting at some point, pass all seven bridges and return to the starting
point so that he will traverse each bridge exactly once?
To find the solution for the puzzled residents of K¨ oenigsberg, Euler decided
to first reduce the problem to an equivalent abstract problem. In a leap of imag-
ination, he said that the shapes and dimensions of the masses of lands that the
bridges connect (A, B, C, D, Figure 2.18a) are immaterial for the problem. What
matters are the connectivity properties of the scene, what today we would call
the topological properties of space. This argument became the beginning of the
discipline of topology. Euler denoted the land masses as vertices of a diagram,
and he denoted the bridges as edges connecting the vertices (Figure 2.18b); hence
the graph theory was born.

C
c d C
g
g
c d
A
e D A e D
a b
a b f
B f
B
(a) (b)
Figure 2.18 The K¨ oenigsberg Bridge Problem.