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 and Motivations

In the past decades a number of popular methods have been developed for control of a multi-input and multi-output system \(\mathcal{S}^{o}\), including optimal LQ control theory, pole-placement methods, \(\mathcal{H}_{2}/\mathcal{H}_{\infty }\) control, and Model Predictive Control (MPC). These methods are intrinsically of centralized nature, i.e. the vector of control actions u is computed based on the knowledge of the whole state x or output y vectors. This allows to guarantee properties, in terms of stability, robustness, and performance. However, these methods display many limitations in case of large-scale [1] or complex [2] systems, i.e., systems with a large size, often characterized by the cooperation of many different parts (e.g., machines, reactors, robots, transportation systems), and possibly by uncertainties on the system components. Just to mention the main issues:

  • the actuators and the transducers may be highly geographically distributed, and this may bring about transmission delays or failure issues.

  • The control problem grows in size with the dimensionality of the system, and the related computational burden may, in turn, grow significantly. This is particularly true for methods, like MPC, where an optimization problem must be solved at any new sampling time. In turn, these scalability issues may induce large - and even inadmissible - computational delays, with serious limitations on the size of practically tractable problems.

  • Single components or subsystems can be subject to structural changes, failures, and some may be removed, added, or replaced. Centralized control systems are normally non-robust and non-flexible with respect to such occurrences. This issue may have a big economic impact, since a new design and implementation phase for the overall control system must be carried out, with significant expenses, e.g., due to the required downtime.

All the above reasons motivate the development of new methods for the design of more flexible control structures where the centralized controller is replaced by a set of M local regulators, possibly coordinated to recover to the maximum extent the performance guaranteed by a centralized solution. According to a terminology nowadays well accepted, we will define decentralized control structures those where the local regulators are fed by independent subsets of states and/or outputs and do not communicate with each other. As a middle-ground solution between centralized and decentralized control, we will denote by distributed control structures the schemes where the M local regulators are fed by not necessarily independent subsets of states and/or outputs and can exchange information to coordinate their actions. A pictorial representation of centralized, decentralized, and distributed control structures in the case M = 2 is reported in Figure 1.

Fig. 1
figure 1

Centralized (top panel), decentralized (bottom left panel), and distributed (bottom right panel) control structures.

Full size image

The possibility to coordinate and negotiate the local control actions provided by distributed schemes and made possible thanks to suitable transmission networks fits very well with an optimization-based framework, where many ideas of game theory can be applied. Therefore, MPC is probably the best advanced control approach for the synthesis of distributed control algorithms and for this reason the aim of this chapter is to present in plain form the main ideas underlying some of the most popular Distributed MPC (DMPC) algorithms. Since nowadays many survey papers and books are dedicated to DMPC, this chapter is not aimed to provide an extensive review of all the available DMPC algorithms, for which the reader is referred to [3, 4], but rather to highlight the main features, properties, and requirements of the major classes of DMPC methods. With the goal to simplify the presentation some restrictive choices will be made: (i) the theoretical properties of the considered methods will not be examined in detail, and the reader will be referred to the relevant literature; (ii) purely regulation problems will be considered; (iii) the system \(\mathcal{S}^{o}\) to be controlled will be assumed to be described by a linear time-invariant discrete-time model. Some of these assumptions will be re-examined in the final section of the chapter.

2 Model and Control Problem Decomposition

As it is claimed in [1], “if such (large-scale) systems must be controlled,(…) they necessitate new ideas for decomposing and dividing the analysis and control problems of the overall system into rather independent subproblems.” Under this viewpoint the decomposition of the dynamic large-scale system model and of the control problem is a preliminary - but key - step for the development of well-posed decentralized and distributed control procedures. In particular, it is definitely worth noting that the adopted model decomposition has a strong impact on the features, properties, and requirements of the control scheme which is designed based on it.

2.1 Model Decomposition

We assume that the large-scale system \(\mathcal{S}^{o}\) is described by the following linear, discrete-time model

$$\displaystyle{ \begin{array}{lcl} \mathbf{x}^{o}(k + 1)& =&\mathbf{A}^{o}\mathbf{x}^{o}(k) + \mathbf{B}^{o}\mathbf{u}(k) \\ \mathbf{y}(k) & =&\mathbf{C}^{o}\mathbf{x}^{o}(k)\end{array} }$$
(1)

where x o ∈ R n, u ∈ R m, y ∈ R p and, unless otherwise specified, the state x o will be assumed to be measurable. The state, output, and/or input variables must satisfy constraints of the general type

$$\displaystyle{ \mathbf{x}^{o} \in \mathcal{ X}^{o}\quad,\quad \mathbf{y} \in \mathcal{ Y }\quad,\quad \mathbf{u} \in \mathcal{ U} }$$
(2)

where \(\mathcal{X}^{o}\), \(\mathcal{Y }\), and \(\mathcal{U}\) are closed sets of proper dimensions containing the origin.

In order to design M decentralized or distributed MPC regulators guaranteeing the stability of the origin of the corresponding closed-loop system, the centralized model (1) must be decomposed into M small scale models \(\mathcal{S}_{i}\), also denoted model partitions. The first problem is that of partitioning the input and output vectors u and y, i.e., to identify, for each subsystem \(\mathcal{S}_{i}\), a local input vector \(u_{i} \in R^{m_{i}}\) and a local output vector \(y_{i} \in R^{p_{i}}\) (commonly, it must hold that ∑ i = 1 M m i = m and that ∑ i = 1 M p i = p). Indeed, a local input/output pair (u i(k), y i(k)) (also denoted channel) must be attributed to each subsystem on the basis of a specific partitioning criterion. Often this is based on physical insight; as an alternative, many methods have been developed and can be adopted to unveil the interactions of MIMO systems. Some of them are based on the analysis of the static and dynamic interactions among inputs and outputs see, e.g., [5, 6].The state-space model, for each subsystem \(\mathcal{S}_{i}\), is of the following general type.

