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 which is projected on a ?xed space triangulation of the numerical domain [3]. 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. This approach, which allows to get information on optimal controls in feedback form, has been shown to be very powerful for low dimensional optimal control problems although convergence results have been proved in Rd. 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. We will discuss a new approach for ?nite horizon optimal control problems where we compute the value function on a tree structure constructed directly by the time discrete dynamics and we do not use a space triangulation to solve the HJB equation [1]. This allows to drop the cost of the space interpolation, moreover the tree will guarantee a perfect matching with the discrete dynamics. To prove convergence and a-priori estimates we will follow [4] and [5]. In the simple case, we will discretize the dynamics with an Euler scheme and we will prove ?rst order convergence by the means of viscosity solutions. We will also discuss how this approach can be extended to high-order schemes and we will show some examples of second order approximation schemes. This is a joint work with Alessandro Alla (PUC, Rio de Janeiro) and Luca Saluzzi (Gran Sasso Science Institute, L’Aquila, Italy).
Copyright. All Rights Reserved.