An Efficient DP Algorithm on a Tree-Structure for Finite Horizon Optimal Control Problems
An Efficient DP Algorithm on a Tree-Structure for Finite Horizon Optimal Control Problems
复制标题
一种求解有限时域最优控制问题的高效树结构DP算法
DOI：
10.1137/18m1203900
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Luca Saluzzi
中科院分区：
文献类型：
--
作者：
A. Alla;M. Falcone;Luca Saluzzi
求解最优控制问题的经典动态规划(DP)方法是基于将值函数刻画为HJB方程的唯一粘性解。数值逼近Bellman方程粘性解的DP格式通常基于投影到固定状态空间网格上的时间离散化。时间离散化可以通过动力学的一步方案来完成，而网格上的投影通常使用局部内插。显然，由于维度的诅咒，网格的使用对于高维问题的可能应用是一个限制。在这里，我们提出了一种新的方法来解决有限时间最优控制问题，其中值函数是在由时间离散动力学构造的树结构算法(TSA)上使用DP算法来计算的。这样，就不需要建立固定的空间三角剖分，也不需要在上面投影。该树将保证与离散动力学的完美匹配，并降低空间内插的成本，从而允许解决非常高维的问题。数值试验结果表明了该方法的有效性。
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 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 on a tree structure algorithm (TSA) 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.