$$\displaystyle{ \begin{array}{lcl} x_{i}(k + 1)& =&A_{ii}x_{i}(k) + B_{ii}u_{i}(k) +\sum _{j\neq i}(A_{ij}x_{j}(k) + B_{ij}u_{j}(k)) \\ y_{i}(k) & =&C_{ii}x_{i}(k) +\sum _{j\neq i}C_{ij}x_{j}(k) \end{array} }$$
(3)

where i = 1, …, M, \(x_{i} \in R^{n_{i}}\). Many different methods can be used to obtain the models \(\mathcal{S}_{i}\) from \(\mathcal{S}^{o}\), each corresponding to a different model partition and to a different corresponding interconnection graph. A very rough classification can be made between non-overlapping and overlapping decompositions: in non-overlapping decompositions the aggregate state of the \(\mathcal{S}_{i}\) model is still of order n, that is the one of the original system \(\mathcal{S}^{o}\). On the contrary, in overlapping decompositions the overall state of the ensemble of models \(\mathcal{S}_{i}\) is greater than the one of \(\mathcal{S}^{o}\), i.e. ∑ i = 1 M n i > n. The characteristics of these two classes will be briefly analyzed in Sections 2.1.1 and 2.1.2.

A critical point regards which constraints should be enforced on the state, output, and/or input variables of \(\mathcal{S}_{i}\), i = 1, …, M, to verify the centralized system constraints (2). Note that constraints involving the variables of more than one subsystems (the so-called coupling constraints) may be present, and even they may lie at the core of specific types of distributed and coordination control problems. For instance, when subsystems share a common, but limited, input resource some constraints of the type \(\sum _{i=1}^{M}u_{i} \in \bar{\mathcal{ U}}\) (for a suitably defined \(\bar{\mathcal{U}}\)) may be enforced. On the other hand, a number of power generation devices may be asked to produce a common, but bounded, output, leading to constraints of the type \(\sum _{i=1}^{M}y_{i} \in \bar{\mathcal{ Y }}\). Another similar example is the case of coordination of moving robots, where collision avoidance constraints are enforced: assuming that the robot - or the robot joints - positions are included in the outputs y i and that two robots (i.e., \(\mathcal{S}_{1}\) and \(\mathcal{S}_{2}\)) are involved, these constraints may be formulated as \((y_{1},y_{2}) \in \mathcal{ Y }_{12}\), for a suitably-defined set \(\mathcal{Y }_{12}\). In some cases coupling constraints can be verified by enforcing a number of local constraints at the same time, e.g., when \(u_{i} \in \mathcal{ U}_{i}\) for all i = 1, …, M involves \(\sum _{i=1}^{M}u_{i} \in \bar{\mathcal{ U}}\). However, this solution may be overly conservative and highly suboptimal in many contexts and should be discarded, at the price of including coupling (also said complicating) constraints in the - distributed - control problem formulation. Summing up, from now on we assume that constraints (2) allow to formulate two types of constraints on the model partition variables: local constraints, to be enforced for all i = 1, …, M

$$\displaystyle{ x_{i} \in \mathcal{ X}_{i}\quad,\quad y_{i} \in \mathcal{ Y }_{i}\quad,\quad u_{i} \in \mathcal{ U}_{i} }$$
(4)

and/or coupling constraints, which will be represented as follows for simplicity

$$\displaystyle{ (x_{1},\ldots,x_{M}) \in \mathcal{ X}_{C}\quad,\quad (y_{1},\ldots,y_{M}) \in \mathcal{ Y }_{C}\quad,\quad (u_{1},\ldots,u_{M}) \in \mathcal{ U}_{C} }$$
(5)

Note, in passing, that there may not be a trivial/direct correspondence between the state variable x i of \(\mathcal{S}_{i}\), i = 1, …, M and the state x o of \(\mathcal{S}^{o}\). Therefore, especially - but not only - when overlapping decompositions are used, it may be critical and/or ambiguous to translate the constraint \(\mathbf{x}^{o} \in \mathcal{ X}^{o}\) into a number constraints on the local state variables x i.Subclasses of the representation (3) are called input-decoupled when B ij = 0 for all i and j ≠ i or state-decoupled when A ij = 0 for all i and j ≠ i. In a wide class of control problems, for instance the coordination of independent vehicles with coupling constraints, the subsystems are dynamically decoupled, with A ij = 0, B ij = 0, C ij = 0 for all i and j ≠ i, but coupled through the state or control constraints (5).

Some final comments are in order. First, the model (1) is often computed as the discretization of a continuous time physical system made by the interconnection of subsystems. In this case, the corresponding matrices have a sparse structure which should be maintained after discretization. Unfortunately, if a Zero Order Hold transformation is used, this property is lost. To recover it, one should resort to the forward Euler (fE) discretization approach or to the approximate discretization method described in [7], specifically developed for distributed control.Secondly, models of type (3) include the information on how subsystems have influence on each other. In other words, if (for j ≠ i) A ij ≠ 0 and/or B ij ≠ 0, the state/input variables of subsystem \(\mathcal{S}_{j}\) directly impact on the dynamics of subsystem \(\mathcal{S}_{i}\). Consistently, we can define the set of neighbors (or parents) of subsystem \(\mathcal{S}_{i}\) as \(\mathcal{N}_{i}:=\{ j:\| A_{ij}\| +\| B_{ij}\|\neq 0\|\}\) and a corresponding direct interconnection graph, which highlights the system-wide dependencies between subsystems. Similar interconnection (possibly undirected) graphs can be drawn when coupling constraints are present, i.e., if a coupling constraint involves a set of subsystems, they should be considered as neighbors.

2.1.1 Non-overlapping Decompositions

Perhaps the most natural choice to decompose \(\mathcal{S}^{o}\) is to partition the state x into M non-overlapping sub-vectors x i with ∑ i = 1 M n i = n, so that, up to a suitable state variable permutation, x o = (x 1, …, x M) and that the original system can be written as

