Implementation of Dynamic Programming for $n$-Dimensional Optimal Control Problems With Final State Constraints

Abstract

Many optimal control problems include a continuous nonlinear dynamic system, state, and control constraints, and final state constraints. When using dynamic programming to solve such a problem, the solution space typically needs to be discretized and interpolation is used to evaluate the cost-to-go function between the grid points. When implementing such an algorithm, it is important to treat numerical issues appropriately. Otherwise, the accuracy of the found solution will deteriorate and global optimality can be restored only by increasing the level of discretization. Unfortunately, this will also increase the computational effort needed to calculate the solution. A known problem is the treatment of states in the time–state space from which the final state constraint cannot be met within the given final time. In this brief, a novel method to handle this problem is presented. The new method guarantees global optimality of the found solution, while it is not restricted to a specific class of problems. Opposed to that, previously proposed methods either sacrifice global optimality or are applicable to a specific class of problems only. Compared to the basic implementation, the proposed method allows the use of a substantially lower level of discretization while achieving the same accuracy. As an example, an academic optimal control problem is analyzed. With the new method, the evaluation time was reduced by a factor of about 300, while the accuracy of the solution was maintained.