Eric Goubault
email: goubault@lix.polytechnique.fr

Aurélien Sagnier
email: aure-lien.sagnier@polytechnique.edu

Michael Farber
email: m.farber@qmul.ac.uk

Directed topological complexity

Keywords: Directed topology, topological complexity, controlled systems, homotopy theory

It has been observed that the very important motion planning problem of robotics mathematically speaking boils down to the problem of finding a section to the path-space fibration, raising the notion of topological complexity, as introduced by M. Farber. The above notion fits the motion planning problem of robotics when there are no constraints on the actual control that can be applied to the physical apparatus. In many applications, however, a physical apparatus may have constrained controls, leading to constraints on its potential future dynamics. In this paper we adapt the notion of topological complexity to the case of directed topological spaces, which encompass such controlled systems, and also systems which appear in concurrency theory. We study its first properties, make calculations for some interesting classes of spaces, and show applications to a form of directed homotopy equivalence.

Introduction

In this paper we adapt the notion of topological complexity [Farber, 2003], [Farber, 2008], to the case of directed topological spaces. Let us briefly motivate the interest in a notion of "directed" topological complexity. It has been observed that the very important motion planning problem of robotics mathematically speaking boils down to the problem of finding a section to the path-space fibration χ : X I → X × X

(1)

where χ(p) = (p(0), p(1)); here X I denotes the space of all continuous paths p : I = [0, 1] → X. If this section can be continuous, then the complexity TC(X) is the lowest possible (equals to one), otherwise, TC(X) is defined as the minimal number of "discontinuities" that would encode such a section. The notion of topological complexity is understandable both algorithmically, and topologically, e.g. TC(X) = 1 is equivalent for X to be contractible.

Generally speaking, the topological complexity TC(X) is defined as the Schwartz genus of the path space fibration. The above definition fits the motion planning problem of robotics when there are no constraints on the actual control that can be applied to the physical apparatus that is supposed to be moved from the state a to the state b. In many applications, however, a physical apparatus may have dynamics that can be described as an ordinary differential equation in the state variables x ∈ R n in time t, and parameterised by the control parameters u ∈ R p , ẋ(t) = f (t, x(t), u(t)).

(2)

The control parameters u(t) are usually restricted to lie within a set u ∈ U . Equivalently, as is well-known, one may describe the variety of trajectories of the control system (2) is by using the language of differential inclusions,

ẋ(t) ∈ F (t, x(t)), (3)
where F (t, x(t)) is the set of all f (t, x(t), u) with u ∈ U . Under some well-investigated conditions this differential inclusion can be proven to have solutions, at least locally. Under these conditions, the set of solutions of the differential inclusion (3) naturally forms a directed space, compare [Grandis, 2009], see also section 2 below. We observe in this paper that the motion planning problem of robotics in the presence of control constraints equates to finding sections to the analogue of the path space fibration (1), i.e. the map taking a d-path to the pair of its end points1 . This material is developed in the following sections where we work in the generality of directed spaces. In particular we introduce the notion of a directed homotopy equivalence which has precisely, and in a certain non technical sense, minimally, the right properties with respect to the directed version of topological complexity.

Definitions

The context of a d-space was introduced in [Grandis, 2009]; we will restrict ourselves later to a more convenient category of d-spaces, that ought to be thought of as some kind of cofibrant replacement of more general (but sometimes pathological) d-spaces.

Definition 1 ( [Grandis, 2009]). A directed topological space, or a d-space X = (X, P X) is a topological space equipped with a set P X of continuous maps p : I → X (where I = [0, 1] is the unit segment with the usual topology inherited from R), called directed paths or d-paths, satisfying three axioms :

• every constant map I → X is directed;

• P X is closed under composition with continuous non-decreasing maps from I → I;

• P X is closed under concatenation.

Note that for a d-space X, the paths space P X is a topological space, equipped with the compact-open topology.

A map f : X → Y between d-spaces is a d-map if it is continuous and for any directed path p ∈ P X the path f • p : I → Y belongs to P Y . In other words we require that f preserves directed paths.

Remark. Given a topological space X equipped with a set D of paths p : I → X, closed under concatenation and such that the union of the images p(I), for p ∈ D is X, we call saturation D of D the smallest set of paths containing D that forms a d-structure on X. The saturation of D is just made of all composites of path of D with continuous and non-decreasing maps from I to I.

d-spaces in control theory. Consider a differential inclusion ẋ ∈ F (x) (4)
where

F is a map from R n to ℘(R n ), the set of all subsets of R n . A function x : [0, ∞) → R n is a solution of inclusion (4) if
x is absolutely continuous and for almost all t ∈ R one has ẋ(t) ∈ F (x(t)), see [Aubin and Cellina., 1984]. In general, there can be many solutions to a differential inclusion.

Lemma 1. [Aubin and Cellina., 1984] Suppose a set-valued map F : R n R n is an upper semicontinuous function of x and such that the set F (x) is closed and convex for all x. Then there exists a solution to Equation (4) defined on an open interval of time.

Consider a smooth manifold X and an upper semicontinuous set-valued mapping x → F (x) where for x ∈ X the image F (x) is a convex cone contained in the tangent space to X at point x, i.e. F (x) ⊂ T x X. Let P X denote the saturation of the set of all solutions to the differential inclusion ẋ ∈ F (x). Then the pair (X, P X) is a d-space. d-spaces in concurrency and distributed systems theory. The semantics of concurrent and distributed systems can be given in terms of d-spaces, more specifically in terms of geometric realizations [START_REF] Fajstrup | [END_REF] of certain pre-cubical sets. As an example, consider the following concurrent program, made of two processes T 1 , T 2 , and two binary semaphores a, b, i.e. resources, that can only be accessed locked by one of the two processes [START_REF] Fajstrup | [END_REF]] at a time : T 1 = P a.V a.P b.V b, T 2 = P a.V a.P b.V b, in the notations. This means that process T 1 is locking a (P a), then relinquishing the lock on a (V a), then locking b (P b), and finally relinquishing the lock of b (V b). Process T 2 does the same sequence of actions. The semantics of this concurrent program is depicted in Figure 1 : it is a partially ordered space X, i.e. a topological space with a global order ≤, closed in X × X. Its d-space structure is given by choosing dipaths to be paths p : I → X such that p is non-decreasing. A number of such dipaths are depicted in Figure 1.

The d-paths map.

In what follows, we will be particularly concerned with the following map : Definition 2. Let (X, P X) be a d-space. Define the d-paths map χ : P X → X × X by χ(p) = (p(0), p(1)) where p ∈ P X.

This map is analogous to the classical path-space fibration (1); the essential distinction is that in the directed setting χ, as defined above, is not necessary a fibration.

Since P X contains only directed paths, the image of χ is a subset of X × X, denoted

Γ X = {(x, y) ∈ X × X | ∃p ∈ P X, p(0) = x, p(1) = y }.
In the classical case, one do not need to force the restriction to the image of the path space fibration since the notions of contractibility and path-connectedness are simple enough to be defined separately. In the directed setting, d-contractibility, and "d-connectedness"are not simple notions and will be defined here through the study of the d-path space map.

Notations: For a, b ∈ X, the symbol P X(a, b) will denote the subspace of P X consisting of all d-paths from the point a ∈ X to the point b ∈ X. We denote by * the concatenation map P X(a, b) × P X(b, c) → P X(a, c).

Note that P X(a, b) is non-empty if and only if (a, b) ∈ Γ X . Any d-map f : X → Y induces continuous maps Γf : Γ X → Γ Y and P f : P X → P Y , such that the diagram

P X P f → P Y ↓ χ X ↓ χ Y Γ X Γf → Γ Y commutes.
3 Directed topological complexity Let (X, P X) be a d-space such that X is an Euclidean Neighbourhood Retract (ENR).

Definition 3. The directed topological complexity -→ TC(X, P X) of a d-space (X, P X) is the minimum number n (or ∞ if no such n exists) such that there exists a map s : Γ X → P X (not necessarily continuous) and Γ X can be partitioned into n ENRs

Γ X = F 1 ∪ F 2 ∪ • • • ∪ F n , F i ∩ F j = ∅, i = j, such that • χ • s = Id, i.e.
s is a (non-necessarily continuous) section of χ;

• s| F i : F i → P X is continuous.
A collection of such ENRs, F 1 , . . . , F n , with n equal to the directed topological complexity of X is called a patchwork.

Example in control theory. As in [Farber, 2008], a motion planner, for the dynamics described by the differential inclusion (4) is a section of the d-paths map produced by the differential inclusion. A section s : Γ X → P X associates to any pair of points (x, y) ∈ Γ X an "admissible" path s(x, y) = γ ∈ P X with γ(0) = x and γ(1) = y.

Example in concurrency and distributed systems theory. Examine again Figure 1; a section of χ is just a scheduler for the actions of the processes T 1 and T 2 .

In the theory of usual (i.e. undirected) topological complexity [Farber, 2003], [Farber, 2008], there are several other equivalent definitions, for example the topological complexity TC(X) is also the minimal cardinality of the covering of X × X by open (resp. closed) sets admitting continuous sections; moreover, the book [Farber, 2008] contains four different definitions of TC(X) leading to the equivalent notions of TC(X). In the directed case, however, the definitions with open or closed covers lead to notions which can be distinct between themselves as well as distinct from the notion with the ENR partitions given above.

Example 1. Consider the interval I = [0, 1] with the d-structure given by the set of all non-decreasing paths, i.e. p : [0, 1] → [0, 1] such that p(t) ≤ p(t ′ ) for any t ≤ t ′ . The space Γ I is {(x, y); x ≤ y} and the map χ : P I → Γ I admits a continuous section

s(x, y)(t) = (1 -t)x + ty where t ∈ [0, 1]. Hence
-→ TC(I) = 1. Note that in this example the space Γ I is contractible and the map χ is a fibration with a contractible fibre.

