We present a tree structure algorithm for optimal control problems with state constraints. We prove a convergence result for a discrete time approximation of the value function based on a novel formulation in the case of convex constraints. Then the Dynamic Programming approach is developed by a discretization in time leading to a tree structure in space derived by the controlled dynamics, taking into account the state constraints to cut several branches of the tree. Moreover, an additional pruning allows for the reduction of the tree complexity as for the case without state constraints. Since the method does not use an a priori space grid, no interpolation is needed for the reconstruction of the value function and the accuracy essentially relies on the time step h. These features permit a reduction in CPU time and in memory allocations. The synthesis of optimal feedback controls is based on the values on the tree and an interpolation on the values obtained on the tree will be necessary if a different discretization in the control space is adopted, e.g. to improve the accuracy of the method in the reconstruction of the optimal trajectories. Several examples show how this algorithm can be applied to problems in low dimension and compare it to a classical DP method on a grid.

A tree structure algorithm for optimal control problems with state constraints

Saluzzi Luca
2020

Abstract

We present a tree structure algorithm for optimal control problems with state constraints. We prove a convergence result for a discrete time approximation of the value function based on a novel formulation in the case of convex constraints. Then the Dynamic Programming approach is developed by a discretization in time leading to a tree structure in space derived by the controlled dynamics, taking into account the state constraints to cut several branches of the tree. Moreover, an additional pruning allows for the reduction of the tree complexity as for the case without state constraints. Since the method does not use an a priori space grid, no interpolation is needed for the reconstruction of the value function and the accuracy essentially relies on the time step h. These features permit a reduction in CPU time and in memory allocations. The synthesis of optimal feedback controls is based on the values on the tree and an interpolation on the values obtained on the tree will be necessary if a different discretization in the control space is adopted, e.g. to improve the accuracy of the method in the reconstruction of the optimal trajectories. Several examples show how this algorithm can be applied to problems in low dimension and compare it to a classical DP method on a grid.
2020
Settore MAT/08 - Analisi Numerica
Dynamic programming; Optimal control; State constraints; Tree structure; Viscosity solutions
File in questo prodotto:
File Dimensione Formato  
AFS_rendiconti.pdf

accesso aperto

Tipologia: Published version
Licenza: Solo Lettura
Dimensione 1.24 MB
Formato Adobe PDF
1.24 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/131685
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact