A Primal-Dual Method for Optimal Control and Trajectory Generation in High-Dimensional Systems
This method enables efficient trajectory generation for high-dimensional systems, addressing the curse of dimensionality that plagues grid-based numerical methods.
The paper presents a primal-dual method for solving the Hamilton-Jacobi equation via the generalized Hopf formula, achieving millisecond-scale computation times for time-optimal control problems with polynomial scaling in dimension.
Presented is a method for efficient computation of the Hamilton-Jacobi (HJ) equation for time-optimal control problems using the generalized Hopf formula. Typically, numerical methods to solve the HJ equation rely on a discrete grid of the solution space and exhibit exponential scaling with dimension. The generalized Hopf formula avoids the use of grids and numerical gradients by formulating an unconstrained convex optimization problem. The solution at each point is completely independent, and allows a massively parallel implementation if solutions at multiple points are desired. This work presents a primal-dual method for efficient numeric solution and presents how the resulting optimal trajectory can be generated directly from the solution of the Hopf formula, without further optimization. Examples presented have execution times on the order of milliseconds and experiments show computation scales approximately polynomial in dimension with very small high-order coefficients.