I + ∩ Γ I -is a 3 point set {(b, b), (b, e)
, (e, e)}. Since each of the sets Γ I ± is contractible we obtain that Γ-→ S 1 is homotopy equivalent to the wedge S 1 ∨ S 1 . Next we observe that the map χ : P -→ S 1 → Γ-→ S 1 admits no continuous section over any neighbourhood U of the point (b, e) ∈ Γ-→ S 1 . To show this one notes that the preimage χ -1 (b, e) has two connected components, one of which consists of the d-paths lying in I + and the other of the d-paths lying in I -. Any open set U ⊂ Γ-→ S 1 containing (b, e) must contain a pair (x + , y + ) ∈ Γ I + and a pair (x -, y -) ∈ Γ I -, arbitrarily close to (b, e). Moreover, we may find two sequences (x ± n , y ± n ) ∈ Γ I ± of points converging to (b, a) and the limits of any section over U along these sequences would land in different connected component of χ -1 (b, e). Hence, we obtain -→ TC( -→ S 1 ) ≥ 2. On the other hand, we may represent Γ-→ S 1 as the union

Γ-→ S 1 = F 1 ∪ F 2
where F 1 = Γ I + and F 2 = Γ I --{(b, e), (b, b), (e, e)} and using the previous example we see that over each of the sets F 1 , F 2 there exists a continuous section of χ. Hence we obtain

-→ TC( -→ S 1 ) = 2. ( 5
)
4 Regular d-spaces

Definition 4. A d-space (X, P X) will be called regular if one can find a partition

Γ X = F 1 ∪ F 2 ∪ • • • ∪ F n , n = -→ TC(X)
onto ENRs such that the map χ admits a continuous section over each F i and, additionally, the sets r ∪ i=1 F i are closed for any r = 1, . . . , n.

Note the following property of the sets which appear in Definition 4:

F i ∩ F i ′ = ∅ for i < i ′ . (6)
In the "undirected" theory of TC(X) this property is automatically satisfied, see Proposition 4.12 of [Farber, 2008].

All examples of d-spaces which appear in this paper are regular. At present we know of no examples of d-spaces which are not regular; we plan to address this question in more detail elsewhere.

Example 3. The directed circle -→ S 1 is regular as follows from the construction of Example 2.

The Cartesian product of d-spaces (X, P X) and (Y, P Y ) has a natural d-space structure. Any path γ : [0, 1] → X ×Y has the form γ(t) = (γ X (t), γ Y (t)) and we declare γ to be directed if its both coordinates are directed, i.e. γ X ∈ P X and

γ Y ∈ P Y . Note that Γ X×Y = Γ X × Γ Y . Proposition 1. If the d-spaces (X i , P X i ) are regular, where i = 1, 2, . . . , k, then -→ TC(X 1 × X 2 × • • • × X k ) -1 ≤ k i=1 -→ TC(X i ) -1 . (7) Proof. Denote -→ TC(X i ) = n i + 1 and let Γ X i = F i 0 ∪ F i 1 ∪ • • • ∪ F i n i
be a partition as in the Definition 4, i.e. each set F i j is an ENR, the map χ admits a continuous section over F i j and each union

F i 0 ∪ • • • ∪ F i r is closed, r = 0, . . . , n i . Denoting X = k i=1 X i
and identifying the space Γ X with the product k i=1 Γ X i , we see that the sets

F 1 j 1 × F 2 j 2 × • • • × F k j k
form a ENR partition of Γ X , where each index j s runs through 0, 1, . . . , n s . The continuous sections F s js → P X s , where s = 1, . . . , k, obviously produce continuous sections

σ j 1 j 2 ...js : F 1 j 1 × F 2 j 2 × • • • × F k j k → P X.
Consider the sets

j 1 +•••+j k =j F 1 j 1 × F 2 j 2 × • • • × F k j k = G j ⊂ Γ X , (8)
with j = 0, 1, . . . , N , where

N = n 1 + n 2 + • • • + n k .
We observe that the terms of the union (8) are pairwise disjoint and open in G j (due to ( 6)) and hence the collection of continuous maps σ j 1 j 2 ...js defines a continuous section G j → P X. This proves that -→ TC(X) ≤ N + 1 as claimed.

Corollary 1. The directed torus ( -→ S 1 ) n satisfies -→ TC(( -→ S 1 ) n ) ≤ n + 1.
Proof. This follows from Proposition 1 and 3.

Definition 5. We say that a d-space X is strongly connected if Γ X = X × X.

In other words, in a strongly connected d-space X for any pair (x, y) in X × X there exists a directed path γ ∈ P X with γ(0) = x, γ(1) = y.

Proposition 2. For any strongly connected d-space X one has TC(X) ≤ -→ TC(X).

Proof. Let X be strongly connected and let Γ

X = X × X = F 1 ∪ F 2 ∪ • • • ∪ F n be a partition into the ENRs as in Definition 3 with n = -→ TC(X).
Then the same partition can serve for the path space fibration X I → X × X which implies our result.

Example 4. Consider the directed loop O 1 which can be defined as the unit circle

S 1 = {z ∈ C; |z| = 1} ⊂ C
with the d-structure described below. Any continuous path γ : [0, 1] → S 1 can be presented in the form γ(t) = exp(iφ(t)) where the function φ : [0, 1] → R is defined uniquely up to adding an integer multiple of ±2π. We declare a path γ to be positive if the function φ(t) is nondecreasing. It is obvious that the obtained d-space is strongly connected. Hence, using Proposition 2, we obtain -→ TC(O 1 ) ≥ TC(S 1 ) = 2, . On the other hand, we can partition

S 1 × S 1 = F 1 ∪ F 2 where F 1 = {(z 1 , z 2 ) ∈ S 1 × S 1 ; z 1 = z 2 } and F 2 = {(z 1 , z 2 ) ∈ S 1 × S 1 ; z 1 = z 2 }.
It is clear that we obtain a section of χ over F 1 by assigning the constant path at z for any pair (z, z) ∈ F 1 . A continuous section of χ over F 2 can be defined as follows by moving z 1 along the circle in the positive direction towards z 2 with constant velocity. We conclude that -→ TC(O 1 ) = 2. (9)

Besides, we see that the directed loop O 1 is regular.

Corollary 2. One has, -→ TC((O 1 ) n ) = n + 1,
i.e. the directed topological complexity of the directed n-dimensional torus (O 1 ) n equals n + 1.

Proof. First we apply (9) and Proposition 1 to obtain the inequality -→ TC((O 1 ) n ) ≤ n + 1. Next we observe that (O 1 ) n is strongly connected and, by Proposition 2,

-→ TC((O 1 ) n ) ≥ TC((S 1 ) n ) = n + 1.

Directed graphs

Let G be a directed connected graph, i.e. each edge of G has a specified orientation. One naturally defines a d-structure on G as follows. Each edge of G can be identified either with the directed interval I (see Example 1) or with the loop O 1 (see Example 4) and "small directed paths", i.e. the paths lying on an edge, are the directed paths specified in Example 1 and Example 4. In general, the directed paths of G are concatenations of small directed paths.

For a directed graph G the set Γ G has the following property: if a pair (x, y) belongs to Γ G where x is an internal point of an edge e and y / ∈ e then all pairs (x ′ , y) also belong to Γ G where x ′ ∈ Int(e).

Proposition 3.

-→ TC(G) ≤ 3.

Proof. Consider the following partition Γ

G = F 1 ∪ F 2 ∪ F 3 where • F 1 is the set of pairs of vertices (α i , α j ) of G which are in Γ G ;
• F 2 is the set of pairs (x, y) ∈ Γ G made of a vertex, and the interior of an arc;

• F 3 is the set of pairs (x, y) ∈ Γ G with x and y lying in the interiors of arcs.

For each pair of vertices (α i , α j ) ∈ Γ G fix a directed path γ ij from α i to α j . This defines a section of χ over F 1 . Note that all pairs (α i , α i ) belong to Γ G and the path γ ii can be chosen to be constant.

Consider now an oriented edge e and a vertex α j such that (x, α j ) ∈ Γ G for an internal point x ∈ Int(e). Let α i be the end point of e and let γ x,α i denote the constant velocity path along e from x to α i . A continuous section of χ over Int(e) × α j can be defined as (x, α j ) → γ x,α i ⋆ γ ij where * stands for concatenation. A continuous section over α j × Int(e) can be defined similarly, and hence we have a continuous section of χ over F 2 .

Finally we describe a continuous section of χ over F 3 . Consider two oriented edges e and e ′ where we shall first assume that e = e ′ . Let α denote the end point of e and β denote the initial point of e ′ . We define a section of χ by (x, y) → γ x,α * γ αβ * γ βy for x ∈ Int(e) and y ∈ Int(e ′ ). Here γ xα denotes a constant velocity directed path along e connecting x to α; the path γ βy is defined similarly and γ αβ is a positive path from α to β.

Finally we consider the case when e = e ′ . For a pair (x, y) ∈ Γ G with x, y ∈ Int(e) we define the section by (x, y) → γ xy where γ xy is a constant velocity path along e from x to y.

All the partial sections described above over various parts of F 3 obviously combine into a continuous section over F 3 .

The following example shows that the directed topological complexity can be smaller than the usual complexity. A patchwork for Γ G : F 1 = {(b, e)} and F 2 = Γ G \F 1 . We thus have -→ TC(G) = 2 (here again, it is easy to see that there is no global section). But TC(G) = 3. However in the special case of strongly connected graphs, the directed and classical topological complexity coincide:

Proposition 4. Let G be a strongly connected directed graph. Then -→ TC(G) = TC(G) = min(b 1 (G), 2) + 1.
Proof. By [Farber, 2008], we know that T C(G) = min(b 1 (G), 2) + 1. As G is strongly connected, we have

-→ TC(G) ≥ TC(G) = min(b 1 (G), 2) + 1, see Proposition 2.
To prove that we have in fact an equality consider the following cases:

• b 1 (G) = 0. Since G is contractible and strongly connected, G must be a single point.

Then -→ TC(G) = 1 and the result follows.

• b 1 (G) = 1. It is easy to see that in this case G must be a cycle, i.e. G has n vertices v 1 , v 2 , . . . , v n and n oriented edges e 1 , e 2 , . . . , e n where e i connects v i with v i+1 for i = 1, . . . , n -1 and e n connects v n and v 1 . We see that -→ TC(G) = 2 similarly to Example 4.

As we have seen already, -→ TC( -→ S 1 ) = 2.

• b 1 (G) ≥ 2. Then TC(G) = 3 (see above) and hence -→ TC(G) ≥ 3. On the other hand, -→ TC(G) ≤ 3 by Proposition 3. Thus -→ TC(G) = 3.

Higher-dimensional directed spaces

We begin by recalling the definition of "geometric" precubical sets [Fajstrup, 2005]. The interest [START_REF] Fajstrup | [END_REF] of such precubical sets is that the precubical semantics of most programs is a geometric precubical set. Also they are sufficiently tractacle for us to compute, in some cases, their directed topological complexity, or more precisely, the directed topological complexity of their directed geometric realization, that we call, cubical complexes (see Definition 7).

Definition 6. A precubical set C is geometric when it satisfies the following conditions:

1. no self-intersection: two distinct iterated faces of a cube in C are distinct 2. maximal common faces: two cubes admitting a common face admit a maximal common face.

Definition 7. A cubical complex is K is a topological space of the form

K = λ∈Λ I n λ /≈
where Λ is a set, (n λ ) λ∈Λ is a family of integers, and ≈ is an equivalence relation, such that, writing p λ : I n λ → K for the restriction of the quotient map λ∈Λ I n λ → K, we have 1. for every λ ∈ Λ, the map p λ is injective, 2. given λ, µ ∈ Λ, if p λ (I n λ ) ∩ p µ (I nµ ) = ∅ then there is an isometry from a face J λ of I n λ to a face J µ of I nµ such that p λ (x) = p µ (y) if and only if y = h λ,µ (x).

As shown in [START_REF] Goubault | [END_REF]] :

Proposition 5. The realization of a geometric precubical set is a cubical complex.

Generalising Proposition 3 one may show that

-→ TC(X) ≤ 2 dim(X) + 1
for nice cubical complexes X. We shall address this question elsewhere.

The directed spheres

Let n be the cartesian product of n copies of the unit segment with the d-structure generated by the standard ordering on [0, 1]. Its d-space structure is generated by a partially-ordered space [START_REF] Fajstrup | [END_REF].

Definition 8. The directed sphere -→ S n of dimension n is defined as the boundary ∂ n+1 of the hypercube n+1 . Its d-structure is inherited from the one of n+1 . Proposition 6.

-→ TC( -→ S n ) = 2 for any n ≥ 1.

The case n = 1 is covered by Example 2; see [Borat and Grant, 2019] for the general case.

Directed homotopy equivalence and topological complexity

As for now, there is no uniquely well-established notion of directed homotopy equivalence between directed spaces, although there has been numeral proposals, among which one linked to our present problem [Goubault, 2017]. We take the view here that directed homotopy equivalences should at least induce equivalent trace categories, viewed with enough structure. We will show in the following sections that directed topological complexity is an invariant of simple equivalences that should be implied by any "reasonable" directed equivalences.

A simple dihomotopy equivalence, and dicontractibility

In [Goubault, 2017], one of the authors introduced a notion of dihomotopy equivalence. The most important ingredient are that two equivalent d-spaces should be homotopy equivalent in some naive way, and their trace spaces should be homotopy equivalent as well2 . First, we need to define continuous gradings : Definition 9. Let v, v ′ ∈ V , q : U → V be a continuous map, and W ⊆ U × U be the inverse image by q × q of (v, v ′ ). Suppose we have a map

h : P V (v, v ′ ) × W → P U
which is continuous and is such that for all (u, u ′ ) ∈ W , h(p, u, u ′ ) ∈ P U (u, u ′ ).

In this case, we say that h is continuously graded over W , and by abuse of notation, we write this graded map as a h : P V ⊸ P U given by grading h u,u ′ : P V (q(u), q(u ′ )) → P U (u, u ′ ), varying continuously for (u, u ′ ) ∈ W in P U P V (v,v ′ ) , with the compact-open topology.

Any reasonable dihomotopy equivalence should be in particular a d-map inducing a (classical) homotopy equivalence that also induced (classical) homotopy equivalences on the corresponding path spaces. We call this minimum requirement, a simple dihomotopy equivalence : Definition 10. Let X and Y be two d-spaces. A simple dihomotopy equivalence between X and Y is a d-map f : X → Y such that :

• f is a d-homotopy equivalence between X and Y , i.e. a homotopy equivalence with homotopy inverse a d-map g : Y → X.

• There exists a map F : P Y ⊸ P X, continuously graded by

F x,x ′ : P Y (f (x), f (x ′ )) → P X(x, x ′ ) for (x, x ′ ) ∈ Γ X , such that (P f x,x ′ , F x,x ′ ) is a homotopy equivalence 3 between P X(x, x ′ ) and P Y (f (x), f (x ′ ))
• There exists a map G : P X ⊸ P Y , continuously graded by G y,y ′ : P X(g(y), g(y ′ )) → P Y (y, y ′ ) for (y, y ′ ) ∈ Γ Y such that (P g y,y ′ , G y,y ′ ) is a homotopy equivalence between P Y (y, y ′ ) and P X(g(y), g(y ′ )).

We sometimes write (f, g, F, G) for the full data associated to the simple dihomotopy equivalence f : X → Y .

Remark :

This definition clearly bears a lot of similarities with Dwyer-Kan weak equivalences in simplicial categories (see e.g. [Bergner, 2004]). The main ingredient of Dwyer-Kan weak equivalences being exactly that P f induces a homotopy equivalence. But our definition adds continuity and directedness requirements which are instrumental to our theorems and to the classification of the underlying directed geometry. Example 6.

• Let X, Y be two directed spaces. Suppose X and Y are isomorphic as d-spaces i.e. that there exists f : X → Y a dmap, which has an inverse, also a dmap. Then X and Y are simply directed homotopy equivalent. The proof goes as follows. Take f = u, g = u -1 , P g = F the pointwise application of u -1 on paths in Y and P f = G the pointwise application of u on paths in X. This data obviously forms a directed homotopy equivalence.

• The directed unit segment -→ I is simply dihomotopically equivalent to a point. Consider the unique map f :

-→ I → { * }, and g : { * } → -→ I (the inclusion of the point as 0 in -→ I ). Define F : P { * } → P -→ I by F ( * ) being the constant map on 0 and G : P -→ I → P { * } to be the unique possible map (since P { * } is a singleton { * }).

As expected, directed topological complexity is an invariant of simple dihomotopy equivalence :

Proposition 7. Let X and Y be two simply dihomotopically equivalent d-spaces. Then -→ TC(X) = -→ TC(Y ).

Proof. As X and Y are dihomotopy equivalent, we have f : X → Y and g : Y → X dmaps, which form a homotopy equivalence between X and Y . We also get G a continuously graded map from P X to P Y , which can be restricted to G y,y ′ : P X(g(y), g(y ′ )) → P Y (y, y ′ ), inverse modulo homotopy to P g y,y ′ ; and F a continuously graded map from P Y to P X such that its restrictions to

P X(x, x ′ ), for (x, x ′ ) ∈ Γ X , F x,x ′ : P X(x, x ′ ) → P Y (f (x), f (x ′ )) is inverse modulo homotopy to P f x,x ′ . Suppose first k = -→ TC(X). Thus we can write Γ X = F X 1 ∪ . . . ∪ F X k such that we have a map s : Γ X → P X with χ • s = Id and s |F X i is continuous. Define F Y i = {u ∈ Γ Y | g(u) ∈ F X i } (which is either empty or an ENR as F X i is ENR and g is continuous) and define t |F Y i (u) = G u • s |F X i • g(u) ∈ P Y (u) for all u ∈ F Y i ⊆ Γ Y . This is a continuous map in u since s |F X i is continuous, g is continuous, and G is continuous and graded. Therefore -→ TC(Y ) ≤ -→ TC(X). Conversely, suppose l : -→ TC(Y ), Γ Y = F Y 1 ∪. . .∪F Y l such that we have a map t : Γ Y → P Y with χ•t = Id and t |F Y i is continuous. Now define F X i = {u ∈ Γ X | f (u) ∈ F Y i } (which is either empty or an ENR as F Y i is ENR and f is continous) and define s |F X i (u) = F u • t |F Y i • f (u) ∈ P X(u) for all u ∈ F X i ⊆ Γ X . This is a continuous map in u since t |F Y i is continuous, f is
continuous, and F is continuous and graded. Therefore -→ TC(X) ≤ -→ TC(Y ). Hence we conclude that -→ TC(X) = -→ TC(Y ) and directed topological complexity is an invariant of dihomotopy equivalence.

A very simple application is that some spaces must have directed topological complexity of 1 :

Definition 11. A d-space X is dicontractible if it is dihomotopically equivalent to a point.
By applying Proposition 7, as the directed topological complexity of a point is 1, all dicontractible spaces have complexity 1, as in the undirected case. Similarly to the undirected case again, although with extra conditions, the converse is also true : Theorem 1. Suppose X is a contractible d-space. Then, the dipath space map has a continuous section if and only if X is dicontractible.

Proof. As X is contractible, we have f : X → {a 0 } (the constant map) and g : {a 0 } → X (the inclusion) which form a (classical) homotopy equivalence. Trivially, f and g are dmaps, and form a d-homotopy equivalence.

Suppose that we have a continuous section s of χ. There is an obvious inclusion map i : {s(a, b)} → P X(a, b), which is graded in a and b. Define R to be this map. Now the constant map r : P X(a, b) → {s(a, b)} is a retraction map for i.

