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

60 A QUICK SKETCH OF MAJOR ISSUES IN ROBOTICS

The path that the K¨ oenigsberg citizens wanted is called today a Euler path,
and the graph it corresponds to is called a Euler graph. Define the number of
edges incident to a graph vertex as the vertex degree. In today’s formulation the
related theorem sounds as follows:

Theorem 2.9.1 (Euler [38]). A finite graph G is an Euler graph if and only if
(a) G is connected and (b) every vertex of G is of an even degree.

In the case of distinct starting and final points (which is the situation typical
for the robot motion planning problems), exactly two vertices must be of an odd
degree. For the K¨ oenigsberg Bridge Problem the answer to the question posed to
Euler is therefore “no” because all the vertices on the corresponding graph are
of an odd degree.
As we saw above in the role of connectivity graphs in the Piano Mover’s
model, graph theory became an important tool in designing motion planning
strategies with complete information. We will see in Chapters 3, 5, and 6 that
topology became a no less important tool in sensor-based motion planning.
Neither Euler nor many of his followers asked explicitly what information
about the scene was available to the traveler in the K¨ oenigsberg Bridge Problem. 6
7
It was implicitly assumed that the traveler had complete information. What if he
didn’t? What if at any moment of the trip the traveler’s knowledge was limited
by what he could see around him plus whatever he remembered from the path
he had traversed already? What if this more realistic situation took place?
No live creature counts on knowing in advance all the objects on its journey, or
calculates the precise path in advance. Algorithmically, the question about avail-
able input information puts the problem squarely into the domain of sensor-based
motion planning, presenting it as a maze-searching problem. Clearly, even if the
K¨ oenigsberg bridges made a Euler graph, and if the traveler had no picture as in
Figure 2.18, we can doubt that he would pass every bridge exactly once, except
perhaps by sheer chance. If not, what would be the traveler’s performance—say,
with the best algorithm possible? Can a strategy be designed that will guarantee
at least passing the whole graph when one starts with a zero knowledge about it?
If so, how about doing it in some reasonably efficient manner? We will return to
these questions later in this chapter.
This branch of motion planning—which can be formulated as moving in a
graph without prior information about it—started long before Euler. Since the
times of Theseus of Athens, people had great interest in labyrinths (mazes). After
Theseus slew the Minotaur, he used the thread of glittering jewels given to him
by Ariadne to find his way in the passages of the Labyrinth of Knossos. Many

6 Eventually this question did appear in graph theory, though much later, as a question of existence
of local algorithms [39].
7 Interestingly, when in the 1960s and 1970s researchers turned to the problem of robot motion
planning, the question of input information was not raised either. There seems to be something in
human psychology that, unless told otherwise, between two choices—minimum and maximum of
input information—we implicitly assume the latter.