Martin Soyer
email: martin.soyer@centralesupelec.fr

Sorin Olaru
email: sorin.olaru@centralesupelec.fr

Konstantinos Ampountolas
email: k.ampountolas@uth.gr

Sheila Scialanga
email: s.scialanga.1@research.gla.ac.uk

Zhou Fang
email: zhou.fang@renault.com

Periodic Set Invariance as a Tool for Constrained Reference Tracking

Keywords: Predictive Control, Constrained Control, Periodic Invariance, Reference Tracking

This paper explores the concept of periodic invariance and its use for trajectory tracking problems subject to state and input constraints, offering important computational advantages. In principle, traditional techniques based on receding horizon optimization are computationally expensive due to long prediction and optimization horizons, and number of control and state constraints in a constrained control problem. Their complexity is further affected by additional constraints needed to ensure recursive feasibility via a controllable invariant set. Practically, such invariant sets are difficult to obtain off-line and use them on-line. To overcome this problem, this paper suggests to employ periodic invariant sets as a simple set-theoretic tool for constrained reference tracking problems.

INTRODUCTION

This paper presents an alternative approach to the traditional constrained tracking design methods [START_REF] Bemporad | Reference governor for constrained nonlinear systems[END_REF]. Essentially, we aim to develop an attractive framework from the computational point of view that:

• guarantees recursive feasibility for a pre-defined region in the state space; • simplified constraints in the on-line optimization.

The recursive feasibility of constrained tracking can be guaranteed by the characterization of the maximal controllable sets [START_REF] Blanchini | Any domain of attraction for a linear constrained system is a tracking domain of attraction[END_REF]. Any initial state within this set can generate feasible trajectories by exploiting the controlled invariance and subsequently optimized with respect to a tracking criterion [START_REF] Blanchini | Any domain of attraction for a linear constrained system is a tracking domain of attraction[END_REF]). We note however, that the characterization of the maximal controllable set is a notorious complex problem both in terms of off-line effort and complexity of the representation, which subsequently affects the on-line computational effort. As an alternative to the explicit use of the maximal controllable set, model predictive control (MPC) has been widely used with its receding horizon formulation. Recursive feasibility in MPC is related to the existence of an invariant terminal set. In the tracking case, this terminal set is parameterized by a virtual feasible trajectory [START_REF] Olaru | Compact explicit mpc with guarantee of feasibility for tracking[END_REF][START_REF] Limon | Tracking model predictive control[END_REF][START_REF] Falugi | Model predictive control for tracking randomly varying references[END_REF][START_REF] Chisci | Dual mode predictive tracking of piecewise constant references for constrained linear systems[END_REF]. This parametrization leads to high on-line computational effort and has been the subject of research in different studies.

Reducing the complexity of the maximal controllable set or the terminal constraints in MPC by means of approximations can compromise the invariance property and consequently the recursive feasibility. The present paper revisits the concept of periodic invariance [START_REF] Lee | Constrained robust model predictive control based on periodic invariance[END_REF]) that allows the relaxation of constraints for a finite number of iterations before reinforcing into the constraints. This property preserves the recursive feasibility of optimization-based tracking control by maintaining a low computational effort.

Among constrained control techniques, the recent Interpolation Based Control (IBC) developed in [START_REF] Nguyen | Implicit improved vertex control for uncertain, time-varying linear discrete-time systems with state and control constraints[END_REF][START_REF] Scialanga | Decentralised control of interconnected systems: An interpolation based approach[END_REF][START_REF] Scialanga | Interpolating constrained control of interconnected systems[END_REF][START_REF] Scialanga | Interpolating control toolbox (ict)[END_REF]) is shown to be faster than traditional optimisation-based techniques such as MPC, while preserving stability and performance. However its extension to tracking problems is based on on-line operations involving invariant sets [START_REF] Soyer | Interpolation based control for reference tracking under constraints[END_REF]. This paper explores how IBC can be enhanced via the periodic invariance concept to deal with the constrained reference tracking problem, and consequently to maintain a low computational effort, compared to optimization-based methods like MPC. By using the notion of strong and weak periodic invariance, we present efficient algorithms for the tracking problem that guarantee the recursive feasibility of IBC.

Notation: A Polytope P in the H-Representation is a set P = {x ∈ R n |F x ≤ g} where F ∈ R q×n and g ∈ R q . A Polyhedron denotes a bounded polytope. A Polyhedron P in V-Representation is a set P = { n i λ i v i /∀i ∈ {0, . . . , n} λ i ≥ 0} where {v 1 , ..., v n } are the vertices. The weighted 2-norm . Q is defined as : ∀x ∈ R n x 2 Q = x T Qx where Q ∈ R n×n is positive definite. 1, N
is the set of integers between 1 and N .

PROBLEM FORMULATION

The dynamical system will be represented in terms of a linear discrete-time model :

x k+1 = Ax k + Bu k , subject to: x k ∈ X, u k ∈ U, ∀ k, (1)
where X ⊂ R n and U ⊂ R m are compact convex sets containing the origin in their respective interior. Definition 1. (Positive invariance). A set C ⊂ R n is said to be positively invariant for the autonomous system

x k+1 = f (x k ) if for any x 0 ∈ C ⇒ x k ∈ C, ∀ k ∈ Z + . Definition 2. (Controlled invariant set). A set C ⊂ X is
said to be controlled invariant with respect to the constrained system (1) if for any state x 0 ∈ C there exists a sequence u k ∈ U such that x k ∈ C, ∀k ∈ Z + . Definition 3. (Maximal Controllable Set to Ω). Given a proper controlled invariant set Ω ⊂ X we define the Maximal controllable set to Ω, denoted C(Ω), to be the collection of initial states x 0 ∈ X for which there exists a finite admissible control sequence that brings x 0 to Ω.

Practically, the controlled invariant set is chosen to be as large as possible in X to avoid conservativeness. The maximal controllable set can be approached off-line with an iterative procedure which implies projections of polyhedrons that can lead to a complex representation [START_REF] Nguyen | Improved vertex control for timevarying and uncertain linear discrete-time systems with control and state constraints[END_REF]). The objective in the remaining of the paper is to introduce optimization-based tracking formulations building on a generalised invariance property with the goal to circumvent the off-line and on-line complexity of the maximal controllable set.

We will present the main contribution by revisiting the concept of periodic invariance [START_REF] Lee | Constrained robust model predictive control based on periodic invariance[END_REF] that will be used to overcome the complexity induced by the construction of the maximal controllable set. A difference will be made in between a strong and weak version of the periodic invariance, the former implying the later. In the following, periodic invariance will be denote as p-invariance. Definition 4. (Strong p-invariance). A set B ⊂ X containing the origin is said to be strongly p-invariant with respect to the constrained system (1) if there exists p ∈ N * such that for all state x k ∈ B, there exists a control sequence (u k , ..., u k+p-1 ) ∈ U p such that x k+p ∈ B and (x k+1 , ..., x k+p-1 ) ∈ X.

The notion of p-invariance which assumes the same periodicity index for any point in the set. We show next that this characteristics can be relaxed to a certain extent and the tracking control associated carry on with simple modifications.

Definition (Weak p-invariance) : Given a compact convex set B ⊂ R n and p ∈ N * , B is said to be weakly p-invariant with respect to the system (1) if for any state x k ∈ B there exists r ≤ p and a control sequence (u k , ..., u k+r-1 ) ∈ U r such that x k+r ∈ B and (x k+1 , ..., x k+r-1 ) ∈ X.

In other words, any state in B returns into B in at most p number of steps.

STRONG p-INVARIANCE

The concept of strong p-invariance can be relevant to the considered systems and the tracking objective whenever maximal controllable set is replaced by a simpler approximation thanks to the following theorem. Theorem 5. Let Ω be a controlled invariant set containing the origin and C N (Ω) be the maximal controllable set to Ω. Given a set B such that Ω ⊆ B ⊂ C N . There exists an integer p ∈ N * such that B is strongly p-invariant.

Proof: B ⊂ C N (Ω), so for any initial state x k ∈ B there exists a control sequence (u k , ..., u k+N -1 ) ∈ U N such that x k+N ∈ Ω ⊂ B. By fixing the periodicity index to the maximal number of time steps N to reach Ω from B the existence is proved. 2

In other words, a simpler inner approximation of the maximal controllable set, while contains the attractive controlled invariant set, is necessarily strongly periodic invariant.

Practical Construction of Strong p-Invariance

Given B ⊂ X a convex polyhedron containing the origin with V = {v 1 , ..., v Nv } its vertices and their cardinality N v ∈ N. The strong p-invariance of the set B with respect to (1) can be computed by Algorithm 1 below, which considers all the vertices of the candidate set B and tests the minimal contraction factor that can be obtained jointly along a time window of length p s . The search for this contraction factor leads practically to a simple Linear Programming (LP) problem.

Under the assumption that the candidate set is contained in a controllable set B ⊂ C N (Ω), the procedures ends in finite time. If this assumption does not hold, the condition λ s B ⊃ X guarantees that the algorithm will terminate in a finite number of steps. In this framework, it is important to observe that an explicit description of a controllable set C N (Ω) is not necessary in the above construction.

Algorithm 1 Strong p-Invariance

Input: The pair (A, B), the sets X, U and B Output:

The periodicity index p p s = 0, λ s = 1 while λ s ≥ 1 do p s = p s + 1 Solve: minimize λ s , u i λ s subject to A k-1 v i + k-2 j=0 A j Bu i,k-2-j ∈ X ∀k ∈ 2, p s , i ∈ 1, N v A ps v i + ps-1 j=0 A j Bu i,ps-1-j ∈ λ s B, i ∈ 1, N v (u vi ) i∈ 1,Nv ∈ U ps end while {λ s B ⊃ X}

Strong p-Invariance Based Reference Tracking

Based on the construction of strong p-invariance, let us now consider that the tracking control problem can use the existence of a p-invariant set B satisfying B ⊂ C ⊂ X.

A prototype receding-horizon optimization for referencetracking, which employs the periodic invariance for a linear prediction model, will be denoted O(N h , p, x k ) and formulated as follows :

J p (x k ) = minimize (u k , ..., u k+N h -1 ) N h i=1 x ref k+i -x k+i 2 Q subject to u k+i ∈ U , x k+i ∈ X ∀i ∈ 1, . . . , M , x k+p ∈ B, (2) with M = max(N h , p). Proposition 6. O(N h , p, x k ) is feasible for all x k ∈ B.
Proof: For any state x k ∈ B, there exists a control sequence (u k , ..., u k+p-1 ) ∈ U p such that (x k+1 , ..., x k+p-1 ) ∈ X and x k+p ∈ B. Thus, in the case of a prediction horizon with N h ≤ p, the problem is feasible.

If N h > p, the argument is slightly more elaborated and needs to rely on the invariance property of the controlled invariant superset C. Indeed by construction B ⊂ C ⊂ X, which implies the existence of a sequence (u k , ...,

u k+N h -1 ) ∈ U N h such that (x k+1 , ..., x k+N h -1 ) ∈ C ⊂ X. 2
Despite the result stated in Proposition 6, one cannot guarantee the recursive feasibility of the control strategy that implements the first part of the optimum control argument. This is because the one-step invariance property on B is not certified, and thus the feasibility of the optimization (2) on B does not imply the feasibility at iteration k + 1, . . . as long as x k+1+p ∈ B does not hold.

To overcome the absence of recursive feasibility, a simple procedure can be constructed to enhance the periodic invariance property. If O(N h , p, x k ) designates the optimization (2), the main idea is to monitor the result of this optimization and to switch to a safe return strategy within the set B whenever the closed-loop trajectory leaves B.

In order to simplify the switching criterion, the cost functions J i (x k ) and J p (x k ) will be compared for any x k ∈ B. As long as the first one is less costly the procedure apply the first component of its control law. The following proposition provides a criterion that separates the case where the system remains in B from the case it leaves B. Proposition 7. Given the optimized costs J 1 (x k ) (resp

J p (x k )) of optimizations O(N h , 1, x k ) (resp O(N h , p, x k )). If J p (x k ) < J 1 (x k ) then x k+1 ∈ B. Proof: If U * p is the optimal solution of O(N h , p, x k ), assume x k+1 ∈ B, then, every constraints of O(N h , 1, x k ) are satisfied, U * p is a feasible solution of O(N h , 1, x k ).
Thus, the optimization of O(N h , 1, x k ) provides a better solution, and

J 1 (x k ) ≤ J p (x k ). 2
With this preliminary result the description of the procedure using strong p-invariance for tracking with recursive feasibility properties is presented in Algorithm 2.

Algorithm 2 Strong p-Invariance Reference Tracking Input x 0 ∈ B ⊂ X, N simu ,N h ,(A, B),X, U,B Output (x k ) k=0,...,Nsimu ,(u k ) k=0,...,Nsimu-1 k = 1, i = 1 repeat for each k if i = 1 then Solve O(N h , 1, x k ) → (J * 1 , (u 1 k , ..., u 1 k+N h -1 )) * if J * 1 < J * p then x k+1 = Ax k + Bu 1 k else x k+1 = Ax k + Bu p k i = p end if else Solve O(N h , i, x k ) ← (J * i , (u i k , ..., u i k+N h -1 )) * if J 1 < J i then x k+1 = Ax k + Bu 1 k i = 1 else x k+1 = Ax k + Bu i k i = i -1 end if end if k = k + 1 until k = N simu
Proposition 8. The control law resulting from the recursive implementation of the first input of the optimal control sequence according to Algorithm 2 is recursively feasible for any initial state x 0 ∈ B.

Proof: Assume the procedure is feasible at step k. Then the current state becomes x k+1 ∈ X and two cases have to be considered :

• If x k+1 ∈ B, then O(N h , p, x k+1
) is feasible thanks to Proposition 6. • If x k+1 ∈ B, then x k+1 is part of a state sequence that began in B. There exists an integer q ≤ p -1 such that the state x k+1-q ∈ B. So there exists a control sequence (u k+1-q , ..., u k+1 , ..., u k-q+p-1 ) ∈ U p such that x k+1-q+p ∈ B and (x k+2-q , ..., x k-q+p ) ∈ X p-1 .

Ignoring the tail, we conclude on the existence of a control sequence (u k+1 , ..., u k+1-q+p ) ∈ U p-q such that x k+2-q+p ∈ B. This concludes the proof as long as O(N h , p -q, x k+1 ) is feasible. 2

WEAK p-INVARIANCE

The next result formalize the relationship between strong and weak version of the periodic invariance. Theorem 9. If B is strongly p-invariant, then B is weakly p-invariant. Alternatively, if p s (resp p w ) denotes the result of the computation of strong periodic invariance (resp weak periodic invariance), then p w ≤ p s .

Proof: The proof is direct by observing that in the definition of weak invariance q = p is a feasible choice for the number of steps for the return sequence. 2 Construction of Weak p-invariance: Given a polyhedron B ⊂ X with set of vertices V = {v 1 , ..., v Nv } and cardinality N v ∈ N. The weak p-invariance index can be computed by Algorithm 3.

Algorithm 3 Weak p-invariance

Input: The pair (A, B), the sets X, U and B Output: the periodicity index p for v i ∈ V do p i w = 0; λ w = 1 while λ w ≥ 1 do

p i w = p i w + 1 Solve: minimize λ w , (u i ) i∈ 1,p i w -1 λ w subject to A k-1 v i + k-2 j=0 A j Bu k-2-j ∈ X, ∀k ∈ 2, p i w A p i w v i + p i w -1 j=0 A j Bu p i w -1-j ∈ λ w B, i ∈ 1, p i w -1
end while end for p w = max(p 1 w , ..., p Nv w )

Proposition 10. Given a convex compact polyhedron B containing the origin, and {p 1 , ..., p Nv } and the periodicity of vertices {v 1 , ..., v Nv } computed by Algorithm 3 is thus inherited by the entire set. Then, for any state x k ∈ B,one can use the same periodicity as its vertex component with highest periodicity.

A tracking procedure using weak periodic invariance and based on the optimization (2) can be proposed as in Algorithm 4. The principle behind the properties of recursive feasibility of the tracking procedure is summarized next, the proofs following the arguments in Section 3:

• If x k ∈ B, the cost functions for an optimization problem with 1-step invariance constraints and p-step invariance constriants are compared. • If the system leaves B, then every costs from 1-step to p-steps return to B are compared. In other words, the validation of the weak periodic invariance is tested at each iteration in order to find the shortest return path into B.

TRACKING IBC WITH p-INVARIANCE

Interpolation-Based Control (IBC) was originally developed in [START_REF] Nguyen | Improved vertex control for timevarying and uncertain linear discrete-time systems with control and state constraints[END_REF][START_REF] Nguyen | Implicit improved vertex control for uncertain, time-varying linear discrete-time systems with state and control constraints[END_REF]; [START_REF] Nguyen | Constrained control of uncertain, time-varying, discrete-time systems[END_REF] as an enhancement of Vertex Control established in [START_REF] Gutman | Admissible sets and feedback control for discrete-time linear dynamical systems with bounded controls and states[END_REF]. It guarantees the same region of attraction as predictive control as well as structural property (smoothness) for set-point regulation problems. The IBC adaptation for tracking is provided in [START_REF] Soyer | Interpolation based control for reference tracking under constraints[END_REF] and we point the reader to this reference for the details.

The IBC design is built on two convex compact controlledinvariant sets containing the origin Ω o and Ω v , where Ω o ⊂ Ω v ⊂ X. Ω o is called the inner set and Ω v is called outer set. These inner and outer sets have to be re-scaled and translated in order to contain the origin of the dynamical system governing the tracking error. The periodic invariance property is preserved by homogeneous transformations.

Algorithm 4 Weak p-Invariance Reference Tracking Input x 0 ∈ B ⊂ X, N simu ,N h , (A, B) ,X, U,B Output (x k ) k=0,...,Nsimu ,(u k ) k=0,...,Nsimu-1 k = 1, i = 1 repeat for each k if i = 1 then Solve O(N h , 1, x k ) → (J * 1 , (u 1 k , ..., u 1 k+N h -1 )) * Solve O(N h , p, x k ) → (J * p , (u p k , ..., u p k+N h -1 )) * if J * 1 < J * p then x k+1 = Ax k + Bu 1 k else x k+1 = Ax k + Bu p k i = p end if else Solve O(N h , i, x k ) → (J * i , (u i k , ..., u i k+N h -1 )) * Solve O(N h , i -1, x k ) → (J * i-1 , (u i-1 k , ..., u i-1 k+N h -1 )) * . . . Solve O(N h , 1, x k ) → (J * 1 , (u 1 k , ..., u 1 k+N h -1 )) * q * = arg min q∈ 1,i (J q ) x k+1 = Ax k + Bu q * k i = i -1 end if until k = N Simu
Theorem 11. (Homogeneity of periodic invariance). Given B strongly p-invariant (p ∈ N * ) with respect to (X, U), then for all α ∈ [0, 1], αB is strongly p-invariant with respect to (αX, αU).

The IBC scheme is applied within a (constrained) admissible framework, thus the reference has to be feasible. In the following procedure, a virtual reference will be considered, generated within an optimization-based reference governor [START_REF] Gilbert | Discrete-time reference governors and the nonlinear control of systems with state and control constraints[END_REF]. Given the outer set Ω v and assume its strong p-invariance, the virtual reference and the scaling factor are solutions of the optimization problem R(

x ref k , x k ): min (x k , ūk , α k ) x ref k -xk 2 s.t. xk = Ax k + B ūk , ūk ∈ (1 -α k )U, x k ∈ {x k } ⊕ α k Ω v ⊂ Ω v . (3)
The main idea is to solve, for the current state x k in Ω v , the optimization problem R(x ref k , x k ) and once the admissible xk and ūk are computed to regulate the tracking error by solving a IBC problem. This tracking error will be defined as k = xk -x k ∈ α k Ω v and two cases have to be considered:

• if k+1 /
∈ Ω v as a result of the IBC at step k then we hold xk and ūk for maximum p steps in order to allow k+i ∈ Ω v for some 0 < i ≤ p. Practically, at each iteration i, we check if k+i ∈ B and if this is the case we release xk+i and ūk+i • if k+1 ∈ Ω v as a result of the IBC at step k we start from the beginning the procedure with virtual reference design and IBC.