We define Finally, we note that H(u, 1) = u and H(u, 0) = s(u(0), u(1)) = i • r(u). Hence r is a deformation retraction and P X(a, b) is homotopy equivalent to {s(a, b)} and has the homotopy type we expect (is contractible for all a and b), meaning that R is a (graded) homotopy equivalence.

H : P X × [0, 1] → P X (u, t) → v s.t.      v(x) = u(x) if 0 ≤ x ≤ t 2 v(x) = s u t 2 , u 1 -t 2 x-t 2 1-t if t 2 ≤ x ≤ 1 -t 2 v(x) = u(x) if 1 -t 2 ≤ x ≤ 1
Conversely, suppose X is dicontractible. We have in particular a continuous map R : { * } → P X, which is graded in (a, b) ∈ Γ X . Define s(a, b) = R a,b ( * ), this is a continuous section of χ.

Remark :

Sometimes, we do not know right away, in the theorem above, that X is contractible. But instead, there is an initial state in X, i.e. a state a 0 from which every point of X is reachable. Suppose then that, as in the Theorem above, χ has a continuous section s : Γ X → P X. Consider s ′ (a, b) = s -1 (a 0 , a) * s(a 0 , b) the concatenation of the inverse dipath, going from a to a 0 , with the dipath going from a 0 to b : this is a continuous path from a to b for all a, b in X. Now, s ′ is obviously continuous since concatenation, and s, are. By a classical theorem [Farber, 2008], this implies that X is contractible and the rest of the theorem holds.

Example 7. Direct applications of Proposition 7 show that :

• Directed n-tori O 1 n and O 1 m cannot be simply dihomotopically equivalent when n = m.

• Directed n-tori O 1 n cannot be dihomotopically equivalent to any directed graph for n ≥ 3.

Natural homology, and dicontractibility

We now come to make a first connection between some invariants that have been introducted in directed topology (see e.g. [START_REF] Dubut | [END_REF]), like natural homology, [START_REF] Dubut | [END_REF].

We first recap the construction of such invariants.

A monotonic reparametrization r is a monotonic continuous surjection from [0, 1] to [0, 1]. Let X be a pospace, i.e. a topological space together with a closed order ≤⊆ X × X. X is then a particular d-space with the directed paths being the continuous and increasing maps from the unit segment, with the standard ordering, to X.

Let now p and q two dipaths from a to b in X. We say that p is reparametrized in q if there exists a monotonic reparametrization γ such that p • γ = q. The trace of p, written p is the equivalence class modulo monotonic reparametrization. Now we can put together all dipaths from point a to point b, modulo monotonic reparametrization in a topological space:

Let X be a pospace and a and b ∈ X. We topologize the set of traces of dipaths from a to b, with the compact-open topology. Its quotient -→ T (X)(a, b) by reparametrization, with the quotient topology is called the trace space in X from a to b (see [Raussen, 2009]).

Definition 12. We define T X to be the category whose:

• objects are traces of X

• morphisms (also called extensions) from p to q with p, a dipath from x to y and q, one from x ′ to y ′ are pairs of traces ( α , β ) such that q = α ⋆ p ⋆ β

We then define -→ T * (X) : T X → Top * which maps:

• every trace p with p from x to y to the pointed space ( -→ T (X)(x, y), p )

• every extension ( α , β ) with α dipath from x ′ to x and β dipath from y to y ′ to the continuous map α ⋆ ⋆ β :

-→ T (X)(x, y) → -→ T (X)(x ′ , y ′ ) which maps p to α ⋆ p ⋆ β .
We can now define the natural homology functors :

Definition 13 (Natural homology). We define for n ≥ 1, -→ H n (X) : T X → M (where M is Ab) composing -→ T * (X) with the (n -1) th homology group functor H n-1 .

Remark. T X is actually the category of factorization (or twisted arrow category) of the category whose objects are points of X and morphisms are traces and this makes -→ T * (X) into a natural system in the sense of [START_REF] Baues | [END_REF].

Example 8. (taken from [START_REF] Dubut | [END_REF]) We consider the pospace -→ S 1 again, which is made up of two directed segments a and b where there initial points are identified, and their final points are identified too. In the following picture, we distinguish two particular points x and y on a, with x < y (respectively x ′ and y ′ on b, with x ′ < y ′ ), which we will use to describe the category of factorization T a+b as well as the natural homology -→ H n (a + b).

0 1 a b x y x ′ y ′
The description of T a+b is now as follows. Objects of T a+b are dipaths, which can be either:

• constant dipaths, 0, x, y, x ′ , y ′ , 1, for all points x, y, x ′ , y ′ that we chose to distinguish in the picture of a + b.

• non constant and non maximal dipaths of the form [0, x], [x, y], [y, 1] etc.

• maximal dipaths a and b

We chose below to draw a picture of a subcategory of T a+b , where x, y, x ′ and y ′ are any distinguished points of a and b as discussed before. The extension morphisms in T a+b are pictured below as arrows ; for instance, there is an extension morphism from dipath [x, y] to [0, y] and to [x, 1], among other extension morphisms:

0 x y [0, x] [y, 1] [x, y] [0, y] [x, 1] a 1 x ′ y ′ [0, x ′ ] [y ′ , 1] [x ′ , y ′ ] [0, y ′ ] [x ′ , 1] b Now, we can picture a subdiagram of -→ H 1 (a + b)
, by applying the homology functor on the trace spaces from the starting point to the end point of the dipaths, objects of T a+b . For instance, the trace space -→ T (a + b)(x, y) (respectively -→ T (a + b)(0, y)) corresponding to dipath [x, y] (respectively [0, y]) in the diagram above, is just a point, hence has zeroth homology group equal to Z (respectively Z). All other zeroth homology groups are trivial with the exception of the ones corresponding to the two maximal dipaths (up to reparametrization) a and b, going from 0 to 1. In that case, -→ T (a + b)(0, 1) is composed of two points, that we can identify with a and b, and has Z 2 (or Z[a, b] with the identification we just made) as zeroth homology. Now the extension morphism from [0, y] to a induces a map in homology which maps the only generator of H 0 ( -→ T (a + b)(0, y)) to generator a in Z[a, b] as indicated in the picture below:

Z Z Z Z Z Z Z Z Z[a, b] ≃ Z 2 Z Z Z Z Z Z Z Z Z[a, b] ≃ Z 2 1 → a 1 → b
We now define bisimulation as in [START_REF] Dubut | [END_REF]. A bisimulation between functor categories into Abelian groups P : F → Ab, and Q : G → Ab is a "relation" labelled with such isomorphisms of Abelian groups, i.e. is a set of triples (σ, η, τ ) which is hereditary in the following sense :

• for all α, β ∈ F from x to x ′ , if (x, η, y) ∈ R, there exists γ, δ ∈ G from y to y ′ such that (x ′ , η ′ , y ′ ) ∈ R and such that the following diagram commutes :

P (x) Q(y) P (x ′ ) Q(y ′ ) α, β η η γ, δ
• for all γ, δ ∈ G from y to y ′ , if (x, η, y) ∈ R, there exists α, β ∈ F from x to x ′ such that (x ′ , η ′ , y ′ ) ∈ R and such that the following diagram, as above, commutes up to homotopy

P (x) Q(y) P (x ′ ) Q(y ′ ) α, β η η ′ γ, δ
The main connection with directed topological complexity is as follows :

Proposition 8. Let X be a d-space. X has directed topological complexity of one (i.e. is dicontractible) implies that its natural homologies -→ H n (X) are all bisimulation equivalent to either, 1 Z : 1 → Z for n = 1, or to 1 0 : 1 → 0 for n > 1, defined as :

• 1 is the terminal category, with one object 1 and one morphism (the identity on 1)

• 1 Z (1) = Z, 1 0 (1) = 0.

Proof. Suppose that X has directed topological complexity of 1. Then by Theorem 1, all trace spaces -→ T (X)(x, y) are contractible, for all (x, y) ∈ Γ X , hence -→ H 1 (X)(x, y) = Z and -→ H n (X)(x, y) = 0 for n > 1. Therefore the natural homology functors are all constant, either with value Z or with value 0, and it is a simple exercise to see that the relation between T X and 1 which relates all objects of T X to the only object 1 of 1 is hereditary, hence is a bisimulation equivalence.

Example 9. We get back to example -→ S 1 . Its first homology functor was calculated in Example 8 and is not a constant functor (it contains Z 2 and Z in its image). Therefore -→ S 1 cannot have directed topological complexity of 1. It is also easy to see that the first natural homology functor of O 1 is Z N between two equal points and hence cannot have directed topological complexity of 1.

Figure 1 :

 1 Figure 1: The semantics of P a.V a.P b.V b|P a.V a.P b.V b.

Example 2 .

 2 Let us consider the directed circle -→ S 1 shown on the figure below: b e It is a directed graph homeomorphic to the circle S 1 which is the union of two directed intervals I + ∪ I -; the d-paths of -→ S 1 are the d-paths lying in one of the intervals I ± . We see that P ( -→ S 1 ) = P (I + ) ∪ P (I -) and P (I + ) ∩ P (I -) is a 2-point set containing the two constant paths p b (t) ≡ b and p e (t) ≡ e. Similarly, one has Γ-→ S 1 = Γ I + ∪ Γ I -and the intersection Γ

Example 5 .

 5 Consider the following graph : b e

(

  H(u, t) is extended by continuity for t = 1 as being equal to u) As concatenation and evaluation are continuous and as s is continuous in both arguments H is continuous in u ∈ P X and in t. H induces families H a,b : P X(a, b) × [0, 1] → P X(a, b), and because H is continuous in u in the compact-open topology, this family H a,b is continuous in a and b in X.

That map would most likely not qualify for being called a fibration in the directed setting.

In[Goubault, 2017], an extra "bisimulation relation" was added to the definition, that we do not use here.

P f is the map on paths which is the natural pointwise extension of f , i.e. P f (u) is the path t → f (u(t)) when u is a path in X.