$$\displaystyle{ \begin{array}{lcl} \left [\begin{array}{*{10}c} x_{1}(k + 1)\\ \vdots \\ x_{M}(k + 1) \end{array} \right ]& =&\left [\begin{array}{*{10}c} A_{11} &\ldots & A_{1M}\\ \vdots &\ddots & \vdots \\ A_{M1}&\ldots &A_{MM} \end{array} \right ]\left [\begin{array}{*{10}c} x_{1}(k)\\ \vdots \\ x_{M}(k) \end{array} \right ] + \left [\begin{array}{*{10}c} B_{11} &\ldots & B_{M1}\\ \vdots &\ddots & \vdots \\ B_{M1}&\ldots &B_{MM} \end{array} \right ]\left [\begin{array}{*{10}c} u_{1}(k)\\ \vdots \\ u_{M}(k) \end{array} \right ]\\ \\ \left [\begin{array}{*{10}c} y_{1}(k)\\ \vdots \\ y_{M}(k) \end{array} \right ]& =&\left [\begin{array}{*{10}c} C_{11} &\ldots & C_{1M}\\ \vdots &\ddots & \vdots \\ C_{M1}&\ldots &C_{MM} \end{array} \right ]\left [\begin{array}{*{10}c} x_{1}(k)\\ \vdots \\ x_{M}(k) \end{array} \right ] \end{array} }$$

It is intuitive that in the definition of the submodels (3) one should partition the original state so that the couplings among the subsystems are reduced as much as possible, i.e. A ij, B ij, C ij, i ≠ j should be null or “small” (according to a proper norm or criterion) to the maximum possible extent. In the common practice, the state permutation/partition can be carried out based on the plant physical insight or based on available algebraic algorithms. For example, there exist graph-based methods for reordering the state, input, and output variables in order to highlight inherent structures, e.g., the presence of weakly interacting subsystems (see, e.g., the ε-nested decomposition proposed in [2]) or cascaded configurations (e.g., the lower-block-triangular LBT decomposition discussed in [2]). Finally, methods have been proposed in the literature [2] for devising suitable changes of coordinates which lead to specific system decompositions (e.g., the input and/or output decentralized forms), at the price of a loss of physical insight.

2.1.2 Overlapping Decompositions

In some cases the coupling strength between different subsystems is relevant, which prevents the decomposition into disjoint subsystems to result into an effective control-oriented partition. An alternative to non-overlapping decompositions is to decompose the systems into subsystems which have some equations (and states) in common, i.e., carrying out a so-called overlapping decomposition. This may result in obtaining overlapping but weakly coupled subsystems. Overlapping decompositions have been widely studied in the past, mainly in the context of decentralized control, see, e.g., [2].In the context of DMPC, a number of distributed control methods require the subsystem interconnections to be represented in the following state-decoupled form