Practically, the optimization (3) generates a virtual trajectory which are fixed points of the system (1). Whenever the reference to be tracked x ref k converges to a fixed point, it can be shown that xk converges to a feasible fixed point x ∈ X with respect to an admissible control ū ∈ U and the the tracking error k asymptotically decreases to zero using the IBC. The formal proofs are adapting the IBC properties for the case of p-invariance similar to the previous sections and are not presented for brevity.

N (Ω o ) = {x ∈ R n |F N x ≤ g N }.
The candidate p-invariant set is represented by a simple inner approximation of C N (Ω o ), represented in blue in Fig. 1. The same set, denoted Ω v , is used as an outer set for the p-invariant MPC and IBC strategies.

Time-Varying (Dynamic) Trajectory

In the first simulation scenario, the reference is generated using the dynamical model ( 4) based on a excitation signal which violates drastically the imposed constraints. As a result, the time-varying reference trajectory leaves the state constraints set as illustrated by dashed trajectories in Fig. 1. The initial state of the system is selected on the frontier of Ω v on a extreme state (corresponding to zero speed if the state is interpreted in terms of positionspeed coordinates). For the comparative study, strong and weak p-invariant sets have been constructed and the p index has been computed using Algorithms 1 and 3 to be p = 14. Using this low complexity set (4 vertices) the reference tracking optimization has been solved according to the Algorithms 2 and 4 and the results confirm the recursive feasibility of both receding-horizon referencetracking algorithms. Even if globally the behaviour is similar, a slight difference can be observed when the state leaves B (the signals are depicted with respect to the time in Fig. 2).

Static Reference Trajectory

In this case, the reference is a fixed-point out of the admissible set and this reference commutes to a symmetric fixed point out of the admissible set at a regular time interval. The invariant set Ω v is the strongly p-invariant set with index p = 8. Figs 3 and4, compare strong and weak p-invariant based reference tracking which provide a recursive feasible control law and good performances. In order to complete the design with stability (convergence) guarantees for such piece-wise constant references, an IBC for tracking is implemented using the periodic invariance notion. The closed-loop performance is depicted in Fig. 5, 6. It is important to observe that although the virtual reference is a fixed point, it is updated at each iteration, and thus leads to a sequence of feasible set-points for the IBC procedure.

CONCLUSIONS

The paper presented a novel scheme for the constrained reference tracking control problem. The proposed optimization framework guarantees recursive feasibility through the use of low complexity periodic invariant sets that replace the costly (in terms of computation and complexity) approximations of the maximal controlled invariant sets.

Moreover it has been shown that the receding horizon optimization can be further enhanced by an interpolationbased control scheme, and thus it guarantees the convergence in the case of piecewise constant reference signals.

  x 1 (k) ≤ 2.6, -3 ≤ x 2 (k) ≤ 3, -5 ≤ u(k) ≤ 5. (5) The two techniques presented in the paper are considered for simulation and comparison: Strong and weak pinvariant reference tracking and periodic IBC. Then two types of trajectories are presented: • A dynamically generated trajectory with the goal to test and illustrate the recursive feasibility and the reactivity of both tracking algorithms; • A sequence of switching of fixed points which aims to test (aside the recursive feasibility) the convergence properties. The inner polyhedral set Ω o = {x ∈ R n |F o x ≤ g o } considered is the Maximal Admissible Set (MAS) with respect to a linear feedback law u k = -[16.65 6.23] x k and has been constructed based on the procedure given in Gilbert and Tan (1991) in polyhedral form. In order to illustrate the complexity of the the maximal controllable set, a controlled invariant approximation C(Ω o ) is computed as a N -step controllable set (N ∈ N * ), thanks to the iterative procedure proposed in Nguyen et al. (2011) leading to the polyhedral form: C

Fig. 1 .

 1 Fig. 1. Trajectories in the state space of reference (dashed), Strong p-invariance procedure (blue) and Weak pinvariance procedure (red).

Fig. 2 .

 2 Fig. 2. Temporal trajectories of reference (dashed), Strong p-invariance (blue) and Weak p-invariance (red). Right: Control action of Strong p-invariance (blue) and Weak p-invariance (red).

Fig. 3 .

 3 Fig. 3. Trajectories in the state space of reference (dashed), Strong p-invariance (blue) & Weak p-invariance (red).

Fig. 4 .

 4 Fig. 4. Temporal trajectories of reference (dashed), Strong p-invariance (blue) and Weak p-invariance (red). Left: states; right: control.

Fig. 5 .

 5 Fig. 5. Trajectories in the state space of reference (dashed), virtual x (blue cross) and state trajectory (red).

Fig. 6 .

 6 Fig.6. Left: time trajectories of reference (dashed), virtual trajectory x (blue) and and state trajectory (red). Right: Control action of periodic invariant IBC.


Mathias Serieye
email: mserieye@laas.fr

Carolina Albea-Sanchez

Alexandre Seuret
email: aseuret@laas.fr

Marc Jungers
email: marc.jungers@univ-lorraine.fr.

Synchronization on a

Keywords: Control of switched systems, Lyapunov methods, Stabilization of nonlinear systems, Multi-agent systems, Complete graph, Consensus, State synchronization

published or not. The documents may come

INTRODUCTION

Over the last few decades, problems of consensus and synchronization in multi-agent systems have aroused a great deal of interest in the systems and control community, mainly motivated by a wide range of applications in physics, biology and engineering. The nature of these problematics is to reach an agreement collectively about some quantity of interest. The authors in [START_REF] Scardovi | Synchronization in networks of identical linear systems[END_REF] characterize the terms consensus and synchronization frequently used in the context of multi-agent system. In (Sinafar et al., 2020a), the authors resumed this as a categorization of multi-agent problems: the complexity in network topology and the complexity in agents dynamics. In the case of consensus control problems, the focus is on the communication constraints rather than the individual system dynamics. Hence, it is common to find in the literature works where the dynamics of agents are described by integrators [START_REF] Shi | Reaching an optimal consensus: Dynamical systems that compute intersections of convex sets[END_REF]; by double-integrators [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF][START_REF] Ren | Consensus algorithms for doubleintegrator dynamics[END_REF]; or by linear systems [START_REF] Fax | Information flow and cooperative control of vehicle formations[END_REF][START_REF] Wieland | On consensus in multi-agent systems with linear high-order agents[END_REF]. The challenges are then to deal with the communication graph features where the connection can be time-dependent [START_REF] Moreau | Stability of multiagent systems with timedependent communication links[END_REF] ; the agents can suffer from communication delay in the network (Olfati-Saber and Murray, 2004) or switching topology [START_REF] Cervantes-Herrera | A distributed control design for the output regulation and output consensus of a class of switched linear multi-agent systems[END_REF][START_REF] Wang | Robust coordination control of switching multi-agent systems via output regulation approach[END_REF]. In contrast to consensus, the emphasis of the research on synchronization is on the individual dynamics rather than the communication limitations. It is possible to find in the literature works on nonlinear multiagent systems [START_REF] Zhang | Sliding mode control for a class of nonlinear multi-agent system with time delay and uncertainties[END_REF][START_REF] Liu | Distributed output-feedback control of nonlinear multi-agent systems[END_REF] or studies on robust synchronization guarantees [START_REF] Dal Col | H ∞ control design for synchronisation of identical linear multi-agent systems[END_REF]. However, most of the existing works have set aside

This work has been partially funded under grant projet ANR-18-CE40-0022-01 (Projet HISPALIS), projet PDI2019-105890RJ-100 (Project HYCAM) and projet ANR 18-CE40-0010-02 (Project HANDY).

nonlinear systems with switching topology, yet relevant in the case of microgrid where agents can represent the electronic power converters [START_REF] Albea | Hybrid dynamical control based on consensus algorithms for current sharing in dc-bus microgrids[END_REF][START_REF] De Persis | A power consensus algorithm for DC microgrids[END_REF][START_REF] Meng | Modeling and sensitivity study of consensus algorithm-based distributed hierarchical control for dc microgrids[END_REF].

Switched systems, as a subclass of hybrid systems [START_REF] Goebel | Hybrid Dynamical Systems: Modeling, Stability, and Robustness[END_REF], consist in the association of a finite set of dynamics with a switching rule that assignes at each time instant which mode is active [START_REF] Liberzon | Switching in systems and control[END_REF]. This kind of systems have generated a rich study concerning their stability to the origin [START_REF] Daafouz | Stability analysis and control synthesis for switched systems : A switched Lyapunov function approach[END_REF][START_REF] Sun | Stability Theory of Switched Dynamical Systems[END_REF], stabilization [START_REF] Geromel | Stability and stabilization of discrete-time switched systems[END_REF] or stabilizability [START_REF] Fiacchini | On the stabilizability of discrete-time switched linear systems: novel conditions and comparisons[END_REF]. Investigations on limit cycles for switched affine systems were mainly done in the continuous-time domain [START_REF] Johansson | Limit cycles with chattering in relay feedback systems[END_REF][START_REF] Rubensson | Convergence to limit cycles in hybrid systems -an example[END_REF] and recently, results have been developed in the discrete-time domain [START_REF] Egidio | Global asymptotic stability of limit cycle and H 2 /H ∞ performance of discrete-time switched affine systems[END_REF]Serieye et al., 2020).

Since modal control is more challenging, especially for nonlinear systems, only few contributions can be found in the literature. Recently, works on multi-agent systems where agents are switched affine systems have aroused. In (Sinafar et al., 2020b,a), the authors have proposed switching control laws based on averaged models or based on linear combination of state matrices. These assumptions are not necessary when considering the stabilization of switched affine systems as it has been proposed in (Serieye et al., 2020). Hence, through this paper, we are aiming at extending the results proposed in (Serieye et al., 2020) in the case of synchronization of a group of switched affine systems interacting thanks to an all-to-all communication configuration. This work has for ambition to be a first step to distributed control of switched affine multi-agent systems.

The paper is organized as follows: in Section 2 the problem is formulated by presenting the switched affine systems and the multi-agent system. In Section 3, one can find some preliminaries on limit cycle useful afterwards. Then, centralized switching control laws are proposed in Section 4 where proofs are given in addition. Finally, before concluding, an academical example offers illustrations on the effectiveness of our method.

