Thomas Bonald
email: thomas.bonald@telecom-paristech.fr

Alexandre Proutière

Two-Target Algorithms for Infinite-Armed Bandits with Bernoulli Rewards

We consider an infinite-armed bandit problem with Bernoulli rewards. The mean rewards are independent, uniformly distributed over [0, 1]. Rewards 0 and 1 are referred to as a success and a failure, respectively. We propose a novel algorithm where the decision to exploit any arm is based on two successive targets, namely, the total number of successes until the first failure and until the first m failures, respectively, where m is a fixed parameter. This two-target algorithm achieves a long-term average regret in √ 2n for a large parameter m and a known time horizon n. This regret is optimal and strictly less than the regret achieved by the best known algorithms, which is in 2 √ n. The results are extended to any mean-reward distribution whose support contains 1 and to unknown time horizons. Numerical experiments show the performance of the algorithm for finite time horizons.

Introduction

Motivation. While classical multi-armed bandit problems assume a finite number of arms [START_REF] Tze | Asymptotically efficient adaptive allocation rules[END_REF], many practical situations involve a large, possibly infinite set of options for the player. This is the case for instance of on-line advertisement and content recommandation, where the objective is to propose the most appropriate categories of items to each user in a very large catalogue. In such situations, it is usually not possible to explore all options, a constraint that is best represented by a bandit problem with an infinite number of arms. Moreover, even when the set of options is limited, the time horizon may be too short in practice to enable the full exploration of these options. Unlike classical algorithms like UCB [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], which rely on a initial phase where all arms are sampled once, algorithms for infinite-armed bandits have an intrinsic stopping rule in the number of arms to explore. We believe that this provides useful insights into the design of efficient algorithms for usual finite-armed bandits when the time horizon is relatively short.

Overview of the results. We consider a stochastic infinite-armed bandit with Bernoulli rewards, the mean reward of each arm having a uniform distribution over [0,[START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. This model is representative of a number of practical situations, such as content recommandation systems with like/dislike feedback and without any prior information on the user preferences. We propose a two-target algorithm based on some fixed parameter m that achieves a long-term average regret in √ 2n for large m and a large known time horizon n. We prove that this regret is optimal. The anytime version of this algorithm achieves a long-term average regret in 2 √ n for unknown time horizon n, which we conjecture to be also optimal. The results are extended to any mean-reward distribution whose support contains 1. Specifically, if the probability that the mean reward exceeds u is equivalent to α(1 -u) β when u → 1 -, the two-target algorithm achieves a long-term average regret in C(α, β)n β β+1 , with some explicit constant C(α, β) that depends on whether the time horizon is known or not. This regret is provably optimal when the time horizon is known. The precise statements and proofs of these more general results are given in the appendix.

Related work.

The stochastic infinite-armed bandit problem has first been considered in a general setting by Mallows and Robbins [START_REF] Mallows | Some problems of optimal sampling strategy[END_REF] and then in the particular case of Bernoulli rewards by Herschkorn, Peköz and Ross [START_REF] Stephen J Herschkorn | Policies without memory for the infinite-armed bernoulli bandit under the average-reward criterion[END_REF]. The proposed algorithms are first-order optimal in the sense that they minimize the ratio R n /n for large n, where R n is the regret after n time steps. In the considered setting of Bernoulli rewards with mean rewards uniformly distributed over [0, 1], this means that the ratio R n /n tends to 0 almost surely. We are interested in second-order optimality, namely, in minimizing the equivalent of R n for large n. This issue is addressed by Berry et. al. [START_REF] Berry | Bandit problems with infinitely many arms[END_REF], who propose various algorithms achieving a long-term average regret in 2 √ n, conjecture that this regret is optimal and provide a lower bound in √ 2n. Our algorithm achieves a regret that is arbitrarily close to √ 2n, which invalidates the conjecture. We also provide a proof of the lower bound in √ 2n since that given in [2, Theorem 3] relies on the incorrect argument that the number of explored arms and the mean rewards of these arms are independent random variables1 ; the extension to any mean-reward distribution [START_REF] Berry | Bandit problems with infinitely many arms[END_REF]Theorem 11] is based on the same erroneous argument2 .

The algorithms proposed by Berry et. al. [START_REF] Berry | Bandit problems with infinitely many arms[END_REF] and applied in [START_REF] Lin | Some optimal strategies for bandit problems with beta prior distributions[END_REF][START_REF] Chen | A note on strategies for bandit problems with infinitely many arms[END_REF][START_REF] Chen | A note on infinite-armed bernoulli bandit problems with generalized beta prior distributions[END_REF][START_REF] Hung | Optimal bayesian strategies for the infinite-armed bernoulli bandit[END_REF] to various mean-reward distributions are variants of the 1-failure strategy where each arm is played until the first failure, called a run. For instance, the non-recalling √ n-run policy consists in exploiting the first arm giving a run larger than √ n. For a uniform mean-reward distribution over [0, 1], the average number of explored arms is √ n and the selected arm is exploited for the equivalent of n time steps with an expected failure rate of 1/ √ n, yielding the regret of 2 √ n. We introduce a second target to improve the expected failure rate of the selected arm, at the expense of a slightly more expensive exploration phase. Specifically, we show that it is optimal to explore n/2 arms on average, resulting in the expected failure rate 1/ √ 2n of the exploited arm, for the equivalent of n time steps, hence the regret of √ 2n. For unknown horizon times, anytime versions of the algorithms of Berry et. al. [START_REF] Berry | Bandit problems with infinitely many arms[END_REF] are proposed by Teytaud, Gelly and Sebag in [START_REF] Teytaud | Anytime many-armed bandits[END_REF] and proved to achieve a regret in O( √ n). We show that the anytime version of our algorithm achieves a regret arbitrarily close to 2 √ n, which we conjecture to be optimal.

Our results extend to any mean-reward distribution whose support contains 1, the regret depending on the characteristics of this distribution around 1. This problem has been considered in the more general setting of bounded rewards by Wang, Audibert and Munos [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF]. When the time horizon is known, their algorithms consist in exploring a pre-defined set of K arms, which depends on the parameter β mentioned above, using variants of the UCB policy [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. In the present case of Bernoulli rewards and mean-reward distributions whose support contains 1, the corresponding regret is in n β β+1 , up to logarithmic terms coming from the exploration of the K arms, as in usual finite-armed bandits algorithms [START_REF] Tze | Asymptotically efficient adaptive allocation rules[END_REF]. The nature of our algorithm is very different in that it is based on a stopping rule in the exploration phase that depends on the observed rewards. This does not only remove the logarithmic terms in the regret but also achieves the optimal constant.

Model

We consider a stochastic multi-armed bandit with an infinite number of arms. For any k = 1, 2, . . ., the rewards of arm k are Bernoulli with unknown parameter θ k . We refer to rewards 0 and 1 as a failure and a success, respectively, and to a run as a consecutive sequence of successes followed by a failure. The mean rewards θ 1 , θ 2 , . . . are themselves random, uniformly distributed over [0, 1].

At any time t = 1, 2, . . ., we select some arm I t and receive the corresponding reward X t , which is a Bernoulli random variable with parameter θ It . We take I 1 = 1 by convention. At any time t = 2, 3, . . ., the arm selection only depends on previous arm selections and rewards; formally, the random variable I t is F t-1 -mesurable, where F t denotes the σ-field generated by the set {I 1 , X 1 , . . . , I t , X t }. Let K t be the number of arms selected until time t. Without any loss of generality, we assume that {I 1 , . . . , I t } = {1, 2, . . . , K t } for all t = 1, 2, . . ., i.e., new arms are selected sequentially. We also assume that I t+1 = I t whenever X t = 1: if the selection of arm I t gives a success at time t, the same arm is selected at time t + 1.

The objective is to maximize the cumulative reward or, equivalently, to minimize the regret defined by R n = n -n t=1 X t . Specifically, we focus on the average regret E(R n ), where expectation is taken over all random variables, including the sequence of mean rewards θ 1 , θ 2 , . . .. The time horizon n may be known or unknown.

3 Known time horizon

Two-target algorithm

The two-target algorithm consists in exploring new arms until two successive targets 1 and 2 are reached, in which case the current arm is exploited until the time horizon n. The first target aims at discarding "bad" arms while the second aims at selecting a "good" arm. Specifically, using the names of the variables indicated in the pseudo-code below, if the length L of the first run of the current arm I is less than 1 , this arm is discarded and a new arm is selected; otherwise, arm I is pulled for m -1 additional runs and exploited until time n if the total length L of the m runs is at least 2 , where m ≥ 2 is a fixed parameter of the algorithm. We prove in Proposition 1 below that, for large m, the target values 31 = 3 n 2 and 2 = m n 2 provide a regret in √ 2n.

Algorithm 1: Two-target algorithm with known time horizon n. Parameters: m, n Function:

Explore I ← I + 1, L ← 0, M ← 0 Algorithm: 1 = 3 n 2 , 2 = m n 2 I ← 0 Explore Exploit ← false forall the t = 1, 2, . . . , n do Get reward X from arm I if not Exploit then if X = 1 then L ← L + 1 else M ← M + 1 if M = 1 then if L < 1 then Explore else if M = m then if L < 2 then Explore else
Exploit ← true

Regret analysis

Proposition 1 The two-target algorithm with targets 1 = 3 n 2 and 2 = m n 2 satisfies:

∀n ≥ m 2 2 , E(R n ) ≤ m + 2 + 1 m 2 -m + 2 2 -1 -m + 2 m 2 + 1 m + 2 m + 1 1 + 1 .
In particular,

lim sup n→+∞ E(R n ) √ n ≤ √ 2 + 1 m √ 2 .
Proof. Note that Let U 1 = 1 if arm 1 is used until time n and U 1 = 0 otherwise. Denote by M 1 the total number of 0's received from arm 1. We have:

E(R n ) ≤ P (U 1 = 0)(E(M 1 |U 1 = 0) + E(R n )) + P (U 1 = 1)(m + nE(1 -θ 1 |U 1 = 1)
), so that:

E(R n ) ≤ E(M 1 |U 1 = 0) P (U 1 = 1) + m + nE(1 -θ 1 |U 1 = 1). (1)
Let N t be the number of 0's received from arm 1 until time t when this arm is played until time t. Note that n ≥ m 2 2 implies n ≥ 2 . Since P (N 1 = 0|θ 1 = u) = u 1 , the probability that the first target is achieved by arm 1 is given by:

P (N 1 = 0) = 1 0 u 1 du = 1 1 + 1 .
Similarly,

P (N 2 -1 < m|θ 1 = u) = m-1 j=0 2 -1 j u 2-1-j (1 -u) j ,
so that the probability that arm 1 is used until time n is given by:

P (U 1 = 1) = 1 0 P (N 1 = 0|θ 1 = u)P (N 2-1 < m|θ 1 = u)du, = m-1 j=0 ( 2 -1 )! ( 2 -1 -j)! ( 2 -j)! ( 2 + 1)! .
We deduce:

m 2 + 1 2 -1 -m + 2 2 -m + 2 m ≤ P (U 1 = 1) ≤ m 2 + 1 . (2)
Moreover,

E(M 1 |U 1 = 0) = 1 + (m -1)P (N 1 = 0|U 1 = 0) ≤ 1 + (m -1) P (N 1 = 0) P (U 1 = 0) ≤ 1 + 2 m + 1 1 + 1 ,
where the last inequality follows from (2) and the fact that 2 ≥ m 2 2 . It remains to calculate E(1 -θ 1 |U 1 = 1). Since:

P (U 1 = 1|θ 1 = u) = m-1 j=0 2 -1 j u 2-j (1 -u) j ,
we deduce:

E(1 -θ 1 |U 1 = 1) = 1 P (U 1 = 1) 1 0 m-1 j=0 2 -1 j u 2-j (1 -u) j+1 du, = 1 P (U 1 = 1) m-1 j=0 ( 2 -1 )! ( 2 -1 -j)! ( 2 -j)! ( 2 + 2)! (j + 1), ≤ 1 P (U 1 = 1) m(m + 1) 2( 2 + 1)( 2 + 2) ≤ 1 P (U 1 = 1) 1 + 1 m .
The proof then follows from ( 1) and (2).

Lower bound

The following result shows that the two-target algorithm is asymptotically optimal (for large m).

Theorem 1 For any algorithm with known time horizon n,

lim inf n→+∞ E(R n ) √ n ≥ √ 2.
Proof. We present the main ideas of the proof. The details are given in the appendix. Assume an oracle reveals the parameter of each arm after the first failure of this arm. With this information, the optimal policy explores a random number of arms, each until the first failure, then plays only one of these arms until time n. Let µ be the parameter of the best known arm at time t. Since the probability that any new arm is better than this arm is 1 -µ, the mean cost of exploration to find a better arm is 1 1-µ . The corresponding mean reward has a uniform distribution over [µ, 1] so that the mean gain of exploitation is less than (n -t) 1-µ 2 (it is not equal to this quantity due to the time spent in exploration). Thus if 1 -µ < 2 n-t , it is preferable not to explore new arms and to play the best known arm, with mean reward µ, until time n. A fortiori, the best known arm is played until time n whenever its parameter is larger than 1 -2 n . We denote by A n the first arm whose parameter is larger than 1 -2 n . We have K n ≤ A n (the optimal policy cannot explore more than A n arms) and

E(A n ) = n 2 .
The parameter θ An of arm

A n is uniformly distributed over [1 -2 n , 1], so that E(θ An ) = 1 - 1 2n . (3)
For all k = 1, 2, . . ., let L 1 (k) be the length of the first run of arm k. We have:

E(L 1 (1)+. . .+L 1 (A n -1)) = (E(A n )-1)E(L 1 (1)|θ 1 ≤ 1- 2 n ) = ( n 2 -1) -ln( 2 n ) 1 -2 n , (4)
using the fact that:

E(L 1 (1)|θ 1 ≤ 1 - 2 n ) = 1- √ 2 n 0 1 1 -u du 1 -2 n .
In particular,

lim n→+∞ 1 n E(L 1 (1) + . . . + L 1 (A n -1)) → 0 (5)
and

lim n→+∞ 1 n P (L 1 (1) + . . . + L 1 (A n -1) ≤ n 4 5 ) → 1.
To conclude, we write:

E(R n ) ≥ E(K n ) + E((n -L 1 (1) -. . . -L 1 (A n -1)))(1 -θ An )).
Observe that, on the event {L 1 (1) + . . . + L 1 (A n -1) ≤ n . Since

P (L 1 (1) + . . . + L 1 (A n -1) ≤ n 4 5 ) → 1 and E(A n ) = n-n 4 5
2 , we deduce that:

lim inf n→+∞ E(K n ) √ n ≥ 1 √ 2 .
By the independence of θ An and L 1 (1), . . . , L 1 (A n -1),

1 √ n E((n -L 1 (1) -. . . -L 1 (A n -1)))(1 -θ An )) = 1 √ n (n -E(L 1 (1) + . . . + L 1 (A n -1)))(1 -E(θ An )),
which tends to 1 √ 2 in view of (3) and ( 5). The announced bound follows.

4 Unknown time horizon

Anytime version of the algorithm

When the time horizon is unknown, the targets depend on the current time t, say 1 (t) and 2 (t). Now any arm that is exploited may be eventually discarded, in the sense that a new arm is explored. This happens whenever either L 1 < 1 (t) or L 2 < 2 (t), where L 1 and L 2 are the respective lengths of the first run and the first m runs of this arm. Thus, unlike the previous version of the algorithm which consists in an exploration phase followed by an exploitation phase, the anytime version of the algorithm continuously switches between exploration and exploitation. We prove in Proposition 2 below that, for large m, the target values 1 (t) = 3 √ t and 2 (t) m √ t given in the pseudo-code achieve an asymptotic regret in 2 √ n.

Algorithm 2: Two-target algorithm with unknown time horizon.

Parameter: m Function:

Explore I ← I + 1, L ← 0, M ← 0 Algorithm: I ← 0 Explore Exploit ← false forall the t = 1, 2, . . . do Get reward X from arm I 1 = 3 √ t , 2 = m √ t if Exploit then if L 1 < 1 or L 2 < 2 then Explore Exploit ← false else if X = 1 then L ← L + 1 else M ← M + 1 if M = 1 then if L < 1 then Explore else L 1 ← L else if M = m then if L < 2 then
lim sup n→+∞ E(R n ) √ n ≤ 2 + 1 m .
Proof. For all k = 1, 2, . . ., denote by L 1 (k) and L 2 (k) the respective lengths of the first run and of the first m runs of arm k when this arm is played continuously. Since arm k cannot be selected before time k, the regret at time n satisfies:

R n ≤ K n + m Kn k=1 1 {L1(k)> 1(k)} + n t=1 (1 -X t )1 {L2(It)> 2(t)} .
First observe that, since the target functions 1 (t) and 2 (t) are non-decreasing, K n is less than or equal to K n , the number of arms selected by a two-target policy with known time horizon n and fixed targets 1 (n) and 2 (n). In this scheme, let U 1 = 1 if arm 1 is used until time n and U 1 = 0 otherwise. It then follows from (2) that P (U 1 = 1) Finally, Combining the previous results yields:

∼ 1 √ n and E(K n ) ≤ E(K n ) ∼ √ n when n → +∞. Now, E Kn k=1 1 {L1(k)> 1(k)} = ∞ k=1 P (L 1 (k) > 1 (k), K n ≥ k), = ∞ k=1 P (L 1 (k) > 1 (k))P (K n ≥ k|L 1 (k) > 1 (k)),
E((1 -X t )1 {L2(It)> 2(t)} ) ≤ E(1 -X t |L 2 (I t ) > 2 (t)) ∼ m + 1 m 1 2 √ t when t → +∞,
lim sup n→+∞ E(R n ) √ n ≤ 2 + 1 m .

4 5 }

 5 , the number of explored arms satisfies K n ≥ A n where A n denotes the first arm whose parameter is larger than 1 -

