Fast Approximate Dynamic Programming for Input-Affine Dynamics

Understand

We propose two novel numerical schemes for approximate implementation of the dynamic programming~(DP) operation concerned with finite-horizon, optimal control of discrete-time systems with input-affine dynamics.

• The proposed algorithms involve discretization of the state and input spaces and are based on an alternative path that solves the dual problem corresponding to the DP operation.
• We provide error bounds for the proposed algorithms, along with a detailed analysis of their computational complexity.
• In particular, for a specific class of problems with separable data in the state and input variables, the proposed approach can reduce the typical time complexity of the DP operation from $O(XU)$ to $O (X+U)$, where $X$ and $U$ denote the size of the discrete state and input spaces, respectively.