$$\displaystyle{ \left \{\begin{array}{lcl} x_{i}(k + 1)& =&A_{ii}x_{i}(k) +\sum _{ j=1}^{M}B_{ij}u_{j}(k) \\ y_{i}(k) & =&C_{i}x_{i}(k)\end{array} \right. }$$
(6)

However, it is rarely possible to obtain a representation of this type by simply applying a non-overlapping decomposition such as the one described in the previous paragraphs. Therefore, it is possible to adopt a fully overlapping decomposition where each subsystem is of full order. The simplest way to obtain this decomposition consists of replicating M times model (1), that is setting, for all i, j = 1, …, M, A ii = A o, B ij = B j, o, C i = C i, o, where B j, o is the j-th block column of B o, while C j, o is the j-th block row of C o; an alternative procedure is sketched in [8]. In general, overlapping decompositions are non-minimal, since the state dimension does not decrease (for each subsystem) under the application of the proposed partition. However, as better specified in the following, for subsystem \(\mathcal{S}_{i}\), the local control variable is assumed to be u i, while the u j’s, j ≠ i are considered as external signals, so that the number of variables to be optimized by the local DMPC algorithm is smaller than in the corresponding centralized problem.

2.2 Partition Properties and Control

The main properties of the model partitions which have a major impact on the resulting decentralized and distributed MPC-based schemes are the following.

  • Minimality of the state representation. Minimality (in terms of dimension of the state/input/output variables for each subsystem) is required to limit the algorithm computational burden, since the number of involved variables generally directly impacts on the computational demands of the algorithm. Also, minimal representations demand minimal information to be stored by local memory units. This, besides requiring scalable memory load, allows for more flexibility of the resulting control systems. In fact, local model variations at subsystem level may require the re-design of local control systems only.

  • Minimality of the interconnection graph. As discussed, to reduce the probability of network-induced issues (e.g., transmission delays, channel overloads, and package losses) the communication burden required by the adopted control architecture must be reduced as much as possible. To this end, one should reduce both (i) the number of communication links between subsystems (i.e., aiming to have a sparse supporting information transmission network), and (ii) the amount of communication that they should afford. While (ii) mostly depends on the type of the adopted control scheme (we defer the reader to Section 4 for a discussion on this point), (i) may strongly depend upon the approach taken for model partitioning, since the implementation of distributed schemes commonly requires to be supported by an underlying communication graph consistent with the subsystem interconnection graph.

  • Descriptive capabilities of the models. Model partitioning may have a negative effect on the descriptive capabilities of the submodels. It would be desirable, in fact, that each local controller has the knowledge on how a control action, taken locally, can impact, not only on the local variables, but also on the variables of the surrounding subsystems. Similarly, a complete information on how the control action taken by other subsystems affects local state variables and outputs may be desired.

It is worth noting that the first and the second requirements are in general conflicting with the third one. Indeed, fully descriptive models, which are the ones that allow for full cooperation between local controllers, are often obtained using overlapping - often fully overlapping - partitions, which are the ones which typically lead to a non-minimal state representation and for which the interconnection graph is maximal.

2.3 MPC Problem Separability

To briefly introduce the optimization problems involved in the decentralized and distributed implementations summarized in this chapter, we first introduce the centralized (non-minimal) model which can be drawn by collecting together all the partitions (3). We define x = (x 1, …, x M), which corresponds to x o, up to a state permutation, only in case of non-overlapping decompositions. Consistently, we can describe the overall large-scale system dynamics with a model of the type

$$\displaystyle{ \begin{array}{lcl} \mathbf{x}(k + 1)& =&\mathbf{A}\mathbf{x}(k) + \mathbf{B}\mathbf{u}(k) \\ \mathbf{y}(k) & =&\mathbf{C}\mathbf{x}(k) \end{array} }$$
(7)

Note that system (7) is nothing else than an expansion [2] of the corresponding contracted system (1), since their output free and forced motions must be indeed equal to each other. Starting with standard centralized MPC, the control action at each time instant k is obtained by solving a control problem of type

$$\displaystyle{ \min _{\begin{array}{c}\mathbf{u}(k),\ldots,\mathbf{u}(k+N-1)\end{array}}J(k) }$$
(8a)

subject to the transient constraints (7), (4), (5), for times k, …, k + N − 1, and a terminal constraint of the type

$$\displaystyle{ \mathbf{x}(k + N) \in \mathcal{ X}_{f} }$$
(8b)

In (8a), J(k) is the cost function, while \(\mathcal{X}_{f}\) in (8b) is the terminal constraint set. As a common ground of the methods discussed in this chapter, problem (8) is required to be separable into a number of subproblems to be solved by local computing units. This first requires that the cost function to be minimized is formally separable, i.e.,

$$\displaystyle{ J(k) =\sum _{ i=1}^{M}\rho _{ i}J_{i}(k) }$$
(9)

where J i(k) is a positive-definite (quadratic, for simplicity) function of local input and state variables of subsystem \(\mathcal{S}_{i}\)

$$\displaystyle{ J_{i}(k) =\sum _{ j=0}^{N-1}[\|x_{ i}(k + j)\|_{Q_{i}}^{2} +\| u_{ i}(k + j)\|_{R_{i}}^{2}] +\| x_{ i}(k + N)\|_{P_{i}}^{2} }$$
(10)

and parameter ρ i > 0, where ∑ i = 1 M ρ i = 1.Secondly, we need to enforce the terminal constraint (8b) by imposing M local terminal constraints of type \(x_{i}(k + N) \in \mathcal{ X}_{f,i}\), and therefore \(\mathcal{X}_{f}\) must be defined as the Cartesian product of M sets \(\mathcal{X}_{f,i} \subseteq \mathbb{R}^{n_{i}}\).However, separability is not the only requirement for the well-posedness of the problem, but also some assumptions - required for general-type MPC problems [8] - must be fulfilled by the “collective” terminal cost and terminal set, i.e., \(V _{f} =\sum _{ i=1}^{M}\rho _{i}\|x_{i}(k + N)\|_{P_{i}}^{2} =\| \mathbf{x}(k + N)\|_{P}^{2}\), with P = diag(ρ 1 P 1, …, ρ M P M) and \(\mathcal{X}_{f}\), respectively. More specifically V f and \(\mathcal{X}_{f}\) must also be a Lyapunov function and a positively invariant set, respectively, for the expanded system (7), controlled using a suitable (and possibly decentralized/distributed) auxiliary control law. The latter requirements are not easily compatible with the separability assumptions: in the sequel, for each of the described methods, we will discuss how they are guaranteed.

3 Decentralized MPC

A simple paradigmatic decentralized method is the one proposed in [9], for large-scale linear processes subject to local input saturations only. The global model (1), with stable matrix A o, is approximated by a number of (possibly overlapping) subsystems of type (3) with stable matrices A ii, used for local predictions. The key feature of decentralized control is that there is no communication between the different local controllers, as shown in Figure 1. Therefore a modelling error is introduced by neglecting couplings, i.e., by setting A ij = 0 and B ij = 0 for all j ≠ i, i = 1, …, M. The proposed decentralized MPC algorithm requires that, at each time instant k, the following optimization problem is solved by each computational unit.

$$\displaystyle{ \min _{\begin{array}{c}u_{i}(k),\ldots,u_{i}(k+N-1)\end{array}}J_{i}(k) }$$
(11)

subject to the dynamical model

$$\displaystyle{ x_{i}(k + 1) = A_{ii}x_{i}(k) + B_{ii}u_{i}(k) }$$
(12)

and the local input constraints \(u_{i}(k) \in \mathcal{ U}_{i}\), for times k, …, k + N − 1. Here no terminal constraint is required in view of the fact that no state constraints are imposed and that the local system matrices A ii are stable. Indeed, the auxiliary control law is u(k) = 0 and, correspondingly, the separability of the cost function is obtained by selecting P i in such a way that A ii T P i A ii − P i = −Q i. This, if we neglect the interconnections terms A ij with j ≠ i, between subsystems, makes V f (as defined in the previous paragraph) a Lyapunov function for the overall - decentralized - system. The asymptotic stability properties of the control system are proved a posteriori if some inequality conditions are verified. In general, in order to achieve closed-loop stability as well as performance in the development of decentralized MPC algorithms, the interconnections (at least the terms A ij) between different subsystems should be weak or the system should display peculiar structures (e.g., acyclic graphs).

A different approach consists of considering couplings as disturbances. For example, in [10], a decentralized MPC algorithm for nonlinear discrete time systems subject to decaying disturbances was presented. In the design of the decentralized MPC, the effects of interconnections between different subsystems are considered as perturbation terms whose magnitude depends on the norm of the system states. No information is exchanged between the local controllers and the stability of the closed-loop system relies on the inclusion of a contractive constraint in the formulation of each of the decentralized MPC problems. In [11], the stability of a decentralized MPC is analyzed from an input-to-state stability (ISS) point of view. For linear systems this approach consists of rewriting the subsystem \(\mathcal{S}_{i}\) model (3) as

$$\displaystyle{ x_{i}(k + 1) = A_{ii}x_{i}(k) + B_{ii}u_{i}(k) +\nu _{i}(k) }$$
(13)

where ν i(k) = ∑ j ≠ i(A ij x j(k) + B ij u j(k)) is regarded as an unknown, but bounded - if local state and input constraints (4) are enforced - disturbance which must be compensated or rejected using an ad-hoc robust MPC scheme. Along this line, e.g., the algorithm in [12] has been proposed for linear systems, resorting to tube-based MPC (see [13, 14] and Chapter Robust Optimization for MPC). For more details, see also Chapter “Scalable MPC Design”.It is worth remarking that, in all the decentralized schemes described above, no information is required to be transmitted between local regulators, since only the information regarding the local state is used in the corresponding MPC optimization problem (11).

4 Distributed MPC

According to the taxonomy proposed in [3] and nowadays widely used, DMPC algorithms can be broadly classified as follows:

  • iterative or non-iterative: in iterative algorithms information can be transmitted among the local regulators many times within the sampling time. This opens the way to the design of methods aimed at achieving a global consensus among the regulators on the actions to be taken within the sampling interval. On the contrary, in non-iterative algorithms information is transmitted only once in the sampling period, so that the regulators are required to possess some robustness properties to compensate for the reduced information available.

  • cooperating and non-cooperating: in cooperating algorithms each local regulator tries to minimize a global cost function, so that Pareto - i.e., system-wide - optimal solutions can be computed, at least in principle. In non-cooperating algorithms each regulator minimizes its local cost function, with possible conflicting goals; in this case, Nash equilibria are to be expected.

  • fully connected or partially connected: in fully connected algorithms information is transmitted and received from any local regulator to all the others. In partially connected methods the information is exchanged between any local regulator and a subset of the others. Although this is not a structural property, it can strongly influence the properties and the transmission load of the methods as well as their computational burden.

4.1 Cooperating DMPC

As a prototype algorithm for this class of DMPC methods, we make reference to the results reported in [8, 15]. The system to be controlled is assumed to be in the state decoupled form (6): this implies that the transition matrix of the expanded system (7) is block-diagonal, i.e., A = diag(A 11, …, A MM). For simplicity we assume A to be asymptotically stable. This ensures the separability of the cost function J(k) as in (9): in fact we can take u(k) = Kx = 0 (i.e., K = 0) as a - decentralized - auxiliary control law for the expanded system and we can select P i, i = 1, …, M in such a way that A ii T P i A ii − P i = −Q i, Q i > 0. This makes V f a Lyapunov function for the system x(k + 1) = Ax(k), as required. Finally, in the present algorithm, only input constraints are enforced. At time k all the local MPC control algorithms have knowledge of the overall state x(k) and of the full system dynamics, meaning that a fully connected communication network is required to support the transmission of the global state to all the local control stations. The following iterative procedure is performed within the sampling period from time k and time k + 1:

  • at iteration (negotiation) step p, p ≥ 1, each local controller in \(\mathcal{S}_{i}\) has the information about the possible input sequences of the other subsystems, u j p−1(k + l), for l = 1, …, N − 1 and j ≠ i, to be broadcast thanks to the available fully connected communication network; the following (global) optimization problem is solved at a local level

    $$\displaystyle{ \min _{u_{i}(k),\ldots,u_{i}(k+N-1)}J(k) }$$
    (14)

    subject to the expanded model (7) and, for l = 0, …, N − 1,

    $$\displaystyle{ u_{i}(k + l) \in \mathcal{ U}_{i} }$$
    (15)
    $$\displaystyle{ u_{j}(k + l) = u_{j}^{p-1}(k + l)\,,\forall j\neq i }$$
    (16)

  • letting u i o(k), …, u i o(k + N − 1) be the optimal solution, a convex combination between the solution at the previous iteration and the newly computed one is used, i.e.

    $$\displaystyle{ u_{i}^{p}(k + l) =\alpha _{ i}u_{i}^{p-1}(k + l) + (1 -\alpha _{ i})u_{i}^{o}(k + l)\,,l = 0,\ldots,N - 1 }$$

    where α i ∈ (0, 1) and ∑ i = 1 M α i = 1.

  • if a termination condition, which can depend on the elapsed time within the sampling period or on an optimality test, is satisfied, the iterative procedure ends and the last computed value u i p(k) is used as u i(k), otherwise a new iteration starts (p ← p + 1)

  • when a new measurement is received, (k ← k + 1) the overall procedure is restarted.

The algorithm requires an initialization for p = 0, which can be obtained based on the optimal control sequence at the previous time k − 1. As shown in [8, 15] stability of the closed-loop system is guaranteed for any number of iterations performed within the sampling time; in addition, it can be proven that the computed solution converges to the one of the corresponding centralized control system as the number of iterations (p) increases. Finally, the method can be extended to cope with unstable open-loop systems, provided that a suitable zero terminal condition is included into the problem formulation, and with tracking problems [8].Interestingly, in [8] it has been shown that, if each local controller adopts a non-cooperating (selfish) approach and minimizes only its own cost function J i, convergence to a Nash equilibrium is achieved and no stability guarantees can be proven. In [16], a further step is done: more specifically, it is shown that it is possible to add, for each subsystem, a constraint related to the maximal satisfactory and sufficiently small (denoted satisficing in the papers) cost γ i, i.e., J i(k) ≤ γ i. According to [16], this variation allows to shift from a purely cooperating scheme (denoted also categorical altruist algorithm) to a scheme (denoted situational altruist) where local (selfish) constraints are introduced.

4.2 Non-cooperating Robustness-Based DMPC

The algorithm described in [17] is based on the idea that each subsystem i transmits to its neighbors its planned state reference trajectory \(\tilde{x}_{i}(k + j)\), j = 1, …, N, over the prediction horizon and guarantees that, for all j ≥ 0, its actual trajectory lies in a “tube” centered in \(\tilde{x}_{i}\), i.e. \(x_{i}(k + j) \in \tilde{ x}_{i}(k + j) \oplus \mathcal{ E}_{i}\), where \(\mathcal{E}_{i}\) is a compact set including the origin. Then, assuming here for simplicity that the system is input decoupled, Equation (3) can be written as

$$\displaystyle{ x_{i}(k + 1) = A_{ii}x_{i}(k) + B_{ii}u_{i}(k) +\sum _{j}A_{ij}\tilde{x}_{j}(k) + w_{i}(k) }$$
(17)

where \(w_{i}(k) =\sum _{j}A_{ij}(x_{j}(k) -\tilde{ x}_{j}(k)) \in \mathcal{ W}_{i}\) is a bounded disturbance to be rejected using the tube-based MPC approach [13] (see also Chapter “Robust Optimization for MPC”), where \(\mathcal{W}_{i} =\bigoplus _{j}A_{ij}\mathcal{E}_{i}\). The term \(\sum _{j}A_{ij}\tilde{x}_{j}(k)\) is equivalent to a non-manipulable input, known in advance over the prediction horizon, to be properly compensated.

From (17), the i-th subsystem nominal model [13] is defined as

$$\displaystyle{ \hat{x}_{i}(k + 1) = A_{ii}\hat{x}_{i}(k) + B_{ii}\hat{u}_{i}(k) +\sum _{j}A_{ij}\tilde{x}_{j}(k) }$$
(18)

Letting K = diag(K 1, …, K M) be a block-diagonal matrix such that both A + BK and A ii + B ii K i are stable, the local control law is chosen as

$$\displaystyle{ u_{i}(k) =\hat{ u}_{i}(k) + K_{i}(x_{i}(k) -\hat{ x}_{i}(k)) }$$
(19)

From (17) and (19), letting \(z_{i}(k) = x_{i}(k) -\hat{ x}_{i}(k)\), it holds that

$$\displaystyle{ z_{i}(k + 1) = (A_{ii} + B_{ii}K_{i})z_{i}(k) + w_{i}(k) }$$
(20)

where \(w_{i} \in \mathcal{ W}_{i}\). Since \(\mathcal{W}_{i}\) is bounded and A ii + B ii K i is stable, there exists a robust positively invariant set \(\mathcal{Z}_{i}\) for (20) such that, for all \(z_{i}(k) \in \mathcal{ Z}_{i}\) and \(w_{i}(k) \in \mathcal{ W}_{i}\), one has \(z_{i}(k + 1) \in \mathcal{ Z}_{i}\). According to the approach developed in [13], given \(\mathcal{Z}_{i}\) and assuming that there exist neighborhoods of the origin \(\varDelta \mathcal{E}_{i}\) such that

$$\displaystyle{ \varDelta \mathcal{E}_{i} \oplus \mathcal{ Z}_{i} \subseteq \mathcal{ E}_{i} }$$
(21)

at any time instant k the i-th subsystem computes the value of \(\hat{u}_{i}(k)\) in (19) as the solution to

$$\displaystyle{ \min _{\hat{x}_{i}(k),\hat{u}_{i}(k),\ldots,\hat{u}_{i}(k+N-1)}J_{i}(k) }$$
(22a)

subject to (18) and the initial state constraint

$$\displaystyle{ x_{i}(k) -\hat{ x}_{i}(k) \in \mathcal{ Z}_{i} }$$
(22b)

For l = 0, …, N − 1, to guarantee that the difference between x i and \(\tilde{x}_{i}\) is effectively limited as initially stated, we require that

$$\displaystyle{ \hat{x}_{i}(k + l) -\tilde{ x}_{i}(k + l) \in \varDelta \mathcal{ E}_{i} }$$
(22c)

Both local (4) and coupling (5) constraints can be imposed. This is done by requiring that, for l = 0, …, N − 1

$$\displaystyle{ \hat{x}_{i}(k + l) \in \hat{\mathcal{ X}}_{i} }$$
(22d)
$$\displaystyle{ (\tilde{x}_{1}(k + l),\ldots,\hat{x}_{i}(k + l)\ldots,\tilde{x}_{M}(k + l)) \in \hat{\mathcal{ X}}_{C} }$$
(22e)

This requires to suitably define the sets \(\hat{\mathcal{X}}_{i}\) and \(\hat{\mathcal{X}}_{C}\) as restricted ones, e.g., by setting \(\hat{\mathcal{X}}_{i} \subseteq \mathcal{ X}_{i} \ominus \mathcal{ Z}_{i}\). Although state constraints only have been defined for simplicity, input constraints can be included similarly. Finally, the scheme calls for the definition of terminal constraints of the type

$$\displaystyle{ \hat{x}_{i}(k + N) \in \hat{\mathcal{ X}}_{f,i} }$$
(22f)

With the optimal solution at time k, it is also possible to compute the predicted value \(\hat{x}_{i}(k + N)\), which is used to incrementally define the reference trajectory of the state to be used at the next time instant k + 1, i.e. \(\tilde{x}_{i}(k + N) =\hat{ x}_{i}(k + N)\). Condition (21) is a key condition for the well posedness of the present distributed control scheme. Despite its analysis goes beyond the scope of this chapter, it is worth remarking that it is equivalent to the so-called tube-based small gain condition for networks discussed in Chapter “Scalable MPC Design”.Remarkably, each local control station uses only local state information (i.e., x i(k)) and its neighbors’ planned state trajectories \(\tilde{x}_{j}(k)\). The latter is transmitted in a neighbor-to-neighbor fashion thanks to the available partially connected communication network.A significant work has been devoted to the proper definition of separable terminal cost and constraint sets. In [17, 18] methods for a proper choice of the weights Q i, R i, P i, of sets \(\mathcal{E}_{i}\), and of the terminal set \(\hat{\mathcal{X}}_{f,i}\) guaranteeing the well posedness and the stabilizing properties of the algorithm are proposed.

4.3 Distributed Control of Independent Systems

A prototype non-iterative algorithm for independent systems coupled through constraints is now described, inspired by the approach described in [19]. The system is assumed to be affected by an unknown, but bounded noise, so that the robust tube-based approach of [13] is used also in this case. The model of the i-th subsystem, i = 1, …, M, is described by

$$\displaystyle{ x_{i}(k + 1) = A_{ii}x_{i}(k) + B_{ii}u_{i}(k) + d_{i}(k) }$$
(23)

where \(d_{i}(k) \in \mathcal{ D}_{i}\) is a bounded disturbance. The M systems are subject to both local and coupling constraints (4) and (5), respectively. For each system i = 1, …, M, the local nominal model

$$\displaystyle{ \hat{x}_{i}(k + 1) = A_{ii}\hat{x}_{i}(k) + B_{ii}\hat{u}_{i}(k) }$$
(24)

is defined and a stabilizing gain K i is computed. Also in this case, the local stabilizing control law is given by

$$\displaystyle{ u_{i}(k) =\hat{ u}_{i}(k) + K_{i}(x_{i}(k) -\hat{ x}_{i}(k)) }$$
(25)

and letting \(z_{i}(k) = x_{i}(k) -\hat{ x}_{i}(k)\), it holds that

$$\displaystyle{ z_{i}(k + 1) = (A_{ii} + B_{ii}K_{i})z_{i}(k) + d_{i}(k) }$$
(26)

In view of the boundedness of the disturbance and the stability of A ii + B ii K i, there exists a robust positively invariant set \(\mathcal{Z}_{i}\) for (26) such that, for all \(z_{i}(k) \in \mathcal{ Z}_{i}\) and \(d_{i}(k) \in \mathcal{ D}_{i}\), one has \(z_{i}(k + 1) \in \mathcal{ Z}_{i}\). At any time instant k only one system, say the i-th one, is allowed to update its future plans by solving a suitable MPC problem, while all the others update their control variables according to the previously computed control sequence and the corresponding auxiliary law, i.e. their future nominal control moves computed at time k are, for all j ≠ i

$$\displaystyle{ \begin{array}{lcl} \hat{u}_{j}(k + l\vert k) & =&\hat{u}_{j}(k + l\vert k - 1)\,,\,l = 0,\ldots,N - 2 \\ \hat{u}_{j}(k + N - 1\vert k)& =&K_{j}\hat{x}_{j}(k + N - 1\vert k - 1)\end{array} }$$

where \(\hat{x}_{j}(k + N - 1\vert k - 1)\) is the evolution of the nominal state starting from \(\hat{x}_{i}(k) = x_{i}(k)\) with the sequence \(\hat{u}_{j}(k + l\vert k - 1)\), l = 0, …, N − 2. We also define \(\hat{x}_{j}(k + N - 1\vert k - 1) = (A_{ii} + B_{ii}K_{i})\hat{x}_{j}(k + N - 1\vert k - 1)\).On the contrary, the i-th system computes the value of \(\hat{u}_{i}(k)\) in (19) as the solution to

$$\displaystyle{ \min _{\hat{x}_{i}(k),\hat{u}_{i}(k),\ldots,\hat{u}_{i}(k+N-1)}J_{i}(k) }$$
(27a)

subject to (18) and the initial state constraint

$$\displaystyle{ x_{i}(k) -\hat{ x}_{i}(k) \in \mathcal{ Z}_{i} }$$
(27b)

Both local (4) and coupling (5) constraints are forced by requiring that, for l = 0, …, N − 1

$$\displaystyle{ \hat{x}_{i}(k + l) \in \hat{\mathcal{ X}}_{i} }$$
(27c)
$$\displaystyle{ (\hat{x}_{1}(k + l\vert k - 1),\ldots,\hat{x}_{i}(k + l)\ldots,\hat{x}_{M}(k + l\vert k - 1)) \in \hat{\mathcal{ X}}_{C} }$$
(27d)

where the sets \(\hat{\mathcal{X}}_{i}\) and \(\hat{\mathcal{X}}_{C}\) are properly restricted subsets of \(\mathcal{X}_{i}\) and \(\mathcal{X}_{C}\), e.g., by setting \(\hat{\mathcal{X}}_{i} \subseteq \mathcal{ X}_{i} \ominus \mathcal{ Z}_{i}\). As in the previous algorithms, the scheme calls for the definition of terminal constraints of the type

$$\displaystyle{ \hat{x}_{i}(k + N) \in \hat{\mathcal{ X}}_{f,i} }$$
(27e)

Similarly to the non-cooperating robustness-based control scheme presented in Section 4.2, a partially connected communication network is required to support the transmission of the planned trajectories \(\hat{x}_{j}(k + l\vert k - 1)\) to each local control station from the (constraint-based) neighboring ones.As described in [19, 20], the basic algorithm here described can be greatly enhanced to allow for more than one system updating its future plans with the optimization procedure at each time step. In addition, cooperation is achieved letting each system to minimize a global cost function and the communication requirements can be significantly reduced with respect to an all-to-all solution by exploiting the graph topology forced by the coupling constraints.Similar schemes have been devised by other research teams, e.g., [21]. The paper [22] also extends this method to cope with economic-based cost functions.

4.4 Distributed Optimization

A different approach with respect to the distributed algorithms previously described consists of computing the optimal solution to the original centralized optimization problem as the iterative solution to smaller, more tractable, and independent ones. This idea, which is the basis of many popular decomposition methods, can be traced back to the early contributions, e.g., [23]. In the context of MPC, the reader is referred to the recent contributions [24–27].A sketch of a simple version the popular dual decomposition approach, proposed in [24], applied to MPC is now described. Constraints of general type can easily be considered in the present framework, although for simplicity of presentation they will be neglected here. Consider the set of input decoupled systems

$$\displaystyle{ \begin{array}{lcl} x_{i}(k + 1)& =&A_{ii}x_{i}(k) + B_{ii}u_{i}(k) +\sum _{j\neq i}A_{ij}x_{j}(k)\\ \end{array} }$$
(28)

and the following centralized problem

$$\displaystyle{ \min _{u(k),\ldots,u(k+N-1)}J(k) }$$
(29)

In view of the formal separability of the cost function J(k), the coupling between the subproblems is due to the “coupling variables” ν i = ∑ j ≠ i A ij x j in (28). Now write Equation (28), similarly to (13), as

$$\displaystyle{ x_{i}(k + 1) = A_{ii}x_{i}(k) + B_{ii}u_{i}(k) +\nu _{i}(k) }$$
(30)

and, denoting by λ i the Lagrange multipliers, consider the Lagrangian function

$$\displaystyle{ \mathcal{L}(k) =\sum _{ i=1}^{M}[J_{ i}(k) +\sum _{ l=0}^{N-1}\lambda _{ i}(k + l)(\nu _{i}(k + l) -\sum _{j\neq i}A_{ij}x_{j}(k + l))] }$$
(31)

For the generic vector variable φ, let \(\bar{\varphi }_{i}(k) = [\varphi _{i}^{T}(k)\,,\ldots \,,\varphi _{i}^{T}(k + N - 1)]^{T}\) and \(\bar{\varphi }= [\bar{\varphi }_{1}^{T}\,,\ldots \,,\bar{\varphi }_{M}^{T}]^{T}\). Then, by relaxation of the coupling constraints, the optimization problem of Equation (29) can be stated as

$$\displaystyle{ \max _{\bar{\lambda }(k)}\min _{\bar{u}(k),\bar{\nu }(k)}\mathcal{L}(k) }$$
(32)

or, equivalently

$$\displaystyle{ \max _{\bar{\lambda }(k)}\sum _{i=1}^{M}\tilde{J}_{ i}(k) }$$
(33)

where, letting \(\bar{A}_{ji}\) be a block-diagonal matrix made by N blocks, all equal to A ji,

$$\displaystyle{ \tilde{J}_{i}(k) =\min _{\bar{u}_{i}(k),\bar{\nu }_{i}(k)}[J_{i}(k) +\bar{\lambda }_{ i}^{T}(k)\bar{\nu }_{ i}(k) -\sum _{j\neq i}\bar{\lambda }_{j}^{T}(k)\bar{A}_{ ji}\bar{x}_{i}(k))] }$$
(34)

