Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Nonlinear Model Predictive Control (NMPC) involves the solution at each sampling instant of a finite horizon optimal control problem subject to the system dynamics, and state and input constraints. However, solving in a centralized way NMPC problems for large-scale systems may be impractical due to the complexity of the Nonlinear Programming (NLP) problem, the topology of the plant and data communication, and the large number of decision variables. Therefore, there is a strong motivation for development of methods for distributed solution of NMPC problems. At the same time, the multi-core computer architectures available nowadays would encourage parallel and distributed NMPC computations [4]. Recently, several approaches for decentralized implementation of MPC algorithms have been developed [18]. As it is pointed out in [14], the possibility to use MPC in a decentralized fashion has the advantage to reduce the original, large size, optimization problem into a number of smaller and more tractable ones. In [7, 12, 19, 20], approaches for distributed MPC for systems consisting of linear interconnected subsystems have been developed.

Approaches for distributed MPC for systems composed of several nonlinear subsystems have been proposed in [6, 9, 11, 14, 15]. In [14], a stabilizing decentralized MPC algorithm for nonlinear systems consisting of several interconnected local subsystems is developed. It is derived under the main assumptions that no information can be exchanged between local control laws. In [6], it is supposed that the dynamics and constraints of the nonlinear subsystems are decoupled, but their state vectors are coupled in a single cost function of a finite horizon optimal control problem. In [11], an optimal control problem for a set of dynamically decoupled nonlinear systems, where the cost function and constraints couple the dynamical behavior of the systems, is solved. In [15], novel control techniques for the control of transportation networks are proposed, which are based on a combination of ideas from the fields of multi-agent systems and MPC.

The distributed MPC approach in [7] is based on the dual decomposition methods [3, 5], whose rationale is to reformulate the large-scale optimization problems by using Lagrange multipliers for relaxing the couplings between the sub-problems. It is applied to systems composed by a set of linear subsystems, subject to both state and input constraints. Since the approach applies to the complex case when the subsystems are coupled through their dynamics, it is referred to as dynamic dual decomposition [7, 17]. The fact that it takes into account the dynamic couplings between the subsystems when optimizing the overall system behavior and at the same time allows for decentralized MPC solution makes it very attractive. In [9], the suboptimal approach from [7] is extended to an approach to distributed NMPC for a more general class of systems consisting of nonlinear subsystems with linearly coupled dynamics subject to both state and input constraints. Thus, the approach in [9] applies the dynamic dual decomposition method [3, 7, 17] and reformulates the original centralized NMPC problem into a distributed quasi-NMPC problem by linearization of the nonlinear system dynamics. It is based entirely on distributed on-line optimization (by gradient iterations) and can be applied to large-scale nonlinear systems. In [10], the suboptimal quasi-NMPC approach from [9] where linear couplings between the subsystems have been assumed, is further extended to solve distributed NMPC problems for interconnected nonlinear systems with separable nonlinearly coupled dynamics.

The purpose of this chapter is to summarize the main ideas of the distributed quasi-NMPC approach in [9] with the extensions in [10], as well as to review the theoretical and the simulation results associated to both linear and nonlinear interconnected systems.

2 Boundary Conditions on the System, Control Objectives, and Constraints

Consider a system composed by the interconnection of a set of subsystems \(\mathcal {N}=\{S_1,\,S_2,\ldots ,\,S_{|\mathcal {N}|}\}\) (Fig. 18.1), which is described by the following nonlinear discrete-time models [14]:

$$\begin{aligned} \mathbf {x}_i(k+1) = \mathbf {f}_i(\mathbf {x}_i(k),\mathbf {u}_i(k)) + \mathbf {g}_i(\mathbf {x}(k)),\quad i=1,\,2,\ldots ,|\mathcal {N}| \end{aligned}$$
(18.1)

where \(\mathbf {x}_i(k) \in \mathbb {R}^{n_{x_i}}\) and \(\mathbf {u}_i(k) \in \mathbb {R}^{n_{u_i}}\) are the state and control input vectors, related to the \(i\)th subsystem, and \(\mathbf {f}_i \,:\, \mathbb {R}^{n_{x_i}} \times \mathbb {R}^{n_{u_i}} \rightarrow \mathbb {R}^{n_{x_i}}\) and \(\mathbf {g}_i \,:\, \mathbb {R}^{n_x} \rightarrow \mathbb {R}^{n_{x_i}}\) are nonlinear functions. In (18.1), the mutual influence of the \(|\mathcal {N}|\) subsystems is described by the functions \(\mathbf {g}_i\), which depend on the overall state:

Fig. 18.1
figure 1

System composed by the interconnection of \(|\mathcal {N}|\) subsystems

Full size image
$$\begin{aligned} \mathbf {x}(k) = [\mathbf {x}_1(k),\,\mathbf {x}_2(k),\ldots ,\mathbf {x}_{|\mathcal {N}|}(k)] \in \mathbb {R}^{n_x} ,\quad n_x = \sum _{i=1}^{|\mathcal {N}|} n_{x_i} \end{aligned}$$
(18.2)

Similarly, the overall control input is denoted:

$$\begin{aligned} \mathbf {u}(k) = [\mathbf {u}_1(k),\,\mathbf {u}_2(k),\ldots ,\mathbf {u}_{|\mathcal {N}|}(k)] \in \mathbb {R}^{n_u} ,\quad n_u = \sum _{i=1}^{|\mathcal {N}|} n_{u_i} \end{aligned}$$
(18.3)

The following control input and state constraints are imposed on the subsystems:

$$\begin{aligned} \mathbf {u}_{\min ,i} \le \mathbf {u}_i(k) \le \mathbf {u}_{\max ,i} ,\,\, \mathbf {x}_{\min ,i} \le \mathbf {x}_i(k) \le \mathbf {x}_{\max ,i},\, i=1,\ldots ,|\mathcal {N}| \end{aligned}$$
(18.4)

and the following assumptions are made:

  • A1. The functions \(\mathbf {f}_i\) and \(\mathbf {g}_i\), \(i=1,\ldots ,|\mathcal {N}|\) are \(C^1\) functions with \(\mathbf {f}_i(0,0)=0\), \(\mathbf {g}_i(0)=0\).

  • A2. \(\mathbf {x}_{\min ,i}<0<x_{\max ,i}\), \(\mathbf {u}_{\min ,i}<0<\mathbf {u}_{\max ,i}\), \(i=1,\ldots ,|\mathcal {N}|\).

  • A3. The nonlinear functions \(\mathbf {g}_i(\mathbf {x}(k))\) of the couplings are separable, i.e., they have the form:

$$\begin{aligned} \mathbf {g}_i(\mathbf {x}(k)) = \sum _{j=1,\,j \ne i}^{|\mathcal {N}|} \mathbf {h}_{ij}(\mathbf {x}_j(k)) ,\quad i=1,\ldots ,|\mathcal {N}| \end{aligned}$$
(18.5)

where \(\mathbf {h}_{ij} \,:\, \mathbb {R}^{n_{x_j}} \rightarrow \mathbb {R}^{n_{x_i}}\) are nonlinear functions with \(\mathbf {h}_{ij}(0)=0\).

It is also assumed that the distributed NMPC controllers for the interconnected subsystems can communicate to each other the computed optimal state trajectories of the subsystems and the trajectories of the Lagrange multipliers, associated to the application of the dual decomposition method. A detailed communication scheme corresponding to the proposed distributed NMPC method is given in Sect. 18.3.

It is supposed that a full measurement \(\bar{\mathbf {x}}=[\bar{\mathbf {x}}_1,\,\bar{\mathbf {x}}_2,\ldots ,\,\bar{\mathbf {x}}_{|\mathcal {N}|}]\) of the overall initial state is available, i.e., \(\mathbf {x}(0)=\bar{\mathbf {x}}\). The optimal regulation problem is considered where the goal is to steer the overall state of the system (18.1) to the origin. This leads to the infinite horizon optimal control problem:

Problem P0 (Infinite Horizon Optimization):

$$\begin{aligned} J^{\infty }(\bar{\mathbf {x}}) = \mathop {\min } \limits _{\mathbf {u}} \, \sum _{k=0}^\infty \sum _{i=1}^{|\mathcal {N}|} s_i(\mathbf {x}_i(k),\mathbf {u}_i(k)) \end{aligned}$$
(18.6)

subject to (18.1) and:

$$\begin{aligned}&\mathbf {x}_i(k) \in \mathcal {X}_i ,\, i=1,\ldots ,\,|\mathcal {N}| \quad \mathrm {for\;all\;} k \end{aligned}$$
(18.7)
$$\begin{aligned}&\mathbf {u}_i(k) \in \mathcal {U}_i ,\, i=1,\ldots ,\,|\mathcal {N}| \quad \mathrm {for\;all\;} k \end{aligned}$$
(18.8)

Here \(s_i(\mathbf {x}_i(k),\mathbf {u}_i(k)) = \Vert \mathbf {x}_i(k)\Vert _{\mathbf {Q}_i}^2 + \Vert \mathbf {u}_i(k)\Vert _{\mathbf {R}_i}^2\) is the stage cost for the \(i\)th subsystem with weighting matrices \(\mathbf {Q}_i,\,\mathbf {R}_i \succ 0\), and the sets \(\mathcal {X}_i\) and \(\mathcal {U}_i\) are defined by:

$$\begin{aligned}&\mathcal {X}_i = \left\{ \pmb {\lambda }_i \in \mathbb {R}^{n_{x_i}} \,|\, \mathbf {x}_{\min ,i} \le \pmb {\lambda }_i \le \mathbf {x}_{\max ,i}\right\} \end{aligned}$$
(18.9)
$$\begin{aligned}&\mathcal {U}_i = \left\{ \pmb {\eta }_i \in \mathbb {R}^{n_{u_i}} \,|\, \mathbf {u}_{\min ,i} \le \pmb {\eta }_i \le \mathbf {u}_{\max ,i}\right\} \end{aligned}$$
(18.10)

It follows from (18.9)–(18.10) that \(\mathcal {X}_i\) and \(\mathcal {U}_i\) are convex (polyhedral) sets, which include the origin in their interior (due to assumption A2).

Similar to [7], the infinite horizon optimal control problem P0 is approximated with an NMPC problem without a terminal cost and terminal constraint, where the objective function is obtained by truncating the infinite horizon objective. Let the measured state at time \(k\) be \(\mathbf {x}=[\mathbf {x}_1,\,\mathbf {x}_2,\dots ,\mathbf {x}_{|\mathcal {N}|}]\). For the current \(\mathbf {x}\), the regulation NMPC solves the problem:

Problem P1 (Centralized NMPC):

$$\begin{aligned} J^{\mathrm {opt}}(\mathbf {x}) = \mathop {\min } \limits _{\mathbf {u}(k:k+N_{\mathrm {p}})} \, J(\mathbf {u}(k:k+N_{\mathrm {p}}),\mathbf {x}) \end{aligned}$$
(18.11)

subject to \(\mathbf {x}(k)=\mathbf {x}\) and:

$$\begin{aligned}&\mathbf {x}_i(k+l) \in \mathcal {X}_i ,\, i=1,\ldots ,\,|\mathcal {N}| ,\, l=1,\ldots ,\,N_{\mathrm {p}}&\end{aligned}$$
(18.12)
$$\begin{aligned}&\mathbf {u}_i(k+l) \in \mathcal {U}_i ,\, i=1,\ldots ,\,|\mathcal {N}| ,\, l=0,\,1,\ldots ,\,N_{\mathrm {p}}-1&\end{aligned}$$
(18.13)
$$\begin{aligned}&\mathbf {x}_i(k+l+1) = \mathbf {f}_i(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l)) + \mathbf {g}_i(\mathbf {x}(k+l)) \nonumber&\\&\qquad \quad i=1,\ldots ,\,|\mathcal {N}| ,\, l=0,\,1,\ldots ,\,N_{\mathrm {p}}-1&\end{aligned}$$
(18.14)
$$\begin{aligned}&\mathbf {x}(k+l) = [\mathbf {x}_1(k+l),\ldots ,\,\mathbf {x}_{|\mathcal {N}|}(k+l)] ,\, l=0,\,1,\ldots ,\,N_{\mathrm {p}}&\end{aligned}$$
(18.15)
$$\begin{aligned}&\mathbf {u}(k+l) = [\mathbf {u}_1(k+l),\ldots ,\,\mathbf {u}_{|\mathcal {N}|}(k+l)] ,\, l=0,\,1,\ldots ,\,N_{\mathrm {p}}-1&\end{aligned}$$
(18.16)

where the cost function is given by:

$$\begin{aligned} J(\mathbf {u}(k:k+N_{\mathrm {p}}),\mathbf {x}) = \sum _{l=\,0}^{N_{\mathrm {p}}} \sum _{i=1}^{|\mathcal {N}|} s_i(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l)) \end{aligned}$$
(18.17)

Here, \(N_{\mathrm {p}}\) is a finite horizon.

3 Description of the Distributed NMPC Approach

3.1 Distributed NMPC by Dynamic Dual Decomposition

Problem P1 can be decomposed by using the dynamic dual decomposition approach [3, 17]. The following decoupled state equations can be formulated:

$$\begin{aligned} \mathbf {x}_i(k+1) = \mathbf {f}_i(\mathbf {x}_i(k),\mathbf {u}_i(k)) + \mathbf {v}_i(k) ,\quad i=1,\ldots ,|\mathcal {N}| \end{aligned}$$
(18.18)

with the additional constraints that:

$$\begin{aligned} \mathbf {v}_i(k) = \sum _{j=1,\, j \ne i}^{|\mathcal {N}|} \mathbf {h}_{ij}(\mathbf {x}_j(k)) \,,\quad i=1,\dots ,\,|\mathcal {N}| \,\,\, \text {for all} \,\, k \end{aligned}$$
(18.19)

The variable \(\mathbf {v}_i \in \mathbb {R}^{n_{x_i}}\) can be interpreted as the influence of the other subsystems in the update of \(\mathbf {x}_i\).

Then, the constraints (18.19) are relaxed by introducing the corresponding Lagrange multipliers \(\mathbf {p}_i \in \mathbb {R}^{n_{x_i}}\) in the cost function (18.17) and the following distributed NMPC problem is formulated:

Problem P2 (Distributed NMPC):

$$\begin{aligned} \widetilde{J}^{\mathrm {opt}}(\mathbf {x})&= \mathop {\max } \limits _{\mathbf {p}(k:k+N_{\mathrm {p}})} \mathop {\min } \limits _{\begin{array}{c} {\mathbf {u}(k:k+N_{\mathrm {p}})} \\ {\mathbf {x}(k:k+N_{\mathrm {p}})} \\ {\mathbf {v}(k:k+N_{\mathrm {p}})} \end{array}} \sum _{l=0}^{N_{\mathrm {p}}} \sum _{i=1}^{|\mathcal {N}|} \left[ s_i(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l))\right. \nonumber \\&\quad \left. +\;\mathbf {p}_i(k+l)^\mathrm{{T}} (\mathbf {v}_i(k+l) - \sum _{j=1,\, j \ne i}^{|\mathcal {N}|} \mathbf {h}_{ij}(\mathbf {x}_j(k+l)))\right] \nonumber \\&=\mathop {\max } \limits _{\mathbf {p}(k:k+N_{\mathrm {p}})} \sum _{i=1}^{|\mathcal {N}|} \left( \mathop {\min } \limits _{\begin{array}{c} {\mathbf {u}_i(k:k+N_{\mathrm {p}})} \\ {\mathbf {x}_i(k:k+N_{\mathrm {p}})} \\ {\mathbf {v}_i(k:k+N_{\mathrm {p}})} \end{array}} \sum _{l=0}^{N_{\mathrm {p}}} \left[ s_i(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l)) \right. \right. \nonumber \\&\left. \left. \quad +\;\mathbf {p}_i(k+l)^\mathrm{{T}} \mathbf {v}_i(k+l) - \sum _{j=1,\, j \ne i}^{|\mathcal {N}|} \mathbf {h}_{ji}^\mathrm{{T}}(\mathbf {x}_i(k+l)) \mathbf {p}_j(k+l)\right] \right) \end{aligned}$$
(18.20)

subject to \(\mathbf {x}(k)=\mathbf {x}\), constraints (18.12)–(18.13) and:

$$\begin{aligned}&\mathbf {x}_i(k+l+1) = \mathbf {f}_i(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l)) + \mathbf {v}_i(k+l) \nonumber \\&i=1,\ldots ,\,|\mathcal {N}| ,\, l=0,\,1,\ldots ,\,N_{\mathrm {p}}-1 \end{aligned}$$
(18.21)
$$\begin{aligned}&\mathbf {p}(k+N_{\mathrm {p}}) = 0 \end{aligned}$$
(18.22)

