| The authors address the problem
of computing a navigation function that serves as a feedback motion strategy
for problems that involve generic differential constraints, nonconvex collision
constraints, and the optimization of a specified criterion. The determination
of analytical solutions to such problems is well beyond the state of the
art; therefore, the authors focus on obtaining numerical solutions that
are based on discretization of the state space (although they do not force
trajectories to visit discretized points). This work improves classical
optimal control techniques for problems of interest to the authors. By introducing
a simplicial complex representation, the authors propose a novel interpolation
scheme that reduces a key bottleneck in the techniques from O(2n) running
time to O(n lg n), in which n is the state space dimension. By exploiting
local structure in the differential constraints, the authors present a progressive
series of three improved algorithms that use dynamic programming constraints
to compute an optimal navigation function. Each makes an assumption that
is more restrictive than the previous one, and exploits that assumption
to yield greater efficiency. These improvements yield a practical increase
in the applicability of dynamic programming computations by one or two dimensions
over classical techniques. Theoretical convergence to the optimal solution
is established for these proposed algorithms. The algorithms are implemented
and evaluated on a variety of problems. Several computed results are presented. |
