Recurrent Model Predictive Control

This paper proposes an off-line algorithm, called Recurrent Model Predictive Control (RMPC), to solve general nonlinear finite-horizon optimal control problems. Unlike traditional Model Predictive Control (MPC) algorithms, it can make full use of the current computing resources and adaptively select the longest model prediction horizon. Our algorithm employs a recurrent function to approximate the optimal policy, which maps the system states and reference values directly to the control inputs. The number of prediction steps is equal to the number of recurrent cycles of the learned policy function. With an arbitrary initial policy function, the proposed RMPC algorithm can converge to the optimal policy by directly minimizing the designed loss function. We further prove the convergence and optimality of the RMPC algorithm thorough Bellman optimality principle, and demonstrate its generality and efficiency using two numerical examples.


I. INTRODUCTION
M ODEL Predictive Control (MPC) is a well-known method to solve finite-horizon optimal control problems online, which has been extensively investigated in various fields [1]- [3]. However, existing MPC algorithms still suffer from a major challenge: relatively low computation efficiency [4].
One famous approach to tackle this issue is the moving blocking technique, which assumes constant control input in a fixed portion of the prediction horizon. It increases the computation efficiency by reducing the number of variables to be optimized [5]. However, this solution cannot guarantee the system stability and constraint satisfaction. In addition, Wang and Boyd (2009) proposed an early termination interiorpoint method to reduce the calculation time by limiting the maximum number of iterations per time step [6].
However, these methods are still unable to meet the online computing requirement for nonlinear and large-scale systems. Some control algorithms choose to calculate an near-optimal explicit policy offline, and then implement it online. Bemporad et al. (2002) first proposed the explicit MPC method to increase the computation efficiency, which partitioned the constrained state space into several regions and calculated explicit feedback control laws for each region [7]. During online implementation, the on-board computer only needs to choose the corresponding state feedback control law according to the current system state, thereby reducing the burden of online calculation to some extent. Such algorithms are only suitable for small-scale systems, since the required storage capacity grows exponentially with the state dimension [8].
Furthermore, significant efforts have been devoted to approximation MPC algorithms, which can reduce polyhedral state regions and simplify explicit control laws. Geyer et al. (2008) provided an optimal merging approach to reduce partitions via merging regions with the same control law [9]. Jones et al. (2010) proposed a polytopic approximation method using double description and barycentric functions to estimate the optimal policy, which greatly reduced the partitions and could be applied to any convex problem [10]. Wen et al. (2009) proposed a piecewise continuous grid function to represent explicit MPC solution, which reduced the requirements of storage capacity and improve online computation efficiency [11]. Borrelli et al. (2010) proposed an explicit MPC algorithm which can be executed partially online and partially offline [12]. In addition, some MPC studies employed a parameterized function to approximate the MPC controller. They updated the function parameters by minimizing the MPC cost function with a fixed prediction horizon through supervised learning or reinforcement learning [13]- [16].
Noted that the policy performance and the computation time for each step usually increase with the number of prediction steps. The above-stated algorithms usually have to make a trade-off between control performance and computation time constraints, and select a conservative fixed prediction horizon. While the on-board computation resources are often changing dynamically. These algorithms thus usually lead to calculation timeouts or resources waste. In other words, these algorithms cannot adapt to the dynamic allocation of computing resources and make full use of the available computing time to select the longest model prediction horizon.
In this paper, we propose an offline MPC algorithm, called Recurrent MPC (RMPC), for finite-horizon optimal control problems with large-scale nonlinearities and nonaffine inputs. Our main contributions can be summarized as below: 1) A recurrent function is employed to approximate the optimal policy, which maps the system states and reference values directly to the control inputs. Compared to previous algorithms employing non-recurrent functions (such as multi-layer NNs), which must select a fixed prediction horizon previously [13]- [16], the use of recurrent structure makes the algorithm be able to select appropriate model prediction horizon according to current computing resources. In particular, the output of the learned policy function after N recurrent cycles corresponds to the nearly optimal solution of N -step MPC. 2) A policy optimization objective is designed by decomposing the MPC cost function according to the Bellman's principle of optimality. The optimal recurrent policy can be obtained by directly minimizing the designed objective function. Therefore, unlike the traditional explicit MPC algorithms [7]- [12] that can only handle linear systems, the proposed algorithm is applicable for general nonlinear and non input-affine systems. Meanwhile, the proposed RMPC algorithm utilizes the recursiveness of Bellman's principle. When the cost function of the longest prediction is optimized, the cost function of short prediction will automatically be optimal. Thus the proposed algorithm can deals with different shorter prediction horizons problems while only training with an objective function with respect to a long prediction horizons. Other MPC algorithms [7]- [16]do not consider the recursiveness of Bellman's principle, when the prediction horizons changes, the optimization problem must be reconstructed and the training or computing process must be re-executed to deal with the new problem.
3) The proposed RMPC algorithm calculates the optimal control policy previously so only needs to eval the forward inferencing process while using online.Expriments shows that it is over 5 times faster than the traditional MPC algorithms [17], [18] under the same problem scale. The paper is organized as follows. In Section II, we provide the formulation of the MPC problem. Section III presents RMPC algorithm and proves its convergence. In Section IV, we present simulation demonstrations that show the generalizability and effectiveness of the RMPC algorithm. Section V concludes this paper.