Denis A Engemann

Federico Raimondo
email: fraimondo@dc.uba.ar

Jean-Rémi King
email: jeanremi.king@gmail.

Mainak Jas
email: mainakjas@gmail.

Alex Gramfort
email: alexandre.gramfort@telecom-paritech.

Stanislas Dehaene
email: stanislas.dehaene@cea.

Lionel L Naccache
email: lionel.naccache@gmail.com

Jacobo D Sitt
email: jdsitt@gmail.com

Automated Measurement and Prediction of Consciousness in Vegetative and Minimally Conscious Patients

Recent findings in clinical neuroscience have emphasized electroencephalography (EEG) as a tool to discriminate different disorders of consciousness (DOC) such as the vegetative and the minimally conscious state. Here we present an automated approach to computing EEGmeasures of consciousness and guiding clinical diagnostics of DOC. Our approach capitalizes the automated extraction of statistically validated EEG-measures quantifying biomarkers of consciousness and filing a database thereof. In a second step, statistical models trained on the database of EEG-measures are then used to predict an incoming patient's state of consciousness. For each new patient, the results of the EEG and the predictions are automatically summarized and deployed to the clinician in form ICML Workshop on Statistics, Machine Learning and Neuroscience * equal contributions of a self-contained HTML-report, which supports interactive visualization and navigation. To validate our approach, we replicated previous findings on EEG-measures of consciousness and quantified the robustness of the EEG-measures to loss of temporal and spatial information. Our results suggest that the EEG-measures can be successfully employed in a wide range of practical contexts to measure a patients degree of consciousness.

1. An automated scalable approach to measure and predict consciousness in clinical settings

Advances in contemporary medicine have as consequence that increasingly more patients survive catastrophic brain injuries but remain in disordered consciousness conditions, such as the vegetative (VS) or the minimally conscious state (MCS). Recent brain imaging and neurophysiological studies have enhanced the scientific understanding of these conditions, but also emphasize novel diag-nostic challenges [START_REF] Laureys | Coma and consciousness: paradigms (re) framed by neuroimaging[END_REF]. The distinction of MCS from VS patients can be elusive even for trained physicians. For example, non-standardized behavioral evaluations can lead to misclassifications of up to 40% [START_REF] Schnakers | Diagnostic accuracy of the vegetative and minimally conscious state: clinical consensus versus standardized neurobehavioral assessment[END_REF], which in turn can lead to erroneous pain-management, prognosis evaluation and even misinformed end-of-life decisions. Furthermore, for a small proportion of patients that are correctly classified as VS (by means of their behavioral responses), functional neuroimaging suggests preserved consciousness [START_REF] Owen | Detecting awareness in the vegetative state[END_REF]. This poses challenges on multiple, interdisciplinary levels. One such challenge is related to incorporating scientific findings on neural correlates of consciousness into the clinical and diagnostic practice. Over the last decade, abundant electrophysiological signatures of consciousness have been proposed. Recently, a systematic analysis of electroencephalography (EEG) measures has been put forward by [START_REF] Sitt | Large scale screening of neural signatures of consciousness in patients in a vegetative or minimally conscious state[END_REF]. A set of measures has been identified that allows to differentiate patients in a vegetative state from those in a minimally conscious or conscious state. These measures quantify putative biomarkers of consciousness such as low-frequency brain-rhythms, stimulusrelated synchronization of EEG signals (evoked responses), information sharing between electrodes and signal complexity. Importantly, previous multivariate classification analyses suggested that these EEG-measures capture complementary information as they yield superior classification performance when combined. This poses the question of how such advanced analysis of the EEG recordings can be used in practice to facilitate clinical diagnostics.

A system for guiding clinical diagnostics of consciousness disorders

Here we implemented an automated solution to clinical diagnostics of disorders of consciousness (DOC) based on statistical analysis of clinical EEG. Its goal is to estimate an undiagnosed patient's degree of consciousness based on the EEG-measures described in [START_REF] Sitt | Large scale screening of neural signatures of consciousness in patients in a vegetative or minimally conscious state[END_REF] and to efficiently communicate the EEG-analysis together with the diagnostic prediction. For this purpose we developed a flexible and scalable data analysis workflow that automates processing of EEG recordings, the extraction of EEG-measures and the communication of results (cf. figure 1 for an illustration of the workflow). The solution that we present here is purely based on open source software and is scalable on multiple levels.

For example, by taking advantage of the Python language and its parallel processing libraries such as joblib1 , multiple CPU-cores can be used to carry out numerical computations. Previously, the only available option to compute the EEG-measures proposed by [START_REF] Sitt | Large scale screening of neural signatures of consciousness in patients in a vegetative or minimally conscious state[END_REF] consisted in using local computers and required licenses for commercial software. Moreover, our solution has built-in support for Amazon web services (AWS), which allows to carry out computations in parallel across subjects. With 20 virtual workstations of which each is equipped with 4 CPU-cores for example, the computation time can be cut down by a factor of 80. Currently, for a single recording, all EEGmeasures can be computed in about 30 minutes. These benchmarks are particularly relevant for the practical purpose of the system. The current implementation facilitates the computation of reference models that are estimated on EEG-measures from hundreds of clinical recordings to predict unseen patients.

This not only facilitates more frequent updates of these reference models, which may be required for research purposes. It also lowers the maintenance burdens, i.e., of detecting and fixing software bugs. To communicate results efficiently, we devised an HTML-report tool that embeds images together with the requisite Java-script code enabling interactive navigation. This self-contained feature promotes automated dispatch of summary-reports to clinicians or operators, hence, facilitates review and interpretation.

This approach thus minimizes manual interaction or intervention by the operator to produce and review findings and is therefore expected to reduce errors. To the best of our knowledge this solution is novel and constitutes the first automated workflow for diagnostics of DOC patients. The following sections detail the implementation strategy and present a validation of the proposed solution based on the analysis of clinical EEG data from DOC patients.

Implementation details

1.2.1. SOFTWARE
Our software solution is based on open source technologies and is written in Python, C, and bash shell scripts.

The computation of the EEG-measures described in [START_REF] Sitt | Large scale screening of neural signatures of consciousness in patients in a vegetative or minimally conscious state[END_REF] was implemented in Python, taking advantage of the Numpy and Scipy libraries for fast matrix calculus and scientific computing [START_REF] Jones | SciPy: Open source scientific tools for Python[END_REF]. Some performance critical computations have been deferred to code written in C, accompanied by Python bindings. Bash scripts are then used to handle distributed computing and distributing jobs using GNU-parallel [START_REF] Tange | Gnu parallel -the command-line power tool[END_REF]. For general data-processing and visualization the open source software package MNE is used [START_REF] Gramfort | MEG and EEG data analysis with MNE-Python[END_REF]2014) The report-technology has meanwhile been made publicly available as part of the MNE package. For unsupervised learning and classification, the scikit-learn library for machine learning is used [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF].

(A) (B) (C) (D)

EEG-RECORDINGS AND PROCESSING

For development and validation analyses, the data reported in [START_REF] Sitt | Large scale screening of neural signatures of consciousness in patients in a vegetative or minimally conscious state[END_REF] were used. Subjects were stimulated using the auditory Local-Global protocol [START_REF] Bekinschtein | Neural signature of the conscious processing of auditory regularities[END_REF]. In this protocol, subjects were presented with a series of sounds that contains regularities at two different hierarchical levels, a local level defined by short-term and global level defined by long-term regularities. The deviations from these regularities evoke distinct event-related potentials that are useful to evaluate the cognitive state of the patient. EEG recordings were sampled at 250 Hz with a 256-electrode geodesic sensor net (EGI) referenced to the vertex. Recordings were band-pass filtered (from 0.5 to 45Hz using a 12 order FFT-based Butterfly filter). Data were then epoched from -200ms to +1336ms relative to the onset of the first sound.

The following parameters reflect default settings of our software solution and do not depend on the validation dataset. Trials were excluded based on their amplitude range with a rejection threshold at 100mV . Trials were subsequently baseline corrected over the first 200 ms window preceding the onset of the first sound. Electrodes with a rejection rate superior to 20% across trials were rejected and were interpolated using a spherical spline interpolation.

To remove remaining artifacts, the FastICA [START_REF] Hyvärinen | Independent component analysis[END_REF] algorithm for Independent Component Analysis (ICA) was used in concert with the ADJUST procedure for identifying artefact-related EEG signal components [START_REF] Mognon | Adjust: An automatic eeg artifact detector based on the joint use of spatial and temporal features[END_REF]. Subsequently, data were rereferenced using an average reference. All data were processed in Python 2.7 using the open source software package MNE [START_REF] Gramfort | MEG and EEG data analysis with MNE-Python[END_REF]2014). Figure 2 gives an overview about the single data processing steps.

Note that our EEG-processing workflow is not confined to a specific EEG-vendor and does not require task-related EEG-recordings.

Notable changes as of July 2015

Adaptive outlier detection To automate detection and repair of bad EEG data segments, we developed an adaptive outlier detection procedure. This procedure first selects bad electrodes where more than 50 % of the epochs have a peak-to-peak amplitude higher than 100 µV . The second step consists on computing the variance of each individual channel and its corresponding z-score across all channels. Channels with a z-score greater than 4 are discarded. This operation is repeated four times. The remaining data is then analysed at the epoch level: epochs with more than 10% of the channels outside the 100 µV peak-to-peak amplitude range are then discarded. Finally, the second step is repeated, but with the standard deviation of the channels filtered with a 4 th order Butterworh high-pass filter at 25 Hz. In order to use the same set of electrodes for every patients, electrodes marked as "bad" by the outlier algorithm are interpolated using a spherical spline interpolation [START_REF] Perrin | Spherical splines for scalp potential and current density mapping[END_REF]. Data was finally re-referenced using an average reference and baseline corrected over the first 200 ms window preceding the onset of the first sound.

