{'fraction_non_alphanumeric': 0.03724719328820979, 'fraction_numerical': 0.015644631783731204, 'mean_word_length': 4.359252823631625, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed MPC: Guaranteeing Global Stabilizability from Locally Designed Tubes

This paper studies a fundamental relation that exists between stabilizability assumptions usually employed in distributed model predictive control implementations, and the corresponding notions of invariance implicit in such controllers. The relation is made explicit in the form of a theorem that presents sufficient conditions for global stabilizability. It is shown that constraint admissibility of local robust controllers is sufficient for the global closed-loop system to be stable, and how these controllers are related to more complex forms of control such as tube-based distributed model predictive control implementations.


INTRODUCTION
There exists various physical systems for which a centralized control implementation is not a suitable solution (Mayne, 2014). The two main reasons for this are: (i) the physical system is spread over a wide area, which makes communication to a central hub expensive and prompt to data loss (power networks, traffic networks, etc.) (Baillieul and Antsaklis, 2007), (ii) the physical system is a composition of individual subsystems with clearly defined physical boundaries (autonomous vehicles, swarms of robots, etc).
In the context of model-based predictive controllers, there is a third situation in which centralized control is not a viable solution, and it has to do with computational requirements. Model predictive control (MPC) is a mature control technique that provides safe and stabilizing control under appropriate design (Mayne et al., 2000). However, in order to compute the control action to be applied to the plant, it needs to solve an optimization problem at each time instant. Clearly then, plants with fast dynamics and a large number of control variables are out of the scope of standard centralized MPC implementations. A natural solution to this problem is to split the plant into smaller subsystems, and then to design local controllers. However, this creates residual interaction between different subsystems, which must be taken into account if control guarantees are to be delivered.
Many distributed MPC (DMPC) implementations have been devised to tackle this problem (for a detailed review see Scattolini (2009); Christofides et al. (2013)). The main aspect in which they differ is in which type of interaction is allowed between subsystems, and how this is treated. In recent years, robust MPC techniques such as tube MPC (TMPC) (Mayne et al., 2005) and others (for example Chisci et al. (2001)), have inspired several DMPC approaches (Farina and Scattolini, 2012;Riverso and Ferrari-Trecate, 2012;Farina et al., 2014;Lucia et al., 2015;Trodden et al., 2016;Baldivieso and Trodden, 2016;Hernandez and Trodden, 2016). The main idea of such approaches is to treat the interactions between subsystems as local disturbances that may be handled (conservatively) by robust local controllers. Communication and iteration between subsystems is then used in different ways to reduce the conservativeness induced by use of a robust method. All of these approaches, either implicitly or explicitly, rely on stabilizability assumptions. These usually require the existence of a global linear feedback with a certain structure affine to the interaction pattern of the global system. This type of assumption is also present in DMPC techniques that are not based on robust approaches such as Conte et al. (2016); Maestre et al. (2011).
In this paper, a fundamental relation that exists between this type of stabilizability assumption, and the various concepts of invariance employed by (tube-based) DMPC architectures, is made explicit. To the best of the authors' knowledge, this relation has not been studied explicitly before (although some related results have been published, which we survey in Section 3), albeit the global stabilizability assumption is present (either explicitly or implicitly) in many of the DMPC approaches proposed to date. First, a collection of linear local robust controllers is introduced in order to study the stabilizability of the global plant from a decentralized perspective. The main result states that a sufficient condition for global stabilizability is that these local controllers are locally stabilizing and constraint admissible. Although very simple, the proposed controllers sit at the core of many tube-based DMPC architectures, which makes this result relevant to the state of the art in DMPC.
The remainder of the paper is organized as follows: Section 2 defines the preliminaries and standard assumptions found in many tube-based DMPC implementations. In order to contextualize the results given in this paper, Section 3 discusses two approaches that are commonly used to meet the previously stated assumptions. The main result is given in Section 4, and three examples are presented in Section 5 in order to illustrate the result, and highlight its advantages and limitations. Finally, Section 6 provides some conclusions.
Notation. The set of consecutive integers {1, . . . , M } is denoted by M. A block-diagonal matrix S with blocks S i and i ∈ M is denoted as diag M (S i ). A vector x that is formed by vertically stacked vectors x i with i ∈ M is denoted as x = col M x i . If S is a matrix, ρ (S) is the spectral radius of S; if ρ (S) < 1 then S is Schur. If A and B are sets, then A ⊕ B := {c = a + b | ∀a ∈ A, b ∈ B} and A ⊖ B := {a ∈ A | ∀b ∈ B, a + b ∈ A} (Minkowski sum and Pontryagin difference respectively). If S i is a collection of sets with i ∈ M, then i S i = S 1 ⊕ · · · ⊕ S M . The matrix I n is the identity of dimension n. If x t is the value of x at time t, then x k/t is the prediction of x k made at time t ≤ k.

Local and global dynamics
First consider the general problem of regulating a network of M , possibly heterogeneous, linear time invariant (LTI) systems that interact with each other via states and inputs. For all i ∈ M the dynamics of subsystem i are represented by the following state space model where x i(j) t ∈ R n i(j) and u i(j) t ∈ R m i(j) are the state and input vectors belonging to subsystem i(j) at time t, with matrices (A ij , B ij ) of corresponding dimension. The set N i ⊂ M is referred to as the set of neighbours of subsystem i, and contains the indexes of all the other subsystems that affect the dynamics of i. Given the assumed noncentralized nature of the plant, consider the case in which each subsystem i is subject to local constraints of the form (1) Assumption 1. (Local behaviour). For all i ∈ M, the pair (A ii , B ii ) is stabilizable and the set (X i × U i ) is compact, convex and contains the origin in its interior.
To simplify the analysis, assume that the subsystems do not share states and/or inputs. The collection of local models forms the following global constrained LTI model: x t+1 = Ax t + Bu t , where (x, u) = col M x i , col M u i ∈ X × U, matrices A and B are compose by the blocks (A ij , B ij ), and X = X 1 × · · · × X M ⊆ R n U = U 1 × · · · × U M ⊆ R m .

Distributed control
One of the main questions in distributed control is how to guarantee certain properties at the global scale (stability, constraint satisfaction, etc.), from a possibly distributed design. In order to achieve these global properties, many DMPC implementations employ synthesis procedures that are either centralized (Maestre et al., 2011;Lucia et al., 2015), or require the solution of problems that can be computationally expensive (Conte et al., 2016;Kern and Findeisen, 2013). In this context, and in particular with tube-based DMPC controllers, the following assumption is usually required (see for example Farina and Scattolini (2012); Riverso and Ferrari-Trecate (2012); Baldivieso and Trodden (2016); Hernandez and Trodden (2016)), Assumption 2. (Block-diagonal stabilizability). There exists a collection of local linear feedbacks K i such that Assumption 2 demands the existence of a globally stabilizing linear feedback K with a block-diagonal structure. This definitively limits the class of systems that can be controlled with such techniques, but a more pressing issue in the context of decentralized control, is that searching for a collection of local feedbacks that fulfils Assumption 2 usually requires centralized computations. There is a vast literature dedicated to analysing the impact that naive local control design has over global behaviour (see for example Cui and Jacobsen (2002)), but perhaps an example is enough to clarify the problem. Example 3. Consider the coupled integrators The local linear feedbacks Example 3 makes clear that careful (perhaps centralized) design is required to meet Assumption 2. The main result of this paper is to make explicit the fundamental relation that exists between the stabilizability requirements in Assumption 2 and the standard notions of invariance that are usually implicit in DMPC controllers. To aid this, various concepts of invariance are now defined. Definition 4. (Positive invariant (PI) set). A set X p is said to be a PI set for the dynamics Remark 6. Non-compact or singleton invariant sets are not considered a valid solution in the following analysis. Remark 7. In view of Remark 6, unstable closed-loop dynamics do not accept invariant sets as described by Definitions 4 and 5.

GLOBAL STABILIZATION: EXISTING APPROACHES
The task of finding local linear feedbacks that fulfil Assumption 2 (or a similar one) appears in different steps of the implementation of DMPC controllers. Some of the techniques used to compute these feedbacks also exploit notions of invariance, and are implicitly related to the more fundamental result shown in this paper. In order to put this result into context, two of these approaches are briefly discussed.

Linear matrix inequalities
In the general DMPC framework (not necessarily tubebased approaches), a common practice is to tackle the distributed controller synthesis problem from a centralized perspective, and to pose a set of LMIs whose solution(s) provides an adequate candidate for the required controller (these LMIs represent standard Lyapunov stability conditions in the context of MPC). In Maestre et al. (2011) a global linear feedback, which is forced to be zero wherever there is no dynamical coupling, is proposed to play the role of the local terminal controller often used in the MPC framework (Mayne et al., 2005). In order to find this feedback, a set of local LMIs is posed alongside with a single global LMI of dimension 4n × 4n (where n is the overall dimension of the plant). A similar problem is found in Conte et al. (2016), where a distributed optimization approach is proposed to find the solution to the local LMIs, in the presence of a system-wide coupled LMI.
The problem of finding separable PI sets is tackled in a similar way in Nilsson and Ozay (2015), where a set of LMIs is proposed to find simultaneously a set of local independent feedbacks K i that fulfil Assumption 2, and a corresponding collection of joint PI sets. This procedure is proposed to tackle disturbed local dynamics, but even when no disturbance is considered, the smaller LMI is of dimension 2n × 2n.

Positively invariant families of sets
Although not explicitly stated, the concept of positively invariant families of sets (PIFs), introduced by Raković et al. (2010), can also be used to analyse the link between local and global closed-loop behaviour (in a centralized fashion). The concept of PIFs is more general than Definition 4 but it is based on the same invariance properties. The main advantage of the specific parametrization proposed in Raković et al. (2010) is that, in the context of global to local dynamics, the dimension of the problem can be considerably reduced (from n to M ) by looking at what the authors call a comparison system.
It is shown in Raković and Gielen (2014) that: (i) a stable comparison system is a sufficient condition for the true system to accept a PIFs, and (ii) if a system admits a PIFs, then it admits a PI set, which therefore means that the closed-loop dynamics are stable. In this context, it might prove easier to find a stable comparison system (of dimension M ) and then relate it to the global system in closed loop form with a particularly structured K.
This notion is the underlying idea of the approach proposed in Kern and Findeisen (2013), where local LMIs are constructed in order to find, in a non-centralized fashion, a collection of local gains K i that fulfils Assumption 2, and a corresponding PIFs.
In all of the these approaches, there is no guarantee that a solution does exist for the proposed set of LMIs (or stable comparison system). This should not be a surprise, given that the successful synthesis of a non-centralized controller depends greatly on the size of the interaction between neighbouring subsystems, and how these are dealt with (communication, iterative optimization, etc.).

GLOBAL STABILIZATION VIA TUBES
The fundamental result shown in this paper stems from the invariance notions implicit in the robust control technique known as Tube MPC (Mayne et al., 2005), and its application to distributed control.

Decentralized linear robust control (inside the tube)
Suppose that subsystem i has no means of obtaining information about what its neighbours' plans are. A sensible, yet conservative, way of performing non-centralized control is to view the dynamical interaction between subsystems as disturbances that must be rejected. In order to move forward, the following assumption is required. Assumption 8. State and input constraints are satisfied by all subsystems: x i t ∈ X i and u i t ∈ U i for all i ∈ M, t ≥ 0. If Assumption 1 is fulfilled, then the following disturbance sets are compact for all i ∈ M Moreover, if Assumption 8 is fulfilled, the sets W i represent a suitable bound for the interaction between subsystems: In view of this and Definition 5, for any linear feedback K i that renders F ii Schur, there exists a compact RPI set Z i for the local disturbed dynamics Given x i 0 ∈ Z i and the invariance of Z i , it follows that then x i t ∈ X i and u i t ∈ U i for all i ∈ M and for all t ≥ 0. Remark 10. In the context of TMPC, the sets Z i are the cross section of the local tubes.
Proposition 9 provides a decentralized perspective to the problem of finding stabilizing and constraint admissible local linear feedbacks. Indeed, as long as the hypotheses of Proposition 9 are met (for all i ∈ M), independent RPI sets could be designed for each subsystem. The closed-loop global system would then take the form F = A + BK, which as shown in Example 3, could be unstable. This seems to defy the invariance properties of the collection of sets Z i .
In spite of the local invariance arguments, the analysis of the local dynamics does evidence an unexpected behaviour. Consider a network with M = 2 and suppose that K i are indeed chosen such that F ii are Schur and that the hypotheses of Proposition 9 are met, but F is not Schur. Given x 0 ∈ Z = Z 1 × Z 2 ⊂ X and unstable closed-loop global dynamics, there must exist a t 1 > 0 such that, z 1 t1−1 ∈ Z 1 but z 1 t1 / ∈ Z 1 . This means that the robust invariant property of Z 1 has been broken, which can only mean that the disturbances affecting subsystem Proposition 11. Suppose K i are chosen such that F ii are Schur but F is not, and that the hypotheses of Proposition 9 are met. Then there exists a finite timet > 0 such that xt −1 ∈ Z but xt / ∈ X or ut / ∈ U. Remark 12. Proposition 11 implies either a state jump from inside Z to outside X, or an input jump from inside KZ to outside U. This, in some cases, might mean a discontinuity of the state trajectories, which is not characteristic of the type of (linear) systems being analysed.

From local robustness to global stability (main result)
The uncharacteristic behaviour made explicit by Remark 12 can be explained by the fundamental relation that exists between Assumption 2 and the notions of invariance employed in Proposition 9 (and by TMPC). Consider the following definition: Definition 13. (Admissibility of tube i). A tube i corresponding to a particular linear feedback K i is said to be constraint admissible if the first part of the hypothesis of Proposition 9 holds, i.e., if Z i ⊂ X i and K i Z i ⊂ U i .
The main result of this paper is now stated: Theorem 14. If there exists constraint admissible tubes for all subsystems i ∈ M, then the collection of local gains K i related to these admissible tubes fulfils Assumption 2.
Proof. First, in view of Remark 7, if F ii admits a RPI set Z i , then F ii is Schur. Given Definition 5, and standard Minkowski sum properties, it is clear that if Z i is RPI for the disturbed dynamics in (3), then where the first inclusion follows from Minkowski sum properties and the second inclusion from the constraint admissibility of tube i. Equations (4) and (5) imply and hence, Z = Z 1 × · · · × Z M ⊆ R n is a PI set for the closed-loop dynamics F . In view of this and Remark 7, F is Schur. Remark 15. Theorem 14 presents sufficient conditions for a collection locally stabilizing linear feedbacks to be globally stabilizing. Remark 16. Unstable global dynamics, as demanded by Proposition 11, imply Assumption 8 is not met, and therefore (some of) the disturbance sets are unbounded. The corresponding RPI sets are also unbounded, thus, the set inclusions required for constraint admissibility of the tubes cannot be met. This implies that the behaviour described by Remark 12 is not possible, because the tubes would not have been admissible.
A collection of constraint admissible tubes Z i is a family of jointly RPI sets. This collection forms what can be referred to as a square PI set, given that Z is defined by the cross product of subsets of the local dynamics state space. This is also pointed out in Maestre et al. (2011);Lucia et al. (2015); Nilsson and Ozay (2015); Conte et al. (2016). Remark 17. The existence of such a particular PI set is a necessary condition for the tubes to be system-wide admissible. This clarifies the main source of conservativeness of Theorem 14.
Large constraint sets for a single subsystem might render impossible to find admissible tubes for the affected neighbours. However, Theorem 14 remains useful for the task of analysing local-to-global stabilizability (the constraint sets could be shrunk, similar to the approach taken in Maestre et al. (2011)).
In the parametrization of PIFs proposed by Raković et al. (2010), each element in the family of sets is also square.
A marginally stable comparison system that admits the corresponding eigenvector as an initial scaling factor, also provides a square PI, and therefore, a collection of local linear feedbacks K i that fulfils Assumption 2.

Tube MPC
The main purpose of the linear robust controller presented in Section 4.1 was to show the fundamental result given by Theorem 14. On its own, this controller can only guarantee robust stabilizability of its region of attraction (the set Z). However, such a controller is at the core of many tubebased DMPC architectures. In order to make this clear, TMPC is now briefly described.
TMPC aims to solves the regulation problem for a nominal undisturbed version of the plant, while securing that the state of the true plant remains bounded inside a tube centred (at each time) at the nominal undisturbed trajectory. Define the nominal model for subsystem i aŝ then, the control action to be applied to the true plant, at each time step, is computed via the following control policy The first term in (7) is a stabilizing control action for the nominal model, and the second one is designed to reject the disturbances. The local feedback K i is any stabilizing gain for the pair (A ii , B ii ). The dynamics of the trajectory where the disturbance w i represents the unknown dynamical coupling, and therefore belongs to W i as defined in (2) (exact same dynamics as (3)).
The pair û i t/t ,x i t/t is obtained from the following open loop optimal control problem, which is standard in nominal MPC implementations, : min subject to the dynamics in (6a) and, for k = t, . . . , t+N −1: Theorem 18. If (i) Z i is an RPI set for the dynamics in (8) and disturbance w i ∈ W i , (ii) l i , V i f andX f i are designed following standard MPC arguments to ensure asymptotic stability of the nominal undisturbed system, and (iii) the setX i ×Û i fulfils Assumption 1, then (a) the set Z i is robustly asymptotically stable for system (3) in closed loop with (7) and (b) constraints (1) are met at all times.
Proof. The reader is referred to Mayne et al. (2005) for the proof.
Note that, for all t > 0, constraint (9a) may be replaced byx i t/t =x i t/t−1 (i.e., independent time evolution of the nominal system, see Rawlings and Mayne (2014)). Given x 0 ∈ Z, the closed-loop dynamics reduce to F = A + BK, which, again, could show the behaviour described by Proposition 9 and Remark 12. However, Theorem 14 shows that this is not the case. Corollary 19. If the hypotheses of Theorem 18 are met for all i ∈ M, then F is Schur.
Proof. Hypotheses (i) and (iii) of Theorem 18 are equivalent to the existence of a constraint admissible tube for subsystem i, hence, if met for all i ∈ M, the hypothesis of Theorem 14 is met, and the collection of local linear feedbacks K i fulfils Assumption 2.

NUMERICAL EXAMPLE
In order to illustrate the main result of this paper, consider a global plant composed by four trucks modelled by point masses, aligned in an horizontal plane (see Fig.  1). Each truck is dynamically coupled to its immediate neighbours through springs k ij and dampers c ij . The control objective is to steer the whole system towards an arbitrary equilibrium point using locally applied horizontal forces. This plant is used as a numerical example for various DMPC algorithms, see for example Riverso and Ferrari-Trecate (2012); Baldivieso and Trodden (2016); Hernandez and Trodden (2016); Trodden et al. (2016).
The state vector of the global plant is composed of the horizontal position and velocity of all trucks, and so (x, u) ∈ R 8 × R 4 . A single subsystem is associated to each truck, the local state and input vectors x i , u i represent the position, velocity and force of the corresponding truck. A sampling time of T s = 0.1 is used to discretize the system (the values of the matrices A and B are omitted). Constraint set X i , RPI set Z i .

Case 1: admissible tubes
Suppose first that the following homogeneous local constraints are enforced for all i ∈ M, Table 1 shows a collection of locally stabilizing linear feedbacks, which produce admissible tubes. These local gains correspond to the LQR feedback obtained for (A ii , B ii ), Q i = I 2 and R i = 1. Figure 2 shows that the RPI set Z i is contained inside the constraint set X i for all i ∈ M (the inclusion K i Z i ⊂ U i is also met). In view of Theorem 14 it must be then, that K is globally stabilizing. This is indeed the case, with ρ (F ) = 0.572.  Fig. 3 shows that the same K 1 from Table 1 produces a RPI set Z new 1 that is not inside X 1 (the RPI set for subsystem 3 also increases in size). This implies that, although the collection of local feedbacks is indeed globally stabilizing, Theorem 14 cannot be used to guarantee it.

Case 3: Non-existence
Heterogeneous constraints are not the only source of conservatism that Theorem 14 suffers from. As made explicit by Remark 17, a necessary condition for the tubes to be system-wide admissible is that a square PI set exists. When the loop is closed with K 11 = −2.924 and K 22 = 0.977, Assumption 2 is fulfilled with ρ (F 11 ) = 0.140, ρ (F 22 ) = 0.994 and ρ (F ) = 0.983. However, it is easy to show that there is no square PI set for the closed-loop F , and therefore, no matter the constraints, the tubes corresponding to the block-diagonal linear feedback will never be simultaneously admissible.

CONCLUSION
The properties of many distributed MPC techniques usually rely on structured stabilizability assumptions, and standard notions of invariance. In this paper, a fundamental relation between these two concepts has been made explicit. Theorem 14 shows that the constraint admissibility of very simple local robust controllers is a sufficient condition for the global plant to be block-diagonal stabilizable. The main source of conservatism for Theorem 14 is the structure requirement. A necessary condition for the tubes to be system-wide feasible, is that the closed-loop system accepts a square PI. Future work will be focused on finding conditions over the coupling terms under which such a particular type of PI set exist.