Notations: Throughout the paper, N denotes the natural numbers; R, the real numbers; R n , the n-dimensional Euclidean space; R n×m , the set of all real n × m matrices and S n the set of symmetric matrices in R n×n . For any n and m in N, matrices I n , 1 n and 0 n,m denote the identity matrix of R n×n , the vector in R n , whose components are all equal to 1 and the null matrix of R n×m , respectively. When no confusion is possible, the subscripts of these matrices that precise the dimension, will be omitted. For any matrix M of R n×n , the notation M 0, (M ≺ 0) means that M is symmetric positive (negative) definite and det(M) represents its determinant. The symbol ⊗ denotes the Kronecker product, for further details on its properties, please refer to [START_REF] Horn | Topics in matrix analysis[END_REF]. • denotes the Euclidean norm. For a symmetric positive definite matrix P and a vector x, we denote x P =

√

x Px, the weighted norm. Let G = (V, E) be a undirected graph. V and E denote respectively the set of nodes and the set of edges. The elements e i, j of E ⊆ V × V specify the incidence relation between distinct pairs of nodes v i , v j . We denote with N the index set of V and with |N| its cardinality.

PROBLEM FORMULATION

Switched affine agents

Consider a set of the discrete-time switched affine systems or agents governed by

x ,k+1 = A σ ,k x ,k + B σ ,k , ∀ ∈ N, σ ,k = u k ∈ K (1)
where, for each ∈ N, x ,k ∈ R n is the state vector considered at time k in N. Variable σ ,k ∈ K characterizes the active mode among the K subsystems and matrices A σ ,k and B σ ,k present appropriate dimension. One feature of this class of systems relies on the fact that the selection of the active mode σ ,k is the only possible control action available at each agent, achieved through the selection of the input u k .

Multi-agent representation

Consider a group of |N| homogeneous switched systems where each agent i ∈ N follows the dynamic given by (1) and has, a priori, its own switching rule σ i,k . A compact representation of such multi-agent systems can be defined with an extended state vector

x k = x 1,k . . . x |N|,k ∈ R n|N| .
Then, it is possible to express the collective dynamic as follows

x k+1 = A(σ k )x k + B(σ k ).
(2) In this representation, the active modes are gathered in a single vector σ k = σ 1,k , . . . , σ |N|,k ∈ K |N| and the matrices A(σ k ) and B(σ k ) of system (2) are given by

A(σ k ) = diag(A σ 1,k , . . . , A σ |N|,k ), B(σ k ) = B σ 1,k , . . . , B σ |N|,k . (3)
The stabilizability of multi-agent systems can depend on the interaction between agents. We aim at designing a centralized switching control law that synchronizes some homogeneous systems. In this view, we consider the following assumption Assumption 1. The graph G is complete, which roughly speaking means that all agents are connected with all agents.

From Assumption 1, one can simplify the control law as a global switching control law, i.e. every agent is controlled with the same switching law u(x k ) ∈ K and

σ k = 1 |N| ⊗ u(x k ).
Therefore, the dynamics of the overall system are reduced to

A(σ k ) = I |N| ⊗ A σ k and B(σ k ) = 1 |N| ⊗ B σ k .
(4) The objective throughout this paper is to design a suitable shared control law that ensures the global asymptotic state synchronization of system (2), i.e. that all agents converge to the same trajectory as k tends to infinity. More precisely, this means that lim

k→+∞ x ,k -x ,k = 0, ∀( , ) ∈ N 2 . ( 5
)
More importantly, the objective is to design a state-dependent control law that is based on the model of the agent (1), not on the collective dynamics (2). Indeed there exist many contributions dealing with the stabilization of such a class of systems such as in [START_REF] Deaecto | Stability analysis and control design of discrete-time switched affine systems[END_REF][START_REF] Hetel | Robust sampled -data control of switched ffine systems[END_REF]. Most of them relies on the resolution of LMI conditions. Therefore, if the number of agents is too large, solving such a problem can be computationally difficult.

As a first step in this direction, Assumption 1 is made so that some first contributions are provided in the context of the synchronization of a set of switched affine systems. The relaxation of this assumption is kept to future work.

PRELIMINARIES ON LIMIT CYCLES OF SWITCHED AFFINE SYSTEMS

Limit cycles

This subsection clarifies the notion of limit cycle considered in this paper. Indeed, it is known that hybrid systems can exhibit a periodic behaviour. Likewise, we are interested in the timevarying steady states of switched affine systems which seem to have such behaviour when the control action is constrained by, for example, periodic updates (Serieye et al., 2020). A limit cycle generally refers to an isolated closed trajectory [START_REF] Sun | Existence and uniqueness of limit cycle for a class of nonlinear discrete-time systems[END_REF][START_REF] Strogatz | Nonlinear Dynamics and Chaos: With Applications to Physics[END_REF] or to a limit set which is a closed orbit [START_REF] Rubensson | Convergence to limit cycles in hybrid systems -an example[END_REF]. To fit with the hybrid nature of system (1), we first need to give few definitions. Definition 1. A cycle, ν, of a switched affine system refers to a periodic switching function from N to K. We define

N ν = min N ∈ N * s.t. ν(i + N) = ν(i), ∀i ∈ N D ν = {1, . . . , N ν }
where N ν stands for the minimum period of the sequence ν and D ν is its minimum domain. Definition 2. Denote the set of cycles from N to K by

C := {ν : N → K, s.t. ∃N ∈ N * , ∀i ∈ N, ν(i + N) = ν(i)} .
We introduce the following modulo notation to ease the readability : this hybrid trajectory is a limit cycle where its components are given by

i ν = ((i -1) mod N ν ) + 1, for any i ∈ N, i ≥ 1. That is, in particular, i ν = i, for any i ∈ D ν and N ν + 1 ν = 1. Definition 3. For a given cycle ν ∈ C, if there exists an isolated closed orbit N → K × R n , k → (σ k , x k ) which is a solution of (1) such that σ k = ν(k + δ) (where δ is a possible shift), then
ρ i+1 ν = A ν(i) ρ i + B ν(i) , ∀i ∈ D ν . ( 6
)
Figure 1 illustrates the previous definition, where one can see that the application of the cycle ν. Equations ( 6) can be written in a more compact formulation as follows

(I nN ν -º ν )ρ := » ν , (7)
where ρ = ρ 1 , ρ 2 , . . . , ρ N ν and where matrices º ν and » ν are given by

º ν =                    0 . . . 0 A ν(N ν ) A ν(1) . . . 0 0 . . . . . . . . . . . . 0 . . . A ν(N ν -1) 0                    , » ν =                 B ν(N ν ) B ν(1) . . . B ν(N ν -1)                 .
In the sequel, we will first present several results related to the asymptotic stability of the limit cycle defined by a given cycle ν selected a priori.

Stabilization to a limit cycle

In this part, the problem of stabilizing a single agent governed by (1) to limit cycle is addressed. Therefore in this section, for the sake of simplicity, the subscript related to the agent will be omitted (i.e. x ,k = x k ). There are few recent contributions on the subject [START_REF] Egidio | Global asymptotic stability of limit cycle and H 2 /H ∞ performance of discrete-time switched affine systems[END_REF]Serieye et al., 2020) where the authors share similar methods and come up with different switching control laws. We invoke here (Egidio et al., 2020, Theorem 2) to adduce some features about the results the author have proposed.

Theorem 1. For a given cycle ν in C, assume there exist matrices P i in S n , i ∈ D ν solution to the following inequalities

P i 0, A ν(i) P i+1 ν A ν(i) -P i ≺ 0, ∀i ∈ D ν .
(8) Then, the following statements hold:

(i) Eq. ( 7) admits a unique solution ρ, defining the limit cycle. (ii) Attractor A ν = i∈D ν {ρ i }, is globally exponentially stable for system (1) with the periodic, time-dependent, switching control law

u(k) = ν(k + δ), δ ∈ D ν , (9) (iii) Moreover, lim k→+∞ x k -ρ ν(k+δ) = 0.
This theorem refers to the stability analysis of periodic systems referring to the works of [START_REF] Bolzern | The periodic Lyapunov equation[END_REF]). In the present paper, the last item (iii) has been added with respect to (Egidio et al., 2020, Theorem 2).

Proof. We will do the proof of the theorem item by item. Proof of (i): Let us consider P = diag (P i ) i=1,...,N ν solution to (8). Therefore, we can see that

º ν Pº ν -P = diag A ν(i) P i+1 ν A ν(i) -P i i=1,...,N ν ≺ 0.
Hence, matrix º ν is Schur stable. This implies, in particular, that 1 is not an eigenvalue of º ν . Consequently, matrix I nN -º ν is nonsingular and equation ( 7) admits a unique solution.

Proof of (ii): Let us consider, without loss of generality, that δ = 0 and the following time-dependent Lyapunov function candidate, V td given by

V td (x k , k) := x k -ρ ν(k) P ν(k) x k -ρ ν(k) , ∀x k ∈ R n , ( 10
) and its forward increment given by ∆V td (x k , k) = V td (x k+1 , k + 1) -V td (x k , k). Note that the expression of V td (x k+1 , k + 1) exposes the term x k+1 which can be manipulated as follows by invoking ( 6)

x k+1 = A ν(k) x k +B ν(k) = A ν(k) x k -ρ ν(k) +A ν(k) ρ ν(k) +B ν(k) =ρ k+1 ν . (11)
Hence, we can obtain the following expression of ∆V td (x k , k)

∆V td (x k , k) = x k -ρ ν(k) A ν(k) P k+1 ν A ν(k) -P ν(k) x k -ρ ν(k) .
The latter expression together with condition (8) respected allow us to conclude that the Lyapunov function is decreasing for all x k ∈ R n \A ν which proves that A ν is globally exponentially stable for system (1).

Proof of (iii): This item simply results from the fact that V tends to zero as k tends to infinity.

Remark 1. The convergence rate of the solution to system (1) to the limit cycle is characterized by the eigenvalues of the monodromy matrix defined by i∈D ν A ν(i) .

The following theorem presents an alternative control law for the same system. The difference is that the control law does not depend on the time but is only computed based on the value of the state. This theorem is taken from (Serieye et al., 2020). Theorem 2. For a given cycle ν, assume there exist matrices {P i } i∈D ν in S n , solution to (8). Then, the following statements hold:

(i) Eq. ( 7) admits a unique solution ρ, defining the limit cycle.

(ii) Attractor A ν = i∈D ν {ρ i } is globally exponentially stable for system (1) where {ρ i } i∈D ν are given by the solution to (7) with the state-feedback control law

u(x) ∈ ν (θ) , θ ∈ argmin i∈D ν (x-ρ i ) P i (x-ρ i ) ⊂ K, (12)
(iii) Moreover, if the {ρ i } i∈D ν of a limit cycle associated to ν ∈ C are two by two different, then there exist k 0 ∈ N and an integer δ ∈ D ν such that u(x k ) = ν(k + δ), ∀k ≥ k 0 .

(13) and consequently lim

k→+∞ x k -ρ ν(k+δ) = 0.
Remark 2. It is worth noting that the previous theorem relies on the same LMI condition (8) but the contribution and interpretation are different.

Proof. The proof of each item is performed below except the one of (i), which is the same as in Theorem 1.

Proof of (ii): Consider the state-dependent Lyapunov function, V sd , given by

V sd (x k ) = min i∈D ν (x k -ρ i ) P i (x k -ρ i ) , ∀x k ∈ R n . (14)
In order to prove (ii), let us note from the control law (12) that, at any time k, we have

V sd (x k ) = (x k -ρ θ ) P θ (x k -ρ θ ) . Likewise, V sd (x k+1 ) is V sd (x k+1 ) = min j∈D ν
x k+1 -ρ j P j x k+1 -ρ j ≤ x k+1 -ρ θ+1 ν P θ+1 ν x k+1 -ρ θ+1 ν , which is the main difference with respect to the proof of Theorem 1. Then, the manipulations, as in (11), yield

∆V sd (x k ) ≤ (x k -ρ θ ) A ν(θ) P θ+1 ν A ν(θ) -P θ (x k -ρ θ ) ,
where matrices P i 's are solutions to (8). Therefore, the global exponential stabilization of the closed-loop system (1),( 12) to attractor A ν is proven.

Proof of (iii): The proof of this item is taken from (Serieye et al., 2020, Theorem 1) but is recalled here for the sake of consistency. The idea is to first prove that the state-dependent control law (12) becomes ultimately periodic, i.e. that (13) holds. The proof is obtained by showing that there exists a sufficiently small scalar > 0 (to be determined in this proof), such that we have the implication: 15) for all j ∈ D ν , with j θ + 1 ν , that is the solution of the next minimization problem ( 12) is θ + 1 ν . To sum up, k 0 is related to the time to reach the level set S , which is always possible to reach thanks to the convergence of the Lyapunov function to zero. The shift δ is determined thanks to the solution θ of the minimization law at time k 0 , that is on the initial condition x 0 and the selection of the previous switchings. First, notice that thanks to the equivalence of weighted norms, there exist constants c i, j > 0, ∀(i, j) ∈ D ν , such that

x ∈ S = {x ∈ R n , V(x) ≤ 2 } and θ ∈ arg min i∈D ν (x -ρ i ) P i (x -ρ i ) implies (x -ρ θ+1 ν ) P θ+1 ν (x -ρ θ+1 ν ) < (x -ρ j ) P j (x -ρ j ), (
x P i ≤ c i, j x P j , (16)
(for instance, select c i, j ≥ λ M (P i )/λ m (P j )). Thanks to LMIs (8) and x ∈ S , we have x k+1 -ρ θ+1 ν P θ+1 ν ≤ x k -ρ θ P θ ≤ , (17) and from ( 6)

x k+1 -ρ θ+1 ν P θ = A ν(θ) (x k -ρ θ ) P θ ≤ A ν(θ) P θ x k -ρ θ P θ , ≤ A ν(θ) P θ (18)
hold, where A ν(θ) P θ denotes the matrix norm induced by the weighted norm • P θ . That yields, due to the triangular inequality and relations ( 16),

ρ θ+1 ν -ρ j P θ -A ν(θ) P θ ≤ ρ θ+1 ν -ρ j P θ -A ν(θ) (x k -ρ θ ) P θ , ≤ ρ θ+1 ν -ρ j + A ν(θ) (x k -ρ θ ) P θ , ≤ x k+1 -ρ j P θ , ≤c θ, j x k+1 -ρ j P j , ∀ j ∈ D ν . ( 19
)
Since the {ρ i } i∈D ν of a limit cycle associated to ν ∈ C are two by two different, it is always possible to find a positive scalar such that the strict inequalities 0 < c θ, j < ρ θ+1 ν -ρ j P θ -A ν(θ) P θ hold for any j ∈ D ν , j θ + 1 ν . Combining the two latter inequalities leads to < x k+1 -ρ j P j , for all j ∈ D ν \{ θ + 1 ν }. Merging these inequalities yields, for all j

∈ D ν \{ θ + 1 ν } x k+1 -ρ θ+1 ν P θ+1 ν ≤ < x k+1 -ρ j P j . ( 20
)
The proof ends by applying item (iii) of Theorem 1, since the control law becomes ultimately periodic.

SYNCHRONIZATION OF SWITCHED AFFINE SYSTEMS

The previous theorems allow stabilizing the set of agents to the same limit cycle (ν, ρ). This means, that each agent with one of both control laws, can individually converge to the limit cycle (ν, ρ). However, these theorems will not ensure the synchronization of the agent along the limit cycle. To do so, one has to include to the control law some level of cooperation.

As mentioned in the introduction, in this section, we will propose three first solutions to solve this problem, consisting of a centralized control solution. The first time-dependent one can be seen as a natural extension of Theorem 1. Two additional solutions, which rely on the state-dependent control law are also presented.

Time-dependent open-loop control using a centralized control law

The main idea of the following theorem is to impose the same periodic (open-loop) switching control law to every agent. This first control comes direct from Theorem 1. Theorem 3. For a given cycle ν ∈ C, assume there exist {P i } i∈D ν in S n for i ∈ D ν solution to (8). Then, the following statements hold:

(i) Eq. ( 7) admits a unique solution ρ, defining the limit cycle.

(ii) The periodic, time-dependent, switching control law (9) exponentially stabilizes the multi agent system (2) to A ν := i∈D ν {1 |N| ⊗ ρ i }, and, consequently, the agents are synchronized, i.e. lim k→+∞ x ,kx ,k = 0, ∀( , ) ∈ N.

Proof. This theorem is a direct application of Theorem 1 to the case of multi-agent systems. The synchronization is ensured since all the agents converge exponentially to ρ ν(k+δ) , with the same δ for all agents.

The centralized time-dependent control law presented in the previous theorem is finally quite simple. It is indeed a centralized solution since all the agents share the same time shift δ. However, as it will be presented in the example section, this centralized solution leads to poor performances, because it is limited by the fact that the control law is finally open loop. In the sequel, two additional solutions will be presented that are state-dependent, leading potentially to better performances.

First state-dependent control law

The first centralized solution consists in building a minswitching control law that gathers and unifies the min-switching law of all the agents. This is presented in the next theorem. Theorem 4. For a given cycle ν ∈ C, assume there exist P i in S n for i ∈ D ν solution to (8). Then, the following statements hold (i) Eq. ( 7) admits a unique solution ρ, defining the limit cycle.

(ii) The centralized, state-dependent, switching control law

u(x k ) ∈ ν (θ) , θ ∈ argmin i∈D ν x k -ρ i P i x k -ρ i ⊂ K, (21)
where ρ i = 1 |N| ⊗ ρ i and P i = I |N| ⊗ P i for all i ∈ N, ensures that attractor A ν := i∈D ν {1 |N| ⊗ ρ i } is globally exponentially stable for system (2), and, consequently, the agents are synchronized, i.e. lim k→+∞ x ,kx ,k = 0, ∀( , ) ∈ N.

Proof. The proof of item (i) is as in Theorem 1. Proof of (ii): Consider the state-dependent Lyapunov function, V sd , given by

V sd (x k ) := min i∈D ν x k -ρ i P i x k -ρ i , ∀x k ∈ R n|N| . (22)
This Lyapunov function is the same as in Theorem 2, but applied to the multi-agent system defined in (2), instead of the dynamics of one single agent (1) and with ρ i = 1 |N| ⊗ ρ i and

P i = I |N| ⊗ P i instead of ρ i and P i . From control law (23), we have V(x k ) = x k -ρ θ P θ x -ρ θ ,
and the min-switching control law ensures that

V(x k+1 ) ≤ x k+1 -ρ θ+1 ν P θ+1 ν x k+1 -ρ θ+1 ν .
Despite the presence of the Kronecker product, it is still possible to do similar manipulations as those performed in (11), achieving

x k+1 = A θ x k + B θ = A θ x k -ρ θ + A θ ρ θ + B θ .
The properties of the Kronecker product yield

A θ ρ θ + B θ = I |N| ⊗ A θ 1 |N| ⊗ ρ θ + 1 |N| ⊗ B θ = I |N| 1 |N| ⊗ (A θ ρ θ ) + 1 |N| ⊗ B θ = 1 |N| ⊗ (A θ ρ θ + B θ ) = 1 |N| ⊗ ρ θ+1 ν := ρ θ+1 ν ,
so that we get

∆V(x k ) ≤ x k -ρ θ A θ P θ+1 ν A θ -P θ x k -ρ θ , = x k -ρ θ I |N| ⊗ A θ P θ+1 ν A θ -P θ x k -ρ θ ,
which is ensured to be negative definite from (8). This means that x k converges to 1 |N| ⊗ ρ u k , or equivalently that, for all ( , ) ∈ N, the triangular inequality ensures lim

k→+∞ x ,k -x ,k ≤ lim k→+∞ ( x ,k -ρ u k + x ,k -ρ u k ) = 0,
which concludes the proof.

Remark 3. From item (iii) in Theorem 2, if the components of the limit cycles are two-by-two different, then there exists δ in D ν such that lim k→+∞ x ,k -ρ ν(k+δ) = 0, ∀ ∈ N.

Second state-dependent control law

An alternative centralized solution to the synchronization problem is presented in this second theorem Theorem 5. For a given cycle ν ∈ C, assume there exist P i in S n for i ∈ D ν solution to (8). Then, the following statements hold (i) Eq. ( 7) admits a unique solution ρ, defining the limit cycle.

(ii) If the {ρ i } i∈D ν of a limit cycle associated to ν ∈ C are two by two different, then the centralized, state-dependent, switching control law

u(x k ) ∈ ν (θ) , θ ∈ argmin i∈D ν (x k -ρ i ) P i (x k -ρ i ) ⊂ K, ( 23
) where xk = 1 |N| 1 |N| ⊗ I n x k denotes the mean of x k , ensures that attractor A ν := i∈D ν {1 |N| ⊗ ρ i } is globally x 2
x 3 x 1 Fig. 2. All-to-all communication graph between 3 agents exponentially stable for system (2) and, consequently, the agents are synchronized, i.e. lim k→+∞ x ,kx ,k = 0, ∀( , ) ∈ N.

Proof. Again, the proof of item (i) is as in Theorem 1. Proof of (ii): Consider the change of variable

xk = 1 |N| 1 |N| ⊗ I n x k .
The dynamics of the mean variable verifies

xk+1 = 1 |N| 1 |N| ⊗ I n x k+1 = 1 |N| 1 |N| ⊗ I n (A θ x k + B θ ) = A θ 1 |N| 1 |N| ⊗ I n x k + B θ := A θ x + B θ .
Then, following item (ii) of Theorem 2, one can conclude that the mean of the agent states converges exponentially to A ν := i∈D ν {ρ i }. However, at this point, the stabilization of any agent to the attractor A ν is not proven. Now, from item (ii) of Theorem 2, we know that the switching control law u(x k ) converges ultimately to ν or a possibly shifted version of it, i.e., that after a finite-time, a periodic switching control law is applied to each agent. Finally, from item (i) of Theorem 1, one gets that all agent states reach synchronization since the control law is synchronized.

EXAMPLES

This section is devoted to compare the different results proposed in this paper. To do so, we select an example adapted from [START_REF] Fiacchini | On the stabilizability of discrete-time switched linear systems: novel conditions and comparisons[END_REF] and (Serieye et al., 2020). In the latter, we proposed a solution to the stabilization of switched affine systems to limit cycle defined a priori, which has been resumed here to extend it to the synchronization of an homogeneous multi-agent system. Let us consider system (2), composed of three homogeneous switched affine systems described by the following matrices

A i A 1 = 1 0 0 0.5 , A 2 = 4 -4 4 4 , B 1 = 0.01 0 , B 2 = 0 0 . (24)
Finally, the all-to-all communication, in which each pair of agents is connected by a unique edge, is illustrated by the simple graph on Figure 2.

A common assumption to ensure the asymptotic stabilization of switched affine systems is to have a linear combination of matrices A i being Schur stable. Although such condition cannot be verified for the example considered, there exists a unique limit cycle (ν, ρ) where ν = {1 11 , 2 2 } as defined in [START_REF] Fiacchini | On the stabilizability of discrete-time switched linear systems: novel conditions and comparisons[END_REF]Serieye et al., 2020) and as can be proven from Theorem 1. Then, the asymptotic stabilization to a limit cycle can be guaranteed.

