A Parallel Algorithm for the Time Decomposition Approach to Constrained Optimal Control Problems

This paper presents an effective, parallel algorithm for solving constrained optimal control problems with long time horizons. The basic idea is to first relax all contraints but the system dynamics by using the multiplier method. A time decomposition and target coordination scheme is then used to decompose the resultant unconstrained optimal control problem into a two-level optimization with a structure for parallel processing. A three-level optimization algorithm is developed to determine the multipliers and to solve the associated two-level unconstrained problem. The algorithm is a hybrid of the multiplier method, Newton method and the Differential Dynamic Programming technique, and has a highly paralel structure at each level of the algorithm. The algorithm is relatively easy to implement, convergent, and applicable to problems with quite general constraints and system dynamics. Numerical results demonstrate its feasiblity and potential computation efficiency when used for parallel processing.