The requirement (18.22) follows from the optimality conditions of Pontryagin’s principle for discrete-time systems [2] and the fact that the state is not specified at the terminal time \(k+N_{\mathrm {p}}\). Here the following notation is used: \(\mathbf {p}(k+l) = [\mathbf {p}_1(k+l),\ldots ,\,\mathbf {p}_{|\mathcal {N}|}(k+l)]\), \(\mathbf {v}(k+l) = [\mathbf {v}_1(k+l),\ldots ,\mathbf {v}_{|\mathcal {N}|}(k+l)]\), \(l=0,\,1,\ldots ,\,N_{\mathrm {p}}\).

The stage cost in the second equality in (18.20) is denoted:

$$\begin{aligned}&s_i^p(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l),\mathbf {v}_i(k+l),\mathbf {p}(k:k+N_{\mathrm {p}})) \nonumber \\&=s_i(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l)) + \mathbf {p}_i(k+l)^\mathrm{{T}} \mathbf {v}_i(k+l) - \!\sum _{j=1,\, j \ne i}^{|\mathcal {N}|}\! \mathbf {h}_{ji}^\mathrm{{T}}(\mathbf {x}_i(k+l)) \mathbf {p}_j(k+l) \end{aligned}$$
(18.23)

The Lagrange multipliers \(\mathbf {p}\) are also referred to as prices [17]. In the special case when the problem P1 is convex and the Slater’s condition holds for the inequality constraints (18.12)–(18.13), then \(J^{\mathrm {opt}}(\mathbf {x})=\widetilde{J}^{\mathrm {opt}}(\mathbf {x})\) (there will be no duality gap [1]).

The inner decoupled optimization problems in problem P2 are Nonlinear Programming (NLP) sub-problems, since the constraints (18.21) and the stage cost function \(s_i^p(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l),\mathbf {v}_i(k+l),\mathbf {p}(k:k+N_{\mathrm {p}}))\) are nonlinear:

Problem P3 \(^\mathbf{i }\) (ith NLP Sub-problem):

$$\begin{aligned} \widetilde{J_i}^{\mathrm {opt}}(\mathbf {p}(k:k+N_{\mathrm {p}}),\mathbf {x}_i) = \mathop {\min } \limits _{\begin{array}{c} {\mathbf {u}_i(k:k+ N_{\mathrm {p}})} \\ {\mathbf {x}_i(k:k+N_{\mathrm {p}})} \\ {\mathbf {v}_i(k:k+N_{\mathrm {p}})} \end{array}} \sum _{l=0}^{N_{\mathrm {p}}} s_i^p(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l),\mathbf {v}_i(k+l),\mathbf {p}(k:k+N_{\mathrm {p}})) \end{aligned}$$
(18.24)

subject to \(\mathbf {x}_i(k)=\mathbf {x}_i\) and:

$$\begin{aligned}&\mathbf {x}_i(k+l) \in \mathcal {X}_i \,,\,\, l=1,\ldots ,\,N_{\mathrm {p}}&\end{aligned}$$
(18.25)
$$\begin{aligned}&\mathbf {u}_i(k+l) \in \mathcal {U}_i \,,\,\, l=0,\,1,\ldots ,\,N_{\mathrm {p}}-1&\end{aligned}$$
(18.26)
$$\begin{aligned}&\mathbf {x}_i(k+l+1) = \mathbf {f}_i(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l)) + \mathbf {v}_i(k+l) ,\, l=0,\,1,\ldots ,\,N_{\mathrm {p}}-1&\nonumber \\ \end{aligned}$$
(18.27)

Denote with \(\mathbf {u}_i^{\mathrm {opt}}(k:k+N_{\mathrm {p}})\), \(\mathbf {x}_i^{\mathrm {opt}}(k:k+N_{\mathrm {p}})\) and \(\mathbf {v}_i^{\mathrm {opt}}(k:k+N_{\mathrm {p}})\) the optimal solution of problem P3\(^i\). Note that the optimizers depend on the prices \(\mathbf {p}\).

3.2 Local Quadratic Programming Approximations

The constraints (18.27) in the problems P3\(^i\), \(i=1,\,2,\ldots ,\,|\mathcal {N}|\) may be non-convex in the general case (due to the nonlinearity of the functions \(\mathbf {h}_{ji}(\cdot )\) and \(\mathbf {f}_i(\cdot ,\cdot )\)). Below, the functions \(\mathbf {h}_{ji}(\cdot )\) and \(\mathbf {f}_i(\cdot ,\cdot )\) are locally approximated by linear functions, leading to a convex quasi-nonlinear approach. An advantage of this approach is that strong duality can be easily claimed, i.e., there will be no duality gap between the solution obtained by solving the centralized quasi-NMPC and the solution corresponding to the distributed quasi-NMPC (see Proposition 1 later in this section). Let \(\mathbf {x}_i(k)=\bar{\mathbf {x}}_i \in \mathcal {X}_i\) be arbitrary and denote the corresponding optimal solution to the sub-problem P3\(^i\) with:

$$\begin{aligned} \mathbf {u}_i^0 = \mathbf {u}_i^{\mathrm {opt}}(\bar{\mathbf {x}}_i,k:k+N_{\mathrm {p}}) ,\, \mathbf {x}_i^0 = \mathbf {x}_i^{\mathrm {opt}}(\bar{\mathbf {x}}_i,k:k+N_{\mathrm {p}}) ,\, \mathbf {v}_i^0 = \mathbf {v}_i^{\mathrm {opt}}(\bar{\mathbf {x}}_i,k:K+N_{\mathrm {p}}) \end{aligned}$$
(18.28)