Independent Component Analysis By the time of the construction of the pipeline in 2015, no accurate automated procedure for selection of ICAcomponents has been available. While semi-automated procedures can be used at scale in smaller dataset where manual checking and correction is feasible, the situation is quite different in larger datasets where exhaustive quality checks are expensive in terms of human processing time. In particular, when not correcting wrong labeled ICA components, there is a substantial risk of removing signal of interest. After some experimentation, we therefore decided to refrain from using ICA in this pipeline.

Validation of EEG-measures of consciousness

To validate the extraction of the EEG-measures against the reference implementation, we replicated the main analysis from [START_REF] Sitt | Large scale screening of neural signatures of consciousness in patients in a vegetative or minimally conscious state[END_REF] on univariate classification (cf. figures 1 and 2, supplement) and we validated the multivariate classification against alternative algorithms and implementations (cf. Figure 3, supplement). We further profiled the EEG-measures by evaluating their discriminative performance as information was removed from the input data. For this purpose, the original data from [START_REF] Sitt | Large scale screening of neural signatures of consciousness in patients in a vegetative or minimally conscious state[END_REF] were used. We considered a subset of patient recordings comprising 69 samples of MCS and 76 samples of VS patients. To emulate the impact of different sensor geometry, the spatial coverage and acquisition settings, the data were spatially (number of sensors) and temporally (sampling frequency) subsampled. Results were then recomputed on the subsampled data and compared to the full data. Classification was based on a support vector machine with an area under the curve (AUC) performance metric. A filter-based feature selection (best k features as defined by univariate F-statistic) and the regularization parameter (C) were tuned using a grid search with 10 fold stratified cross-validation that was repeated 5 times. Figure 3 depicts measure-wise (average across sensors) central tendencies and dispersion across all subsampled datasets. For details on the computation of the univariate AUC scores, see the supplementary materials.

It can be observed that certain types of measures, for example the wSMI connectivity measure [START_REF] King | Information sharing in the brain indexes consciousness in noncommunicative patients[END_REF] or evoked response measures, such as the contingent nega- et al. (2013; 2014)). Subsequently, the EEG data are cleaned from environmental noise, intrinsic and physiological artifacts. This is achieved by peak-to-peak amplitude rejection of contaminated data segments and removal of artifact signal components as estimated from Independent Component Analysis (ICA). Data are then segmented according to task-related events or fixed-length epochs (resting state) and stored to disk. In the next step relevant EEG-measures are computed and stored to disk together with meta-data and added to the database. Visual summaries of the results are saved into an HTML report. Fed with EEG-measures from the database, a statistical model is employed to estimate the probability of each diagnostic class. Visual summaries of the patient's measured EEG-measures and the probability estimates are deployed in form of a second HTML report. The entire procedure is scalable and can be executed locally or remotely on multiple workers in a distributed fashion.

tive variation (CNV) exhibit more performance variability across data inputs. In contrast, information theory measures, e.g., PE, K and low frequency cortical oscillations show little variability, e.g., α, θ and δ. These findings were expected as the connectivity measures naturally benefit from higher spatial sampling density, whereas α power can be computed on single favorably located sensors. This latter finding extends previously reported results [START_REF] Sitt | Large scale screening of neural signatures of consciousness in patients in a vegetative or minimally conscious state[END_REF]. Not only are low-frequency oscillations among the Discriminative performance of EEG-measures across subsampled data 256) was progressively subdivided by two and remaining electrodes were manually selected. They were chosen such that the resulting electrode net was spatially symmetric and included a subset of standard locations described by the international 10-20 system. In total, 6 electrode nets (256 to 8 electrodes) were compared at 250Hz and 125Hz temporal sampling frequency. The boxplots summarize each EEG-measure individually depicting the central tendency and dispersion of area under the curve (AUC) scores across the datasets. The red lines represent the median, the red squares the mean. The results suggest that certain EEG-measures were more robust across varying density of information in the input data. Note that AUC scores below 0.5 indicate a negative relationship between the respective EEG-measure and the targetcategory. Acronyms for EEG-measures are explained in the supplementary materials (cf. Table 1). A multuvariate comparison is depicted in figure 4 most robust predictors of consciousness, their computation is also highly robust across different sensor configurations and temporal sampling rates. This is of high practical relevance, as it may inform practitioners about reasonable low cost choices for the assessment of consciousness. For instance, the low frequency brain rhythms can be reliably extracted from a few electrodes only using a low temporal sampling frequency. This finding may have practical implication when single measures have to be selected for fast ambulant screening based on low-density EEG. Likewise, these measures remain robust at reduced sampling rates which may be helpful for mobile EEG acquisition setups with limited recording capacity such as for long term recordings. Additional insights can be obtained from comparing crossvalidated classification performance based on multivariate inputs including all the EEG-measures. Figure 4 depicts such scores for each subsampled version of the input data. The findings show considerable overlapping estimation variance across folds for each dataset, suggesting that for multivariate classification the availability of high-density sampling is not particularly relevant. In other words, regular clinical EEG-setups that commonly include between 32 and 64 channels are sufficient to acquire data from which reliable EEG-measures can be computed.

To summarize, the experiments provide novel insights re-garding the stability, or reliability, of the EEG-measures. The univariate results (cf. Figure 3) highlight certain types of measures that are more robust to loss of information than others. In contrast, the multivariate results (cf. Figure 4) demonstrate that removing temporal and spatial information does not relevantly decrease predictive performance when all information is fed into a statistical model.

Conclusion

In the present work we presented an integrated scalable solution for measuring, predicting and guiding clinical diagnostics of disorders of consciousness (DOC). This approach promotes a translation from neuroscience findings and data science technologies to clinical practice. The validation analyses not only suggest a successful implementation of the EEG-measures reported in [START_REF] Sitt | Large scale screening of neural signatures of consciousness in patients in a vegetative or minimally conscious state[END_REF] but also extend our understanding of their practical properties such as their dependency on particular acquisitions setups. Future enhancement in classification and diagnostics are expected from incorporating additional samples (clinical EEG-recordings) and a prediction of the patient's recovery into the proposed system. Similarly, it should be easily adjustable to other physiological and pathological conditions in which an evaluation of the subject's degree of consciousness is relevant. This would at least include anesthesia and sleep. Our solution, this way, promotes a diagnostic practice emphasizing brain-circuits disorders [START_REF] Insel | Brain disorders? precisely[END_REF].

Figure 1 .

 1 Figure 1. Overview on the automated approach to measurement and diagnostics of consciousness. Panel (A) and (B) illustrate group results for a subset of EEG-measures for different groups of patients suffering from disorders of consciousness (DOC), i.e., vegetative state (VS), minimally conscious state (MCS) and conscious (CS). Panel (A) depicts univariate area under the curve (AUC) scores for mean values across channels. From top to bottom, permutation entropy (PE), complexity measure (K), the wSMI connectivity, normalized alpha-band power, the classification score for the global and the local auditory novelty task, respectively, and the contingent negative variation (CNV). Different colors and different sizes refer to contrasts of interest and significance thresholds, respectively. Big circles refer to false discovery-rate (FDR) corrected p-values. The computation of the EEG-measures was implemented after Sitt et al. (2014), supplementary materials. Panel (B) depicts related topographies for a subset of the measures shown in panel (B). The outermost column shows a non-parametric statistical map based on a Wilcoxon rank sum test where white, gray and black areas indicate uncorrected p-values greater than 0.05, smaller than 0.05 or smaller than 0.01 respectively. Panel (C) illustrates the overall workflow. EEG data are entered into the system by the operator, the automated pipeline is launched on a web-server, summary reports are dispatched to the operator. Panel (D) shows a screenshot of a diagnostic report that presents the estimated probability of the patient being in a minimally conscious state.

Figure 2 .

 2 Figure2. Schematic EEG data-processing workflow. The procedure comprises two complementary routines, depicted by blue and red connecting arrows between the steps. Directly after acquisition, data are converted in to the FIFF file format (cf.[START_REF] Gramfort | MEG and EEG data analysis with MNE-Python[END_REF] 2014)). Subsequently, the EEG data are cleaned from environmental noise, intrinsic and physiological artifacts. This is achieved by peak-to-peak amplitude rejection of contaminated data segments and removal of artifact signal components as estimated from Independent Component Analysis (ICA). Data are then segmented according to task-related events or fixed-length epochs (resting state) and stored to disk. In the next step relevant EEG-measures are computed and stored to disk together with meta-data and added to the database. Visual summaries of the results are saved into an HTML report. Fed with EEG-measures from the database, a statistical model is employed to estimate the probability of each diagnostic class. Visual summaries of the patient's measured EEG-measures and the probability estimates are deployed in form of a second HTML report. The entire procedure is scalable and can be executed locally or remotely on multiple workers in a distributed fashion.

Figure 3 .

 3 Figure3. Univariate evaluation of discriminative performance of different EEG-measures as spatial and temporal information is removed from the data. New datasets were derived from temporally and spatially subsampling the original data. To generate a set of realistic electrode nets the original number of electrodes (256) was progressively subdivided by two and remaining electrodes were manually selected. They were chosen such that the resulting electrode net was spatially symmetric and included a subset of standard locations described by the international 10-20 system. In total, 6 electrode nets (256 to 8 electrodes) were compared at 250Hz and 125Hz temporal sampling frequency. The boxplots summarize each EEG-measure individually depicting the central tendency and dispersion of area under the curve (AUC) scores across the datasets. The red lines represent the median, the red squares the mean. The results suggest that certain EEG-measures were more robust across varying density of information in the input data. Note that AUC scores below 0.5 indicate a negative relationship between the respective EEG-measure and the targetcategory. Acronyms for EEG-measures are explained in the supplementary materials (cf. Table1). A multuvariate comparison is depicted in figure4

https://pythonhosted.org/joblib/ parallel.html

Acknowledgments

References


Caetano B Cardeliquio
email: caetano.cardeliquio@l2s.centralesupelec.fr