On Figures 3,4 the evolutions of the system variables obtained in simulation are illustrated, being the switching control laws those proposed in Section 4. From the left to the right, the simulations are performed with the centralized control laws given in Theorems 3, 4 and 5. Figure 3 shows the timeevolutions of the states and of the control inputs and, Figure 4 Fig. 3. From left to right, the different columns correspond to simulations results where is applied in first, the periodic control law (9); in second, the all state-dependent control law (21) and finally, the mean state-dependent control law (23). From top to bottom, the different rows correspond respectively to the evolution of the first state variable of each agent, the evolution of the second state variable of each agent and the switching signal σ k .

depicts the state evolutions in the state plane. Note as the system converges to A ν with all proposed control laws, as it is highlighted in the second row subfigures, which correspond to the shadow area plotted in Figure 3.

The initial condition was selected such that the agents start from different positions in the state periodic sequence ρ of the limit cycle (ν, ρ), i.e. x 0 := x 1,0 x 2,0 x 3,0 = ρ 1 ρ 8 ρ 11 . It is worth noting that even if each agent i starts from different positions in the limit cycle, the initial condition is not in A ν .

Even though each control law ensures the synchronization of the multi-agent system (2), control law (9) provides a slower transient time than the ones generated from the others control laws proposed in Section 4.

CONCLUSION

In this paper, some centralized switching control laws have been given to synchronize a set of discrete-time switched affine systems in a given limit cycle. The controllers are obtained from the framework given in (Serieye et al., 2020) and [START_REF] Egidio | Global asymptotic stability of limit cycle and H 2 /H ∞ performance of discrete-time switched affine systems[END_REF]. On one hand, we propose a time-dependent control law, that is related to periodic systems. On the other hand, two state-dependent control laws that can improve performance with respect to the first one. An academical example shows the paper contribution. This work is a first step to progress on switched affine multi-agent system stabilization and suggests further study on distributed control for synchronization. Fig. 4. From left to right, the different columns correspond to the trajectories in the phase plane from simulations results where is applied in first, the periodic control law (9); in second, the all agent state-dependent control law (21) and finally, the agent mean state-dependent control law (23). From top to bottom, the different rows correspond respectively to the state evolution for the complete simulation time and the state evolution corresponding to the shadow area represented in Fig. 3. The state periodic sequence of the limit cycle is represented on the second row by the red points.

  Synchronization on a limit cycle of multi-agent systems governed by discrete-time switched affine dynamics M. Serieye * C. Albea * * A. Seuret * M. Jungers * * *

Fig. 1 .

 1 Fig. 1. Illustrative example of Definition 3 .


Martin Soyer

Sorin Olaru

Zhou Fang

From constraint satisfactions to periodic positive invariance for discrete-time systems

This paper deals with the analysis of the trajectories of autonomous dynamical systems with respect to static constraints. Two notions of constraints satisfaction and set-invariance are introduced in order to relax the classical definitions and offer a new perspective with potentially increased flexibility in the topology of the candidate sets. The relaxation comes from the possibility to violate the constraints for intervals of finite length along the evolution of the trajectory. In this line of developments, two alternative definitions emerge: a weak one which allows the validation of each constraint taken independently with an upper bound on the violation interval and the other one which imposes the length of the interval with a guarantee of constraint satisfaction. The main interest of those concepts is to handle simpler sets as positively invariant candidates with clear advantages in constrained control design.

I. INTRODUCTION

The analysis of constrained dynamical systems has a long history with well established theoretical concepts and well known design tools. On the theoretical side one can recall the mathematical theory of viability [START_REF] Aubin | Viability theory[END_REF] and the set theoretic methods [START_REF] Blanchini | Set-theoretic methods in control[END_REF] covering among other notions the positive invariance. On the applications side, the constrained control and model predictive control in particular are among the design techniques with established popularity [START_REF] Mayne | Constrained model predictive control: Stability and optimality[END_REF]. Other topics involving constraints at different stages are the reference governors [START_REF] Gilbert | Discrete-time reference governors for systems with state and control constraints and disturbance inputs[END_REF] and the fault detection and isolation [START_REF] Seron | Multisensor switching control strategy with fault tolerance guarantees[END_REF].

The present work is closely related to the invariant set characterization for constrained dynamical systems. The long line of developments on this topic had an impetus in the 80s and 90s with fundamental results [START_REF] Bitsoris | Positively invariant polyhedral sets of discrete-time linear systems[END_REF]- [START_REF] Blanchini | Set invariance in control[END_REF] followed up by extensions and generalization to monotonicity and comparison principles for constrained systems analysis [START_REF] Bitsoris | Positive invariance, monotonicity and comparison of nonlinear systems[END_REF].

Often, the system limitations can be modeled as (polyhedral) constraints or alternatively by convex sets and whenever the dynamics can be assimilated to linear systems, well establish computational tools (e.g. the ones leading to the maximal output admissible set [START_REF] Gilbert | Linear systems with state and control constraints: The theory and application of maximal output admissible sets[END_REF]) can be employed. However these constructions can be often time consuming and lead to the high complexity representation of the resultant set. Considering approximation of this set may lose the invariance property, and inner invariant approximation computation was seen as a potential alternative [START_REF] Scibilia | On feasible sets for mpc and their approximations[END_REF].

This work explores a novel perspective on the analysis of constraints satisfaction by relaxing the constraint validation 1 Renault Technocentre, AD Simulation & VR center, Guyancourt, France martin.soyer/zhou.fang@renault.com 2 Université Paris-Saclay, CNRS, CentraleSupélec, Laboratoire des signaux et systèmes, 91190, Gif-sur-Yvette, France martin.soyer/sorin.olaru@centralesupelec.fr to an interval along the trajectories. In other words the trajectories are allowed to violate the constraints as long as the future iterations will come back on the feasible domain and all these constraints violations can be upper bounded in terms of the interval of time. Two notions emerge: a weak version of constraint satisfaction where only an upper bound is imposed on the length of violation window. As a counterpart, the strong satisfaction of constraints on a interval of predefined length, imposes the return to the feasible domain precisely at the end of this lap of time. Using these principles, the set-invariance notions are revisited, establishing the weak and strong periodic invariance (denoted p-invariance) of a given set in the state space.

The advantages of dealing with such relaxed notions of constraint satisfaction and invariance can be related to the use of periodic invariant sets in control design which have been shown to bring interesting computational alternatives in [START_REF] Lee | Constrained robust model predictive control based on periodic invariance[END_REF], [START_REF] Scialanga | Reduced-complexity interpolating control of constrained interconnected systems and applications[END_REF] and as a benchmark in a practical Driving Simulation test-case [START_REF] Soyer | A novel Motion Cueing Algorithm based on real-time optimization and periodic invariant sets[END_REF].

The paper is organized as follows: Section II presents the notion of weak satisfaction of constraints, starting from the trajectories and gradually extending the concepts to multiple constraints and tubes of trajectories. Section III moves the objective to the set invariance and provides the weak notion by focusing on the role of each trajectory in the economy of the violation of the set-membership. Finally, the Section IV provides a link in between the two constructions through the strong counterparts of both constraint satisfaction and positive invariance.

Notations:

The power n ∈ N of a function is denoted by

f n (x) = f • ... • f n times (x) = f (f (f (...))) n times (x).
The subset of integers between a and b is denoted