The following two-step iterative procedure is then used at any time step to compute the optimal solution

  1. 1.

    for a fixed \(\bar{\lambda }\), solve the set of M independent minimization problems given by Equation (34) with respect to \(\bar{u}_{i}(k),\bar{\nu }_{i}(k)\);

  2. 2.

    given the collective values of \(\bar{u},\bar{\nu }\) computed at the previous step, solve the maximization problem given by (33) with respect to \(\bar{\lambda }\). This problem can be solved in a distributed way using a gradient step, see [24].

To summarize, the described iterative algorithm must be supported by a partially connected communication network (for both steps 1 and 2, provided that the latter uses a distributed gradient step). More specifically, at each iteration, for step 1 it is required that, for all i = 1, …, M, the i-th local computing station receives the current values of λ j(k + l), l = 1, …, N − 1 by the agents j ≠ i which have i as neighbor, i.e., such that \(i \in \mathcal{ N}_{j}\); on the other hand, for step 2, it is required that the i-th station receives the current values of x j(k + l) by its neighbors \(j \in \mathcal{ N}_{i}\).It is well recognized that this kind of decomposition approaches are characterized by slow convergence, due to the great number of iterations required to obtain a solution. However, to this regard, many efficient algorithms have been developed, see, for instance, [26]. In addition, the fundamental properties of recursive feasibility and stability are not a-priori guaranteed, and can be achieved by a proper definition of the optimization problem and of the constraints, see [27].A final remark is due: as noted above and as apparent from (33), the separability of the cost function J(k) is a major requirement also for this method, as well as - for constrained problems - the separability of the terminal constraint set. The previously discussed approaches can be used to this aim, including the one presented in [17, 18]. Also the recent work [28] is devoted to this problem and allows for scalable design. See Chapter “Scalable MPC Design” for more details.