André R Fioravanti
email: fioravanti@fem.unicamp.br

Catherine Bonnet
email: catherine.bonnet@l2s.centralesupelec.fr

Silviu-Iulian Niculescu
email: silviu.niculescu@l2s.centralesupelec.fr

Stability and Robust Stabilisation Through Envelopes for Retarded Time-Delay Systems

Keywords: Robust Stabilisation, Stability, State-Feedback, Time-delay systems

This work deals with stability and robust stabilisation of retarded time-delay systems by applying a new method for obtaining an envelope that bounds all the system poles. Through LMIs we are able to determine envelopes that can be applied to verify the stability of the system and can also be utilised to design robust state-feedback controllers which cope with design requirements regarding αstability.

INTRODUCTION

Time-delays are inherently coupled with almost every dynamical system. This can be due to the time necessary to acquire the information needed for the control, the time required to transport information, the processing time, the sampling period, the propagation time on networked systems, among many others. Although many times those delays are neglected, they may cause poor performance or, in a worst scenario, they may even cause instability. Stability for time-delay systems was discussed, among others, in [START_REF] Michiels | Stability, Control, and Computation for Time-Delay Systems -an Eigenvalue-Based Approach[END_REF], [START_REF] Richard | Time-delay systems:an overview of some recent advances and open problems[END_REF] and [START_REF] Briat | Stability Analysis of Time-Delay Systems[END_REF].

For the stabilisation through state feedback, delay independent controllers can be devised using Riccati equations [START_REF] Lee | Memoryless H ∞ Controllers for State Delayed Systems[END_REF]; [START_REF] Shen | Memoryless Stabilization of Uncertain Dynamic Delay Systems: Riccati Equation Approach[END_REF], whereas the delay dependent case was designed by means of Lyapunov-Krasoviskii functionals in Fridman andShaked (2001, 2002); Niculescu (1998a). Lyapunov-Krasoviskii functionals were also utilised for robust control of state delay systems in [START_REF] Xia | Robust control of state delayed systems with polytopic type uncertainties via parameter-dependent lyapunov functionals[END_REF]. A controller design approach through a finite LTI comparison system was developed in [START_REF] Cardeliquio | Stability Analysis and State-Feedback Control Design for Time-Delay Systems[END_REF] and in [START_REF] Cardeliquio | Stability Analysis and Output-Feedback Control Design for Time-Delay Systems[END_REF]. Criteria for robust stability and stabilisation was dealt in [START_REF] Li | Criteria for robust stability and stabilization of uncertain linear systems with state delay[END_REF]. Robust exponential stabilisation for systems with time-varying delays can be seen in [START_REF] Seuret | Robust exponential stabilization for systems with time-varying delays[END_REF]. Robust stability and stabilisation for singular systems with parametric uncertainties were discussed, among others, in [START_REF] Xu | Robust stability and stabilization for singular systems with state delay and parameter uncertainty[END_REF] and [START_REF] Wang | Delaydependent robust stability and stabilization for uncertain singular system with time-varying delay[END_REF]. Delay independent stability for uncertain systems can be seen in [START_REF] Luo | Delay-independent robust stability of uncertain linear systems[END_REF] and delay dependent stability and stabilisation in [START_REF] Moon | Delay-dependent robust stabilization of uncertain statedelayed systems[END_REF], [START_REF] Fridman | Parameter dependent stability and stabilization of uncertain time-delay systems[END_REF] and [START_REF] Boukas | Delay-dependent robust stabilizability of singular linear systems with delays[END_REF]. The discrete counterpart was studied in [START_REF] Wu | On stability and stabilizability of positive delay systems[END_REF], for positive systems. Guaranteed LQR control was dealt in [START_REF] Kubo | Guaranteed LQR properties control of uncertain linear systems with time delay of retarded type[END_REF] and robust polytopic H ∞ static output feedback in [START_REF] Eli | Retarded linear systems with stochastic uncertainties -robust polytopic H ∞ static output-feedback control[END_REF]. Finally, α-stability was discussed in [START_REF] Wang | α-stability analysis of perturbed systems with multiple noncommensurate time delays[END_REF] for non commensurate delays and in [START_REF] Niculescu | H ∞ memoryless control with an α-stability constraint for time-delay systems: an lmi approach[END_REF] via LMIs.

The use of an envelope that ensures that all poles are contained inside it was discussed in [START_REF] Michiels | Stability, Control, and Computation for Time-Delay Systems -an Eigenvalue-Based Approach[END_REF]. Different types of envelopes were also discussed in T. Mori and Kokame (1989) and [START_REF] Wang | Further results on stability of ẋ(t) = Ax(t) + Bx(tτ )[END_REF]. In those cases, the methods utilised to establish the envelopes were not used to test stability nor to design controllers. In fact, in general, the envelope extends to the right half plane and due to that, it only provides a region where the poles are allowed to be without any guarantee about the stability of the system. The present work is based on Linear Matrix Inequalities (LMIs) instead of the singular value approach, see [START_REF] Michiels | Stability, Control, and Computation for Time-Delay Systems -an Eigenvalue-Based Approach[END_REF], and provides a different analysis regarding the use of envelopes. A procedure to test robust stability for retarded time-delay systems is established. In addition, a robust state-feedback controller coping with project requirements regarding α-stability can be designed.

Notation. Matrices are denoted by capital letters, whilst small letters represent scalars and vectors. For real matrices or vectors the symbol ( ′ ) indicates transpose and for complex matrices or vectors the symbol ( * ) denotes conjugate transpose. The determinant of a matrix A is indicated by det(A). The sets of real, integer and natural numbers including zero are denoted by R, Z and N, respectively. ℜ(.) is the real part of a complex number. A left eigenvector is defined as a row vector x L satisfying x L A = λ L x L , where λ L is a left eigenvalue of the matrix A. For partitioned matrices the symbol • represents each one of its Hermitian blocks. The induced p-norm of a matrix A is given by A p , A ∈ C n×m . Finally, X > 0 (X ≥ 0) denotes that the symmetric matrix X is positive definite (positive semi-definite).

PROBLEM STATEMENT

Consider the uncertain retarded linear time-delay system with N delays, whose minimal realisation is given by

ẋ(t) = N i=0 A i x (t -τ i ) , (1)
where

x(t) ∈ R n is the state variable, 0 = τ 0 < τ 1 < • • • < τ N are the delays, A i ∈ R n×n for all i ∈ {0, .
. . , N } and the system matrices belong to a convex polytope

P := co A ℓ 0 , • • • , A ℓ N , ℓ ∈ 1, . . . , N v ,
(2) defined by the convex combination of N v vertices. Each matrix can be individually defined as [START_REF] Bernussou | A linear programming oriented procedure for quadratic stabilization of uncertain systems[END_REF])

A i := Ni ℓ=1 ξ ℓ i A ℓ i , Ni ℓ=1 ξ ℓ i = 1, ξ ℓ i ≥ 0 . (3) Hence, N v = Π N i=0 N i . Example 1.
As an example consider the matrix

A 1 = -2 [0 1] [-1 3] 2 (4)
where [0 1] and [-1 3] represents the parametric uncertainty on A 1 . This matrix can be rewritten as

A 1 = ξ 1 1 A 1 1 + ξ 2 1 A 2 1 + ξ 3 1 A 3 1 + ξ 4 1 A 4 1 (5) where ξ 1 1 + ξ 2 1 + ξ 3 1 + ξ 4 1 = 1 , ξ 1 1 , ξ 2 1 , ξ 3 1 , ξ 4 1 ≥ 0 .
It is easy to see that the convex combination that creates A 1 for this particular transition matrix is

A 1 = ξ 1 1 -2 0 -1 2 + ξ 2 1 -2 1 3 2 + ξ 3 1 -2 0 3 2 + ξ 4 1 -2 1 -1 2 . (6)
System ( 1) is exponentially stable if and only if all zeros of its characteristic equation

det sI - N i=0 A i e -sτi = 0 (7)
are in the open left half-plane [START_REF] Bellman | Differential-difference equations[END_REF].

The following Proposition introduces an envelope that completely surround all of its poles. Proposition 1. Let λ be any real number. If there exist a characteristic root s 0 of equation ( 7), such that s 0 = λ+ω and if there exist matrices

T = T ′ > 0, Q i = Q ′ i > 0, for all i ∈ {0, . . . , N } and a scalar µ that satisfy     T T . . . T Q 0 . . . Q N     ≥ 0, (8) and 
   µT A ℓ 0 Q 0 e -λτ0 . . . A ℓ N Q N e -λτN • Q 0 0 0 • 0 . . . 0 • 0 0 Q N     ≥ 0, (9)
for all ℓ ∈ {1, . . . , N v }, then

|s 0 | ≤ √ µ. ( 10
)
Proof: First, let us consider the nominal system without any uncertainties, i.e., N v = 1. The following inequality is always true, which is easily verifiable applying Schur's complement

A i Q i A ′ i e -2λτi • A ′ i e -(λ-ω)τi Q -1 i ≥ 0. ( 11
)
Adding them for all i ∈ {0, . . . , N } leads to

      N i=0 A i Q i A ′ i e -2λτi • N i=0 A ′ i e -(λ-ω)τi N i=0 Q -1 i       ≥ 0, ( 12
)
where we can apply Schur's complement and utilise (9) to get

µT ≥ Σ N i=0 Q -1 i -1 Σ * , (13) where Σ
N i=0 A i e -(λ+ω)τi . Notice that from (8) T ≥ N i=0 T Q -1 i T, (14)
which multiplying through the left and through the right by T -1 and calculating its inverse leads to

T ≤ N i=0 Q -1 i -1 . ( 15
)
Therefore, using this result in (13), implies that µT ≥ ΣT Σ * .