≤ ∞ k=1 P 3 √k1

 k=13 (L 1 (k) > 1 (k))P (K n ≥ k) ≤ E(Kn) k=1 P (L 1 (k) > 1 (k)),where the first inequality follows from the fact that for any arm k and all u ∈ [0, 1],P (θ k ≥ u|L 1 (k) > 1 (k)) ≥ P (θ k ≥ u) and P (K n ≥ k|θ k ≥ u) ≤ P (K n ≥ k),and the second inequality follows from the fact that the random variables L 1 (1), L 1 (2), . . . are i.i.d. and the sequence 1 (1), 1 (2), . . . is non-decreasing. Since E(K n ) ≤ E(K n ) ∼ √ n when n → +∞ and P (L 1 (k) > 1 (k)) ∼ 1 when k → +∞, we deduce: {L1(k)> 1(k)} = 0.

1 -

 1 X t )1 {L2(It)> 2 (t)} ) ≤ m

Specifically, it is assumed that for any policy, the mean rewards of the explored arms have a uniform distribution over [0, 1], independently of the number of explored arms. This is incorrect. For the 1-failure policy for instance, given that only one arm has been explored until time n, the mean reward of this arm has a beta distribution with parameters 1, n.

This lower bound is 4 n/3 for a beta distribution with parameters 1/2, 1, see[START_REF] Lin | Some optimal strategies for bandit problems with beta prior distributions[END_REF], while our algorithm achieves a regret arbitrarily close to 2 √ n in this case, since C(α, β) = 2 for α = 1/2 and β = 1, see the appendix. Thus the statement of [2, Theorem 11] is false.

The first target could actually be any function 1 of the time horizon n such that 1 → +∞ and 1/ √ n → 0 when n → +∞. Only the second target is critical.

Acknowledgments

The authors acknowledge the support of the European Research Council, of the French ANR (GAP project), of the Swedish Research Council and of the Swedish SSF.

Lower bound

We believe that if E(R n )/ √ n tends to some limit, then this limit is at least 2. To support this conjecture, consider an oracle that reveals the parameter of each arm after the first failure of this arm, as in the proof of Theorem 1. With this information, an optimal policy exploits an arm whenever its parameter is larger than some increasing function θt of time t. Assume that 1 -θt ∼ 1 c √ t for some c > 0 when t → +∞. Then proceeding as in the proof of Theorem 1, we get:

Numerical results

Figure 1 gives the expected failure rate E(R n )/n with respect to the time horizon n, that is supposed to be known. The results are derived from the simulation of 10 5 independent samples and shown with 95% confidence intervals. The mean rewards have (a) a uniform distribution or (b) a Beta(1,2) distribution, corresponding to the probability density function u → 2(1 -u). The single-target algorithm corresponds to the run policy of Berry et. al. [START_REF] Berry | Bandit problems with infinitely many arms[END_REF] with the asymptotically optimal target values √ n and 3 √ 2n, respectively. For the two-target algorithm, we take m = 3 and the target values given in Proposition 1 and Proposition 3 (in the appendix). The results are compared with the respective asymptotic lower bounds 2/n and 3 3/n. The performance gains of the two-target algorithm turn out to be negligible for the uniform distribution but substantial for the Beta(1,2) distribution, where "good" arms are less frequent.