5 Extensions and Applications

The DMPC algorithms discussed in the previous sections have been designed for linear, discrete-time, and time invariant systems, and the main approaches and ideas behind most of the nowadays available methods for the regulation problem have been described. However, the recent and tumultuous research activity in the field has produced a number of algorithms dealing with a large variety of systems and control problems. Among them, we here recall some of the most interesting research directions, with some references:

  • DMPC algorithms have been developed for continuous-time and nonlinear systems in, e.g., [21, 29–31].

  • The output feedback case has been studied in [32], while the tracking problem has been analyzed, e.g., in [8, 33]. An alternative approach, based on the particular class of MPC strategies called Command Governor methods, has been reported in [34] and in the papers referenced therein.

  • DMPC for systems affected by stochastic noises has been considered in [35–37].

  • Economic MPC (see Chapter “Economic Model Predictive Control: Some Design Tools and Analysis Techniques”) has been extended to cope with a distributed implementation in [22, 38].

  • The new and emerging field of coalitional control, which can be seen as an evolution of DMPC where the topology of the control structure can vary with time, has been treated in [39], where an up-to-date literature review is also reported.

Many applications domains of DMPC have been explored, although most of the reported research still makes reference to simulation studies, with only few real applications (mainly laboratory experiments). In view of its nature, DMPC fits very well with the control of large, spatially distributed systems, possibly interconnected through a network. For this reason, power networks, smart grids, and in general distributed energy management systems are the natural domains where DMPC can offer advantages with respect to a centralized solution, see, for instance, [40–44]. Another class of problems where DMPC can have a great potential impact concerns the management and control of irrigation canals, as discussed in [45]. The coordination of multi-vehicle systems with DMPC has been considered, e.g., in [46, 47]. Finally, applications in other fields are described in [48, 49].

6 Conclusions and Future Perspectives

The research activity in Distributed Model Predictive Control has been intense in the last decade and many methods are nowadays available, see, for instance, the many contributions reported in [4]. In parallel with the development of new algorithms, also the most significant fields of application of DMPC have been clarified. In our opinion, these include networked systems, like power, water, and traffic networks, the coordination of autonomous vehicles and flying systems (drones), the control of very large-scale, weakly coupled, systems. However, there is still a significant gap between research results and real-world applications since most of the DMPC algorithms have only been tested in simulations or with laboratory benchmarks. Among the most promising future research directions, we believe that the reconfigurability of DMPC will be a major topic. To this regard, plug-and-play and coalitional control strategies, possibly driven by external events, will be required to enhance the ability of DMPC to deal with many real control problems and to provide significant improvements with respect to the nowadays adopted control solutions.