6.2.4 Shortest-Path Roadmaps

Instead of generating paths that maximize clearance, suppose that the
goal is to find shortest paths. This leads to the *shortest-path
roadmap*, which is also called the *reduced visibility graph* in
[588]. The idea was first introduced in [742] and may
perhaps be the first example of a motion planning algorithm. The
shortest-path roadmap is in direct conflict with maximum clearance
because shortest paths tend to graze the corners of
. In fact,
the problem is ill posed because
is an open set. For any
path
, it is always possible to find a
shorter one. For this reason, we must consider the problem of
determining shortest paths in
, the closure of
. This means that the robot is allowed to ``touch'' or
``graze'' the obstacles, but it is not allowed to penetrate them. To
actually use the computed paths as solutions to a motion planning
problem, they need to be slightly adjusted so that they come very
close to
but do not make contact. This slightly increases
the path length, but the additional cost can be made arbitrarily small
as the path gets arbitrarily close to
.

The *shortest-path roadmap*, , is constructed as follows.
Let a *reflex vertex* be a polygon vertex for which the interior
angle (in
) is greater than . All vertices of a convex
polygon (assuming that no three consecutive vertices are collinear)
are reflex vertices. The vertices of are the reflex
vertices. Edges of are formed from two different sources:

- []
**Consecutive reflex vertices:**If two reflex vertices are the endpoints of an edge of , then an edge between them is made in . - []
**Bitangent edges:**If a*bitangent line*can be drawn through a pair of reflex vertices, then a corresponding edge is made in . A bitangent line, depicted in Figure 6.10, is a line that is incident to two reflex vertices and does not poke into the interior of at any of these vertices. Furthermore, these vertices must be mutually visible from each other.

If the bitangent tests are performed naively, then the resulting
algorithm requires time, in which is the number of
vertices of
. There are pairs of reflex vertices that
need to be checked, and each check requires time to make
certain that no other edges prevent their mutual visibility. The
plane-sweep principle from Section 6.2.2 can be adapted to
obtain a better algorithm, which takes only
time. The
idea is to perform a *radial sweep* from each reflex vertex, . A ray is
started at
, and events occur when the ray touches
vertices. A set of bitangents through can be computed in this way
in
time. Since there are reflex vertices, the
total running time is
. See Chapter 15 of
[264] for more details. There exists an algorithm
that can compute the shortest-path roadmap in time
,
in which is the total number of edges in the roadmap
[384]. If the obstacle region is described by a simple
polygon, the time complexity can be reduced to ; see
[709] for many shortest-path variations and references.

To improve numerical robustness, the shortest-path roadmap can be
implemented without the use of trigonometric functions. For a
sequence of three points, , , , define the
*left-turn predicate*,
TRUEFALSE, as
TRUE if and
only if is to the left of the ray that starts at and
pierces . A point is a reflex vertex if and only if
TRUE, in which and are the points
before and after, respectively, along the boundary of
. The
bitangent test can be performed by assigning points as shown in Figure
6.14. Assume that no three points are collinear
and the segment that connects and is not in collision. The pair,
, , of vertices should receive a bitangent edge if the
following sentence is
FALSE:

(6.1) |

in which denotes logical ``exclusive or.'' The predicate can be implemented without trigonometric functions by defining

(6.2) |

in which . If , then TRUE; otherwise, FALSE.

Steven M LaValle 2012-04-20