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

MOTION PLANNING WITH INCOMPLETE INFORMATION 65

Under Tarry’s algorithm, assuming that the start and target vertices are distinct
and there exists a path between them, the target vertex is guaranteed to be reached,
and every edge will be traversed exactly twice, once in each direction, with the
exception of the two edges incident to the start and target vertices, which will
be traversed once each. Using our terminology, the upper bound on the length
of paths generated by the algorithm is as follows:

Theorem 2.9.3. For any finite maze, Tarry’s algorithm will generate a path of
length P such that

P ≤ 2D + 2 p i (2.23)
i
where D is the length of M-line, and p i are perimeters of obstacles in the maze.

Finally this gives us an answer to our question above: What performance can be
expected for an unknown Euler graph.
It took a long time, over 70 years, for the next improvement to come. In
1970, Fraenkel proposed a more economical algorithm [45, 46]. Though it has
the same performance as Tarry’s in the worst case, it performs better if the robot
is lucky with the maze; then, some or even all graph edges may be traversed
just once. Fraenkel’s algorithm is more complex that Tarry’s. It makes use of
a counter, which is set to zero at the start vertex. The algorithm operates as
follows:

Fraenkel’s Algorithm:

1. Whenever one arrives at a vertex not visited before, increase the counter
by 1.
2. When arriving at a vertex v such that before entering it there was at least
one edge incident to it that was not traversed before, and upon arrival at v
there remains at most one such edge, decrease the counter by 1.
3. As long as the counter is positive, the tour is conducted according to the
Tarry’s algorithm, except, whenever possible, an edge not traversed before
is preferred to an edge already traversed.
4. As soon as the counter contains zero, leave all edges via their entrance
edges.

The accompanying theorem, whose proof is relatively involved, is derived for
the case when the start and target vertices coincide. The theorem states that
under Fraenkel’s algorithm the target vertex is guaranteed to be reached if
reachable, and every edge will be traversed at least once but never more than
twice, once in each direction. Using our terminology and the M-line concept, the
upper bound on the length of paths generated by the Fraenkel’s algorithm is as
follows: