论文标题
树结构算法，用于具有状态约束的最佳控制问题
A tree structure algorithm for optimal control problems with state constraints
论文作者
论文摘要
我们提出了一种针对状态约束的最佳控制问题的树结构算法。我们证明了基于约束问题的新表述的离散时间近似的离散时间近似。然后，动态编程方法是由时间的离散化开发的，导致由受控动力学得出的空间中的树结构，在这种构造中，考虑到状态约束以切割树的几个分支。此外，额外的修剪允许降低树木复杂性，因为情况没有状态约束。由于该方法不使用先验空间网格，因此重建值函数不需要插值，而准确性基本上依赖于时间步骤$ h $。这些功能允许减少CPU时间和内存分配。最佳反馈控件的合成基于树上的值，如果采用控制空间中的不同离散化，例如提高方法在重建最佳轨迹中的准确性。几个示例表明，该算法如何应用于低维度的问题，并将其与网格上的经典DP方法进行比较。
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 of the constrained problem. Then the Dynamic Programming approach is developed by a discretization in time leading to a tree structure in space derived by the controlled dynamics, in this construction the state constraints are taken into account 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.