The optimal solution (18.28) depends on the values of the prices \(\mathbf {p}\). Therefore, it would be necessary for \(\mathbf {p}\) and the solution (18.28) to be updated iteratively. In order to simplify the computations while iterating, the system model (18.1) with the coupling functions given by (18.5) is linearized around the point \((\mathbf {u}_i^0,\,\mathbf {x}_i^0,\,\mathbf {v}_i^0,\,\bar{\mathbf {x}}_i)\) and the predicted states are obtained with the linearized model:

$$\begin{aligned}&\mathbf {x}_i(k+l+1) = \mathbf {S}_{\mathbf {x}_i}(k+l) \mathbf {x}_i(k+l) + \mathbf {S}_{\mathbf {u}_i}(k+l) \mathbf {u}_i(k+l) \nonumber \\&\quad + \sum \nolimits _{\begin{array}{l} {j=1} \\ {j \ne i} \end{array}}^{|\mathcal {N}|} \mathbf {A}_{ij}(k+l) \mathbf {x}_j(k+l) + \mathbf {e}_{0i}(k+l) ,\,\, i=1,\ldots ,\,|\mathcal {N}| ,\, l=0,\,1,\ldots ,\,N_{\mathrm {p}}-1 \nonumber \\ \end{aligned}$$
(18.29)

where the matrices \(\mathbf {S}_{\mathbf {x}_i}(k+l)\), \(\mathbf {S}_{\mathbf {u}_i}(k+l)\), \(\mathbf {A}_{ij}(k+l)\), and the vector \(\mathbf {e}_{0i}(k+l)\) are given by:

$$\begin{aligned}&\displaystyle \mathbf {S}_{\mathbf {x}_i}(k+l) = \nabla _{\mathbf {x}_i} \mathbf {f}_i(\mathbf {x}_i^0(k+l),\mathbf {u}_i^0(k+l))&\end{aligned}$$
(18.30)
$$\begin{aligned}&\displaystyle \mathbf {S}_{\mathbf {u}_i}(k+l) = \nabla _{\mathbf {u}_i} \mathbf {f}_i(\mathbf {x}_i^0(k+l),\mathbf {u}_i^0(k+l))&\end{aligned}$$
(18.31)
$$\begin{aligned}&\displaystyle \mathbf {A}_{ij}(k+l) = \nabla _{\mathbf {x}_j} \mathbf {h}_{ij}(\mathbf {x}_j^0(k+l)) ,\, j=1,\,2,\ldots ,\,|\mathcal {N}| ,\, j \ne i \end{aligned}$$
(18.32)
$$\begin{aligned}&\displaystyle \mathbf {e}_{0i}(k+l) = \mathbf {f}_i(\mathbf {x}_i^0(k+l),\mathbf {u}_i^0(k+l)) + \sum _{j=1,\, j \ne i}^{|\mathcal {N}|} \mathbf {h}_{ij}(\mathbf {x}_j^0(k+l)) - \mathbf {S}_{\mathbf {x}_i}(k+l) \mathbf {x}_i^0(k+l)&\nonumber \\&\qquad \qquad \displaystyle -\;\mathbf {S}_{\mathbf {u}_i}(k+l) \mathbf {u}_i^0(k+l) - \sum _{j=1,\,j \ne i}^{|\mathcal {N}|} \mathbf {A}_{ij}(k+l) \mathbf {x}_j^0(k+l)&\end{aligned}$$
(18.33)

Then similar to (18.18), the following decoupled linear state equations are formulated:

$$\begin{aligned} \mathbf {x}_i(k+l+1)&= \mathbf {S}_{\mathbf {x}_i}(k+l) \mathbf {x}_i(k+l) + \mathbf {S}_{\mathbf {u}_i}(k+l) \mathbf {u}_i(k+l) + \mathbf {w}_i(k+l) + \mathbf {e}_{0i}(k+l) \nonumber \\ i&=1,\ldots ,\,|\mathcal {N}| ,\, l=0,\,1,\ldots ,\,N_{\mathrm {p}}-1 \end{aligned}$$
(18.34)

with the additional constraints that:

$$\begin{aligned} \mathbf {w}_i(k+l) = \sum _{j=1,\,j \ne i}^{|\mathcal {N}|} \mathbf {A}_{ij}(k+l) \mathbf {x}_j(k+l) ,\quad i=1,\ldots ,\,|\mathcal {N}| \end{aligned}$$
(18.35)

Then, the NLP sub-problems P3\(^i\) are approximated with the QP sub-problems:

Problem P4 \(^\mathbf{i }\) (ith QP Sub-problem):

$$\begin{aligned} J_i^*(\mathbf {p}(k:k+N_{\mathrm {p}}),\mathbf {x}_i) = \mathop {\min } \limits _{\begin{array}{l} {\mathbf {u}_i(k:k+N_{\mathrm {p}})} \\ {\mathbf {x}_i(k:k+N_{\mathrm {p}})} \\ {\mathbf {w}_i(k:k+N_{\mathrm {p}})} \end{array}} \sum _{l=0}^{N_{\mathrm {p}}} s_{\mathrm {QP},i}^p(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l),\mathbf {w}_i(k+l),\mathbf {p}(k:k+N_{\mathrm {p}})) \end{aligned}$$
(18.36)

subject to \(\mathbf {x}_i(k)=\mathbf {x}_i\), (18.25), (18.26), and:

$$\begin{aligned} \mathbf {x}_i(k+l+1)&= \mathbf {S}_{\mathbf {x}_i}(k+l) \mathbf {x}_i(k+l) + \mathbf {S}_{\mathbf {u}_i}(k+l) \mathbf {u}_i(k+l) + \mathbf {w}_i(k+l) + \mathbf {e}_{0i}(k+l) \nonumber \\ l&=0,\,1,\ldots ,\,N_{\mathrm {p}}-1 \end{aligned}$$
(18.37)

In (18.36), the function \(s_{\mathrm {QP},i}^p\) is given by:

$$\begin{aligned}&s_{\mathrm {QP},i}^p(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l),\mathbf {w}_i(k+l),\mathbf {p}(k:k+N_{\mathrm {p}})) = s_i(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l)) \nonumber \\&\quad + \mathbf {p}_i(k+l)^\mathrm{{T}} \mathbf {w}_i(k+l) - \mathbf {x}_i(k+l)^\mathrm{{T}} \sum _{j=1,\,j \ne i}^{|\mathcal {N}|} \mathbf {A}_{ji}(k+l)^\mathrm{{T}} \mathbf {p}_j(k+l) \end{aligned}$$
(18.38)

Denote with \(\mathbf {u}_i^*(k:k+N_{\mathrm {p}})\), \(\mathbf {x}_i^*(k:k+N_{\mathrm {p}})\) and \(\mathbf {w}_i^*(k:k+N_{\mathrm {p}})\) the optimal solution of P4\(^i\). The following centralized quasi-NMPC problem with quadratic cost and linear constraints is formulated:

Problem P5 (Centralized Quasi-NMPC):

$$\begin{aligned} J^*(\mathbf {x}) = \mathop {\min } \limits _{\mathbf {u}(k:k+N_{\mathrm {p}})} \, J(\mathbf {u}(k:k+N_{\mathrm {p}}),\mathbf {x}) \end{aligned}$$
(18.39)

subject to \(\mathbf {x}(k)=\mathbf {x}\), constraints (18.12), (18.13), and (18.29).

The cost function \(J(\mathbf {u}(k:k+N_{\mathrm {p}}),\mathbf {x})\) is given by (18.17).

Then, the distributed quasi-NMPC problem is as follows:

Problem P6 (Distributed Quasi-NMPC):

$$\begin{aligned} \mathop {\max } \limits _{\mathbf {p}(k:k+N_{\mathrm {p}})} \sum _{i=1}^{|\mathcal {N}|} J_i^*(\mathbf {p}(k:k+N_{\mathrm {p}}),\mathbf {x}_i) = \end{aligned}$$
(18.40)
$$\begin{aligned} \mathop {\max } \limits _{\mathbf {p}(k:k+N_{\mathrm {p}})} \sum _{i=1}^{|\mathcal {N}|} \mathop {\min } \limits _{\begin{array}{c} {\mathbf {u}_i(k:k+N_{\mathrm {p}})} \\ {\mathbf {x}_i(k:k+N_{\mathrm {p}})} \\ {\mathbf {w}_i(k:k+N_{\mathrm {p}})} \end{array}} \sum _{l=0}^{N_{\mathrm {p}}} s_{\mathrm {QP},i}^p(\mathbf {x}_i(k+l),\mathbf {u}_i(k+l),\mathbf {w}_i(k+l),\mathbf {p}(k:k+N_{\mathrm {p}})) \end{aligned}$$
(18.41)

subject to \(\mathbf {x}(k)=\mathbf {x}\), constraints (18.12), (18.13), (18.34), and:

$$\begin{aligned} \mathbf {p}(k+N_{\mathrm {p}}) = 0 \end{aligned}$$
(18.42)

Then, the decomposition of the optimization problem P5 is given by the following proposition:

Proposition 18.1

Suppose that \(\mathbf {x}=[\mathbf {x}_1,\,\mathbf {x}_2,\ldots ,\,\mathbf {x}_{|\mathcal {N}|}]\) is a feasible point for problem P5. Then:

$$\begin{aligned} J^*(\mathbf {x}) = \mathop {\max } \limits _{\mathbf {p}(k:k+N_{\mathrm {p}})} \sum _{i=1}^{|\mathcal {N}|} J_i^*(\mathbf {p}(k:k+N_{\mathrm {p}}),\mathbf {x}_i) \end{aligned}$$
(18.43)

where maximization is subject to \(\mathbf {p}(k+N_{\mathrm {p}})=0\).

The proof follows similar arguments as in [7, 9] and the fact that the Slater’s condition always holds for a feasible convex QP [1, pp. 226–227].

Proposition 18.1 shows that the computation of \(\mathbf {u}_i^*(k:k+N_{\mathrm {p}})\), \(\mathbf {x}_i^*(k:k+N_{\mathrm {p}})\) and \(\mathbf {w}_i^*(k:k+N_{\mathrm {p}})\) for given prices \(\mathbf {p}(k:k+N_{\mathrm {p}})\) is completely decentralized. However, finding the optimal prices requires coordination [7]. Given a price prediction sequence \(\mathbf {p}_i^r(k:k+N_{\mathrm {p}})\) for the \(r\)-th iteration, the corresponding sequences \(\mathbf {u}_i^{*r}(k:k+N_{\mathrm {p}})\), \(\mathbf {x}_i^{*r}(k:k+N_{\mathrm {p}})\) and \(\mathbf {w}_i^{*r}(k:k+N_{\mathrm {p}})\) are computed locally by solving P4\(^i\). Then, the prices are updated distributedly by a gradient step:

$$\begin{aligned}&\mathbf {p}_i^{r+1}(k+l) = \mathbf {p}_i^r(k+l) + \gamma _i^r [\mathbf {w}_i^{*r}(k+l) - \sum _{j=1,\,j \ne i}^{|\mathcal {N}|} \mathbf {A}_{ij}(k+l) \mathbf {x}_j^{*r}(k+l)] \nonumber \\&\quad l=0,\,1,\ldots ,\,N_{\mathrm {p}}-1 \,\,\, \text {with} \,\,\, \mathbf {p}_i^{r+1}(k+N_{\mathrm {p}}) = \mathbf {p}_i^r(k+N_{\mathrm {p}}) = 0 \end{aligned}$$
(18.44)

where \(\gamma _i^r\) is the step size. In a neighborhood of the solution \(\mathbf {u}_i^0\), \(\mathbf {x}_i^0\), \(\mathbf {v}_i^0\) to the NLP sub-problems P3\(^i\), \(i=1,\ldots ,\,|\mathcal {N}|\), the linearized model (18.29) can sufficiently accurately approximate the nonlinear model (18.1). Therefore, to approximate the NMPC solution it would be necessary to periodically update the linearized model (18.29) and to apply formula (18.44) for a number of steps. This is done by a slight modification of the suboptimal algorithm for distributed quasi-NMPC in [9].

3.3 An Algorithm for Distributed Quasi-NMPC

In [7], an approach to distributed MPC for linear systems has been suggested, where the prices are updated according to (18.44). In [9], a suboptimal algorithm for distributed quasi-NMPC for nonlinear systems with linear couplings has been proposed. Here, the algorithm in [9] is slightly modified to consider a more general class of systems consisting of nonlinear subsystems with separable nonlinear couplings (see Sect. 18.2). The algorithm includes two loops. In the outer loop, the NLP sub-problems P3\(^i\), \(i=1,\,2,\ldots ,\,|\mathcal {N}|\), are solved and the matrices of the linearized model are computed, which are used in the approximating QP sub-problems P4\(^i\), \(i=1,\,2,\ldots ,\,|\mathcal {N}|\). Then, in the inner loop, the price sequences and solution are updated based on Proposition 18.1 and applying formula (18.44) for a given number of steps. The algorithm is presented as Algorithm 18.1.

figure a

The steps 4 to 11 in Algorithm 18.1 include an iterative solution of the NLP sub-problems P3\(^i\), approximating them with the QP sub-problems P4\(^i\), and then updating the prices by utilizing Proposition 18.1.

It should be noted that alternatively, an approach similar to [13, 16] can be applied, where the idea would be to avoid solving the NLP sub-problems P3\(^i\) in step 4 and to formulate the approximating QP sub-problems P4\(^i\) by using the optimal sequences \(\mathbf {u}_i^*(k:k+N_{\mathrm {p}})\), \(\mathbf {x}_i^*(k:k+N_{\mathrm {p}})\) and \(\mathbf {w}_i^*(k:k+N_{\mathrm {p}})\), computed in the previous time instant.

Fig. 18.2
figure 2

The communication between the distributed MPC controllers

Full size image

The communication between the distributed MPC controllers is illustrated in Fig. 18.2 for three subsystems (only the inner loop in Algorithm 18.1 is depicted). The solution of the QP sub-problems P4\(^i\) and the update of prices is distributed, but requires for the neighboring subsystems to communicate their price sequences and optimal state trajectories.

4 Theoretical Results

The dynamic dual decomposition approach is applied for the first time to distributed MPC in [7], where a system composed by the interconnection of a set of linear subsystems \(\mathcal {N}=\{S_1,\,S_2,\ldots ,\,S_{|\mathcal {N}|}\}\) is considered. The interconnected subsystems are described by the following linear discrete-time models:

$$\begin{aligned} \mathbf {x}_i(k+1) = \sum _{j=1}^{|\mathcal {N}|} \mathbf {A}_{ij} \mathbf {x}_j(k) + \mathbf {B}_i \mathbf {u}_i(k),\, i=1,\,2,\ldots ,\,|\mathcal {N}| \end{aligned}$$
(18.45)

where \(\mathbf {x}_i(k) \in \mathbb {R}^{n_{x_i}}\) and \(\mathbf {u}_i(k) \in \mathbb {R}^{n_{u_i}}\) are the state and control input vectors, related to the \(i\)th subsystem, and \(\mathbf {A}_{ij} \in \mathbb {R}^{n_{x_i} \times n_{x_j}}\) and \(\mathbf {B}_i \in \mathbb {R}^{n_{x_i} \times n_{u_i}}\) are constant matrices.

For the system (18.45), the infinite horizon optimal control problem P0 is considered, where the nonlinear equality constraints (18.1) are replaced by the linear equality constraints (18.45). The problem P0 is approximated with a linear centralized MPC problem P1, where the nonlinear constraints (18.14) are replaced by linear ones, associated to the model (18.45).

In [7], a suboptimal algorithm for distributed linear MPC is developed, which includes an iterative solution of the QP sub-problems for the linear subsystems and updating the price sequences (illustrated in Fig. 18.2). Further in [7], a stopping criterion for the iterative distributed MPC scheme is proposed that can be locally verified at each subsystem and that guarantees closed loop suboptimality above a pre-specified level \(\alpha \in (0,\,1)\) and asymptotic stability of the overall linear system. With this criterion, at each time instant the minimal number of iterations is obtained such that the following holds (cf. Theorem 4 in [7]):

$$\begin{aligned} \alpha J_{\mathrm {MPC}}^\infty (\bar{\mathbf {x}}) \le J^\infty (\bar{\mathbf {x}}) \,\,\, \text {and} \,\,\, \Vert \mathbf {x}(k)\Vert ^2 \rightarrow 0 \,\,\, \text {as} \,\,\, k \rightarrow \infty \end{aligned}$$
(18.46)