N [a,b] = N ∩ [a, b].
The open ball of radius r > 0 centered in the origin is denoted B 0 (0, r).

Ω denotes the frontier of Ω. V(P ) denotes the set of vertices of a bounded polyhedral set P . A convex set Ω ⊂ R n is said to be positively invariant with respect to the autonomous system x(k

+ 1) = f (x(k)) if for any initial state x 0 ∈ Ω we have f (x 0 ) ∈ Ω. C 0 (R n , R m ) denotes the continuous functions from R n to R m .

II. CHARACTERIZATION OF TRAJECTORIES WITH RESPECT TO SUBLEVEL SETS

A. Preliminary notions and definitions

Consider a discrete-time autonomous system:

x(k + 1) = f (x(k)) (1)
defined by a mapping f ∈ C 0 (R n , R n ). Given an initial condition x 0 , the forward trajectory of the system (1) is the sequence denoted x(k, x 0 ), k ∈ N.

Next, the trajectories of the dynamical systems (1) will be characterized from the point of view of the sublevel sets of given function defined over the state space R n . For a given function h ∈ C 0 (R n , R m ), the sublevel set is defined as:

L h = {x ∈ R n | h(x) ≤ 0} (2)
At each time instant k ∈ N, the state x(k, x 0 ) can be characterised by the set membership with respect to a given sublevel set L h . The next definition extends this set membership to a complete trajectory.

Definition II.1. Given the initial condition x 0 of the system (1) and a function h ∈ C 0 (R n , R), we denote the Validation Index Set (VIS) as the maximal ordered collection of indices T ⊂ N such that x(k, x 0 ) ∈ L h for any k ∈ T .

Obviously, the VIS is dependent on the initial conditions and the topology of the sublevel-set. In order to formally describe this dependence in mathematical terms let us introduce the functional:

T : R n × C 0 (R n , R) -→ 2 N (x, h) -→ t ∈ N | f t (x) ∈ L h (3)
Example II.1. Consider the autonomous nonlinear system :

x k+1 = 0.8x 1 0.8x 3 1 + 0.5x 2 2 -1 (4)
and the circular paraboloid h : (x 1 , x 2 ) → x 2 1 + x 2 2 -0.85 2 . Then L h 0 corresponds to a circle with a radius of 0.85. A trajectory of the system is depicted in Fig. 1 for the initial state x 0 = [-1 1] leading to T (x 0 , h) = {2, 4, 5, 6, ...}.

B. Weak satisfaction of constraints

Definition II.2 (Weak constraint satisfaction). Given p ∈ N, the trajectory of the system (1) is weakly p-satisfying the constraint h(x) ≤ 0 if it exists a function r : N → N [1,p] such that x(k + r(k), x 0 ) ∈ L h for any k ∈ N.

In short, the weak p-satisfaction of a constraint indicates that a violation of the inequality will last for at most p timeinstants along the trajectory. Is worth to be mention that whenever a trajectory is weakly p-satisfying a constraint, it will be satisfying also for any index grater than p. Thus the subsequent developments we will be interested in the minimal index of weak constraint satisfaction. Theorem II.1. There exists p ∈ N such that the constraint h(x) ≤ 0 is weakly p-satisfied by the trajectory of the system (1) with initial condition x 0 ∈ R n if and only if

• T (x 0 , h) is unbounded; • The optimization problem: max j∈N {t j+1 -t j } with t j ∈ T (x 0 , h) (5)
has a bounded solution.

Proof. If h(x) is weakly p-satisfied for x(k, x 0 ) ∀k ∈ N then there exists a function r :

N → N [1,p] such that x(k + r(k), x 0 ) ∈ L h ∀k ∈ N
and the Validation Index Set verifies:

{r(0), r(1) + 1, . . . , r(k) + k, . . . } ⊂ T (x 0 , h)
Consequently T (x 0 , h) is unbounded and the optimization problem is feasible (any element t j ∈ T (x 0 , h) has a successor t j+1 ). Since T (x 0 , h) is an ordered subset of N it is countable and the difference t j+1 -t j ≤ p using the boundedness of r(.).

If T (x 0 , h) = (t i ) i∈N is (ordered) unbounded set and the optimization problem has a bounded solution p, then if we define the function :

r : N -→ N [1,p] k -→ t k -k the trajectory x(k, x 0 ) k ∈ N is weakly p-satisfying the constraint according to Definition II.2.
When dealing with vector functions, the weak psatisfaction of constraints will be considered by evaluating the range of violation for each of the components, taken independently. More precisely, given the vector function h = [h 1 , . . . , h m ] T ∈ C 0 (R n , R m ) constructed using the element-wise constraints h i (x) ≤ 0, the following definition will be used.

Definition II.3 (Weak vector-constraint satisfaction). The trajectory of the system (1) with initial condition x 0 ∈ R n is weakly p-satisfying the vector constraints h(x) ≤ 0 if it exists a function r :

N → N m [1,p] such that x(k + r i (k), x 0 ) ∈ L hi , ∀i ∈ {1, . . . , m}
and for any k ∈ N.

Theorem II.2. The m-dimensional vector-constraint h(x) ≤ 0 is weakly satisfied by the trajectory of the system (1) with initial condition x 0 ∈ R n if and only if

• The sets T (x 0 , h i ) with i ∈ N [1,m] are unbounded;

• The optimization problem:

max i∈N [1,m] max j∈N {t j+1 -t j } with t j ∈ T (x 0 , h i ) (6)
has a bounded solution.

Proof. According to Theorem II.1 applied here for each i ∈ N [1,m] , the constraint h i (x) ≤ 0 is weakly satisfied by the trajectory if and only if the optimization problem (5) has bounded solution.

As a consequence, the optimization ( 6) is feasible and has a bounded solution given by the most conservative index of weak satisfaction.

At the level of trajectories, the weak satisfaction of the constraints doesn't guarantee the simultaneous satisfaction of constraints on a finite time interval as illustrated next.

Example II.2. Consider the functions:

h 1 (x 1 , x 2 ) = 4(x 1 -1) 2 + (x 2 -3) 2 -16 (7) h 2 (x 1 , x 2 ) = 4(x 1 -1) 2 + (x 2 + 3) 2 -16 (8)
and the dynamics:

x(k + 1) = 0.9 0 0 -1 x(k) (9)
The first constraint is weakly 3-satisfied while the second is weakly 2-satisfied by the trajectory initiated in x 0 = [2.8 0.8] T . As it can be seen in the Fig. 2 the trajectory converge to a limit cycle which satisfies alternatively (but not simultaneously) both constraints and the difference in between the indices of weak satisfaction are related here to the choice of the initial conditions.

C. Extensions to tubes of trajectories

The definition of the VIS can be extended from trajectories to tubes of trajectories. The functional which associates to a set of initial conditions in R n the time-indices which validate the sublevel set is defined as:

S : 2 R n × F(R n , R) -→ 2 N (X, h) -→ t ∈ N | f t (X) ⊂ L h (10
) In other words, for a given subset X of R n , the VIS S(X, h) is an ordered subset of N which collects the indices of successive images of initial conditions in X via f (.) Fig. 2. Weak satisfaction of constraints [START_REF] Dorea | (a, b)-invariant polyhedral sets of linear discrete-time systems[END_REF] such that the trajectories are simultaneously included in the sublevel set L h . The VIS for tubes of trajectories is the intersection of VIS for each individual trajectories within the tube:

S(X, h) = x∈X T (x, h) (11)
Theorem II.3. The tube of trajectories of the system (1) initiated in X ⊂ R n is weakly p-satisfying the m-dimensional vector-constraint h(x) ≤ 0 if and only if

• The sets S(X, h i ) with i ∈ N [1,m] are unbounded;

• The optimization problem:

p = max i∈N [1,m] max j∈N {t j+1 -t j } such that t j ∈ S(X, h i ) (12)
has a bounded solution.

Proof. If there exist an unboundedness of the set S(X, h i ) ensures the trajectories validate regularly the constraint and thus each index has a successor in this ordered set. Conversely, the weak constraint satisfaction guarantees the finite distance in between two indices of validation in forward time and thus unboundedness of S(X, h i ).

The second condition translates in the mathematical form the alternative of choices: either the two successive states are validating the constraints or the validation will be enforced after exactly p iterations.

The previous concepts are useful in constrained control, but there is one particular problem of interest: the case of initial conditions given by the constraint set itself. Let the intersection of the sublevel set of the vector function h ∈ C 1 (R n , R m ) :

Ω(h) = {x ∈ R n |h(x) ≤ 0} . ( 13
)
Definition II.4 (Weak satisfaction of self-constraints). The tube of trajectory of the system (1) initiated in Ω(h) is weakly p-satisfying the constraints h(x) ≤ 0 if it exists a function r :

N → N m [1,p] such that x(k + r i (k), x 0 ) ∈ L hi , ∀k ∈ N
and for all i ∈ {1, . . . , m} where m is the dimension of the vector function h(.).

Certifying the weak satisfaction of a set of constraints is a direct application of the Theorem II.3. If it exists, the minimal index is is the solution of the optimization:

p = max i∈N [1,m] max j∈N {t j+1 -t j } witht j ∈ S(Ω(h), h i ) (14)
It should be noticed that in the general case the selfconstraint satisfaction is not necessarily implying the inclusion of the images of the set Ω(h) into itself (see the tube of trajectories corresponding to the Example II.2).

III. WEAK SET INVARIANCE

A. The general framework

The previous section treated the satisfaction of constraints at the level of inequalities and their sublevel set, the vector functions were treated also in terms of validation of element-wise constraints. This constraint satisfaction was not enforced simultaneously at some time-instants along a trajectory or tube of trajectories. In this section, we concentrate on the set-membership of the states along the trajectories of dynamical systems. In particular we aim to characterize the properties of the trajectories that leave the set Ω for finite intervals before coming back. This notion is closely related to the positive invariance as described by the next definition.

Definition III.1 (Weak invariance). Let p ∈ N. The set Ω ⊂ R n is weakly p-invariant with respect to the system (1) if for any x 0 ∈ Ω, it exists a function r : N → N [1,p] such that x(k + r(k), x 0 ) ∈ Ω for any k ∈ N.

Lemma III.1. A set Ω ⊂ R n containing the origin in its interior is weakly p-invariant with respect to the system (1) if the constrained µ Ω (x) ≤ 0 defined using

