Sampled–Data Model Predictive Control Using Adaptive Time–Mesh Refinement Algorithms

Abstract

We address sampled–data nonlinear Model Predictive Control (MPC) schemes, in particular we address methods to efficiently and accurately solve the underlying continuous-time optimal control problems (OCP). In nonlinear OCPs, the number of discretization points is a major factor affecting the computational time. Also, the location of these points is a major factor affecting the accuracy of the solutions. We propose the use of an algorithm that iteratively finds the adequate time–mesh to satisfy some pre–defined error estimate on the obtained trajectories. The proposed adaptive time–mesh refinement algorithm provides local mesh resolution considering a time–dependent stopping criterion, enabling an higher accuracy in the initial parts of the receding horizon, which are more relevant to MPC. The results show the advantage of the proposed adaptive mesh strategy, which leads to results obtained approximately as fast as the ones given by a coarse equidistant–spaced mesh and as accurate as the ones given by a fine equidistant–spaced mesh.

1 Introduction

This article discusses an adaptive time–mesh refinement algorithm to efficiently and accurately solve optimal control problems (OCP) and proposes its use in Model Predictive Control (MPC) schemes.

In the last decade, most of the MPC literature has been using discrete–time models (e.g. [12, 14, 27]). However, some of the earlier theoretical works on nonlinear MPC used continuous–time models (see [4, 9, 16, 17]). Recently, [13] proposed a multi–step MPC scheme, which despite still being a discrete–time scheme, has the optimization and feedback updates done at possibly different time instants. The authors show that such technique can lower the computational load while maintaining stability and quantifiable robust performance estimates. In [21], some of the authors that vastly contributed to spread the use of discrete–time MPC (c.f. [27]) show that a continuous–time method is significantly more efficient than standard discrete–time methods when solving constrained linear quadratic problems.

To implement MPC schemes, some form of discretization, or at least a finite parameterization, is eventually needed to solve the OCP. Nevertheless, there are several advantages in maintaining a continuous–time model until later stages. In addition to being able to obtain more accurate solution to OCPs faster, it might be essencial in nonlinear systems that can rapidly change behavior in some short time intervals or even when there is a discontinuity at some critical instant (e.g. impulsive control [10, 23]). Also, path-following MPC strategies are more complex to implement in discrete-time than in sampled-data schemes (compare [24, 25] with [3, 28]).

We also argue that the time is ripe to start using continuous–time MPC, even in applications [8, 28]. Many theoretical questions of using sampled–data systems are well documented in the literature [5–7, 11, 15, 26] and there are now several ready available software packages to solve nonlinear OCP [18].

In OCP solvers using direct collocation methods, the control and the state are discretized in an appropriately chosen mesh of the time interval. Then, the continuous–time OCP is transcribed into a finite–dimensional nonlinear programming problem (NLP) which can be solved using widely available software packages [18]. Most frequently, in the discretization procedure, regular time meshes having equidistant spacing are used. However, in some cases, these meshes are not the most adequate to deal with nonlinear behaviours. One way to improve the accuracy of the results, while maintaining reasonable computational time and memory requirement, is to construct a mesh having different time steps. The best location for the smaller steps sizes is, in general, not known a priori, so the mesh is refined iteratively. In a mesh–refinement procedure the problem is solved, typically, in an initial coarse uniform mesh in order to capture the basic structure of the solution and of the error. Then, this initial mesh is repeatedly refined according to a chosen strategy until some stopping criterion is attained. Several mesh refinement methods employing direct collocation methods have been described in the recent years [1, 2, 22, 29].

In this paper, we adapt and apply to an MPC context an adaptive time–mesh refinement algorithm to solve nonlinear OCP [20]. The algorithm computes iteratively an adequate time-mesh that satisfies some pre–defined error estimates on the obtained trajectories. The refinement method used here (a) permits several levels of refinement, obtaining a multi–level time–mesh in a single iteration. (b) it also permits different refinement criteria – the relative error of the primal variables, the relative error of the dual variables or a combination of both; (c) it considers distinct criteria for refining the mesh and for stopping the refinement procedure – the refinement strategy can be driven by the information given by the dual variables and it can be stopped according to the information given by the primal variables. As described in [20], there are advantages in choosing the error of the adjoint multipliers as a refinement criterion. To decrease the overall computational time, the solution computed in the previous iteration is used as a warm start in the next one, which proved to be of major importance to improve computational efficiency. This adaptive strategy leads to results with higher accuracy and yet with lower overall computational time, when compared to results obtained by meshes having equidistant spacing, as is the case when using discrete–time models from the beginning.

