The vector fields developed in the last section yield feasible trajectories, but not necessarily optimal trajectories unless the initial and goal states are in the same convex -cell. If , then it is possible to make a continuous version of Dijkstra's algorithm [708]. This results in an exact cost-to-go function over based on the Euclidean shortest path to a goal, . The cost-to-go function serves as the navigation function, from which the feedback plan is defined by using a local steepest descent.

Suppose that is bounded by a simple polygon (no holes). Assume that only normalized vector fields are allowed. The cost functional is assumed to be the Euclidean distance traveled along a state trajectory. Recall from Section 6.2.4 that for optimal path planning, must be used. Assume that and have the same connectivity.8.12 This technically interferes with the definition of tangent spaces from Section 8.3 because each point of must be contained in an open neighborhood. Nevertheless, we allow vectors along the boundary, provided that they point'' in a direction tangent to the boundary. This can be formally defined by considering boundary regions as separate manifolds.

Consider computing the optimal cost-to-go to a point for a problem such as that shown in Figure 8.12a. For any , let the visibility polygon refer to the set of all points visible from , which is illustrated in Figure 8.12b. A point lies in if and only if the line segment from to is contained in . This implies that the cost-to-go from to is just the Euclidean distance from to . The optimal navigation function can therefore be immediately defined over as

 (8.42)

Level sets at regularly spaced values of this navigation function are shown in Figure 8.13a.

How do we compute the optimal cost-to-go values for the points in ? For the segments on the boundary of for any , some edges are contained in the boundary of , and others cross the interior of . For the example in Figure 8.12b, there are two edges that cross the interior. For each segment that crosses the interior, let the closer of the two vertices to be referred to as a way point. Two way points are indicated in Figure 8.12b. The way points of are places through which some optimal paths must cross. Let for any denote the set of way points of .

A straightforward algorithm proceeds as follows. Let denote the set of points over which has been defined, in the th iteration of the algorithm. In the first iteration, , which is the case shown in Figure 8.13a. The way points of are placed in a queue, . In each following iteration, a way point is removed from . Let denote the domain over which is defined so far. The domain of is extended to include all new points visible from . These new points are . This yields , the extended domain of . The values of for are defined by

 (8.43)

in which is the way point that was removed from (the optimal cost-to-go value of was already computed). The way points of that do not lie in are added to . Each of these will yield new portions of that have not yet been seen. The algorithm terminates when is empty, which implies that for some . The execution of the algorithm is illustrated in Figure 8.13.

The visibility polygon can be computed in time if is described by edges. This is accomplished by performing a radial sweep, which is an adaptation of the method applied in Section 6.2.2 for vertical cell decomposition. The difference for computing is that a ray anchored at is swept radially (like a radar sweep). The segments that intersect the ray are sorted by their distance from . For the algorithm that constructs the navigation function, no more than visibility polygons are computed because each one is computed from a unique way point. This implies running time for the whole algorithm. Unfortunately, there is no extension to higher dimensions; recall from Section 7.7.1 that computing shortest paths in a 3D environment is NP-hard [172].

The algorithm given here is easy to describe, but it is not the most general, nor the most efficient. If has holes, then the level set curves can collide by arriving from different directions when traveling around an obstacle. The queue, , described above can be sorted as in Dijkstra's algorithm, and special data structures are needed to identify when critical events occur as the cost-to-go is propagated outward. It was shown in [443] that this can be done in time and space .

Steven M LaValle 2012-04-20