Conclusion

The proposed algorithm uses two levels of sampling in the exploration phase: the first eliminates "bad" arms while the second selects "good" arms. To our knowledge, this is the first algorithm that achieves the optimal regrets in √ 2n and 2 √ n for known and unknown horizon times, respectively. Future work will be devoted to the proof of the lower bound in the case of unknown horizon time. We also plan to study various extensions of the present work, including mean-reward distributions whose support does not contain 1 and distribution-free algorithms. Finally, we would like to compare the performance of our algorithm for finite-armed bandits with those of the best known algorithms like KL-UCB [START_REF] Cappé | Kullback-leibler upper confidence bounds for optimal sequential allocation[END_REF] and Thompson sampling [START_REF] Kaufmann | Thompson sampling: An asymptotically optimal finite-time analysis[END_REF] over short time horizons where the full exploration of the arms is generally not optimal.


Andrey Polyakov
email: andrey.polyakov@inria.fr

Alexander Poznyak
email: apoznyak@ctrl.cinvestav.mx

Jean-Pierre Richard
email: pierre.richard@inria.fr

Robust Output Stabilization of Time-Varying Input Delay Systems using Attractive Ellipsoid Method

The problem of output control design for linear system with unknown and time-varying input delay, bounded exogenous disturbances and bounded deterministic measurement noises is considered. The prediction technique is combined with Luenberger-like observer design in order to provide the stabilizing output feedback. The scheme of parameters tuning for reduction of measurement noises effect and exogenous disturbances effects is developed basing on Attractive Ellipsoids Method. Under some restrictions it is formalized as semidefinite programming problem. The theoretical results are supported by numerical simulations.

I. INTRODUCTION

Models with time delays frequently appear in networked systems [START_REF] Kruszewski | A switched system approach to exponential stabilization through communication network[END_REF], chemical [START_REF] Stephanopoulos | Chemical process control: an introduction to theory and practice[END_REF] and biological processes [START_REF] Flower | Relaxation oscillations in a class of delay differential equations[END_REF], automobile [START_REF] Choi | Robust throttle control of automotive engines[END_REF] and aerospace industries [START_REF] Yefremov | An active stabilization algorithm for a spacecraft with viscoelastic elements under uncertainties[END_REF]. The real-life applications need control algorithms, which are robust with respect to exogenous disturbances, system uncertainties and measurement noises. The control problems for systems with known delays are studied for both linear and nonlinear systems, state, input and output delays ( see, for example, [START_REF] Artstein | Linear systems with delayed controls: A reduction[END_REF], [START_REF] Watanabe | Finite spectrum assignment and observer for multivariable systems with commensurate delays[END_REF], [START_REF] Richard | Time-delay systems: An overview of some recent advances and open problems[END_REF], [START_REF] Krstic | Delay Compensation for Nonlinear, Adaptive, and PDE Systems[END_REF], [START_REF] Bekiaris-Liberis | Compensation of time-varying input and state delays for nonlinear systems[END_REF], [START_REF] Mazenc | Lyapunov-Krasovskii functionals and application to input delay compensation for linear timeinvariant systems[END_REF], [START_REF] Polyakov | Minimization of disturbances effects in time delay predictor-based sliding mode control systems[END_REF] and references within). However, an important performance index of control systems is a robustness with respect to unknown and time-varying delay. Such analysis for full state feedback control algorithms has been done for systems with linear (see, for example, [START_REF] Fridman | Robust sampled-data stabilization of linear systems: an input delay approach[END_REF]) and relay feedbacks [START_REF] Polyakov | On practical stabilization of the systems with relay delay control[END_REF]. In [START_REF] Han | Sliding mode control in the presence of input delay: A singular perturbation approach[END_REF], [START_REF] Dambrine | Robustness of sliding mode control under delays effects : a case study[END_REF] the first order sliding mode control systems with input delay was studied. There are few researches devoted to the output control design for systems with time-varying and unknown delay [START_REF] Choi | Output feedback regulation of a chain of integrators with an unknown time-varying delay in the input[END_REF], [START_REF] Polyakov | Interval observer approach to output stabilization of time-varying input delay system[END_REF], [START_REF]Output stabilization of time-varying input delay systems using interval observation technique[END_REF]. However, they study robustness properties of time-delay control systems only with respect to uncertainties in timedelay. Moreover, the adaptive control scheme presented in [START_REF] Choi | Output feedback regulation of a chain of integrators with an unknown time-varying delay in the input[END_REF] is applicable only to a chain of integrators.

This paper treats the problem of output control design for linear system with unknown and time-varying input delay, bounded exogenous disturbances and bounded deterministic measurement noises. Two approaches can be considered in order to tackle this problem. The first one is based on finite-time (or fixed-time) observer design for the system with unknown control input [START_REF] Seuret | A sliding mode observer for linear systems with unknown time varying delay[END_REF], [START_REF] Zheng | On obserability of nonlinear time-delay systems with unknown inputs[END_REF]. Theoretically such an observer guarantees that after finite (or fixed) period of time the observed states will coincide with the real ones. This property ensures fulfilling of separation principle, so any existing full-state control can be applied. Unfortunately, in practice the exact convergence of the observer cannot be guaranteed due to noises, inaccuracy of digital realization of the continuous-time observer, etc. So, in fact the additional robustness analysis of the closed-loop system is required. This second step does not assume fulfilling separation principle. The stability and robustness analysis in this case has to be done for whole closed-loop system including observer and controller parts. In particular, an output-based control design was presented for delay-free linear [START_REF] Polyak | Suppression of bounded exogenous disturbances: Output feedback[END_REF] and nonlinear (quasi-Lipschitz) [START_REF] Gonzalez-Garcia | Using the method of invariant ellipsoids for linear robust output stabilization of spacecraft[END_REF] systems using attractive (invariant) ellipsoids method (AEM) [START_REF] Nazin | Rejection of bounded exogenous disturbances by the method of invariant ellipsoids[END_REF], [START_REF] Gonzalez-Garcia | Output linear feedback for a class of nonlinear systems based on the invariant ellipsoid method[END_REF]. The present paper extends this technique to systems with unknown and time-varying input delay.

The paper is organized as follows. The next section considers notations used in the paper. Section III presents system description and problem statement. Then, the attractive ellipsoid method is introduced and discussed for timedelay systems. Section V.A develops the control algorithm for quasi-Lipschitz nonlinear systems with unknown and time-varying input delay. The scheme for tuning of the control parameters in order to minimize the stabilization error according AEM is introduced. Finally, numerical simulation results are presented.

II. NOTATIONS

• R is a set of real numbers; R + := {x ∈ R : x > 0}.

• The notation diag{λ 1 , ..., λ n } means diagonal matrix with elements λ i , where λ i may be both numbers and square matrices. • I n = diag{1, 1, ..., 1} ∈ R n×n is an identity matrix;

• λ max (P ) and λ min (P ) denote maximum and minimum eigenvalues of the symmetric matrix P ∈ R n×n . • The notation P > 0(< 0, ≥ 0, ≤ 0) for P ∈ R n×n means that P is symmetric and positive (negative) definite (semidefinite). • trace P is a sum of diagonal elements of the matrix P ∈ R n×n .

III. PROBLEM STATEMENT

Consider the input delay control system of the form

ẋ = Ax + Bu(t -h(t)) + Df (t, x), y = Cx + Eg(t), (1)
where x ∈ R n is the system state, u ∈ R m is the vector of control inputs, y ∈ R k is the measured output, A ∈ R n×n , B ∈ R n×m , C ∈ R k×n , D ∈ R n×r and E ∈ R k×p are known matrices. The input delay h(t) is assumed to be unknown but bounded by

0 ≤ h ≤ h(t) ≤ h, (2)
where h : R → R is a locally measurable function and the numbers h, h are given. Denote ∆h = h -h.

The locally measurable function f : R n+1 → R r describes bounded exogenous disturbances and system uncertainties

f T (t, x)Q f f (t, x) ≤ 1, ∀t ∈ R and ∀x ∈ R n , (3)
where Q f ∈ R r×r is a given positive definite matrix.

The locally measurable function g : R → R p describes bounded deterministic measurement noises

g T (t)Q g g(t) ≤ 1, ∀t ∈ R, (4)
where Q g ∈ R p×p is a given positive definite matrix.

The system (1) is studied with the initial conditions:

x(0) = x 0 u(t) = v(t) for t ∈ [-h, 0), (5)
where v : R → R n is some continuous function.

Assumption The pair (A, B) is controllable and the pair (A, C) is observable.

Assumption 2: The information on the control signal u(t) on the time interval [t -h, t) can be stored and used for control design proposes.

The main goal of this paper is to present a control algorithm, which

• stabilizes the states of the system (1) at the origin;

• minimizes (in some sense) negative effects of exogenous disturbances, measurement noises and uncertainties of time delay.

IV. ATTRACTIVE ELLIPSOIDS METHOD FOR TIME DELAY SYSTEMS

The classical optimal control concept addresses the problem of the minimization of some functional (for example, quadratic) subject to all possible trajectories of the system with admissible controls. Taking system uncertainties and disturbances into account requires robustification of the optimal control schemes. The optimality concept presented in the paper [START_REF] Nazin | Rejection of bounded exogenous disturbances by the method of invariant ellipsoids[END_REF] considers the stabilization problem for the linear disturbed control system. It introduces a criterion based on the minimal attractive ellipsoid of the system, which characterizes an influence of disturbances to the closed-loop system. The optimal AEM control minimizes (in some sense) the disturbances effects (i.e. suppresses them). This concept is definitely very close to H ∞ -control approaches. The similar control ideas were presented in the paper [START_REF] Usoro | A Lagrange approach to set-theoretic control synthesis[END_REF] in the beginning of 1980s. However, in that time the authors were not able to propose the effective computational schemes for control parameters tuning. Today control design using attractive ellipsoids methods admits LMI formalization [START_REF] Boyd | Linear Matrix Inequalities in System and Control Theory[END_REF], [START_REF] Nazin | Rejection of bounded exogenous disturbances by the method of invariant ellipsoids[END_REF] and the scheme for optimal adjustment of control parameters can be represented as Semi-Definite Programming Problem [START_REF] Nazin | Rejection of bounded exogenous disturbances by the method of invariant ellipsoids[END_REF], [START_REF] Gonzalez-Garcia | Using the method of invariant ellipsoids for linear robust output stabilization of spacecraft[END_REF], [START_REF] Polyakov | Invariant ellipsoid method for minimization of unmatched disturbances effects in sliding mode control[END_REF].

In order to describe the principles of AEM for time-delay systems let us consider initially the control system with constant and known input delay:

ẋ(t) = Ax(t) + Bu(t -h) + Df (t) (6)
where x ∈ R n is the system state, the matrices A, B, D are the same as in the equation ( 1), h ∈ R + is a given constant, disturbance function f (t) satisfies (3) and u ∈ R n is a fullstate predictor-based linear control [START_REF] Artstein | Linear systems with delayed controls: A reduction[END_REF]:

u(t) = Kz(t) (7)
where L ∈ R m×n is the matrix of the feedback gains and

z(t) = e Ah x(t) + 0 -h e -Aθ Bu(t + θ)dθ. (8)
The predictor variable z(t) satisfies the following delay-free differential equation

ż(t) = (A + BK)z(t) + e Ah f (t). (9)
Definition 3 ([24]): The ellipsoid

ξ(P ) = {z ∈ R n : z T P -1 z ≤ 1}, P > 0 ( 10
)
with the center in the origin and the configuration matrix P is said to be invariant (attractive) for the system (9), (3) if the property z(0) ∈ ξ(P ) implies z(t) ∈ ξ(P ) for all t > 0, (z(t) → ξ(P ) as t → ∞) holds for any f satisfying (3).

The attractive ellipsoids can be considered as a characteristic of the influence of the disturbances (3) to the system (6) in a steady mode. So, if the control u provides minimal (in some sense) attractive ellipsoid to the closed-loop system [START_REF] Artstein | Linear systems with delayed controls: A reduction[END_REF], then it can be considered as an AEM optimal stabilizing controller, which minimizes the effects of the system disturbances [START_REF] Nazin | Rejection of bounded exogenous disturbances by the method of invariant ellipsoids[END_REF].

The usual criterion of the ellipsoid minimality [START_REF] Nazin | Rejection of bounded exogenous disturbances by the method of invariant ellipsoids[END_REF], [START_REF] Gonzalez-Garcia | Using the method of invariant ellipsoids for linear robust output stabilization of spacecraft[END_REF], [START_REF] Polyakov | Invariant ellipsoid method for minimization of unmatched disturbances effects in sliding mode control[END_REF] is minimize trace(P ).

The trace of the matrix P describes the sum of the squares of the ellipsoid's semiaxes.

For linear delay-free system (9) any attractive ellipsoid is also invariant [START_REF] Nazin | Rejection of bounded exogenous disturbances by the method of invariant ellipsoids[END_REF]. However, for the original time-delay system (6) the attractive and invariant set may not coincide [START_REF] Polyakov | Minimization of disturbances effects in time delay predictor-based sliding mode control systems[END_REF]. Indeed, let ξ(P z ) be some invariant ellipsoid for the system [START_REF] Krstic | Delay Compensation for Nonlinear, Adaptive, and PDE Systems[END_REF]. Then using the formula for the solution of the system (6) we obtain

x(t + h) = e Ah x(t) + t+h t e (t+h-s)A Bu(s -h)ds+
+ h 0 e (h-θ)A Df (t + θ)dθ = z(t) + h 0 e (h-θ)A Df (t + θ)dθ.
The last integral term is called unavoidable stabilization error [START_REF] Polyakov | Minimization of disturbances effects in time delay predictor-based sliding mode control systems[END_REF].

Let us denote by S w the set of all possible values of the unavoidable stabilization error, which is bounded due to [START_REF] Flower | Relaxation oscillations in a class of delay differential equations[END_REF]. Then the obtained formula gives the attractive set S x = S x (P z ) for the original system (6) (see, Fig. 1 ) in the form

S x = ξ(P z ) +S w ,
where ξ(P z ) is an invariant ellipsoid for the prediction system (9) and the symbol + means the Minkowski (geometrical) sum of the sets (see, for example, [START_REF] Kurzhanski | Ellipsoidal Calculus for Estimation and Control[END_REF]).

It is easy to see, that y(t) → ξ(P z ) implies x(t) → S x , so S x is attractive set. However, in the general case x(0) ∈ S x does not imply z(0) ∈ ξ(P z ), so S x may not be invariant.

The uncertain function f (t) is bounded for each time moment and belongs to ellipsoid ξ(Q -1 f ). Regardless of the fact that for any t and θ the value e (h-θ)A Df (t + θ) also belongs to the some ellipsoid, the sets S w and S x may not be elliptic. Due to this in [START_REF] Polyakov | Minimization of disturbances effects in time delay predictor-based sliding mode control systems[END_REF] it was introduced the optimization criterion for the attractive set S x (P z ) based on ellipsoidal estimate ξ(Q(P z )) of this set (see, Fig. 1), where Q(P z ) is a configuration matrix of minimal (with respect to trace criteria) ellipsoid, which estimates of the set S x (P z ). Due to linearity of the criterion [START_REF] Mazenc | Lyapunov-Krasovskii functionals and application to input delay compensation for linear timeinvariant systems[END_REF] the proposed construction of attractive ellipsoid reduces the problem of the AEM optimal control design for the original system (6) to the same problem for the predictor system (9) (see, Theorem 1 from [START_REF] Polyakov | Minimization of disturbances effects in time delay predictor-based sliding mode control systems[END_REF] for the details). The present paper uses this result as motivation for applying attractive ellipsoids technique only to the predictor system even when an input delay is unknown and time-varying.

V. STABILIZING CONTROL DESIGN

A. Predictor-based output feedback

Introduce a Luenberger-like observer of the form ẋ = (A + LC)x + Bu(t -h) -Ly(t), [START_REF] Polyakov | Minimization of disturbances effects in time delay predictor-based sliding mode control systems[END_REF] where the matrix L ∈ R n×k is needed to be defined. Consider also the error equation

ė = (A+LC)e+B(u(t-h)-u(t-h(t)))-Df -LEg, ( 13
)
where e = x -x.

Select the control in the form

u(t) = Kz(t), ( 14
)
where the matrix of control K ∈ R m×n is needed to be designed and

z(t) = e Ah x(t) + 0 -h e -Aθ Bu(t + θ)dθ (15)
is the predictor variable (estimating the state x at time t+h).

In this case the closed-loop system can be rewritten in the form

     ė = (A + LC)e + BK t-h t-h(t) ż(τ )dτ -Df -LEg, ż = (A + BK)z + e Ah LCe.
(16) Theorem 4: If the tuple (α, τ 1 , τ 2 , X , Z, L, Y) satisfies the bilinear matrix inequality

        Π 1 Π T 21 Π T 21 BY D LE Π 21 Π 2 Π 23 0 0 0 Π 21 Π T 23 Π 3 0 0 0 Y T B T 0 0 -1 e αh R 0 0 D T 0 0 0 -τ 1 Q f 0 E T L T 0 0 0 0 -τ 2 Q f         ≤ 0, (17)
Π 1 = AZ + ZA T + LCZ + ZC T L T + αZ, Z > 0, (18) Π 2 = AX + X A T + BY + Y T B T + αX , X > 0, ( 19
)
Π 21 = e Ah LCZ, Π 23 = AX +BY, Π 3 = R - 1 ∆h X (20) α, τ 1 , τ 2 ∈ R + : α ≥ τ 1 + τ 2 , Z, X , R ∈ R n×n , Y ∈ R m×n , L ∈ R n×k , R > 0, ( 21
) then ε(Z, X ) := {e ∈ R n , z ∈ R n : e T Z -1 e + z T X -1 z ≤ 1} (22)
is exponentially attractive ellipsoid of the system [START_REF] Dambrine | Robustness of sliding mode control under delays effects : a case study[END_REF] with

K = YX -1 .
The proof of this theorem is based on Lyapunov-Krasovskii functional method. It considers the functional of the form

V (t, e(t), z(t), ż(•)) = e T (t)Z -1 e(t) + z T (t)X -1 z(t) + V 1 (t, ż(•)) + V 2 (t, ż(•)), V 1 (t, ż(•)) = (∆h) 2 t t-h e α(s-t+h) żT (s) R ż(s)ds, V 2 (t, ż(•)) = ∆h 0 -∆h t-h t-h+θ e α(s-t+h) żT (s) R ż(s)ds dθ, where R = e -γh X -1 RX -1 .
The next lemma treats the question about feasibility of the system of matrix inequalities ( 17)-( 21) and other relaxations to SDP tools will also be given later on.

Lemma 5: Under Assumption 1 the system of matrix inequalities ( 17)-( 21) is feasible at least for small ∆h. This lemma can be proven in two steps. Firstly, we consider the reduced system of matrix inequalities, which is obtained from ( 17)-( 21) for ∆h → 0. Secondly, we use the properties of controllability and observability of the pairs {A, B}, {A, C} in order to see feasibility of the reduced system of matrix inequalities.

B. Adjustment of Control Parameters: Computational Aspects

The predictor variable z estimates the future state of observer variable x(t + h) and the vector e describes the observation error e = x -x, so in order to improve control precision we may minimize the size of the attractive ellipsoid of the system (16), i.e. we need to solve the following optimization problem minimize trace Z + trace X s.t. ( 17) -( 21).

The optimization ( 23), ( 17)-( 21) has the linear cost functional and the constraints represented in the form of Bilinear Matrix Inequality (BMI). For low order systems, such a problem can be solved by some BMI solver, for example, PENBMI. In the same time, the constraints can be restricted in order to obtain SDP problem.

Lemma 6: If for some α, β ∈ R + the following LMI system is feasible:

    -S FC FC T FC FC -V     ≤ 0, S > 0, V > 0, (24)
-

β e αh I n BY Y T B T -R ≤ 0, (25)
        QA + A T Q+ FC + C T F+ αQ + S Q QD FE Q -1 β I n 0 0 D T Q 0 -τ 1 Q f 0 E T F T 0 0 -τ 2 Q g         ≤ 0, (26)
      -2 Q 0 0 1 ∆h Q + V e Ah 0 0 e Ah e A T h 0 0 e A T h Σ       ≤ 0, (27)