µ Ω (x) = {min α ∈ [-1, ∞) : x ∈ (1 + α)Ω}, (15)
is weakly p-satisfied by the tube of trajectories of the system (1) initiated in Ω.

Proof. According to the Definition III.1, a link needs to be established between the set-membership and the sublevelset of a given inequality. The statement of the Theorem establishes this link under the assumption that the origin is an interior point of Ω by means of a Minkowski functional (15). Indeed, it can be easily verified that L µ Ω = Ω. The proof is complete by noting that according to Definition II.2, the weak satisfaction of the constraint µ Ω (x) ≤ 0 guarantees the existence of a function r :

N → N [1,p] such that x(k + r(k), x 0 ) ∈ L µ Ω = Ω.
Theorem III.2. A set Ω ⊂ R n containing the origin in its interior is weakly p-invariant with respect to the system (1) if and only if

• T (x 0 , µ Ω ) is unbounded for all x 0 ∈ Ω;

• The optimization problem:

max x0∈Ω max j∈N {t j+1 -t j } with t j ∈ T (x 0 , µ Ω ) (16)
has a bounded solution.

Proof. First if the set is weakly p-invariant then for each index k in T (x 0 , µ Ω ) it exists an index k+r(k) ∈ T (x 0 , µ Ω ) and thus recursively there exists a successor index thus proving the set is unbounded. Consequently the optimization problem is feasible and upper bounded by the index p of weak invariance. Thus the optimum exists.

Conversely, the satisfaction of the first conditions proves the feasibility of the optimization problem. By choosing p the optimal solution, the conditions of weak invariance are fulfilled.

B. Weak invariance of polyhedral set with respect to LTI dynamics

As shown in the case of weak constraint satisfaction, whenever the dynamical system and the set of constraints has additional structural properties, the computation of the indices of weak invariance can be enhanced. The ultimate objective of the present section is to present a commonly encountered case for which the computation is finitely determined.

Next we will detail the case of linear time-invariant systems:

x

(k + 1) = Ax(k). ( 17
)
with a Schur matrix A.

Lemma III.3. Consider a bounded polyhedral set Ω ⊂ R n containing the origin in its interior. Let p be the minimal index such that Ω is weakly p-invariant with respect to the asymptotically stable system (17). Then p is the solution of the optimization problem:

max x0∈ Ω max j∈N {t j+1 -t j } with t j ∈ T (x 0 , µ Ω ) (18)
Proof. The Lemma claims that the index of weak invariance can be computed by optimizing over the constraint satisfaction indices of the trajectories initiated on Ω. By contradiction, suppose that the maximum index corresponds exclusively to an interior point x such that x(0, x) ∈ Ω and

x(p, x) ∈ Ω but x(i, x) / ∈ Ω for all i ∈ N [1,p-1]
. Note however that there exist γ > 1 such that γ x ∈ Ω. By linearity of the dynamics and convexity of the set Ω it follows γx(i, x) /

∈ Ω for all i ∈ N [1,p-1] . The constraint satisfaction index for the set Ω being p leads to γx(p, x) = x(p, γ x) ∈ Ω which shows that the optimum value of the optimization is obtained by the point γ x ∈ Ω which leads to a contradiction.

Theorem III.4. Consider a bounded polyhedral set Ω ⊂ R n containing the origin in its interior. The minimal index p such that Ω is weakly p-invariant with respect to the asymptotically stable system (17) is finitely determined.

Proof. Lemma III.3 indicates the computation of the index p can be resumed to the study of the frontier of the set Ω. Given the asymptotic stability property of the dynamics and the origin as an interior point of Ω, there exist a finite time instant p such that

N [ p,∞) ⊂ T (v i , µ Ω )
for all v i ∈ V(Ω). Exploiting the existence of this finite upper bound and the finite number of vertices for a bounded polyhedral set, the finite computation of the index p follows.

Example III.1. Consider a bounded polyhedron X 0 and the linear system :

x(k + 1) = 0.9806 0.0685 -0.4842 0.7134 x(k) (19)
The successive images of X 0 are depicted in Fig. 3 with the validation indices of trajectories initiated in X 0 with respect to each halfspace constituting X 0 itself. In this example the minimal index of weak invariance of X 0 is p = 12 which is the maximal gap between two successive elements of

T (v i , µ X0 ) where v i ∈ V(X 0 ). -1.4 -1.2 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 -8 -6 -4 -

IV. STRONG CONSTRAINT SATISFACTION AND STRONG

INVARIANCE

The weak constraint satisfaction and weak invariance offer two different perspectives on the validation of static constraints along the trajectories of a dynamical system. The present section aims to link the two notions through a strong version which imposes additional restrictions on the allowed interval between violation of constraints.

Definition IV.1 (Strong vector-constraint satisfaction). The tube of trajectories of the system (1) with initialized in X ⊂ R n is strongly p-satisfying the vector constraints h(x) ≤ 0 with h :

R n → R m if x(k, x 0 ) ∈ L hi x(k + 1, x 0 ) / ∈ L hi =⇒ x(k + p, x 0 ) ∈ L hi , (20)
for each i ∈ N [1,m] , for any x 0 ∈ X and for any k ∈ N.

Theorem IV.1. The m-dimensional vector-constraint h(x) ≤ 0 is strongly p-satisfied by the trajectory of the system (1) with initial condition x 0 ∈ X ⊂ R n if and only if

• The sets T (x 0 , h i ) with i ∈ N [1,m] are unbounded;

• For each i ∈ N [1,m] and for any successive elements t j , t j+1 ∈ T (x 0 , h i ) we have either t j+1 -t j = 1 or t j + p ∈ T (x 0 , h i ).

Without establishing a formal result, it can be noticed that strong constraint satisfaction index can (and usually is) larger than the weak counterpart. Also, from the computational point of view, the case of stable linear systems leads to a finite determination of the strong index of constraints' satisfaction.

Corollary IV.2. If the m-dimensional vector-constraint h(x) ≤ 0 is strongly p-satisfied by the trajectory of the system (1) with initial condition x 0 ∈ X ⊂ R n , then the same vector constraints are weakly p-satisfied.

Proof. By simply choosing the function:

r i (k) =                1 if x(k, x 0 ) ∈ L hi x(k + 1, x 0 ) ∈ L hi p if x(k, x 0 ) ∈ L hi x(k + 1, x 0 ) / ∈ L hi r i (k -1) -1 if x(k, x 0 ) / ∈ L hi x(k + 1, x 0 ) / ∈ L hi (21)
Definition IV.2 (Strong invariance). Let p ∈ N. The set Ω ⊂ R n is strongly p-invariant with respect to the system (1) if

x(k, x 0 ) ∈ Ω x(k + 1, x 0 ) / ∈ Ω =⇒ x(k + p, x 0 ) ∈ Ω, (22)
for each x 0 ∈ Ω, and for all k ∈ N.

Theorem IV.3. A set Ω ⊂ R n containing the origin in its interior is strongly p-invariant with respect to the system (1) if and only if

• T (x 0 , µ Ω ) is unbounded for all x 0 ∈ Ω;

• For any successive elements t j , t j+1 ∈ T (x 0 , µ Ω ) we have either t j+1 -t j = 1 or t j + p ∈ T (x 0 , h i ).

The proof is omitted for space reasons its argument following the same argument as the proof of Theorem IV.1.

Corollary IV.4. If the set Ω ⊂ R n is strongly p-invariant with respect to the system (1) then it is weakly p-invariant.

Note also that strong invariance index is grater or equal with the weak invariance index. Next result bridges the gap between the strong p-satisfaction of (self)-constraints and the strong positive p-invariance. Theorem IV.5. Let a set Ω = {x ∈ R n |h i (x) ≤ 0} containing the origin in its interior. If the set is strongly p-invariant with respect to the dynamics (1) then the trajectory initiated in Ω are strongly p-satisfying the vector-constraints defining this set.

Proof. The level set of the Minkowski function satisfies:

L µ Ω = i L hi (23)
and ensures:

µ Ω (f p (Ω)) ≤ 0 =⇒ h i (f p (Ω)) ≤ 0, ∀i ∈ N [1,m] (24)
Note that the assumption of the origin being an interior point can be relaxed by an appropriate change of coordinates and has been adopted here to facilitate the proof.

The main concepts presented in the paper are summarized together with their relationships in Figure 4.

The last results are recalling the computational aspects and underline the fact that in the case of linear systems the numerical tools for certifying the p-invariance are relatively mature and scale adequately with respect to the dimension of the state space or the complexity of the sets to be analysed.

Proposition IV.1. The strong p-invariance of a bounded polyhedral set, containing the origin in its interior, with respect to a stable linear dynamics (17) is equivalent with the strong p-satisfaction of the constraint µ Ω (v i ) ≤ 0 for v i ∈ V(Ω).

V. CONCLUSION

The paper revisited the notions of constraint satisfaction and positive invariance by introducing a relaxation (generalization) on the window on possible violations. If the classical notions impose a satisfaction of the set of constraints (or, alternatively, of the set-membership) at each sampling time, in the present work, the validation needs to be done at least once in a given time interval. The length of this time interval is parameterizing the weak or strong versions of the constraint satisfaction (invariance).

Is interesting to note that the classical rigid notions of positive invariance are covered by the present framework and additionally, the results are providing a link to alternative constructions in the literature as for example the periodic invariant sets.

Given the present foundation, the directions to be explored are related to

• the qualitative analysis of the link in between the length of the interval of constraint satisfaction (invariance) and the complexity of the set of constraints • the extension from autonomous systems to (constrained) controlled systems • the formulation of a robust version, to cope with the presence of bounded uncertainties.

Fig. 1 .

 1 Fig. 1. Trajectory of the system (4)

Fig. 3 .

 3 Fig.3. A weak invariant set and the successive images of X 0 through the system (19). For completeness the indices of weak constraints satisfaction is presented for each halfspace involved in the polyhedral set description.

Fig. 4 .

 4 Fig.[START_REF] Gilbert | Discrete-time reference governors for systems with state and control constraints and disturbance inputs[END_REF]. Summary of concepts introduced with the structural relationship between the constraints satisfaction and the invariance and subsequently on the qualitative assessment of these properties.