An efficient DP algorithm on a tree-structure for finite horizon optimal control problems
For researchers in optimal control, this method addresses the curse of dimensionality in DP by eliminating grid-based interpolation, though it is an incremental improvement over existing DP approaches.
The authors propose a tree-structured DP algorithm for finite horizon optimal control that avoids fixed state-space grids and interpolation, enabling solution of high-dimensional problems. Numerical tests demonstrate effectiveness.
The classical Dynamic Programming (DP) approach to optimal control problems is based on the characterization of the value function as the unique viscosity solution of a Hamilton-Jacobi-Bellman (HJB) equation. The DP scheme for the numerical approximation of viscosity solutions of Bellman equations is typically based on a time discretization which is projected on a fixed state-space grid. The time discretization can be done by a one-step scheme for the dynamics and the projection on the grid typically uses a local interpolation. Clearly the use of a grid is a limitation with respect to possible applications in high-dimensional problems due to the curse of dimensionality. Here, we present a new approach for finite horizon optimal control problems where the value function is computed using a DP algorithm on a tree structure algorithm (TSA) constructed by the time discrete dynamics. In this way there is no need to build a fixed space triangulation and to project on it. The tree will guarantee a perfect matching with the discrete dynamics and drop off the cost of the space interpolation allowing for the solution of very high-dimensional problems. Numerical tests will show the effectiveness of the proposed method.