In MPC context, the prediction can be interpreted in the sense of planning. When we make plans for the future, we establish planning strategies with detail level depending on the prediction horizon. Combining this idea with the refinement strategy, we obtain an adaptive time–mesh refinement algorithm which generates meshes with higher concentration of node points in the beginning of the prediction horizon and less concentration of node points in the end of the same interval, enforcing the idea of having more nodes point where they are needed and keeping a low overall number of node points. This is an important issue, because we want to increase the accuracy of the solution without compromising CPU times.

2 The Adaptive Mesh Refinement Algorithm for Optimal Control Problems

Let us consider the optimal control problem:

$$\begin{aligned} \mathcal {P}(t_0,t_f): \text {Minimise}~~&\int _{t_0}^{t_f} \mathrm{L}\left( t, {\mathbf {x}}(t), {\mathbf {u}}(t)\right) \mathrm{d}t + \mathrm{G}\left( {\mathbf {x}}(t_f) \right) \end{aligned}$$

(1)

$$\begin{aligned} \text {subject to}~~&\dot{{\mathbf {x}}}(t) = {\mathbf {f}}(t, {\mathbf {x}}(t), {\mathbf {u}}(t))&\text {a.e.}~ t\in \left[ t_{0}, t_{f}\right] \,, \end{aligned}$$

(2)

$$\begin{aligned}&{\mathbf {x}}(t_0)= {\mathbf {x}}_0 \,,&\end{aligned}$$

(3)

$$\begin{aligned}&{\mathbf {x}}(t_f) \in \mathbb {X}_1 \subset \mathbb {R}^n\,, \end{aligned}$$

(4)

$$\begin{aligned}&{\mathbf {x}}(t) \in \mathbb {X}\subset \mathbb {R}^n&\text {a.e.}~ t\in \left[ t_{0}, t_{f}\right] \,, \end{aligned}$$

(5)

$$\begin{aligned}&{\mathbf {u}}(t) \in \mathbb {U}\subset \mathbb {R}^m&\text {a.e.}~ t\in \left[ t_{0}, t_{f}\right] \,, \end{aligned}$$

(6)

where ${\mathbf {x}}: \left[ t_{0}, t_{f}\right] \rightarrow \mathbb {R}^n$ is the state, ${\mathbf {u}}: \left[ t_{0}, t_{f}\right] \rightarrow \mathbb {R}^m$ is the control and $t \in \left[ t_{0}, t_{f}\right]$ is time. The functions involved comprise the running cost $\mathrm{L}: \left[ t_{0}, t_{f}\right] \times \mathbb {R}^n \times \mathbb {R}^m \rightarrow \mathbb {R}$, the terminal cost $\mathrm{G}: \mathbb {R}^n \rightarrow \mathbb {R}$ and the system dynamics ${\mathbf {f}}: \left[ t_{0}, t_{f}\right] \times \mathbb {R}^n \times \mathbb {R}^m \rightarrow \mathbb {R}^n$.

As stated in [19, 20], the adaptive mesh refinement process starts by discretizing the time interval $[t_0,t_f]$ in a coarse mesh used to solve the NLP problem associated to the OCP in order to catch the main structure of the solution. According to some refinement criteria, the mesh is divided in $K \in \mathbb {N}$ mesh intervals