α ≥ τ 1 + τ 2 , R > 0, Q > 0, X > 0, V > 0, (28)
Σ:= Π 2 √ ∆h(AX +BY) √ ∆h(AX +BY) T ∆hR -X , Q, X , S ∈ R n×n , Y ∈ R m×n , F ∈ R n×k , V ∈ R 2n×2n
then the tuple (α, X , Z, L, Y), where X = Q -1 and L = Q -1 F, satisfies ( 17)-( 21). This lemma allows to organize the procedure for controller and observer parameters tuning basing on semidefinite programming technique. Indeed, for any fixed α, β ∈ R + the system of matrix inequalities ( 24)-( 28) becomes LMI form. So, in order to minimize the attractive ellipsoid [START_REF] Polyak | Suppression of bounded exogenous disturbances: Output feedback[END_REF] we need to solve the following optimization problem minimize trace(Q -1 ) + trace X s.t. ( 24) - [START_REF] Polyakov | Invariant ellipsoid method for minimization of unmatched disturbances effects in sliding mode control[END_REF].

The cost functional of the problem is nonlinear now. Fortunately, this optimization problem is equivalent the following SDP problem minimize trace(H) + trace(X ) s.t. ( 24) -( 28) and

H I n I n Q ≥ 0, H > 0, H ∈ R n×n . (29)
This equivalence obviously follows from the inequality H ≥ Q -1 and Shur complement. For a given α, β ∈ R + let us denote by J(α, β) the solution of the optimization problem [START_REF] Kurzhanski | Ellipsoidal Calculus for Estimation and Control[END_REF]. The corresponding solution can be found using any SDP solver (for example, SeDuMi). In order to minimize the function J(α, β) some derivative-free method can be used (for example, the procedure fminsearch of MATLAB). Lemma 6 does not prove equivalence between conditions (17)-( 21) and ( 24)-( 28), since its proof is based on Λinequality (Young's matrix inequality) [START_REF] Poznyak | Advanced Mathematical Tools for Automatic Control Engineers: Deterministic Techniques[END_REF]. Therefore, the presented optimization scheme may give only suboptimal and a rather conservative solution, which can be considered just as an approximation for the AEM optimal feedback. VI. NUMERICAL EXAMPLE Consider the system (1) with parameters

A =   -0.1 1 0 -0.1 0 -0.4 0 -0.1 0.2   , B =   1 0 1   , C = 1 0 0 0 0 1 , D =   1 0.5 0   , E = 1 0 0 1 , Q f = 10

VII. CONCLUSIONS

The paper presents the output-based robust control for linear time-invariant system with unknown bounded input delay. The design procedure combines Luenberger observer with predictor scheme. Stability analysis of the closed-loop system is based on the method of Lyapunov-Krassovski functionals. Robustness properties of the presented control scheme is studied using attractive ellipsoid method. Procedure of control parameters tuning for optimal reduction of exogenous disturbances and measurement noises is formulated as an optimization problem with linear cost functional and constraints presented in the form of bilinear matrix inequalities. The scheme for finding a suboptimal solution of the obtained bilinear problem is presented using semidefinite programming technique. It is also important to study the robustness of the method with respect to parametric uncertainties, for example, in matrices A, B, C. This problem is opened for future research. The norms of the vectors of measurement noises g(t) and observation errors e(t).

Fig. 1 .

 1 Fig. 1. The attractive set Sx and its ellipsoidal estimate.

  4 and Q g = 10 4 2 -0.3 -0.3 1.[START_REF] Yefremov | An active stabilization algorithm for a spacecraft with viscoelastic elements under uncertainties[END_REF] , h = 0.35, h = 0.5.The matrix A is unstable, λ 1 = 0.273, λ 2,3 = -0.0869 ± 0.2830i. The selected matrices Q f and Q g correspond to disturbances and noises of the order O(10 -2 ).Using the optimization procedure (29) for α = 0.05 and β = 0.004 we obtain the following suboptimal solution:K subopt = -0.0232 0.0943 -0.4889 ,The numerical simulation results for the obtained output feedback control application are depicted on Fig.2-5. They have been done for h(t) = 0.35 + 0.15 sin 2 (t), f (t, x) = 0.01 cos(t), g(t) = 0.0036 sin(3t) -0.0062 cos(3t) 0.0078 sin(3t) + 0.0029 cos(3t) ,x 0 = (0.5, 0, -0.1) T and u(t) = 0 for t ∈ [-h, 0].

Fig. 2 .

 2 Fig. 2. Evolution of real and observed state x 1 .

Fig. 3 .Fig. 4 .

 34 Fig. 3. Evolution of real and observed state x 2 .

Fig. 5 .

 5 Fig. 5. Control signal u.

Fig. 6 .

 6 Fig. 6.The norms of the vectors of measurement noises g(t) and observation errors e(t).

This work was supported by EU Interreg IV A 2 Mers Seas Zeeën Cross-border Cooperation Programme under SYSIASS project 06-020. It was also supported by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the Contrat de Projets Etat Region (CPER) CIA 2007-2013.


Jean-Philippe Bombenger

Alberto Barsella

Christiane Carré

Gregory Taupier

Kokou Dodzi

Honorat Dorkenoo

Loïc Mager

Stress birefringence patterning in photopolymer induced by structured illumination

We report on the stress birefringence distribution induced by the photopatterning of a multifunctional crosslinkable acrylate monomer sensitized in the visible range. The patterning of this material, prepared in a glass cell of a few tens of microns thickness, is obtained through illumination in a two steps process. The first step is performed using an illumination pattern with a high contrast and a low spatial frequency. The second one is a uniform illumination. The discrepancies in the shrinkage experimented by the material leads to the apparition of patterned stress birefringence revealed trough polarimetry and diffraction measurements.

Nowadays, photopolymers have become true optical materials suitable for the fabrication of diffractive or refractive elements. Beside the possibility of the direct photopatterning of the material surface and refractive index at a microscopic scale, photopolymers simplify and lighten the fabrication of optical elements. Indeed, the patterning is achieved in a one step illumination process which does not require any chemical post-treatment and can be performed at low temperature. The application fields of the photopolymers are principally holography [START_REF] Dhar | Holographic storage of multiple high-capacity digital data pages in thick photopolymer systems[END_REF][START_REF] Hewett | Holographic drives set for long-awaited debut[END_REF][START_REF] Guo | A review of the optimisation of photopolymer materials for holographic data storage[END_REF] and the microscale optical elements. [START_REF] Croutxe-Barghorn | Fabrication of microlenses by direct photo-induced crosslinking polymerization[END_REF][START_REF] Zeng | Integration of polymer microlens array at fiber bundle extremity by photopolymerization[END_REF][START_REF] Pavelyev | Diffractive optical elements with radial fourlevel microrelief fabricated by two-photon polymerization[END_REF][START_REF] Neumann | Direct laser writing of surface reliefs in dry, self-developing photopolymer films[END_REF] Moreover, the doping of the photopolymer matrix with push-pull chromophores opened new development to non linear optics [START_REF] Gillot | Photo-patterning of the quadratic optical properties of doped photopolymers[END_REF] by allowing the spatial control of the quadratic optical non linearity.

In general, the photopolymers are considered as isotropic materials but anisotropy of the refractive index may appear under some specific conditions. Indeed, the birefringence can be obtained by using additives or chemical moieties with defined functions. For example, a photocrosslinkable liquid crystal is able to freeze the mesophase orientation [START_REF] Ono | New fabrication method for anisotropic gratings formed in photocrosslinkable polymer liquid crystals[END_REF] after polymerization and inherit of permanent birefringence properties. Some specific monomers exhibiting a light polarization dependant photocrosslinking allow the control of the polymeric chain grow direction. These materials are used as liquid crystal alignment layer [START_REF] Schadt | Optical patterning of multi-domain liquid-crystal display with wide viewing angles[END_REF] for the design of polarization control devices. The birefringence may also appear in non functionalized photopolymers, however in that case they are processed and used in defined conditions. In particular, when sub-wavelength refractive index gratings are built in the medium, the birefringence may originate from the so-called form birefringence regime. [START_REF] Yang | Form birefringence of volume gratings in photopolymers[END_REF] One also obtains some birefringence by applying external anisotropic stresses (mechanical, electrical, thermal…). Finally, the diffraction properties of thick gratings [START_REF] Kogelnick | Coupled wave theory for thick hologram gratings[END_REF] depend also on the polarization state of the incident beam and can then be used to build birefringent elements.

In this letter, we present an original way of inducing spatially distributed birefringence in an acrylate based photopolymer. The material used is free from any optically anisotropic additives. When the photocrosslinking is induced by an anisotropic distribution of the actinic light intensity, the photopolymer undergoes an anisotropic shrinkage that leads to a mechanical stress and consequently to a permanent birefringence. The phenomenon was observed while patterning the material using binary intensity gratings (Ronchi ruling) and studied by characterizing the diffraction properties in the Raman-Nath regime described in the following formalism.

The photocrosslinkable material presented in this paper is prepared in films with a typical thickness of few tens of microns and the grating spacing values explored are large compared to the wavelength. These experimental conditions correspond to the Raman-Nath diffraction regime. Considering a linearly polarized beam at normal incidence, the amplitude of the diffracted intensity in the l order in the Raman-Nath diffraction regime is given by equation (1): [START_REF] Born | Principles of optics[END_REF][START_REF] Goodman | Introduction à l'optique de Fourier et à l'holographie[END_REF] ( )

d n J A i l i ∆ λ π 2 2 2 , (1)
where A i is the amplitude of this incident wave linearly polarized in the direction i, J l is the l th order Bessel function of the first kind, λ the wavelength, d the sample thickness and ∆n i the amplitude of the refractive index modulation in the direction i. The polarizations of the different beams are described by their components parallel and perpendicular to the grating wavevector η the diffraction efficiency for the l th order in the parallel and perpendicular directions, A // and A ⊥ are the corresponding projections of A r . The angle between g K r and the diffracted beam polarization at l th order, ( )

g l d l d K A r r , = θ , is given by relation (3): θ η η θ tan tan // l l l d ⊥ = . (3)
Equations ( 2) and (3) show that the intensities of the diffracted beams and moreover the rotation of their polarization depend of the polarization of the incident beam. Here the depolarization due to the birefringence is not taken into account as a small birefringence does not induce an important dephasing between the components parallel and perpendicular to g K r along the propagation in a thin medium.

The material is based on a commercially available trifunctional acrylate monomer the tris[2hydroxy ethyl] isocyanurate triacrylate (SR 368, SARTOMER speciality). This monomer, solid at room temperature (T m =56°C), leads to a high hardness material (T g > 250°C) after crosslinking. Its photosensitization in the visible range is achieved by addition of bis(4cylcopentadien-1-yl)-bis[2,6-difluoro-3-(1H-pyrrol-1-yl)-phenyl]titanium (Irgacure 784, Ciba speciality) at a 3% wt. rate. The Irgacure is directly dissolved in the liquid monomer at 65°C without additional solvent and stirred over 12 hours. The mixture is then conditioned in a few tens of microns thick glass cell, filled by capillarity at 65°C. The shelf lifetime of the samples extends over more than one month. The SR368 tends to crystallize in the cell after a few days, but it can be used after a new heating at 60°C. The photopatterning of the material is achieved by imaging the desired pattern in the material. The experimental set-up is shown in Fig. 1. An argon laser provides the actinic light at 514 nm. The object is illuminated by the expanded laser beam. A rotating diffusive disk is inserted at the focus point of the beam expander to homogenize the light distribution by time averaging the speckle. The object is then imaged in the material by an association of two 1.4 numerical aperture 50 mm camera objectives. The image plane is set in the glass cell placed on a hot-plate. The focus is achieved by adjusting the object position while observing the image quality at the sample plane with a microscope. The objects imaged in the cells are binary intensity gratings with different periods from 3 to 12 lines per millimetre. The sample is placed between crossed polariser and analyser. The variation of the transmitted light intensity related to the bleaching of the photoinitiator is monitored using a photodiode to measure the light taken by a beamsplitter before the analyser. The depolarization due to the induced birefringence is monitored by measuring the light intensity at the exit of the analyzer. The patterning process occurs in two steps. First, the grating is imaged in the material, inducing the photopolymerization of the illuminated areas. In a second step, the grating is removed and the sample is uniformly illuminated. After the patterning process, the observation of the sample with a polarizing microscope reveals an alternation of bright and dark stripes due to the photoinduced birefringence (see Fig. 2).

In bulk polymerization process, the polymerization temperature, the photosensitizer concentration and the illumination conditions greatly affect the final polymerization rate and therefore the material properties. We have studied the evolution of the induced birefringence as a function of the actinic light intensities and the exposure times for the first structured illumination and for the second uniform illumination steps. The patterning protocol leading to the highest observed birefringence is the following. During the whole process, the sample is maintained at 60°C, slightly above the monomer melting temperature, to insure the fluidity of the mixture and to improve the final polymerization rate. The first illumination is achieved with a power density of 2 mW/cm 2 during 6 minutes. Then, the sample is left 20 minutes in the dark in order to ensure a complete post-polymerization process in the irradiated areas. Finally, the sample is uniformly illuminated with a 0.5 mW/cm 2 power density during 80 minutes and cooled down to room temperature.

We have characterized the diffraction properties of the photoinduced birefringent gratings using 633 nm linearly polarized light beam. The grating period was 12 lines per millimetre and the sample thickness was 100 microns. The grating fulfils the Raman-Nath diffraction regime with a Klein-Cook factor 15 Q < 0.1. At a normal incidence angle, the diffraction efficiency of the +/-1 order is 1.0±0.2 % for a light polarization parallel to g K r and 0.6±0.2 % for a polarization perpendicular to g K r . No variation of the diffraction angle with polarization was observed. The calculation of the refractive index modulation is achieved considering a sinusoidal grating in the approximation of low modulation amplitude. [START_REF] Goodman | Introduction à l'optique de Fourier et à l'holographie[END_REF] The diffraction efficiency data give an index modulation amplitude of ∆n // = (2.0±0.2)•10 -4 in g K r the parallel direction and ∆n ⊥ = (1.5±0.2)•10 -4 in the perpendicular direction. When positioning the sample between two polarizers, the extinction of the transmitted beam and of the diffracted beam are observed at different orientations of the output polarizer. For +/-1 order diffracted order, the largest rotation of the beam polarization was θ θl d = 22°, obtained for an incident beam polarization angle θ around 45° (see Fig. 3). As expected, the minimum orientation difference was observed for a polarization of the incident beam along the two directions // ê and ⊥ e ˆ. All these results are consistent with the calculations presented above. The model does not take into account a possible dephasing between the two orthogonal polarization components. This agrees with the experimental results, as no sensitive depolarisation of the transmitted or the diffracted beam is observed. Indeed, if one considers a sample with a uniform 5•10 -5 birefringence and a 100 microns thickness, at normal incidence, the dephasing between the parallel and perpendicular components is about 2° only and therefore can be neglected in the description of the diffraction.

A similar polarization effect has already been demonstrated in acousto-optics experiments [START_REF] Blomme | On the polarization of light diffracted by ultrasound[END_REF] for crystals under mechanical stress. Nevertheless, with photopolymers, it is possible to record much more complex birefringence distributions and do this more easily than using acousto-optic effect.

If the induced birefringence is negligible in the diffraction description, the induced depolarization is high enough to be observed. Advantage is taken of this depolarization to monitor the establishment of the birefringence. For this purpose, the patterning is achieved with a sample placed between crossed polarizers (see Fig. 1). The grating direction is oriented at 45° from the incident light polarization direction. The light intensity transmitted through the sample is measured before and after the analyzer in order to separate the contribution of the photoinitiator bleaching from the birefringence one. The depolarization of the transmitted light is already observed at the first step of the photopatterning process. This tendency remains in the second step until its saturation at the end of the uniform illumination. We interpret the origin of the photoinduced birefringence as the effect of stored mechanical constrains due to the non uniform shrinkage. Indeed, it is well known that the polymerization of bulk acrylate monomer based materials is accompanied by a matter densification inducing an increase of the refractive index and the shrinkage of the medium. These stresses modify the refractive index ellipsoid via elasto-optic effect. It is worthy to note that this phenomenon is only observed in high hardness material where the induced strains are not able to relax at short time scale. The photopatterning of softer materials based on other monomers as pentaerytritol triacrylate or even on plasticized SR368 doesn't induce any observable birefringence. The observation of a depolarization at the first polymerization step indicates that the anisotropic light distribution corresponding to an inhomogeneous polymerization leads to stress distribution. This phenomenon is explained considering the variation of the shrinkage with the direction leading to anisotropic strains. Therefore, by knowing the elasto-optic coefficient of the material, it would be possible to evaluate the strains induced in the materials. For a variation of the sample thickness (between 40 and 200 µm) and of the grating period (between 3 and 12 lines/mm), the diffraction efficiency remains around 1% and the birefringence around a few 10 -5 . These variations are low and the influence of the experimental conditions cannot be distinguished from the effect of samples variability. This agrees with the elasto-optics origin as the effect depends on the deformation rate and not with the absolute deformation. But, the spatial resolution of the imaging setup and of the material itself would limit the observation of birefringence at very low grating spacing. Nevertheless, the examination with the polarizing microscope shows that 120 lines/mm grating still presents some birefringence which gives hope to go the sub-micron scale optimization of the material, of the set-up (spatial resolution, depth of field) and of the process. As mentioned before, the photopolymerization conditions (temperature, light intensity, exposure time) have a sensitive influence. The conditions used here are comparable to these leading to a high polymerization rate of the final product and therefore to a high hardness material. Finally, the lifetime of the induced birefringence distribution appears to be very long. No modification of the samples properties was observed over more than six months for samples stored at room temperature.

We have demonstrated that a permanent distribution of birefringence may be induced by a photopatterning of high hardness photocrosslinkable materials. The inscription of diffraction gratings, operating in the Raman-Nath regime, was achieved and we observed a rotation of the polarization direction between the incident and the diffracted beams. The birefringence was attributed to elasto-optic effect in the material where the photopolymerization using an anisotropic light intensity distribution has induced anisotropic strains in the material.

The development of this topic requires now the development a new photocrosslinkable material with improved birefringence properties. Among the different solutions arising, the most promising one is the use of photocrosslinkable sol-gel matrix. Indeed, they present a better hardness compare to organics systems. The possibility of using different metal alkoxy should also provide a better control of the birefringence.

The mastering of the birefringent grating would allow the control of the diffraction properties by the control of the polarization of the incident beam. Here only linear gratings have been considered. It is possible to use more complicated illumination patterns (e.g. checkers board, concentric circles) leading to very complex birefringence distributions that may be used to control the polarization distribution in a light beam profile. Finally, the control of the birefringence at a microscopic scale will recover a great interest in the development and the optimization of diffractive optics elements. [START_REF] Lajunen | High efficiency broadband diffractive elements based on polarization gratings[END_REF][START_REF] Fratz | Digital polarization holograms with defined magnitude and orientation of each pixel's birefringence[END_REF]

Figure captions

22.4°

(

  050.1940) Diffraction and gratings: Diffraction (160.4890) Materials: Organic Material (260.1440) Physical optics: Birefringence (260.5430) Physical optics: Polarization

  fields associated to the different beams are given by equation 2: fields associated respectively to the incident beam and to the diffracted beam at the l th order,

Figure 1 :

 1 Figure 1: Experimental setup. (M) microscope objective, (R) rotating diffusive disk, (C) collimating lens, (G) binary grating, (O) Nikon AF NIKKOR 50 mm camera objectives, (P 1 ) polarizer, (P 2 ) analyzer, (H) hot plate, (S) sample, (B) beamsplitter, (D 1 ) photodiode for the monitoring of the variation of the transmitted intensity due to the photoinitiator bleaching, (D2) photodiode for the monitoring of the variation of the transmitted intensity due to the depolarization of light.

Figure 2 :

 2 Figure 2: Image of the photopatterned sample using a polarizing microscope. (a) polarization parallel to the grating wavevector, (b) incident polarization at 45° from the grating wavevector, (c) incident polarization orthogonal to the grating wavevector.

Figure 3 :

 3 Figure3: Polar plot of the intensity versus the exit polarizer orientation for a polarization of the incident beam at 45° from the grating wavevector. Solid squares: transmitted beam, hollow squares: first order diffracted beam. The curves correspond to the square cosine fit. The transmitted beam shows no depolarization. The 1 st order diffracted beam is linearly polarized and its polarization is rotated with a 22° angle compared to the transmitted beam.

  Figure 1

Acknowledgement

The authors acknowledge the Région Alsace and the INTERREG III / Rhenaphotonics program for their financial supports.


S E Parsegov
email: s.e.parsegov@gmail.com

A E Polyakov
email: polyakov@ipu.ru

P S Shcherbakov

Fixed-time consensus algorithm for multi-agent systems with integrator dynamics

Keywords: multi-agent systems, consensus, fixed-time convergence

The paper addresses the problem of exact average-consensus reaching in a prescribed time. The communication topology is assumed to be defined by a weighted undirected graph and the agents are represented by integrators. A nonlinear control protocol, which ensures a finite-time convergence, is proposed. With the designed protocol, any prescribed convergence time can be guaranteed regardless of the initial conditions.

INTRODUCTION

Consensus or agreement problem is a key problem in decentralized cooperative control of multi-agent systems [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF], [START_REF] Ren | Distributed Coordination of Multi-agent Networks: Emergent Problems, Models, and Issues[END_REF]. This is partly due to many important applications in control of spacecrafts, mobile robots, UAVs, sensor networks and in other fields such as optimization. In the leaderless consensus problem it is required that all nodes-agents to converge to a common value which is not prespecified in advance (minimize the disagreement between the agents in the system to zero).

In [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and timedelays[END_REF], a classical continuous linear consensus control protocol for networks of integrators was studied. It was shown that the second smallest eigenvalue of interaction graph Laplacian, called algebraic connectivity, determines the convergence rate of consensus algorithms. Evidently, the protocols that provide high convergence rate are more preferred in applications. In [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF], [START_REF] Shafi | Graph Weight Design for Laplacian Eigenvalue Constraints with Multi-Agent Systems Applications[END_REF] the problems of vertex-edge weight design to provide the desired spectra of graph Laplacians are considered. It should be noted that by maximizing the algebraic connectivity we obtain a better performance of linear algorithms but still reach an agreement just asymptotically. Moreover, the convergence time essentially depends on the initial conditions of the agents. On the other hand, in numerous practical applications it is required that the transient processes have to be finished in a prescribed time.

The main objective of this paper is to design an averageconsensus control protocol which provides the finite-time convergence property to the multi-agent system; on top of that, any guaranteed settling time has to be be specified in advance regardless of the initial positions of the agents.

The paper is supported by the RFBR grant No 13-07-00990 A The theory of finite-time stability and stabilization problems has been a subject of intensive research in recent years; e.g., see [START_REF] Haimo | Finite time controllers[END_REF], [START_REF] Bhat | Finite-time stability of continuous autonomous systems[END_REF], [START_REF] Moulay | Finite-time stability and stabilization: State of the art[END_REF], [START_REF] Orlov | Discontinous systems: Lyapunov analysis and robust synthesis under uncertainty conditions[END_REF], Polyakov & Poznyak (2012). For use of finite-time control ideology in consensus problems see [START_REF] Cortés | Finite-time convergent gradient flows with applications to network consensus[END_REF], [START_REF] Hui | Finite-time semistability, Filippov systems, and consensus protocols for nonlinear dynamical networks with switching topologies[END_REF], [START_REF] Wang | Finite-time consensus problems for networks of dynamic agents[END_REF], [START_REF] Xiao | Finite-time formation control for multi-agent systems[END_REF]. Finite-time stability analysis usually exploits the theory of non-smooth Lyapunov functions and involves such concepts as weak and strong stability, differential inclusions, generalized gradients and derivatives [START_REF] Roxin | On finite stability in control cystems[END_REF], [START_REF] Hui | Finite-time semistability, Filippov systems, and consensus protocols for nonlinear dynamical networks with switching topologies[END_REF].

Obviously, there is a great need in finite-time consensus algorithms; moreover algorithms that guarantee any predefined convergence time regardless of the initial conditions of the agents are most desired. The corresponding modification of the finite-time stability was called fixedtime stability (see, [START_REF] Polyakov | Nonlinear feedback design for fixed-time stabilization of linear control systems[END_REF]). Fixed-time algorithms can be also found in [START_REF] Andrieu | Astolfi Homogeneous Approximation, Recursive Obsertver and Output Feedback[END_REF] and [START_REF] Cruz-Zavala | Uniform robust exact differentiator[END_REF]. In [START_REF] Parsegov | Nonlinear fixedtime control protocol for uniform allocation of agents on a segment[END_REF], a fixed-time control protocol for a specific formation control problem was designed.

Polynomial state feedback control systems have attracted considerable attention in nonlinear control [START_REF] Ebenbauer | Analysis and design of polynomial control systems using dissipation inequalities and sum of squares[END_REF]. This class of control systems appears in models of a wide range of applications such as chemical processes, electronic circuits and mechatronics, biological systems, etc. This paper presents new consensus control protocols of a polynomial type which guarantee fixed-time convergence to a common value.

The paper is organized as follows. The next section presents the notations used in the paper. The section 3 discusses the problem statement and the basic assumptions. After then some preliminaries are given. The main theoretical result is formulated and proven in Section 5.

Finally, the numerical simulations results and conclusions are presented.

NOTATIONS

• R is the set of real numbers; R + = {x ∈ R : x > 0}.

• Denote by D * ϕ(t) the upper right-hand Dini derivative of the function ϕ : R → R at the point t ∈ R, i.e.

D * ϕ(t) := lim sup h→+0 ϕ(t + h) -ϕ(t) h .
• Let us introduce the power operation, which preserves the sign of the number, s [k] := sign(s)|s| k , (1) where s ∈ R and sign(s) is the sign function

sign(s) = 1 if x > 0, -1 if x < 0, 0 if x = 0.
In this case, (-2) [2] = -4.

If A ∈ R n×m then the introduced power operation A [p] is understood componentwise. For example,

A = 1 -2 3 0 , A [2] = 1 -4 9 0 .
• λ * (P ) is the minimum positive eigenvalue of the symmetric matrix P ∈ R n×n : P = P . • For z ∈ R n and p ∈ R + we denote

z p := n i=1 |z i | p 1 p .
(2)

• Denote a unit vector by

1 n = [1, 1, . . , 1] ∈ R n . • If ν = (ν 1 , ..., ν n ) ∈ R n then the notation diag(ν) is
introduced for the diagonal matrix with the elements ν i ∈ R, i = 1, 2, ..., n.

PROBLEM STATEMENT

We consider a group of n numbered mobile agents. Let their positions at time t ≥ 0 be denoted by x i (t) ∈ R, i = 1, 2, ..., n. The dynamic model of each agent is described by a simple integrator:

ẋi = u i , i = 1, 2, . . . , n, (3)
where u i ∈ R is the state feedback, called control protocol, to be designed based on the information received by agent i from its neighbors,

x = [x 1 , x 2 , . . . , x n ] .
The objective in this paper is to design a feedback control protocol u i , which

• solves the average-consensus problem in a fixed time for all initial conditions, i.e.

∃T max ∈ R + : x i (t) = x * , t > T max , where i = 1, 2, ..., n and x * := (1/n) n i=1
x i (0);

• exploits only the local information about the distances of the agent from its neighbors according to the communication topology, i.e.

u i = n j=1 φ ij x j -x i , i = 1, 2, . . . , n, (4)
where φ ij are continuous functions of distances for all i, j and φ ij = 0 if the corresponding agents are not neighboring.

Below we consider some helpful notions, definitions and auxiliary lemmas needed for further discussion.

PRELIMINARIES

Graphs and Linear Consensus Protocol

Algebraic graph theory plays an important role in the analysis of consensus problems. Each agent of multi-agent system communicates with some of the agents according to the communication topology (structure of the system). Such a structure can be represented by a (generally) directed graph. In this work, we consider graphs which are undirected and do not contain self-edges.

We use weighted undirected graph G(A) for representing the communication topology, where A = [a ij ], i, j = 1, 2, . . . , n is a weighted adjacency matrix. Each agent in the multi-agent system is associated with a vertex in the graph and a ij is a weight of the information channel represented by the edge {i, j}. If a ij = 0 it means that there is no edge between the corresponding vertices-agents.

Undirected topology means the neighboring agents receive the same information about the distance between them.

Notice that under the assumptions above, a well-known linear control protocol Olfati-Saber & Murray ( 2004), Chebotarev & Agaev (2009) of the form

u i = n j=1 a ij (x j -x i ), i = 1, 2, . . . , n, (5)
does solve the average-consensus problem; however the agents reach consensus asymptotically and the settling time depends on the initial conditions.

The dynamics of multi-agent system (3) under control protocol (5) can be rewritten in a vector form ẋ = -Lx, (6) where L is a symmetric matrix n × n named the Laplacian of graph G(A): L = diag(A1 n ) -A.

The matrix L of an undirected graph has some properties that are important in analysis of consensus problems (see [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and timedelays[END_REF][START_REF] Yu | Coordination in multiagent systems and Laplacian spectra of digraphs[END_REF], [START_REF] Ren | Distributed Coordination of Multi-agent Networks: Emergent Problems, Models, and Issues[END_REF]):

• L has at least one zero eigenvalue with associated eigenvector 1 n . • L has a simple zero eigenvalue if and only if the corresponding graph is connected. x Lx

• x Lx = 1 2 n i,j=1 a ij (x j -x i ) 2 ;
x 2 = λ * (L) > 0, (7) and therefore n i=1

x i = 0 implies x Lx ≥ λ * (L)x x.

Fixed-time Convergence

Consider the following system: ż = g(t, z), z(0) = z 0 , (8) where z ∈ R n and g : R + × R n → R n is a possibly discontinuous nonlinear function. In this case, the solutions of (8) are understood in the sense of [START_REF] Filippov | Differential Equations with Discontinuous Right-Hand Sides[END_REF]. Assume that the origin is an equilibrium point of system (8). Definition 1. [START_REF] Bhat | Finite-time stability of continuous autonomous systems[END_REF]). The origin is said to be a globally finite-time stable equilibrium point for system (8) if it is globally asymptotically stable and any solution z(t, z 0 ) of (8) attains it in finite time, i.e., z(t, z 0 ) = 0 ∀ t ≥ T (z 0 ), where T : R n → R + ∪ {0} is the settling-time function.

For example, any solution of the system ż = -z 1 3 , z ∈ R, converges to the origin in the finite time T (z 0 ) := 2 3 [START_REF] Polyakov | Nonlinear feedback design for fixed-time stabilization of linear control systems[END_REF]). The origin is said to be a fixed-time stable equilibrium point of system (8) if it is globally finite-time stable and the settling-time function T (z 0 ) is bounded, i.e. there exists T max > 0 :

3 |z 0 | 2 . Definition 2.
T (z 0 ) ≤ T max ∀z 0 ∈ R n . The system ż = -z [ 1 2 ] -z [2] , z ∈ R, z(0) = z 0 is fixed-time stable, since its solution has the form z(t,z 0 )=    sign(z 0 ) tan 2 T (z 0 ) -t 2 0 ≤ t ≤ T (z 0 ), 0 t > T (z 0 ),
where T (z 0 ) = 2 arctan( |z 0 |) ≤ π. Lemma 3. [START_REF] Polyakov | Nonlinear feedback design for fixed-time stabilization of linear control systems[END_REF]). If there exists a continuous radially unbounded function V : R n → R + ∪ {0} such that

