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 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 with a tree structure algorithm 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.

An efficient DP algorithm on a tree-structure for finite horizon optimal control problems

Saluzzi Luca
2019

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 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 with a tree structure algorithm 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.
2019
Settore MAT/08 - Analisi Numerica
Dynamic programming; Hamilton-Jacobi-Bellman equation; Optimal control; Tree structure
File in questo prodotto:
File Dimensione Formato  
AFS_SISC19.pdf

accesso aperto

Tipologia: Published version
Licenza: Solo Lettura
Dimensione 6.14 MB
Formato Adobe PDF
6.14 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11384/131684
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 31
  • ???jsp.display-item.citation.isi??? 22
social impact