"A Dynamic Programming approach on a tree structure for finite horizon optimal control problems"
, 499 DSL
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 those equations is typically based on a time discretization which is projected on a fixed space triangulation of the numerical domain. The time discretization can be done by a one step scheme for the dynamics and the projection on the grid typically uses a polynomial interpolation. In this talk, we will discuss a new approach for finite horizon optimal control problems where we compute the value function on a tree structure built directly by the time discrete dynamics avoiding the use of a space triangulation to solve the HJB equation. This allows to drop the cost of the space interpolation and the tree will guarantee a perfect matching with the discrete dynamics. We will also provide error estimates for the algorithm if the dynamics is discretized with an Euler method. Furthermore, this approach has been extended to high-order schemes and to nonlinear Partial Differential Equations. Finally, we will show the effectiveness of the method trough numerical examples. This is a joint work with Maurizio Falcone (La Sapienza, Roma) and Luca Saluzzi (GSSI, L'Aquila).