Dynamic Programming on a tree for the approximation of finite horizon optimal control problems

Abstract: 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 [2]. The DP scheme for the numerical approximation of viscosity solutions of those equations is typically based on a time discretization coupled with a projection on a fixed space triangulation of the numerical domain [3]. The time discretization is obtained by a one-step scheme for the dynamics and the projection is based on a polynomial interpolation. This approach allows to get a synthesis of optimal controls in feedback form and is very powerful for nonlinear optimal control problems in low dimension although general convergence results are valid in any dimension. The computational cost is severe in high dimension and several methods have been proposed to mitigate the "curse of dimensionality" of DP schemes, e.g. static and dynamic domain decomposition, fast-marching and fast-sweeping methods, discrete representation formulas (when available), see [3] and the references therein.
We present a new approach for finite horizon optimal control problems [1, 4] where we compute the value function on a tree structure generated by the time discrete dynamics avoiding the construction of a space grid/triangulation to solve the HJB equation. This drops the computational cost of space interpolation although the tree mantains a perfect matching with the discrete dynamics. We prove first order convergence to the value function for a first order discretization of the dynamics. We will also discuss extensions to high-order schemes and to problems with state constraints also showing some numerical tests.
Works in collaboration with A. Alla (PUC, Rio de Janeiro) and L. Saluzzi (Sapienza, Roma).
References
[1] A. Alla, M. Falcone and L. Saluzzi. An efficient DP algorithm on a tree-structure for finite horizon optimal control problems, SIAM Journal on Scientific Computing, (41) 4, 2019, A2384-A2406
[2] M. Bardi, I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser, Basel, 1997.
[3] M. Falcone, R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, Society for Industrial and Applied Mathematics, Philadelphia, 2013.
[4] L. Saluzzi, A. Alla and M. Falcone. Error estimates for a tree structure algorithm for dynamic programming equations, submitted, 2018 arxiv.org/abs/1812.11194

numerical analysis

Audience: researchers in the topic

Seminars on Numerics and Applications