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

64 A QUICK SKETCH OF MAJOR ISSUES IN ROBOTICS

The first systematic procedure for solving maze problems—in fact, for cov-
ering a general graph—seems to be the one suggested by Wiener in 1873. His
algorithm is as follows:

Wiener’s Algorithm: Starting at point S, proceed along the graph edges as far as
possible, selecting at each vertex an edge that has not been traversed before. At
a vertex where such motion is no longer possible, retrace the sequence of edges
until you arrive at a vertex with some unused edges.

Clearly, Wiener’s method presents a version of what is called today an exhaus-
tive search. One will also recognize in this algorithm a geometric version of the
“width-first” procedure that appears in many textbooks in computer science. The
procedure does guarantee covering all edges of the graph, but it will produce
many repetitive visits to the same vertices.
Does an algorithm have to be that inefficient? For example, how about the
following simple algorithm found in children stories? “Keep your left hand on
the wall as you walk, and you will eventually get out of the labyrinth.” This
naive procedure will only work if all the walls in the labyrinth are connected.
Clearly, if one keeps the hand on the wall that is a part of an island inside the
labyrinth, one will walk in the labyrinth forever.
To understand the limits of achievable performance of algorithms with incom-
plete information, let us see first what that limit is for algorithms with complete
information, for a general graph.

Theorem 2.9.2 (Ore [42]). In a finite connected graph, it is always possible to
construct a cyclic directed path passing through each edge once and only once in
each direction.

This promises a much better performance than in Wiener’s algorithm, but is such
performance feasible for an algorithm with incomplete information? The positive
answer was given in the method by Tremaux (reported by Lucas in 1892 [43]).
It was shown in 1895 by Tarry [42, 44] that the same result can be obtained in
a more economical way. In Tarry’s algorithm, called Tarry’s rule,for agiven
graph, when the point robot arrives at a vertex v, the following input information
is assumed: (i) the subset of those edges incident to v that the robot traversed
before when leaving v—that is, those edges that were traversed in the direction
pointing away from v; (ii) the entrance edge via which the robot first arrived at
v. The procedure is very simple:

Tarry’s Rule:

1. Upon arrival at v, continue via an edge (v, v ) that was not yet traversed

in the direction of v to v .
2. Choose the entrance edge as a last resort.