II. PRELIMINARIES
Consider general time-invariant discrete-time dynamic system x with state x i ∈ X ⊂ R n , control input u i ∈ U ⊂ R m and the system dynamics function f : R n × R m → R n . We assume that f (x i , u i ) is Lipschitz continuous on a compact set X , and the system is stabilizable on X . Define the cost function V (x 0 , r 1:N , N ) of the N -step Model Predictive Control (MPC) problem where x 0 is initial state, N is length of prediction horizon, is the N -step cost function of state x 0 with reference r 1:N , u N i−1 is the control input of the ith step in N -step prediction, and l ≥ 0 is the utility function. The purpose of MPC is to find the optimal control sequence to minimize the objective V (x 0 , r 1:N , N ), which can be denoted as where the superscript * represents optimal.

A. Recurrent Policy Function
In practical applications, we only need to execute the first control input u N 0 * (x 0 , r 1:N ) of the optimal sequence in (3) at each step. Given a control problem, assume that N max is the maximum feasible prediction horizon. Our aim is to make full use of computation resources and adaptively select the longest prediction horizon k ∈ [1, N max ], which means that we need to calculate and store the optimal control input u k 0 * (x, r 1:k ) of ∀x ∈ X , ∀r 1:k and ∀k ∈ [1, N max ] in advance. This requires us to find an efficient way to represent the policy and solve it offline.
We firstly introduce a recurrent function, denoted as π c (x 0 , r 1:c ; θ), to approximate the control input u c 0 * (x 0 , r 1:c ), where θ is the vector of function parameters and c is the number of recurrent cycles of the policy function. The goal of the proposed Recurrent MPC (RMPC) algorithm is to find the optimal parameters θ * , such that The structure of the recurrent policy function is illustrated in Fig. 1. All recurrent cycles share the same parameters θ, where h c ∈ R q is the vector of hidden states. Each recurrent cycle is mathematically described as where h 0 = 0, σ h and σ y are activation functions of hidden layer and output layer, respectively. As shown in Fig. 1, the recurrent policy function calculates and outputs a control input at each recurrent cycle. Assuming that we have found the optimal parameters θ * , it follows that the output of the cth cycle π c (x 0 , r 1:c ; θ * ) = u c 0 * (x 0 , r 1:c ) for ∀c ∈ [1, N max ]. This indicates that the more cycles, the longer the prediction horizon. In practical applications, the calculation time of each cycle t c is different due to the dynamic change of computing resource allocation (see Fig. 2). At each time step, the total time assigned to the control input calculation is assumed to be T . Denoting the total number of the recurrent cycles at each time step as k, then the control input is π k (x 0 , r 1: Therefore, the recurrent policy is able to make full use of computing resources and adaptively select the longest prediction step k. In other word, the more computing resources allocated, the longer prediction horizon will be selected, which usually would lead to the better control performance.
Remark 1. Previous MPC algorithms employs non-recurrent form neural networks [13]- [16], which must select a fix prediction horizon previously. RMPC employes recurrent function to approximate the optimal policy, which maps the system states and reference values directly to the control inputs. The use of recurrent structure makes the algorithm be able to select appropriate model prediction horizon according to current computing resources. The output of the learned policy network after N recurrent cycles corresponds to the nearly optimal solution of N -step MPC.

B. Objective Function
To find the optimal parameters θ * offline, we first need to represent the MPC cost function in (2) in terms of θ, denoted by V (x 0 , r 1:N , N ; θ). From (2) and the Bellman's principle of optimality, the global minimum V * (x 0 , r 1:N , N ) can be expressed as:

It follows that
Therefore, for the same x 0 and r 1:N , it is clear that This indicates that the ith optimal control input u N i−1 * (x 0 , r 1:N ) in (3) can be regarded as the optimal control input of the N -i+1-step MPC control problem with initial state x i−1 . Hence,by replacing all ). Then, we can obtain the N -step cost function in terms of θ: To find the optimal parameters θ * that make (4) hold, we can construct the following objective function: Therefore, we can update θ by directly minimizing J(θ). The policy update gradients can be derived as where dV (x 0 , r 1: Denoting π Nmax−i+1 (x i−1 , r i:Nmax ; θ) as π Nmax−i+1 and By defining two immediate variables, φ i = dxi dθ and ψ i = dπ Nmax −i+1 dθ , we have their recursive formula and the details of gradient backpropagation are shown in Fig.3.
Therefore, the gradient formula can be simplified as: Taking the Gradient Descent (GD) method as an example, the updating rules of the policy function are where α θ denotes the learning rate and K indicates Kth iteration.
The framework and pseudo-code of the proposed RMPC algorithm is shown in Algorithm 1 and Fig. 4.

Algorithm 1 RMPC algorithm
Given an appropriate learning rate α θ and any arbitrarily small positive number . Initial with arbitrary θ 0 repeat Randomly select x 0 , r 1:Nmax ∈ X Calculate dJ(θ K ) dθ K using (10) Update policy function using (11) until |J(θ K+1 ) − J(θ K )| ≤ Remark 2. Traditional explicit MPC algorithms [7]- [12] can only handle linear systems.The proposed RMPC algorithm uses an optimization objective designed by decomposing the MPC cost function according to the Bellman's principle of optimality. The optimal recurrent policy can be obtained by directly minimizing the designed objective function without restrictions on the form of systems. Meanwhile, the proposed algorithm utilizes the recursiveness of Bellman's principle. When the cost function of the longest prediction is optimized, the cost function of short prediction will automatically be optimal. Thus the proposed algorithm can deals with different shorter prediction horizons problems while only training with an objective function with respect to a long prediction horizons. Other MPC algorithms [7]- [16]do not consider the recursiveness of Bellman's principle, when the prediction horizons changes, the optimization problem must be reconstructed and the training or computing process must be re-executed to deal with the new problem.

C. Convergence and Optimality
There are many types of recurrent functions belonging to the structure defined in (5), and recurrent neural networks (RNN) are the most commonly used. In recent years, deep RNNs have been successfully implemented in many fields, such as natural language processing and system control, attributing to their ability to process sequential data [19], [20]. Next, we will show that as the iteration index K → ∞, the optimal policy π c (x 0 , r 1:c ; θ * ) that make (4) hold can be achieved using Algorithm 1, as long as π c (x 0 , r 1:c ; θ) is an overparameterized RNN. The over-parameterization means that the number of hidden neurons is sufficiently large. Before the main theorem, the following lemma and assumption need to be introduced.
where c is the number of recurrent cycles, W = W h ∪ W y , b = b h ∪ b y and U h are parameters, σ h and σ y are activation functions. Supposing G c (y c ; W, b) is over-parameterized, for where ∈ R + is an arbitrarily small error.
The reported experimental results and theoretical proofs have shown that the straightforward optimization methods, such as GD and Stochastic GD (SGD), can find global minima of most training objectives in polynomial time if the approximate function is an over-parameterized neural network or RNN [24], [25]. Based on this fact, we make the following assumption.
Assumption 1. If the approximate function is an overparameterized RNN, the global minimum of objective function in (9) can be found using an appropriate optimization algorithm such as SGD [26].
We now present our main result.
Thus, we have proven that RMPC algorithm can converge to θ * . In other words, it can find the nearly optimal policy of MPC with different prediction horizon, whose output after cth recurrent cycles corresponds to the nearly optimal solution of c-step MPC.

IV. ALGORITHM VERIFICATION
In order to evaluate the performance of the proposed RMPC algorithm, we choose the vehicle lateral control problem in path tracking task as an example [27].

A. Overall Settings
The policy network is trained offline on the PC, and then deployed to the industrial personal computer (IPC). The vehicle dynamics used for policy training are different from the controlled plant. For online applications, the IPveC-controller gives the control signal to the plant according to the state information and the reference trajectory. The plant feeds back the state information to the IPC-controller, so as to realize the closed-loop control process. The feedback scheme of the HIL experiment is depicted in Fig 5. The type of IPC-controller is ADLINK MXC-6401, equipped with Intel i7-6820EQ CPU and 8GB RAM, which is used as a vehicle on-board controller [28]. The plant is a real-time system, simulated by the vehicle dynamic model of CarSim [29]. The longitudinal speed is assumed to be constant, v x = 16m/s, and the expected trajectory is shown in Fig. 10. The system states and control inputs of this problem are listed in Table I, and the vehicle parameters are listed in Table II.

B. Problem Description
The offline policy is trained based on the nonliner and non input-affine vehicle dynamics: where F yf and F yr are the lateral tire forces of the front and rear tires respectively [30]. The lateral tire forces can be approximated according to the Fiala tire model: where α # is the tire slip angle, F z# is the tire load, µ # is the friction coefficient, and the subscript # ∈ {f, r} represents the front or rear tires. The slip angles can be calculated from the relationship between the front/rear axle and the center of gravity (CG): The loads on the front and rear tires can be approximated by: The utility function of this problem is set to be u i−1 Therefore, the policy optimization problem of this example can be formulated as: where V (x 0 , r 1:

C. Algorithm Details
The policy function is represented by a variant of RNN, called GRU (Gated Recurrent Unit). The input layer is composed of the states, followed by 4 hidden layers using rectified linear unit (RELUs) as activation functions with 128 units per layer, and the output layer is set as a tanh layer, multiplied by 0.2 to confront bounded control. We use Adam method to update the network with the learning rate of 2 × 10 −4 and the batch size of 256.

D. Result Analysis
For nonlinear MPC problems, we can solve it with some optimization solvers, such as ipopt [17] and bonmin [18], which can be approximately regarded as the numerical optimal solution. Fig. 6 compares the calculation efficiency of RMPC and the optimization solvers based on the symbolic framework CasADi [31] under different prediction steps for online applications. It is obvious that the calculation time of the optimization solvers is much longer than RMPC, and the gap increases with the number of prediction steps. Specifically, when N = c = 15, the fastest optimization solver ipopt is over 5 times slower than RMPC (ipopt for 26.2ms, RMPC for 4.7ms). This demonstrates the effectiveness of the RMPC method. We run Algorithm 1 for 10 times and calculate the policy error e N between the solution of ipopt solver and RMPC at each iteration for N ∈ [1,15], where u N max * and u N min * are respectively the maximum and minimum value of u N 0 * (x 0 , r 1:N ) for ∀x 0 , r 1:N ∈ X , ∀N ∈ [1,15], N is the number of prediction steps. e N indicates the relative error of control quantity π N (·) from cycle network respect to the optimum u N * 0 (·) in N step prediction control problem . In Fig. 7, we plot policy error curves during training with different prediction steps N . It is clear that all the policy errors decrease rapidly to a small value during the training process. In particular, after 10 4 iterations, policy errors for all N ≥ 5 reduce to less than 2%. This indicates that Algorithm 1 has the ability to find the near-optimal policy of MPC problems with different prediction horizons N . Fig. 8 shows the policy performance of the ipopt solver solution and learned policy π c (x 0 , r 1:c ; θ) with different prediction horizons. The policy performance is measured by the lost function of 200 steps (10s) during the simulation period staring from random initialized state, i.e., For all prediction domains N , the learned policy performs as well as the solution of ipopt solver. More recurrent cycles (or long prediction steps) help reduce the accumulated cost L.  compares the control output between the learned policy(after 15 recurrent cycles) with ipopt controller.Obviously, the trajectory controlled by RMPC controller almost overlaps with the ipopt controller. The more recurrent cycles of the learned policy, the smaller the trajectory tracking error.This is why we want to adaptively select the optimal law with longest prediction horizon in real applications.
To summarize, the example demonstrates the optimality, efficiency and generality of the RMPC algorithm.

V. CONCLUSION
This paper proposes the Recurrent Model Predictive Control (RMPC) algorithm to solve general nonlinear finite-horizon optimal control problems. Unlike traditional MPC algorithms, it can make full use of the current computing resources and adaptively select the longest model prediction horizon. Our algorithm employs an RNN to approximate the optimal policy, which maps the system states and reference values directly to the control inputs. The output of the learned policy network after N recurrent cycles corresponds to the nearly optimal solution of N -step MPC. A policy optimization objective is designed by decomposing the MPC cost function according to the Bellman's principle of optimality.The optimal recurrent policy can be obtained by directly minimizing the designed objective function, which is applicable for general nonlinear and non input-affine systems. The convergence and optimality of RMPC is further proved. We demonstrate its optimality, generality and efficiency using a HIL experiment. Results show that RMPC is over 5 times faster than the traditional MPC algorithm. The control performance of the learned policy can be further improved as the number of recurrent cycles increases.