$$\begin{aligned} \mathcal {S}_k&= [\tau _{k-1}, \tau _k[\,, \quad k = 1,\ldots ,K, \end{aligned}$$

where $(\tau _0,\ldots ,\tau _K)$ coincide with nodes. These mesh intervals $\mathcal {S}_k$ form a partition of the time interval while the mesh nodes have the property $\tau _0< \tau _1< \ldots < \tau _K \,.$

The subintervals $\mathcal {S}_k$ that verify the refinement criteria are refined taking into account different levels of refinement in a single iteration, i.e., they are divided into smaller subintervals according to user–defined levels of refinement ${\bar{\varepsilon }}=, \left[ \varepsilon _1,\, \varepsilon _{2},\,\ldots ,\, \varepsilon _{m} \right]$. The procedure is repeated until the stopping criterion is achieved. A subinterval $\mathcal {S}_{k,j}$ is at the $j^{th}$ level of refinement if

(7)

for $j=1,\ldots ,m$. This procedure adds more node points to the subintervals in higher levels of refinement, corresponding to higher errors, and it adds less node points to those in lower refinement levels (Fig. 1). By defining several levels of refinement, we get a multi–level time–mesh in a single iteration.

Fig. 1

Illustration of the multi–level adaptive time–mesh refinement strategy

3 The Model Predictive Control Framework

Consider a sampling step $\delta >0$, the prediction horizon T and a sequence of sampling instants $\{t_i\}_{i\ge 0}$ with $t_{i+1}=t_i+\delta$. The sampled-data MPC algorithm follows the receding horizon strategy [9]:

• 1. Measure state of the plant ${\mathbf {x}}_{t_i}$;

• 2. Determine ${\bar{{\mathbf {u}}}} : \left[ t_i, t_i+T \right] \rightarrow \mathbb {R}^m$ solution to the OCP $\mathcal {P}(t_i,t_i+T)$ (1)-(6).

• 3. Apply the control ${\mathbf {u}}^{*}(t) := {\bar{{\mathbf {u}}}}(t)$ to the plant in the interval $t \in \left[ t_i, t_i+\delta \right]$, disregarding the remaining control ${\bar{{\mathbf {u}}}}(t), t > t_i + \delta$;

• 4. Repeat this procedure for the next sampling time instant $t_i + \delta$.

We extend the adaptive time–mesh refinement algorithm described in [20] in order to allow different refinement levels according to some partition of the time domain. This extension is of relevance in the MPC context, since it is desirable to have a solution with higher accuracy in the initial part of the horizon.

Motivation. The time interval $t \in \left[ t_{0}, t_{f}\right]$, the prediction horizon T, and the sampling step $\delta >0$, satisfy $\delta<< T< < t_f - t_0$. When applying the MPC procedure to solve an OCP, at each time instant $t_i$ we compute the solution in $\left[ t_i, t_i+T \right]$ but we just implement the open–loop control until $t_i+\delta$. Therefore, taking into account the planning strategy discussed above, it would be an improvement if we have an adaptive time–mesh able to cope this feature, i.e., a time–mesh that is highly refined in the lower limit of the time interval $\left[ t_i, t_i+T \right]$ and it is coarser in the upper limit of the same interval. Then, we would implement the control on the time interval $\left[ t_i, t_i+\delta \right]$ computed with high accuracy in a refined mesh. For the remaining time interval we have an estimate of the solution.

Time–Mesh Refinement Algorithm. In this extension, we also consider a time–dependent stopping criterion for the mesh refinement algorithm with different levels ${\bar{\varepsilon }}_{{\mathbf {x}}}(t)$. Instead of having a fixed stopping criterion $\varepsilon _{{\mathbf {x}}}^{\text {max}}$, now we have a time–dependent ${\bar{\varepsilon }}_{{\mathbf {x}}}(t)$ stopping criterion which sets different levels of accuracy for the solution, along the time domain. For example, the time–dependent levels of refinement can be defined as

where $1< \alpha _1< \cdots < \alpha _j \le \varepsilon _{{\mathbf {x}}}^{\text {max}}$ and $0< \beta _1< \beta _2< \cdots< \beta _j < 1$ are user–defined scalars.

This procedure adds more node points to the subintervals that are in lower levels of the stopping criterion for the refinement procedure, corresponding to time instants close to the initial time as illustrated in Fig. 2.

Fig. 2

Illustration of the extended (time–dependent) time–mesh refinement strategy

Refinement and Stopping Criteria. In order to proceed with the mesh refinement strategy, we have to define some refinement criteria and a stopping criterion. We consider as refinement criteria: the estimate of the relative error of the adjoint multipliers (dual variables). For the stopping criterion, we consider a threshold for the relative error of the trajectory $\left| \left| \varepsilon _{{\mathbf {x}}}\right| \right| _\infty$.

Warm Start. Since we are solving a sequence of open–loop OCPs, to decrease the CPU time, when going from the problem in $\left[ t_i, t_i+T \right]$ to the one in $\left[ t_i + \delta , t_i+T\right.$ $\left. +\delta \right]$, the solution of the previous is used as a warm start for the problem. To create this warm start, the solution obtained in $\left[ t_i, t_i+T \right]$ is projected in the new mesh in $\left[ t_i+\delta , t_i+T+\delta \right]$ using the cubic Hermite interpolation.

Model Predictive Control coupled with the Extended Algorithm. We start the MPC procedure in the typical way but considering an adaptive mesh refinement strategy. We descritise the time interval $\left[ t_{0}, t_{f}\right]$ and we solve our OCP in open–loop. Then, we implement the control in the first sampling interval. When starting the next MPC step, we apply the time–mesh refinement strategy in order to find the best mesh suited to the solve the OCP in the second sampling interval (Fig. 3). In the MPC algorithm, step 2 is modified as follows:

• 2.

  • (a) Select the intervals $S_{k,j}$ to be refined according to the time–dependent levels of refinement ${\bar{\varepsilon }}_{{\mathbf {x}}}(t)$ and generate a new time grid;

  • (b) Determine ${\bar{{\mathbf {u}}}} : \left[ t_i, t_i+T \right] \rightarrow \mathbb {R}^m$ solution to the OCP $\mathcal {P}(t_i,t_i+T)$ (1)–(6), in the new time-grid;

Fig. 3

Time–mesh refinement algorithm for MPC

4 Application: Parking Manoeuvres

In order to apply our MPC strategy, let us consider the car–like system problem with $t \in [0,20]$, in seconds, $\mathbf {x}(t) = (x(t),y(t),\psi (t))$ and $\mathbf {u}(t)=(u(t),c(t))$. Aiming minimum energy, this problem $(\mathrm{P}_{\text {CP}})$ can be stated as:

$$\begin{aligned} \text {Minimise}~&\int _{0}^{20} u^2 (t) \mathrm {d}t \end{aligned}$$

(8)

$$\begin{aligned} \text {subject to}~~&\dot{x}(t) = u(t)\cos (\psi (t))&\text {a.e.}~ t \in [0,20] \nonumber \\&\dot{y}(t) = u(t)\sin (\psi (t))&\text {a.e.}~ t \in [0,20] \end{aligned}$$

(9)

$$\begin{aligned}&\dot{\psi }(t) = u(t)\,c (t)&\text {a.e.}~ t \in [0,20] \nonumber \\&{\mathbf {x}}(0)= {\mathbf {x}}_0 \,, \end{aligned}$$

(10)

$$\begin{aligned}&{\mathbf {x}}(20) \in \mathbb {X}_1, \end{aligned}$$

(11)

$$\begin{aligned}&{\mathbf {x}}(t) \in \mathbb {X}\,,&\forall t\in \left[ t_{0}, t_{f}\right] \end{aligned}$$

(12)

$$\begin{aligned}&-1 \le u(t) \le 1&\text {a.e.}~ t \in [0,20] \end{aligned}$$

(13)

$$\begin{aligned}&-0.7 \le c(t) \le 0.7&\text {a.e.}~ t \in [0,20] \end{aligned}$$

(14)

where u(t) is the speed and c(t) is the curvature. The end–point constraints are specified as

$$\begin{aligned} {\mathbf {x}}_0 =&(x_0,\,y_0,\,\psi _0) = (1.5,3.5,{}^{\pi }\!/_{2}) \end{aligned}$$

(15)

$$\begin{aligned} \mathbb {X}_1 =&\left\{ (x,y,\psi ) : \left( x-x_f \right) ^2 + \left( y-y_f \right) ^2 + \left( \psi -\psi _f \right) ^2 \le r^2 \right\} \end{aligned}$$

(16)

Fig. 4

Pathwise state constraints (17) for $(\mathrm{P}_{\text {CP}})$

where $r^2 = 0.1$, and ${\mathbf {x}}_f = (x_f,\,y_f,\,\psi _f)=(4,0,0)$ is a user–defined target point. Moreover, we define a pathwise state constraint (see Fig. 4) set $\mathbb {X}$ is the set of points $(x,\,y,\,\psi )$ satisfying

$$\begin{aligned} \left\{ \begin{aligned} -M&\le y \le M&\text {if}~ x \in [x_0,x^*] \\ -b\left( \mathbf {x} \right)&\le y \le b\left( \mathbf {x} \right)&\text {if}~ x \in [x^*,x^\star ] \\ -m&\le y \le m&\text {if}~ x \in [x^\star ,x_f] \end{aligned} \right. \end{aligned}$$

(17)

where $x^*=2, x^\star =3, y^\star = -1.5,\,M=4$ and

$$\begin{aligned} b\left( \mathbf {x} \right) = y^\star - \sqrt{\rho ^2 - (x - x^\star )^2}\,, \quad \rho =\vert x^\star - x^*\vert \,. \end{aligned}$$

In order to test the MPC algorithm, we start by introducing some perturbations on the system dynamics test–plant:

$$\begin{aligned} \left\{ \begin{aligned} \dot{x}(t)&= u(t) \left( 1+ \delta _u \right) \cos (\psi (t)) \\ \dot{y}(t)&= u(t) \left( 1+ \delta _u \right) \sin (\psi (t)) \\ \dot{\psi }(t)&= u(t)\left( 1+ \delta _u \right) \,c (t)\left( 1+ \delta _c \right) \end{aligned} \right. . \end{aligned}$$

(18)

We consider $\delta = 2\;\mathrm {s}$ which means that we will solve a sequence of 10 open–loop OCPs and we define $\delta _u = \delta _c = 0.1$. We also set $\varepsilon _{{\mathbf {x}}}^{\text {max}} = 5 \times 10^{-5}$ and

This problem is solved considering three meshes:

(a):

$\pi _\mathrm{{ML}}$: the multi–level time–mesh refinement strategy with MPC;

(b):

$\pi _\mathrm{{F}}$: equidistant–spaced with the smallest time step of $\pi _\mathrm{{ML}}$;

(c):

$\pi _\mathrm{{C}}$: equidistant–spaced with the largest time step of $\pi _\mathrm{{ML}}$.

As it can be seen in Fig. 5a, considering the mesh $\pi _\mathrm{{ML}}$, the car–like system successfully stops when the terminal condition (16) is satisfied without violating any constraint. The sequence of solutions given by each sampling step on MPC is shown in Fig. 5b. The predictions are plotted with a dashed line, while the implemented controls are plotted with a solid line. Each segment is drawn with a different color representing different MPC sampling times.

Fig. 5

Optimal trajectory for $(\mathrm{P}_{\text {CP}})$. a MPC trajectory, b Sequence of optimal trajectories

The numerical results concerning the three meshes are shown in Table 1, which shows information about the number of nodes, the smallest time step, the number of iterations needed to solve the NLP problem, the maximum absolute local errors of the trajectory, and the CPU times for solving the OCP problem and for computing the local error as well.

According to Table 1, the mesh $\pi _\mathrm{{ML}}$ has only $11.4\,\%$ of the nodes of $\pi _\mathrm{{F}}$, nevertheless both meshes have maximum absolute local error of the same order of magnitude. Computing the solution using $\pi _\mathrm{{ML}}$ takes less than $20\,\%$ of the time needed to get a solution using $\pi _\mathrm{{F}}$, resulting in significant savings in memory and computational cost.

The mesh $\pi _\mathrm{{C}}$ is the initial coarse mesh considering equidistant spacing. Without applying our refinement strategy, the MPC produces a solution with lower accuracy, $1.261\textsc {e}^{-3}$, when compared against the solution obtained via refinement procedure, $4.169\textsc {e}^{-5}$. Moreover, the CPU time spent to compute solution using $\pi _\mathrm{{ML}}$ is, as expected, $50\,\%$ higher than the one spent to obtain a solution using $\pi _\mathrm{{C}}$, however it is a good trade–off since the accuracy of the solution increases by two orders of magnitude. In all tests, the procedure gives the optimal solution which is computed spending a few seconds overall to solve 10 MPC steps.

Table 1 Comparing MPC results for the problem $(\mathrm{P}_{\text {CP}})$

The use of adaptive mesh refinement algorithm in real time optimization problems has additional benefits since it is possible to quickly obtain a solution even if the refinement procedure is interrupted at an early stage.

5 Conclusions

We develop an extended adaptive time–mesh refinement algorithm providing local mesh resolution refining only where it is required. In this extension, we consider a time–dependent stopping criterion for the mesh refinement algorithm with different levels ${\bar{\varepsilon }}(t)$. In the end, the OCPs are solved within MPC with an adapted mesh with local mesh resolution which has less nodes in the overall procedure, yet having maximum absolute local error of the same order of magnitude when compared against a refined mesh with equidistant–spacing.

Due to the fast response of the algorithm, it can be used to solve real–time optimization problems. The application demonstrates the advantage of the proposed adaptive mesh strategy, which leads to results obtained approximately as fast as the ones given by a coarse equidistant–spacing mesh and as accurate as the ones given by a fine equidistant–spacing mesh.

With this framework we can use continuous–time plant models directly. The discretization procedure can be automated and there is no need to select a priori the adequate time step.

Even if the optimization procedure is forced to stop in an early stage, as might be the case in real-time, we can still obtain a meaningful solution, although it might be a less accurate one.