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:
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) |
(6.2) |
Steven M LaValle 2020-08-14