(1) V (z) = 0 ⇔ z = 0;

(2) any solution z(t) of ( 8) satisfies the inequality D * V (z(t)) ≤ -(αV p (z(t)) + βV q (z(t))) k for some α, β, p, q, k > 0: pk < 1, qk > 1, then the origin is globally fixed-time stable for system (8) and the following estimate holds:

T (z 0 ) ≤ 1 α k (1 -pk) + 1 β k (qk -1) , ∀z 0 ∈ R n .
This lemma together with its refinement given below are the cornerstones for the design of the nonlinear fixed-time average-consensus control protocol.

Consider the case where the constants p and q are of the form p = 1 -1 2γ and q = 1 + 1 2γ , γ > 1. Lemma 4. [START_REF] Parsegov | Nonlinear fixedtime control protocol for uniform allocation of agents on a segment[END_REF]). If there exists a continuous radially unbounded function V :

R n → R + ∪ {0} such that (1) V (z) = 0 ⇔ z = 0;
(2) any solution z(t) of (8) satisfies the inequality D * V (z(t)) ≤ -αV p (z(t))-βV q (z(t)) for some α, β > 0, p = 1 -1 2γ , q = 1 + 1 2γ , γ > 1, then the origin is globally fixed-time stable for system (8) and the following estimate of the settling time function holds:

