Algorithms for Computing Numerical Optimal Feedback Motion Strategies

Abstract

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.