where \(\bar{\mathbf {x}}\) is the initial state of the overall system (18.45), \(\mathbf {x}(k)\) is the response of the system (18.45) in closed-loop with the distributed MPC law, \(J_{\mathrm {MPC}}^\infty (\bar{\mathbf {x}})\) is the cost associated to infinite horizon performance of the distributed MPC law, and \(J^\infty (\bar{\mathbf {x}})\) is the cost obtained by solving the infinite horizon optimal control problem P0 for the system (18.45).

It is shown in [10] that under certain assumptions the infinite horizon cost, associated with the suboptimal distributed quasi-NMPC control (designed by applying the approach in Sect. 18.3) in closed-loop with the nonlinear system (18.1), is bounded and an estimate of the degree of suboptimality is derived.

The relation of the distributed quasi-NMPC approach [9, 10] to other distributed MPC approaches and their comparison is a subject of a future research.

5 Application Results

In [7], the performance of the developed distributed MPC approach for linear interconnected systems is evaluated by applying it to a simulation example with equally sized water containers, connected in series.

In [8], the distributed linear MPC approach is applied to the MPC-based path planning for a UAV (Unmanned Aerial Vehicles) communication chain under radio path loss constraints. The centralized path planning optimization problem with linear model of the UAVs and coupled inequality constraints is reformulated into an equivalent distributed path planning optimization problem, where the resulting QP sub-problems are completely decoupled. The MPC-based optimization sub-problems are computed autonomously within each UAV, using convex quadratic programming and gradient iterations, with the requirement that each UAV communicates its current measured position and the computed optimal velocity trajectory to its neighboring UAVs.

In [9], the distributed quasi-NMPC approach is applied to a system composed by two nonlinear subsystems with linear couplings in the presence of state and input constraints and bounded disturbances.

Here, the distributed quasi-NMPC approach described in Sect. 18.3 is applied to a system consisting of two nonlinear subsystems with nonlinear couplings. The two subsystems \(S_1\) and \(S_2\) are described by:

$$\begin{aligned}&S_1 : x_1(k+1) = \sqrt{3 x_1(k)^2 + 1} + u_1(k) - 1 + \mu _1 x_2^3(k) \end{aligned}$$
(18.47)
$$\begin{aligned}&S_2 : x_2(k+1) = e^{-\sin (x_2(k))} + u_2(k) - 1 + \mu _2 x_1^3(k) \end{aligned}$$
(18.48)

The functions \(f_1\), \(f_2\), \(h_{12}\), \(h_{21}\) in the description (18.1) with the assumption A3 are:

$$\begin{aligned}&f_1(x_1(k),u_1(k)) = \sqrt{3 x_1(k)^2 + 1} + u_1(k) - 1 \end{aligned}$$
(18.49)
$$\begin{aligned}&f_2(x_2(k),u_2(k)) = e^{-\sin (x_2(k))} + u_2(k) - 1 \end{aligned}$$
(18.50)
$$\begin{aligned}&h_{12}(x_2(k)) = \mu _1 x_2^3(k) \,,\,\,\, h_{21}(x_1(k)) = \mu _2 x_1^3(k) \end{aligned}$$
(18.51)

The functions \(h_{12}\) and \(h_{21}\) describe the mutual influence of the two subsystems. The following constraints are imposed on the system (18.47)–(18.48):

$$\begin{aligned}&-0.3 \le u_i(k) \le 0.5 \,,\,\, i=1,\,2 \end{aligned}$$
(18.52)
$$\begin{aligned}&-2 \le x_1(k) \le 2 \,,\,\,\, -1.5 \le x_2(k) \le 1.5 \end{aligned}$$
(18.53)

The coefficients related to the couplings between the two subsystems are \(\mu _1=\mu _2=0.2\). The prediction horizon in the centralized NMPC problem P1 is \(N_{\mathrm {p}}=10\) and the weighting matrices are \(Q_i=R_i=1\), \(i=1,\,2\).

Fig. 18.3
figure 3

The control inputs \(u_1\) and \(u_2\) for subsystems \(S_1\) and \(S_2\)

Full size image
Fig. 18.4
figure 4

The states \(x_1\) and \(x_2\) of subsystems \(S_1\) and \(S_2\)

Full size image

The centralized NMPC problem is represented as a distributed NMPC problem (problem P6) by applying the dual decomposition approach. Then, Algorithm 18.1 with parameters \(Q=5\), \(L=3\), \(\gamma _i=0.3,\,i=1,\,2\) is used to generate the two control inputs for an initial state \(x(0)=[1.2\,\,\,1.2]\). The corresponding trajectories of the control inputs \(u_1,\,u_2\) and the states \(x_1,\,x_2\), associated to the two subsystems are depicted in Figs. 18.3 and 18.4. The trajectories obtained with the following approaches are compared:

  • The suboptimal distributed quasi-NMPC approach with linearization (described in Sect. 18.3);

  • A suboptimal distributed NMPC approach without linearization. In this case, a modification of Algorithm 18.1 is used for the on-line computation of the control inputs. It has only one loop, where the optimal solutions of the NLP sub-problems P3\(^i\), \(i=1,\,2,\ldots ,\,|\mathcal {N}|\) are computed distributedly, and then the price sequences are updated by applying (18.44) by using the computed optimal solutions. The loop is repeated \(Q=5\) times and the step size in (18.44) is \(\gamma _i=0.3,\,i=1,\,2\).

  • The centralized NMPC approach, which solves problem P1 at each time instant.

6 Conclusions

In this chapter, the distributed quasi-NMPC approach is described in details and an algorithm based on on-line optimization is presented. The theoretical and the application results associated to both linear and nonlinear interconnected systems are reviewed. The relation of the suggested distributed NMPC approach to other distributed approaches is a subject of a future research.