T (z 0 ) ≤ T max := πγ √ αβ ∀z 0 ∈ R n .
The last lemma provides more exact estimate of the settling time (see, [START_REF] Parsegov | Nonlinear fixedtime control protocol for uniform allocation of agents on a segment[END_REF] for the details).

FIXED-TIME CONSENSUS CONTROL PROTOCOL

Consider now the situation where every edge {i, j} is associated with some function φ ij that satisfy

φ ij x j -x i = -φ ji x i -x j , (9)
for two neighboring agents and φ ij ≡ 0 if there is no edge between the vertices i and j. In Olfati-Saber & Murray ( 2004), the functions φ ij are referred to as action functions.

Recall s [k] := sign(s)|s| k (see, the section with notations).

Choose the following action functions meeting the condition ( 9)

φ ij = α(a ij (x j -x i )) [µ] + β(a ij (x j -x i )) [ν] ,
(10) where α, β ∈ R + , µ ∈ (0, 1), ν > 1 are control parameters and a ij = a ji ≥ 0, i, j = 1, 2, . . . , n are elements of the weighted adjacency matrix A. Theorem 5. Consider system (3) with a connected communication topology, i.e. the graph G(A) is connected. Given the control protocol

u i = n j=1 φ ij x j -x i , i = 1, 2, . . . , n, (11)
the system (3) solves the average-consensus problem in a finite time, which is globally bounded by T 1 max :