Finally, let s 0 = λ + jω be an eigenvalue of Σ associated with a right-eigenvector v. It is well known, see [START_REF] Strang | Introduction to Linear Algebra[END_REF] and [START_REF] Bulirsch | Introduction to numerical analysis[END_REF], that left and right eigenvalues are equal. Hence, s 0 is also an eigenvalue of Σ associated with a left-eigenvector x L , with dimension 1 × n. In this case, we can multiply inequality ( 16) to the left by x L and to the right by its conjugated transpose,

x * L , obtaining µx L T x * L ≥ x L ΣT Σ * x * L (17) and since x L = 0 and T > 0, µ ≥ (λ + ω)(λ -ω), (18) leading to |s 0 | ≤ √ µ. ( 19
)
Finally, for the uncertain system, it follows immediately from the linear dependence of the LMIs that the solution of the problem in question is obtained calculating it in each one of the vertices, ℓ ∈ {1, . . . , N v }, of the polytope of uncertainties P, given by (2), which concludes the proof.

STABILITY

We shall now see how one can use the envelope to analyse the stability of a retarded time-delay system. Proposition 2. Let λ = λ 0 ∈ R, µ = λ 2 0 -ε, for some ε > 0. If there exist T, Q i > 0, for all i ∈ {0, . . . , N } such that (8) and ( 9) are both satisfied, then the envelope lies entirely on the left side of the vertical axis crossing λ 0 .

Proof: From ( 19) we have that if λ + ω is a root of the system, then

|λ + ω| ≤ λ 2 0 -ε, (20)
which can be rewritten as

λ 2 + ω 2 ≤ λ 2 0 -ε. (21)
This expression, clearly, is never going to be satisfied with λ ≥ λ 0 , which implies that it cannot exist parts of the envelope to the right side of the vertical axis passing through λ 0 .

With this result, we propose a change of coordinates through the new variable s = z-d, with d > 0. Calculating the envelope for z, (7) becomes

det zI -(A 0 + dI) - N i=1
A i e -zτi e dτi = 0, (

allowing us to work with an equivalent problem on the new parameters Ã0 = A 0 + dI,

Ãi = A i e dτi , for all i ∈ {1, . . . , N }. (23)
From equation ( 19) we have that λ 2 + ω 2 ≤ µ directly implies ω = ± µλ 2 , for µ ≥ λ 2 . The envelope is then defined on the complex plane by the set of points where ω = ± µλ 2 , when µ ≥ λ 2 . For µ < λ 2 we define the envelope as "closed". Now, if the envelope is closed on the z-plan before z = d, it will be closed before the origin on the s-plan, guaranteeing stability for the original system. Hence, the existence of a solution for ( 9) and ( 8), for the modified system (23), with µ = d 2ε and λ = d, for some d > 0 and ε > 0, it implies that the original system (1) is stable.

STATE-FEEDBACK

We now address the stabilisation problem. Consider the system

ẋ(t) = N i=0 A i x (t -τ i ) + Bu(t), (24)
with A i given by (3), B defined as

B := M ℓ=1 η ℓ B ℓ , M ℓ=1 η ℓ = 1, η ℓ ≥ 0 (25)
and the polytope redefined as

P := co A ℓ 0 , • • • , A ℓ N , B ℓ , ℓ ∈ 1, . . . , N v , (26)
with

N v = M Π N i=0 N i .
We want to control this system by means of a state feedback control law u(t) = N i=0 K i x (tτ i ) ∈ R m to be designed through LMIs. This controller copes with project requirements and adds a certain degree of robustness to the closed-loop system. As will be shown the controller can be memoryless, i.e., K i ← 0, for i ≥ 1 or can even use some of the delayed states. Theorem 1. There is a state-feedback control that stabilises the system (1) if there exist matrices T = T ′ > 0,

Q i = Q ′ i > 0, Y i ∀i ∈ {0, . . . , N } and positive scalars d, ε, with µ = d 2 -ε, λ = d, such that      µT Ãℓ 0 Q 0 + Bℓ 0 Y 0 e -λτ0 . . . Ãℓ N Q N + Bℓ N Y N e -λτN • Q 0 0 0 • 0 . . . 0 • 0 0 Q N      ≥ 0
(27) and ( 8) are all satisfied, where Ãi is given by ( 23) and Bi = Be dτi for all i ∈ {0, . . . , N }. In this case, the controller matrices are given by

K i = Y i Q -1 i .
Proof: Applying Schur's complement in ( 27) we get exactly ( 9) with A i ← Ãi + Bi K i , which completes the proof.

Is it possible to go one step further and design a controller that guarantees α-stability. Making the change of variables z = s + d, with d = d * + α, d * > 0, α > 0, it implies that if an envelope lies completely before d * on the z-plane, then it will lies completely on the left side of the vertical line ℜ(s) = -α on the s-plan.

NUMERICAL EXAMPLES

Let us illustrate the results of this work with some examples. For the first example we consider a system without uncertainties. All other examples take into account parametric uncertainties on the system matrices.

Example 2. Consider the following system matrices

A 0 A 1 = 0 1 0 0.5413 -2 -3 -1.0827 -1.6240
, with τ = 0.4 and B = [0 1] ′ , we have an unstable system with poles at 1.3194 and 2.4125. Choosing α = 1, d = µ(A 0 ) + A 1 , where µ(.) is a matrix measure (T. Mori and Kokame, 1989), and applying Theorem 1 we achieve α-stability as can be seen in Figure 1.

The gains for the controller are

[ K 0 K 1 ] = [ 35.2114 -15.2267 -1.0869 -4.5434 ] .
One remark that is interesting to highlight, it is that in computational terms, for systems without uncertainties is possible to minimise µ through a standard generalised eigenvalue problem approach. However, for the uncertain case this is no longer possible. The problem is then solved by a linear search on µ.

For the next examples, let us describe the uncertainty as

A = A 1 + ∆A 2 * , with 0 ≤ ∆ ≤ ∆ max .
Hence, the vertices of the polytope are A 1 and A 2 := A 1 + ∆ max A 2 * . Now, for comparison purposes, we will design two controllers. One for the nominal plant neglecting the uncertainty and, therefore, fixing ∆ = 0, and the second one taking the uncertainty into account. For both controllers designed we execute the following procedure. Starting with ∆ = 0 we calculate all roots of the closed-loop system characteristic equation using QPmR [START_REF] Vyhldal | Qpmr -quasipolynomial mapping based rootfinder[END_REF]). Incrementing ∆ = ∆ + p, where p is small step, e.g., p = 0.05, we recalculate the poles and we repeat this procedure until the systems reach instability. With this procedure we can verify that the robustness is not only valid for 0 ≤ ∆ ≤ ∆ max but for a higher interval. Two numerical examples are shown below.

Example 3. Consider the following matrices for the system (24)

A 0 = 0 -1 2 3 + ∆ 1 0 2 -3 A 1 = 0 -0.5413 1.0827 1.6240 B = 0 1 ′ ,
where 0 ≤ ∆ ≤ 2.5 represents a parametric uncertainty and τ = 0.4. Imposing ∆ = 0 and applying Theorem 1 to the system obtained, we have K 1 = [7.1766 -15.0622] and K 2 = [-1.0764 -1.9799]. For the designed K we get that the system is stable for 0 ≤ ∆ ≤ 1.1. Now, lets apply Theorem 1 considering all vertices.

A 1 0 A 2 0 = 0 -1 2.5 -1 2 3 7 -4.5 .
The new controller gains obtained are K 1 = [103.7664 -19.2698] and K 2 = [-1.0823 -6.1536]. Applying once again the procedure described above, we have that the system is stable for 0 ≤ ∆ ≤ 4.9. Furthermore, for 0 ≤ ∆ ≤ 2.5, not only the poles are on the left halfplane, but our procedure ensures that they are all inside the envelope. A plot with a variety of linear combinations of (3), i.e., different values of ∆, is ploted altogether with the envelope on Figure 2. Example 4. Let us consider A 0 , A 1 and B from the previous example, with τ = 0.2, 0 ≤ ∆ ≤ 1.5 and α = 1. Designing a controller for the nominal system we get K 1 = [43.8852 -18.9928], K 2 = [-1.0825 -3.6587]. Calculating the poles for each increment of ∆ we verify stability for 0 ≤ ∆ ≤ 2.9. Designing the robust controller through Theorem 1, with ∆ = 1.5, we get It is then clear the superiority of the robust controller in comparison to the controller designed for the nominal system when there are parametric uncertainties present.

Example 5. Let us consider the matrices (Li and Souza, 1997a), [START_REF] Moon | Delay-dependent robust stabilization of uncertain timedelayed systems[END_REF] and [START_REF] Moon | Delay-dependent robust stabilization of uncertain statedelayed systems[END_REF])

A 0 = -2 0 1 3 + ∆ 0.2 0 0 0.2 A 1 = -1 0 -0.8 -0.1 B = 0 1 ′ , ∆ ≤ 1.
In Li and Souza (1997a) the largest upper bound for the delay is τ max = 0.5557. In [START_REF] Moon | Delay-dependent robust stabilization of uncertain timedelayed systems[END_REF] they showed that, in fact, the system is stabilisable for all delays.

Applying Theorem 1, choosing properly the vertices that bounds ∆, we confirm that the system is stable for all delays and we get K 1 = [-18.1576 -1.8716], K 2 = [1.0399 0.1020]. We went one step further and achieve independent stabilisation for ∆ ≤ 12.

CONCLUSION

Through an LMI approach, it was possible to use envelopes not only to study stability but to design robust feedback controllers for retarded time-delay systems. The controller designed is robust to parametric uncertainties and can guarantee delay independent stability (α = 0) or delay dependent αstability, for every τ ≤ τ * . Ongoing work establishes a similar approach for neutral time-delay systems.

  Fig. 1. α-stability, α = 1

Fig. 3 .

 3 Fig. 2. Envelope for an Uncertain Retarded Time-Delay System

⋆ This work was supported by grants from Smart 2 Erasmus Mundus, Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq/Brazil) grant 305600/2017-6 and Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) grant 2018/04905-1.