T 1 max = 2 ᾱ(1 -µ) + 2 β(ν -1) , ∀x 0 ∈ R n , (12) ᾱ
= α2 µ (λ * (L µ )) µ+1 2 , β = β2 ν n 1-ν 2 (λ * (L ν )) ν+1 2
, where α, β ∈ R + , µ ∈ (0, 1) and ν > 1 are control parameters, L µ and L ν are the Laplacians of the graphs

G A [ 2µ µ+1 ] and G A [ 2ν ν+1 ] , respectively.
Proof. The proof uses on some ideas introduced in Olfati-Saber & Murray ( 2004) for nonlinear action functions ϕ ij of general form.

Denote

x * := (1/n) n i=1

x i (0).

Introduce a vector

δ = [δ 1 , δ 2 , . . . , δ n ] called disagree- ment, x i (t) = x * + δ i (t).
It is easy to see that δi (t) = ẋi (t) and x j -x i = δ j -δ i , for all i, j = 1, 2, . . . , n.

Since the equality (9) holds, then

n i=1 ẋi (t) = 0. (13) Hence (1/n) n i=1 x i (t) = (1/n) n i=1 x i (0) = x * and n i=1 δ i (t) = 0, ∀t > 0. (14)
Therefore, average-consensus problem will be implied by stability of the following system δi =

n j=1 φ ij δ j -δ i , i = 1, 2, . . . , n. (15)
Introduce the following Lyapunov function candidate

V (δ) = 0.5δ δ = 0.5 n i=1 δ 2 i . (16)
Its total derivative is

V (δ) = n i=1 δ i δi = n i=1 δ i n j=1 φ ij δ j -δ i .
Taking into account (9) we derive

V (δ) = n i=1 n j=1 δ i φ ij δ j -δ i = 0.5 n i=1 n j=1 δ i φ ij δ j -δ i + 0.5 n i=1 n j=1 δ j φ ji δ i -δ j = 0.5 n i=1 n j=1 δ i φ ij δ j -δ i -0.5 n i=1 n j=1 δ j φ ij δ j -δ i = -0.5 n i=1 n j=1 (δ j -δ i )φ ij δ j -δ i . (17)
Since s = sign(s)|s| then from ( 10) and ( 17) we can easily obtain

V (δ) = 1 2 n i,j=1 (δ i -δ j ) αa µ ij (δ j -δ i ) [µ] +βa ν ij (δ j -δ i ) [ν] = -1 2 n i,j=1 αa µ ij |δ j -δ i | µ+1 +βa ν ij |δ j -δ i | ν+1 ≤ 0.
Since 1 < µ + 1 < 2, ν + 1 > 2, then using the norm equivalence property

z l ≤ z r ≤ n 1 r -1
l z l for any z ∈ R n and l > r > 0 ( • p is defined by ( 2)), we estimate V (δ) as follows:

V (δ) ≤ -0.5α   n i,j=1 a 2µ µ+1 ij (δ j -δ i ) 2   µ+1 2 -0.5βn 1-ν 2   n i,j=1 a 2ν ν+1 ij (δ j -δ i ) 2   ν+1 2
.

The equality (7) implies that for

n i=1 δ i = 0 we have n i,j=1 a 2µ µ+1 ij (δ j -δ i ) 2 = 2δ L µ δ ≥ 4λ * (L µ )V (δ), ( 18
) n i,j=1 a 2ν ν+1 ij (δ j -δ i ) 2 = 2δ L ν δ ≥ 4λ * (L ν )V (δ), (19)
where L µ and L ν are the Laplacians of a weighted graphs

G A [ 2µ µ+1 ] and G A [ 2ν ν+1 ] , respectively.
Taking into account ( 18), ( 19) and ( 14) we get

V (δ(t)) ≤ -2 µ α(λ * (L µ )) µ+1 2 V µ+1 2 -2 ν βn 1-ν 2 (λ * (L ν )) ν+1 2 V ν+1 2 .
Introduce the following notations: p = µ+1 2 , q = ν+1 2 , ᾱ = 2 2p-1 α(λ * (L µ )) p , β = 2 2q-1 βn 1-q (λ * (L ν )) q .

Then the total derivative of the Lyapunov function calculated along the trajectories of (15) satisfies the following inequality V (δ(t)) ≤ -ᾱV p (δ(t)) -βV q (δ(t)),

ᾱ, β > 0, 0 < p < 1, q > 1, which by Lemma 3 immediately implies fixed-time stability of the origin of the system (15) with the settling time estimate (12).

The theorem presents quite a conservative settling time estimate, since its proof is based on the results of Lemma 3. A more accurate estimate can be derived with the use of the Lemma 4 as formulated by the next corollary. Corollary 6. If, under the conditions of Theorem 5, the parameters µ and ν of protocol ( 11) are chosen as µ = 1-1 γ ν = 1 + 1 γ , γ > 1, then the settling time can be estimated by the following value

T 2 max := πγn 1 4γ 2 √ αβλ 1 2 -1 4γ * (L µ )λ 1 2 + 1 4γ * (L ν ) . (21)
The proof of this corollary immediately follows from inequality ( 20) and Lemma 4.

The fixed-time control protocols have an advantage in convergence rate with respect to both finite-time and linear protocols even in the case real-life applications, which usually deal with the practical stability concept. Due to system uncertainties, exogenous disturbances, delays and measurement noises the practical realization of a control protocol provides only convergence to a zone (a neighborhood of the origin). So, in practice both finite-time and linear protocols have similar qualitative property, namely, they provide finite-time convergence to the neighborhood of the origin. Moreover, in practical applications finitetime algorithms are only locally faster than linear ones. In contrast to this, the fixed-time control guarantees convergence to the same zone in a fixed time, which can be prescribed independently of initial conditions. It is faster than finite-time and linear protocols globally and locally. More detailed analysis of the practical fixed-time stability is given in Polyakov (2012).

Example.

To demonstrate the efficiency of the proposed fixed-time consensus protocol we consider the multi-agent system which consists of 6 agents with integrator dynamics (3) and the interaction topology represented by the following undirected graph

For the same initial conditions x(0) = x 0 := [350,100,200,250,400, 500] Fig. 1 presents the results of simulations for the linear and the proposed nonlinear control protocols. The values of the The obtained estimates T 1 max and T 2 max confirm the theoretical conclusions of Theorem 5 and Corollary 6 showing fixed-time convergence to average consensus in the nonlinear case. The settling time is seen to be less than the theoretical estimates:

T 1 max ≈ 3.438, T 2 max ≈ 2.548, (22) real convergence time is about T (x 0 ) ≈ 1.647. It can be also seen that the second estimate gives much more precise result.

CONCLUSIONS

The contribution of the paper is the following:

• a nonlinear control protocol to solve an averageconsensus problem is developed; • it is proved that the guaranteed settling time of the system can be specified in advance regardless of the initial conditions of the agents (fixed-time convergence); • the two different estimates for the settling time are obtained; • as opposed to the known finite-time consensus control protocols the designed fixed-time control protocol guaranties the convergence rate faster than the linear one globally; • the prespecified settling time is shown to be independent of the dimension of the agents.

On the other hand there is one drawback: we considered only the case of undirected topology. This problem is subjected for future research.

The theoretical results were successfully tested through several numerical experiments. The fixed-time stability framework applied in the paper looks promising in different multi-agent problems.

  the semipositive definiteness means that all other eigenvalues are positive. • For a connected graph the second smallest eigenvalue λ * (L) = λ 2 (L) is called the algebraic connectivity of L. It quantifies the convergence rate of consensus algorithms. • The algebraic connectivity equals min x =0, 1 n x=0

Fig. 1 .

 1 Fig. 1. Structure of the system parameters of the fixed-time control law (11) were chosen as γ = 1.1 ⇒ µ ≈ 0.091, ν ≈ 1.909, α = β = 1. in order to compare them.

Fig. 2 .

 2 Fig. 2. Trajectories of the system under the linear and nonlinear protocols