Philippe Balbiani

Jean-François Condotta

Gérard Ligozat

Reasoning about generalized intervals: Horn representability and tractability

This paper organizes the topologic forms of the possible relations between generalized intervals. Working out generalized interval algebra on the pattern of point algebra and interval algebra, it introduces the concept of Horn representability just as the one of convexity. It gives the class of Horn representable relations a simple characterization based on the concept of strong preconvexity. Adapting the propagation techniques designed to solve the networks of constraints between points or between intervals, it shows that the issue of consistency of a Horn representable generalized interval network can be solved in polynomial time by means of the weak path-consistency algorithm, a new incomplete algorithm for computing a minimal set of temporal constraints.

INTRODUCTION

It is hard to overemphasize the importance for computer science and artificial intelligence of the development of reasoning systems that are concerned with temporal information. The thing is that the nature of time raises grave difficulties for those who take on the matter of its representation. Without doubt, the model of the points designed by Vilain and Kautz [START_REF] Vilain | Constraint propagation algorithms for temporal reasoning[END_REF] and the model of the intervals elaborated by Allen [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] are the better known models for reasoning about time. In these models, temporal information is represented by a network of constraints between a finite number of variables. An important matter is deciding consistency of a network. Concerning points, Ladkin and Maddux [START_REF] Ladkin | The algebra of constraint satisfaction problems and temporal reasoning[END_REF] prove that the issue of consistency of a point network can be solved in polynomial time by means of the path-consistency algorithm. Relating to intervals, Vilain and Kautz [START_REF] Vilain | Constraint propagation algorithms for temporal reasoning[END_REF] demonstrate that deciding consistency of an interval network becomes NP-complete.

Therefore, the question of characterizing tractable subclasses of interval algebra has been considered. Nebel and Bürckert [START_REF] Nebel | Reasoning about temporal relations: a maximal tractable subset of Allen's interval algebra[END_REF] give a definitive answer to the question of which subclasses among those which contain base relations are tractable. To be more precise, the subclass of Horn representable relations is the unique maximal tractable subclass having this property. Moreover, deciding consistency can be accomplished by using the path-consistency algorithm. Horn representability is a syntactic concept, in view of the fact that Horn representable relations can be described by Horn clauses in a suitable language. Ligozat [START_REF] Ligozat | A new proof of tractability for ORD-Horn relations[END_REF] produces a simple characterization of the same class in terms of preconvex relations. Preconvexity is a geometric concept, for the simple reason that preconvex relations can be roughly described as convex relations with some lower dimensional base relations taken out.

Working out generalized interval algebra on the pattern of point algebra and interval algebra, Ligozat [START_REF] Ligozat | On generalized interval calculi[END_REF] organizes the topologic forms of the possible relations between generalized intervals. A problem is that the coincidence between the syntactic concept of Horn representability and the geometric concept of preconvexity does not hold any longer, as Ligozat [START_REF] Ligozat | A new proof of tractability for ORD-Horn relations[END_REF] notices in the context of generalized interval algebra, because the subclass of Horn representable relations is a proper subset of the set of all preconvex relations. A further complication is that, as Balbiani, Condotta and Fariñas del Cerro [START_REF] Balbiani | A new tractable subclass of the rectangle algebra[END_REF] remark in the context of rectangle algebra, the set of all preconvex relations is not a subclass in the usual sense, given that it is not closed for intersection. This leads them to define a restricted geometric notion, the concept of strong preconvexity, which has this closure property.

In the context of generalized interval algebra as well, it is interesting to consider the tractability issues both from the syntactic point of view and the geometric one. A primary goal of this paper is to give the class of Horn representable relations between generalized intervals a simple characterization in terms of strongly preconvex relations. An outcome of this characterization is that it allows to demonstrate that the issue of consistency of a Horn representable generalized interval network can be solved in polynomial time by means of the weak path-consistency algorithm, a new incomplete algorithm for computing a minimal set of temporal constraints. Successive sections are arranged along the following lines. Section 2 introduces the relational algebra of generalized intervals. We devote the whole section 3 to the syntactic concept of Horn representability. In sections 4, 5 and 6, we identify the geometric concepts of convexity, weak preconvexity and strong preconvexity. Section 7 focuses on the issue of consistency of a generalized interval network.

GENERALIZED ALGEBRA

Given a model of time consisting of the totally ordered set of all rational numbers, a generalized interval is a list of p rational numbers, with the first number less than the second, the second less than the third, etc. We will use x, y, z, etc, for these, assuming for any list x of p rational numbers, the first number is denoted by x 1 , the second by x 2 , etc. Such lists of p rational numbers are also sometimes called p-intervals. We want to formalize the notion of binary relation between a p-interval and a q-interval for any p; q 1. To keep things concrete, we will confine ourselves to results about the notion of binary relation between two p-intervals for some p 1. Extending these to the remaining cases is a simple matter. In order to formalize the position of x with respect to y we have to decompose the set of all rational numbers into subsets. If we define y 0 as 1 and y p+1 as +1 then the numbers y 1 , : : :, y p clearly define a partition of this set into 2 p + 1 zones numbered from 0 to 2 p such that:

-For all i 2 f0; : : :; pg, zone 2 i is ]y i ; y i+1 ; -For all i 2 f1; : : :; pg, zone 2 i 1 is fy i g.

x 1

x 2 x 3

Figure 1: A 3-interval x = (x 1 ; x 2 ; x 3 ).

Obviously, each rational number belongs to exactly one zone. This shows that the position of x with respect to y is a sequence of p zones which specifies for each i 2 f1; : : :; pg which zone the number x i belongs to. Let Q be the set of all sequences of p zones. We will use a, b, c, etc, for these, assuming for any sequence a of p zones, the first zone is denoted by a 1 , the second by a 2 , etc. If we define a 0 as 0 and a p+1 as 2 p then:

a is a position between generalized intervals iff, for all i 2 f1; : : :; pg, a i 2 Figure 2: The 7 zones defined by a 3-interval y = (y 1 ; y 2 ; y 3 ).

Let P be the set of all positions. Positions are also called basic relations. They constitute the exhaustive list of the possible relations between generalized intervals. For example, if x 1 2]y 0 ; y 1 , x 2 2]y 0 ; y 1 and x 3 2]y 2 ; y 3 then the position of x with respect to y is the sequence (0; 0; 4) and if x 1 2]y 0 ; y 1 , x 2 = y 1 and x 3 2]y 2 ; y 3 then the position of x with respect to y is the sequence (0; 1; 4). In order to represent indefinite information, we allow the binary relation between two generalized intervals to be any subset of the set of all basic relations. We will use , , , etc, for these. In the relational approach to temporal reasoning, the operations of inverse and composition play an important role. The inverse of a, denoted by a 1 , is the position b such that, for all i 2 f1; : : :; pg:

-For all j 2 f0; : : :; pg, if 2 i 1 2 a j ; a j+1 ]] then b i = 2 j; -For all j 2 f1; : : :; pg, if 2 i 1 = a j then b i = 2 j 1.

The composition of a and b, denoted by a; b, is the set of all positions c such that, for all i 2 f1; : : :; pg:

-For all j 2 f0; : : :; pg, if a i = 2 j then c i 2 b j ; b j+1 ]]; -For all j 2 f1; : : :; pg, if a i = 2 j 1 then c i = b j .

For instance, the inverses of (0; 0; 4) and (0; 1; 4) are the positions (4; 4; 6) and (3; 4; 6) whereas the composition of (0; 0; 4) and (0; 1; 4) is the set f(0; 0; 2); (0; 0;3);(0; 0;4)g of positions. Since binary relations between generalized intervals are sets of basic relations, the operations of inverse and composition are extended as follows. The inverse of , denoted by 1 , is fa 1 : a 2 g. The composition of and , denoted by

; , is S fa; b : a 2 &b 2 g. This brings us to the question of whether these defini- tions capture the intended meaning of the operations involved. Let x y mean that the position of x with respect to y belongs to . Ligozat [START_REF] Ligozat | On generalized interval calculi[END_REF] shows that the operations of inverse and composition have the following important properties:

-x 1 y iff y x;

-x ; y iff there is a generalized interval z such that x z and z y.

This proves a simple but fundamental result:

-The algebra (2 P ; ; \; ; ;; P; 1 ; ; ; f(1; : : :; 2 p 1)g) is a relational algebra.

HORN REPRESENTABILITY

Horn representable relations correspond to particular sets of clauses. Clauses are built up from p variables u 1 , : : :, u p and p variables v 1 , : : :, v p using the arithmetical symbols <, =, >, , 6 = and . A literal is any expression of the form u i <v j , where i; j 2 f1; : : :; pg and < is an arithmetical symbol. A set of literals is a Horn clause iff it contains zero or exactly one positive literal, assuming for any i; j 2 f1; : : :; pg, the literals u i < v j , u i = v j , u i > v j , u i v j and u i v j are positive and the literal u i 6 = v j is negative. For example, the clauses fu 2 = v 1 ; u 3 6 = v 2 g and fu 2 = v 1 ; u 3 6 = v 3 g are Horn clauses whereas the clauses fu 2 < v 1 ; u 3 6 = v 2 ; u 3 = v 3 g and fu 2 > v 1 ; u 3 = v 2 ; u 3 6 = v 3 g are not Horn clauses. A definite clause contains exactly one positive literal and zero or more negative literals. A positive unit clause is a definite clause containing no negative literal. Nebel and Bürckert [START_REF] Nebel | Reasoning about temporal relations: a maximal tractable subset of Allen's interval algebra[END_REF] consider only Horn clauses using the arithmetical symbols =, , 6 = and . It is straightforward to prove that every Horn clause using the arithmetical symbols <, =, >, , 6 = and is equivalent to a couple of Horn clauses using the arithmetical symbols =, , 6 = and .

To define Horn representable relations we need to evaluate variables occurring in the given literals of a clause. We shall say that a validates the literal u i <v j iff a i <(2 j 1). For instance, (0; 1; 3) and (0; 1; 5) validate the literal u 2 = v 1 , seeing that 1 = (2 1 1). In this spirit, a basic relation validates a clause iff it validates at least one literal of the clause. For example, (0; 1; 3) and (0; 1; 5) validate the clauses fu 2 = v 1 ; u 3 6 = v 2 g and fu 2 = v 1 ; u 3 6 = v 3 g. Then we can define the Horn representable relations as follows:

-is Horn representable iff there is a set S of Horn clauses such that exactly the basic relations of validate every clause of S. One says that S is a Horn representation of . To illustrate the truth of this, the binary relations f(0; 0; 4); (0; 1; 3);(0; 1; 4);(0;1; 5)g and f(0; 1; 3); (0; 1; 4);(0;1; 5); (0;2; 4)g are Horn representable or to be more precise, the Horn clauses fu 1 < v 1 g, fu 2 v 1 g, fu 3 v 2 g, fu 3 v 3 g, fu 2 = v 1 ; u 3 6 = v 2 g and fu 2 = v 1 ; u 3 6 = v 3 g constitute a Horn representation of the former binary relation whereas the Horn clauses fu 1 < v 1 g, fu 2 v 1 g, fu 2 < v 2 g, fu 3 v 2 g, fu 3 v 3 g, fu 2 = v 1 ; u 3 6 = v 2 g, fu 2 = v 1 ; u 3 6 = v 3 g constitute a Horn representation of the latter binary relation. It is not necessarily the case that the line of reasoning suggested by Nebel and Bürckert [START_REF] Nebel | Reasoning about temporal relations: a maximal tractable subset of Allen's interval algebra[END_REF] within the context of Horn representable relations between intervals applies to Horn representable relations between generalized intervals when p 3. In particular, although the reader may easily verify that the set of all Horn representable relations between generalized intervals is closed for intersection and inverse, there is no evidence that the set of all Horn representable relations between generalized intervals is closed for composition when p 3. Therefore, we are not in a position to give any sort of proof that the set of all Horn representable relations between generalized intervals constitutes a subclass of the generalized interval algebra when p 3.

CONVEXITY

To define the set of all convex relations, it is helpful to first arrange in ascending order the sequences of p zones. Let a b mean that a i b i for all i 2 f1; : : :; pg. For instance, (0; 0; 3) (0; 1; 5) and (0; 1; 3) (0; 2; 5). As a product of chains, it is easily shown that (Q; ) is a distributive lattice. (P; ) is also a distributive lattice, because (P; ) is a sublattice of (Q; ). The interval bounded by a and b, denoted by a; b], is the binary relation fc: a c and c bg. This leads us to make the following definition:

-is convex iff there are positions a; b such that = a; b].

To illustrate the truth of this, the binary relation f(0; 1; 3); (0; 1;4);(0; 1;5)g is convex. Clearly, convex relations are Horn representable or to be more precise, if is convex then there is a set S of positive unit clauses such that S is a Horn representation of . For instance, the positive unit clauses fu 1 < v 1 g, fu 2 v 1 g, fu 3 v 2 g, fu 3 v 3 g constitute a Horn representation of the interval bounded by (0; 0; 3) and (0; 1; 5) whereas the positive unit clauses fu 1 < v 1 g, fu 2 v 1 g, fu 2 < v 2 g,

(0,0,0) (0,6,6) (6,6,6) (0,0,6) (2,2 ,2) (4,4,4)
Figure 3: The lattice (P; ) for p = 3. fu 3 v 2 g, fu 3 v 3 g constitute a Horn representation of the interval bounded by (0; 1; 3) and (0; 2; 5). In general, the converse is false, Horn representable relations need not be convex. For a counterexample, take the case of the Horn representable relations f(0; 0; 4); (0; 1;3); (0;1;4); (0;1;5)g and f(0; 1; 3); (0; 1; 4);(0; 1; 5); (0;2; 4)g.

Evidently, the set of all convex relations is closed for intersection. In particular, the set of all convex relations containing contains a least element, denoted by I( ), the convex closure of . Ligozat [START_REF] Ligozat | On generalized interval calculi[END_REF] demonstrates that the convex closure has the following important properties:

-I( 1 ) = I( ) 1 ; -I( ; ) = I( ); I( ).

The conclusion can be summarized as follows: the set of all convex relations is closed for inverse and composition. Therefore, the set of all convex relations constitutes a subclass of the generalized interval algebra: the convex class.

WEAK PRECONVEXITY

To define the set of all weakly preconvex relations, we have to bring in the operations of topologic closure and dimension as follows. The topologic closure of denoted by C(a), is the set of all positions b such that, for all i 2 f1; : : :; pg, either b i = a i or j b i a i j = 1 and b i is odd. For instance, the topologic closure of (0; 1; 4) is the binary relation f(0; 1; 3); (0; 1;4);(0; 1; 5)g. The dimension of a, denoted by dim(a), is p fa i mod 2: i 2 f1; : : :; pgg. For example, the dimension of (0; 1; 4) is 2.

Seeing that binary relations between generalized intervals are sets of basic relations, we extend the operations of topologic closure and dimension as follows. The topologic closure of , denoted by C( ), is S fC(a): a 2 g. The dimension of , denoted by dim( ), is supfdim(a): a 2 g. Ligozat [START_REF] Ligozat | Generalized intervals: a guided tour[END_REF] proves that the following conditions are equivalent:

-C( ) is convex; -I( ) C( );

-dim(I( ) n ) < dim( ).
This justifies the role played by topologic closure in the following definition:

-is weakly preconvex iff C( )

is convex iff I( ) C( ) iff dim(I( ) n ) < dim( ).
For instance, the binary relations f(0; 0; 4); (0; 1;3);(0; 1; 5)g and f(0; 1; 3); (0; 1;5); (0; 2; 4)g are weakly preconvex or more exactly, the topologic closure of the former binary relation is the interval bounded by (0; 0; 4) and (0; 1; 5) whereas the topologic closure of the latter binary relation is the interval bounded by (0; 1; 3) and (1; 3; 5). It is clear that convex relations are weakly preconvex. This brings us to the question of whether Horn representable relations are weakly preconvex. Suppose is Horn representable, we show it is weakly preconvex. By our definition of Horn representability, we know that there is a set S of Horn clauses such that S is a Horn representation of . Let S consist of all positive unit clauses of S. With no loss of generality, suppose, for all i; j 2 f1; : : :; pg, if u i 6 = v j appears in some clause of S n S then u i = v j is not a consequence of S . Let be the binary relation which elements are exactly the basic relations validating every clause of S . Since S S, then . Since S is a set of positive unit clauses, then is convex. It follows that I( ) . Let us show that C( ). Consider the basic relation a of . It follows that a validates every clause of S . Then we can define a basic relation b of such that a 2 C(b) as follows. Let 2 f1; : : :; pg. If a i is even then there is j 2 f0; : : :; pg such that a i = 2 j and let b i = 2 j. Otherwise a i is odd and there is j 2 f1; : : :; pg such that a i = 2 j 1.

If u i = v j is a consequence of S then let b i = 2 j 1. Otherwise u i v j is not a consequence of S or u i v j is not a consequence of S . In the former case let b i = 2 j whereas in the latter case let b i = 2 (j 1). The reader may easily verify that b is a basic relation of such that a 2 C(b). This gives us the following result: C( ). It follows that I( ) C( ), hence is weakly preconvex. From all this it follows that: Theorem 1 If is Horn representable then is weakly preconvex.

Although Ligozat [START_REF] Ligozat | A new proof of tractability for ORD-Horn relations[END_REF] shows that weakly preconvex relations between intervals are Horn representable, weakly preconvex relations between generalized intervals need not be Horn representable when p 3, unfortunately. Take, for example, the case of the weakly preconvex relations f(0; 0; 4); (0; 1; 3); (0;1; 5)g and f(0; 1; 3); (0; 1; 5); (0;2; 4)g. Ligozat [START_REF] Ligozat | Generalized intervals: a guided tour[END_REF] demonstrates that the topologic closure has the following important properties:

-C( 1 ) C( ) 1 ; -C( ; ) C( ); C( ).

The interesting result is: the set of all weakly preconvex relations is closed for inverse and composition. Although Ligozat [START_REF] Ligozat | A new proof of tractability for ORD-Horn relations[END_REF] proves that the set of all weakly preconvex relations between intervals is closed for intersection, the reader may easily verify that the set of all weakly preconvex relations between generalized intervals is not closed for intersection when p 3. Consider, for instance, the weakly preconvex relations f(0; 0; 4); (0; 1; 3); (0;1; 5)g and f(0; 1; 3); (0; 1;5); (0;2;4)g. Therefore, the set of all weakly preconvex relations between generalized intervals does not constitutes a subclass of the generalized interval algebra when p 3.

STRONG PRECONVEXITY

Assume p 3. The trouble with the set of all weakly preconvex relations is that it is not closed for intersection with convex relations. One has only to consider the weakly preconvex relations f(0; 0; 4); (0; 1;3); (0; 1;5)g and f(0; 1; 3); (0; 1;5); (0;2;4)g and the convex relation f(0; 1; 3); (0; 1;4); (0;1;5)g. This justifies the role played by intersection with convex relations in the following definition:

-is strongly preconvex iff, for all binary relation , if is convex then \ is weakly preconvex.

To illustrate the truth of this, the binary relations f(0; 0; 4); (0; 1;3); (0; 1;4);(0; 1;5)g and f(0; 1; 3); (0; 1;4); (0;1;5); (0; 2;4)g are strongly preconvex. Clearly, strongly preconvex relations are weakly preconvex. Let us see if there is any connection between Horn representability and strong preconvexity. Suppose is Horn representable, we demonstrate it is strongly preconvex. By our definition of Horn representability, we know that there is a set S( ) of Horn clauses such that S( ) is a Horn representation of . If is not strongly preconvex then there is a binary relation such that is convex and \ is not weakly preconvex. Since is convex, then it is Horn representable. In particular, there is a set S( ) of positive unit clauses such that S( ) is a Horn representation of . Furthermore, the reader may easily verify that S( ) S( ) is a Horn representation of \ . By theorem 1, \ is weakly preconvex, and this is impossible. These considerations prove: Theorem 2 If is Horn representable then is strongly preconvex. Now suppose is strongly preconvex, we prove it is Horn representable. Since I( ) is convex, then it is Horn representable. In particular, there is a set S(I( )) of positive unit clauses such that S(I( )) is a Horn representation of I( ). Consider the basic relation a of I( ). Suppose a 6 2 . Let a = fb: for all i 2 f1; : : :; pg, if a i is odd then b i = a i g. Obviously, a 2 a . Furthermore, the reader may easily verify that a is convex. It follows that a is Horn representable. What is more, there is a set S( a ) = ffu i1 = v j1 g; : : :; fu iM = v jM gg of positive unit clauses using the arithmetical symbol = such that S( a ) is a Horn representation of a . Let a = \ a . Since is strongly preconvex, then a is weakly preconvex. It follows that I( a ) C( a ). Let us demonstrate that a 6 2 I( a ). Suppose a 2 I( a ), we derive a contradiction. Since I( a ) C( a ), then a 2 C( a ) and there is a basic relation b of a such that a 2 C(b). Since b 2 a , then b 2 and b 2 a . It follows that b 6 = a and, for all i 2 f1; : : :; pg, if a i is odd then b i = a i . Since a 2 C(b), then, for all i 2 f1; : : :; pg, either a i = b i or j a i b i j = 1 and a i is odd, hence if a i is even then b i = a i . It follows that b = a, a contradiction. This gives us the following result: a 6 2 I( a ). Since I( a ) is convex, then I( a ) is Horn representable. To be more precise, there is a nonempty set S(I( a )) = ffu k1 < l1 v m1 g; : : :; fu kN < lN v mN gg of positive unit clauses such that S(I( a )) is a Horn representation of I( a ). Let a = a n I( a ) and a = I( ) n a . It follows that a is Horn representable. Ultimately, then, the set S( a ) = S(I( )) ffu i1 6 = v j1 ; : : :; u iM 6 = v jM ; u 1 < l1 v m1 g; : : :; fu i1 6 = v j1 ; : : :; u iM 6 = v jM ; u kN < lN v mN gg of definite clauses is a Horn representation of a . All in all, let S = S fS( a ): a 2 I( ) n g. The reader may easily verify that exactly the basic relations of validate every clause of S. It follows that is Horn representable. Hence we have: Theorem 3 If is strongly preconvex then is Horn representable.

GENERALIZED NETWORKS

Assume p 3. A generalized interval network is a structure of the form (n; M) where n 1 and M is a square n n matrix with entries in 2 P . Hence M isa function assigning, for all i; j 2 f1; : : :; ng, a subset M(i; j) of P, i.e. a binary relation. A tuple (x(1); : : :; x(n)) of generalized intervals is called a (maximal) solution of (n; M) iff, for all i; j 2 f1; : : :; ng, there is a basic relation a of (maximal dimension in) M(i; j) such that x(i) a x(j). (n; M) is (maximally) consistent iff it possesses a (maximal) solution. In what follows we assume that all our generalized interval networks satisfy the following conditions:

-For all i 2 f1; : : :; ng, M(i; i) = f(1; : : :; 2 p 1)g; -For all i; j 2 f1; : : :; ng, M(i; j) = M(j; i) 1 .

It is a well-known fact that by applying the following algorithm -the path-consistency algorithm -we obtain in polynomial time an equivalent generalized interval network:

-Successively replace, for all pairwise distinct i; j; k 2 f1; : : :; ng, the constraints M(i; k) and M(k; i) by the constraints M(i; k) \ (M(i; j); M(j; k)) and M(k; i) \ (M(k; j); M(j; i)).

We make use of this in the following definition:

-(n; M) is path-consistent iff, for all pairwise distinct i; j; k 2 f1; : : :; ng, M(i; k) M(i; j); M(j; k) and M(k; i) M(k; j); M(j; i).

An important matter is deciding consistency of a generalized interval network. It would be naive to suppose that constraints between generalized intervals can be expressed in terms of constraints between intervals, for the simple reason that although Ligozat [START_REF] Ligozat | Generalized intervals: a guided tour[END_REF] shows that if a weakly preconvex generalized interval network is path-consistent then either it contains the empty constraint or it is maximally consistent, the issue of consistency of a weakly preconvex generalized interval network is NP-complete. The fact of the matter is that the issue of consistency of an interval network is polynomial-time reducible to the issue of consistency of a weakly preconvex generalized interval network. Consider the interval network (n; M). Then we can define the weakly preconvex generalized interval network (n 0 ; M 0 ) as follows. Let 0 = n (n + 1). For all i; j 2 f1; : : :; ng, let:

-M 0 (i; j) = f(a 1 ; a 2 ; 5; : : :; 2 p 1): (a 1 ; a 2 ) 2 I(M(i; j))g; -M 0 (i; n + i + (j 1) n) = f(a 1 ; a 2 ; 5; : : :; 2 p 1): (a 1 ; a 2 ) 2 M(i; j)g f(b 1 ; b 2 ; 6; : : :; 2 p): b 1 ; b 2 2 f0; 2; 4g and b 1 b 2 g; -M 0 (n + i + (j 1) n; j) = f(1; 3; 5; : : :; 2 p 1)g.

The reader may easily verify that (n 0 ; M 0 ) is consistent iff (n; M) is consistent. All this goes to show that:

Theorem 4 The issue of consistency of a weakly preconvex generalized interval network is NP-complete.

This polynomial-time reducibility of the issue of consistency of an interval network to the issue of consistency of a weakly preconvex generalized interval network serves to illustrate the role played by intersection with convex relations in the following definition:

-(n; M) is weakly path-consistent iff, for all pairwise distinct i; j; k 2 f1; : : :; ng, M(i; k) I(M(i; j); M(j; k)) and M(k; i) I(M(k; j); M(j; i)).

From all the evidence it is clear that by applying the following algorithm -the weak path-consistency algorithm -we obtain in polynomial time an equivalent weakly pathconsistent network:

-Successively replace, for all pairwise distinct i; j; k 2 f1; : : :; ng, the constraints M(i; k) and M(k; i) by the constraints M(i; k)\I(M(i; j); M(j; k)) and M(k; i) \ I(M(k; j); M(j; i)).

We first observe that path-consistent generalized interval networks are weakly pathconsistent. In general, the converse is false, weakly path-consistent generalized interval networks need not be path-consistent. Let us demonstrate that the problem of deciding consistency of a generalized interval network can be solved in polynomial time by means of the weak path-consistency algorithm if only Horn representable relations are used. Consider the Horn representable generalized interval network (n; M).

Seeing that Horn representable relations are strongly preconvex, (n; M) is a strongly preconvex generalized interval network. In view of the fact that the set of all strongly preconvex relations is closed for intersection with convex relations, it is beyond question that by applying the weak path-consistency algorithm, we obtain in polynomial time an equivalent weakly path-consistent strongly preconvex generalized interval network (n; M 0 ). Then we can define the convex generalized interval network (n; M 00 ) as follows. For all i; j 2 f1; : : :; ng, let M 00 (i; j) = I(M 0 (i; j)). Given that the set of all convex relations is closed for composition, (n; M 00 ) is a path-consistent convex generalized interval network. Seeing that convex relations are weakly preconvex, (n; M 00 ) is a path-consistent weakly preconvex generalized interval network. In this respect, either it contains the empty constraint or it is maximally consistent. The former case implies that (n; M 0 ) contains the empty constraint, hence (n; M) is not consistent. The latter case implies that (n; M 0 ) is maximally consistent, hence (n; M) is consistent. Now tractability of the issue of consistency of a Horn representable generalized interval network follows easily:

Theorem 5 The issue of consistency of a Horn representable generalized interval network can be solved in polynomial time by means of the weak path-consistency algorithm.

CONCLUSION

We would like to emphasize that so far our main concern has been the connection between the syntactic concept of Horn representability and the geometric concepts of convexity, weak preconvexity and strong preconvexity. More precisely, we have given the set of all Horn representable relations between generalized intervals a simple characterization based on the concept of strong preconvexity. An advantage of this characterization is that it has allowed to present a simple proof that the issue of consistency of a Horn representable generalized interval network can be solved in polynomial time by means of the weak path-consistency algorithm. Much remains to be done. We wish to investigate the question whether the class of binary relations between two generalized intervals generated by the set of all Horn representable relations between generalized intervals is the unique maximal tractable subclass among those which contain base relations. Future work also includes permitting the processing of metric constraints between generalized intervals, an important matter in the development of reasoning systems that are concerned with temporal information.

a i 1 ;

 1 a i+1 ]], assuming for any pair a; b of integers, a; b]] is the largest integer interval with even endpoints and contained in a; b].


Vineeth S Varma

Romain Postoyan
email: romain.postoyan@univ-lorraine.fr.

Energy Efficient Time-Triggered Control over Wireless Sensor/Actuator Networks

We investigate the scenario where a controller is connected to a plant using a wireless network. Our objective is to design control strategies, which efficiently use the network in terms of energy, by taking into account the fluctuations of the wireless channel. In particular, we consider discretetime systems and we focus on time-triggered control. That is, we assume that we know a controller, which ensures a desired property (such as stability), as long as two successive transmissions are not spaced by more than a fixed number of steps N . The problem formulation is generic in the sense that we do not make any assumption on the plant and the controller structures or properties, all we need to ensure is the constraint on the transmission times. We then present triggering strategies to minimize the energy expenditure based on knowledge on the channel state, while ensuring that two successive transmissions are not spaced by more than N steps. The results demonstrate that periodically communicating after exactly N time instants has passed (to minimize the number of transmissions), is not always the optimal scheme to minimize the energy cost. As a result of certain properties of the wireless channel, communicating more often when the wireless channel conditions are good, results in a smaller energy consumption overall despite a higher frequency of communication. Numerical results confirm the validity of the approach and show that a significant amount of energy can be saved.

I. INTRODUCTION

The literature on sensor networks has extensively dealt with the extraction and communication of information obtained through the sensors. Communicating the obtained information with a high data rate or reliability, while consuming as little energy or power as possible, is the primary objective of works in this field, see e.g., [START_REF] Ye | An energy-efficient mac protocol for wireless sensor networks[END_REF], [START_REF] Van Dam | An adaptive energy-efficient mac protocol for wireless sensor networks[END_REF]. The approaches used to reduce the power consumption are based on the communication requirements and wireless aspects like access protocols, scheduling and transmission power control [START_REF] Lin | Atpc: adaptive transmission power control for wireless sensor networks[END_REF]. On the other hand, the literature on networked control systems (NCS) concentrates on applications in which actuation plays a major role, see e.g., [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF], [START_REF] Heemels | An introduction to event-triggered and self-triggered control[END_REF], [START_REF] Mazo | Decentralized event-triggered control over wireless sensor/actuator networks[END_REF], [START_REF] Hespanha | A survey of recent results in networked control systems[END_REF]. These are systems in which the plant and the controller communicate with each other via a communication network. In this context, the energy expenditure incurred is often assumed to be directly related to the frequency of communication through the network, meaning that the less we transmit, the less the energy expenditure due to communication.

Many researchers have recently published results which bridge the gap between the two approaches mentioned above, and develop a more unified framework for analyzing and reducing the energy consumption in NCS. In [START_REF] Quevedo | Dynamic controller allocation for control over erasure channels[END_REF], [START_REF] Leong | On the optimality of threshold policies in event triggered estimation with packet drops[END_REF] for instance, the implementation of event-triggered controllers over practical communication channels is investigated. The survey [START_REF] De Castro | On energyaware communication and control co-design in wireless networked control systems[END_REF] provides a list of works that implement energy efficient sensor design in the context of NCS. Minimizing the energy consumption by a sensor, with the ability to harvest energy, communicating over a wireless channel has been done in [START_REF] Knorn | Optimal energy allocation for linear control over a packet-dropping link with energy harvesting constraints[END_REF]. Another work of interest among others, is [START_REF] Quevedo | Energy efficient state estimation with wireless sensors through the use of predictive power control and coding[END_REF], in which the authors look at energy efficient transmit power control in a wireless sensor/actuator network, with the power control based on efficiency of the estimation.

The primary objective of our work is to reduce, and if possible, minimize the energy consumed by a control system, in which the sensors and the actuators are connected to the controller through a wireless channel. The controller is assumed to be able to complete its task, as long as it is updated, within an interval of N time instants from the previous update. We assume that the communication is perfect (no noise through quantization) and without delay when a sufficient amount of energy is consumed. The problem formulation is generic in the sense that the system and the controller can have any dynamics and the control objective can be stability and/or optimality for instance. The only requirement for our results to hold, is on the frequency of communication as mentioned above, which is assumed to imply that a desired property for the closed-loop system holds. We propose communication strategies (determining when to communicate) that reduce the total discounted energy cost based on: 1) the clock state, which is the number of time instants that has passed since the previous communication. This takes a value in the set {1, 2, . . . , N }, as communication is enforced when N instants have passed for the controller to perform its task. 2) the channel fading, which is a positive real number indicating the strength of the wireless connection between the wireless transmitter and the receiver (see, e.g., [START_REF] Knorn | Optimal energy allocation for linear control over a packet-dropping link with energy harvesting constraints[END_REF], [START_REF] Quevedo | Energy efficient state estimation with wireless sensors through the use of predictive power control and coding[END_REF]). The higher the value of the channel fading, the lower the amount of energy that has to be spent for successful communication.

Although the literature mentioned above treats the problem of energy efficient communication in NCS, the strategies obtained usually are either from a communication perspective (not considering the plant state) or from a control perspective (not considering the channel fading). Designing a power control scheme taking into account both the wireless channel fading and the plant state jointly has been done in [START_REF] Gatsis | Optimal power management in wireless control systems[END_REF], where the authors develop a co-designed power control policy for linear systems when the wireless channel distribution is known. In comparison, our results apply to general systems and controllers, but, which satisfy time triggering conditions. The latter enables us to separate the control and communication problems as the former is solved by restricting the set of communication strategies to the subset which satisfies the time triggering condition.

We treat three primary cases of interest, based on the wireless channel model assumed:

1) The wireless channel conditions remain a constant for all time: in this simple case, reducing the frequency of communication obviously minimizes the energy cost.

That is, the optimal policy is transmitting only when the clock state is exactly N .

2) The wireless channel conditions are known for a certain number of time instants in the future: several practical scenarios have appeared over the recent years, for which forecasting the wireless channel state over a long time horizon is realistic, see [START_REF] Ekman | Unbiased power prediction of rayleigh fading channels[END_REF], [START_REF] Fouresti | Communication switching method, access point, network controller and associated computer programs[END_REF]. In this case, we develop a rollout algorithm [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF] for signal power control, that consumes an amount of energy lower than or equal to that consumed by the policy given by the first case. Simulation results actually have shown that it consumes a much smaller energy cost.

3) The probability distribution of the wireless channel conditions are also known: this assumption is often made in wireless literature (see [START_REF] Lin | Atpc: adaptive transmission power control for wireless sensor networks[END_REF], [START_REF] Quevedo | Energy efficient state estimation with wireless sensors through the use of predictive power control and coding[END_REF], [START_REF] Gatsis | Optimal power management in wireless control systems[END_REF]) as the channel statistics can be learned. In this case, we are able to compute and minimize the minimal expected energy costs by modeling the problem as a Markov decision process. The rest of the paper is structured in the following manner. The problem is formally stated in Section II. Section III presents the proposed communication strategies for the three cases mentioned above. Section IV provides numerical results that illustrate the energy gains observed by implementing the proposed policies. Finally, Section V concludes the paper. The proofs are omitted due to space limitations.

II. PROBLEM STATEMENT

We investigate the scenario where a controller is implemented over a wireless network and communicates with the plant at time instants t i ∈ Z ≥0 , i ∈ Z ≥0 (where Z ≥0 = {0, 1, . . . }). In order to monitor the plant, low-energy sensors are deployed which measure the plant state and communicate this information to the controller. The primary objective of this work is to develop a communication scheduling scheme that minimizes (when possible) the energy consumption at the sensor while ensuring that the controller can consistently perform its task.

A. Control requirements

When a transmission occurs, the plant sensors send the current value of the output vector to the controller, which also sends in the meantime, the current value of the control input to the plant. We assume that the transmission delays and that quantization can be neglected and that both transmissions occur over the same channel and do not interfere. Define by N ∈ Z >0 (where Z >0 = {1, 2, . . . }), the maximum allowable transmission interval (MATI) where

t i+1 ∈ {t i , t i + 1, . . . , t i + N }, ∀i (1)
We assume that the MATI, N as defined in (1) ensures that the control system satisfies a desired property, like stability or optimality for instance. This general assumption allows covering various situations without imposing any model for the plant and the controller. For instance, conditions to ensure stability properties for system, including a bound on N , are provided in [START_REF] Postoyan | Time-triggered control of nonlinear discrete-time systems[END_REF]. The near-optimal time-triggered strategies presented in [START_REF] Bus ¸oniu | Near-optimal strategies for nonlinear and uncertain networked control systems[END_REF] can also be modeled by [START_REF] Ye | An energy-efficient mac protocol for wireless sensor networks[END_REF].

For the sake of convenience, we introduce the clock state τ (t) to count the number of steps since the last transmission.

τ (t + 1) =        1 when τ (t) ∈ {1, . . . , N } (transmission) τ (t) + 1 when τ ∈ {1, . . . , N -1} (no transmission).
(2) Where τ (t) is reset to 1 when a transmission occurs and is incremented by 1 when that is not case. We are free to trigger a transmission whenever τ (t) ∈ {1, . . . , N } in order to satisfy the control objective. As the energy consumed per transmission depends on the wireless channel, we consider a wireless channel model as described in the following section.

B. Channel fading and energy costs

The signals sent through wireless channels experience an attenuation due to various factors like shadowing, multipath propagation and path loss (distance). In the framework of wireless communications, this process is called channel fading. The channel fading is, in general, a time-varying quantity, and we model the gain (or loss) of the signal strength due to the channel fading at time t by the real number h t , which is assumed to satisfy the following condition.

Assumption 1: The wireless channel fading at time t ∈ Z ≥0 is given by h t ∈ H where H := [h min , +∞] and h min > 0.

Assumption 1 guarantees that, at any time t, the channel h t is larger than or equal to h min > 0, where h min is the channel fading when the the wireless channel connection is the weakest. This property is required to ensure that communication at any time can be successful with no loss. Indeed, a real wireless device will have a bit-error rate. However, we assume that reliable communication can always be performed using error correcting codes and by using the maximum energy [START_REF] Elaoud | Adaptive use of error-correcting codes for real-time communication in wireless networks[END_REF], [START_REF] Nafaa | Forward error correction strategies for media streaming over wireless networks[END_REF]. Note that in future work, we can relax this condition by considering stochastic control. We also assume that h t is known to the sensor, with a negligible sensing energy cost compared to cost of sending a wireless transmission. This assumption is often justified, as in practice, the receiver will typically sent pilot signals for the transmitter to estimate the channel (see [START_REF] Gatsis | Optimal power management in wireless control systems[END_REF] for instance).

Let the energy spent by the transmitter to communicate at time t be given by E t ∈ [0, E max ], where E max > 0 is the maximum energy output of the transmitter. In practice, we are free to select the energy E t at each t ∈ Z >0 . The energy required in order to communicate with no loss depends on the wireless channel fading. We assume that the minimum amount of energy needed in order to communicate without loss is inversely proportional to the channel fading h t as formalized below.

Assumption 2: When the transmitter consumes E t Joules of energy at time t, then the communication is lossless if

E t ≥ E 0 h t (3)
where

E 0 > 0 is a positive real number satisfying E 0 ≤ E max h min .
Assumption 2 is suitable when the communication performance metric is a non-decreasing function of the signal to noise ratio and the communication system implements capacity achieving codes. For satisfying a certain quality of service (like communication with no loss) the signal to noise ratio must be above a certain threshold, resulting in channel inversion for the energy (and transmit power) spent. Additional information on the validity of this assumption can be seen in in Section IV.A of [START_REF] Gatsis | Optimal power management in wireless control systems[END_REF]. Assumptions 1 and 2 guarantee that, at any time t, the communication between the sensor and the controller will be successful when an energy E 0 h t is consumed by the wireless transmitter.

C. Performance metric

We are interested in minimizing the total energy consumed by the transmitter over an infinite horizon. As this cost will be unbounded in general, we introduce a discount factor δ ∈ (0, 1) and look at the total discounted cost (often studied in literature, e.g. [START_REF] Bus ¸oniu | Near-optimal strategies for nonlinear and uncertain networked control systems[END_REF], [START_REF] Antunes | Rollout event-triggered control: beyond periodic control performance[END_REF]), measured in Joules as

e := ∞ t=1 δ t E t , (4)
while ensuring that the interval between two successful communication instants is in {1, 2, . . . , N }. From Assumption 2, we know that when E t ≥ E0 ht , the communication is successful. Therefore, we reduce our problem into finding a sequence d t ∈ {0, 1} for any t, where E t = d t E0 ht , which minimizes the total energy cost, i.e., the cost function,

e = ∞ t=1 δ t d t E 0 h t . (5)
Hence, when d t = 0, the energy spent at time t is equal to zero, meaning that we do not transmit. When d t = 1, a transmission occurs and we use E0 ht Joules to successfully transmit. Minimizing e in (5) would require knowing h t for all t, which is not reasonable in practice. Therefore, we define ht := (h t , h t+1 , . . . , h t+M ), the M + 1 dimensional vector formed by the concatenation of the current channel h t and M future channels, where M ∈ Z ≥0 at time t ∈ Z >0 . We also introduce h|t := (h 1 , h 2 , . . . , h t ) that represents the value of the channel fading from 1 to t ∈ Z ≥0 . We assume that these M future channel fadings are known at any time t. Assumption 3: At any time t, ht is known by the transmitter, where M ∈ Z ≥0 .

Assuming that the transmitter knows all the realizations of the system state in advance can also be seen as a way of obtaining an upper bound for the performance of scenarios that assume a reduced time horizon for forecasting. It is worth noting that several practical scenarios have appeared over the recent years as seen in [START_REF] Ekman | Unbiased power prediction of rayleigh fading channels[END_REF] or [START_REF] Fouresti | Communication switching method, access point, network controller and associated computer programs[END_REF]. Note that the case of M = 0, is a special case of Assumption 3 where no future channel fadings are known.

Our goal is to design "policies" which determine d t , given ht (the vector of known channels) and τ (t) (the clock state), such that the energy cost e in ( 5) is minimized when possible, while ensuring τ (t) ≤ N for any t, hence ensuring the desired control task. We define a policy as π M : Z >0 × H M +1 → {0, 1} (H defined in Assumption 1), which is a function that determines whether to communicate or not given τ (t) and ht .

Given a policy π M and channel fadings h|t+M , let the communication decision made at time t be given by d t (π M , h|t+M ), and the clock state as a result of these decisions be given by τ (t) = S t (π M , h|t+M ), where S t is some function to be designed. Denote by Π the set of all policies satisfying the time triggering rule (1), i.e.,

Π := {π M |π M (N , ḡ) = 1 ∀ḡ ∈ H M +1 , ∀N ≥ N }.
Our objective is to find policies π M ∈ Π that (when possible) minimize the cost function

e(π M , h|∞ ) := ∞ t=1 δ t d t (π M , h|t+M ) E 0 h t . (6)
Since knowing all the future channel values, i.e., h|∞ is not generally possible in practice, we are interested in optimizing the decisions in order to minimize the expected cost. Let h t ∼ P where P is the probability distribution of h t , and the probability distribution function (PDF) of h t is P (•). The expected energy cost ē(π M ) (over channel realizations) while using a policy π M is given by

ē(π M ) := Eh |∞ e(π M , h|∞ ), (7)
where Eh |∞ := H ∞ Π ∞ t=1 P (h t )d h|∞ is the expectation over all the channels.

The objective of our work is to minimize ē(π M ), when P t is known and otherwise, find policies that reduce the consumed energy e(π M , h|∞ ) compared to a base policy defined in the following section.

III. MAIN RESULTS

A. Constant channel fading

In this subsection, we look at the trivial case where the channel fading is a constant for all time. This kind of model is suitable when both the transmitter and receiver are stationary and is at line-of-sight with no obstructions. This results in a Rician channel fading with a small variance, i.e., approximately a constant.

Assumption 4: There exists h 0 ≥ h min such that h t = h 0 for any t ∈ Z >0 .

Note that h 0 is necessarily known in view of Assumption 3. We will now introduce a policy π B M which we will refer to as the "base heuristic".

Definition 1: The base heuristic π B M is given by, for any τ ∈ {1, . . . , N } and ḡ ∈ H M +1 ,

π B M (τ, ḡ) := 1 if τ = N 0 if τ < N . (8)
This policy minimizes the communication frequency by transmitting the measurement only when the clock state is N . Additionally, this policy does not require any information on the channel fading (present or future). Therefore, the implementation is very straightforward and requires almost no computational resources or information. Moreover, such a policy is optimal under Assumptions 1-4, as we show in the next proposition. Note that such a policy would also be naturally used when ignoring the channel fadings fluctuations and considering only the control requirements.

Proposition 1: When Assumptions 1-4 hold, the expected energy cost ē(π M ) is minimized by implementing the base heuristic, i.e., π * M = π B M and results in a total energy consumption of ē(π

B M ) = δ N E0 h0(1-δ N ) .

B. Channel statistics are unknown

In most practical systems Assumption 4 does not hold true, as h t typically varies in time. The energy cost from when the base heuristic is implemented for any general channel model (h t is not necessarily a constant) is given by

e(π B M , h|∞ ) = ∞ i=1 δ iN E 0 h iN . (9)
In this section, we only suppose that Assumptions 1-3 hold and we do not make any assumption on the channel statistics, i.e., the PDF is unknown. We propose a rollout algorithm (see [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF]), which outperforms the base heuristic. Recently, some works like [START_REF] Gatsis | Optimal power management in wireless control systems[END_REF], [START_REF] Antunes | Rollout event-triggered control: beyond periodic control performance[END_REF] have utilized the rollout algorithm in the field of event-triggered control. Although the latter does not result in an optimal solution, it may produce considerable (and often dramatic) performance improvements over the base heuristic, as confirmed in the simulation results presented in Section IV.

The rollout algorithm assumes that the algorithm only affects a certain horizon of time, and that the base heuristic is implemented after this horizon. The related costs of the system beyond the horizon are calculated assuming that the base heuristic given in Definition 1 is implemented. The total energy cost within the time period {t, t + 1, ..., t + M } is minimized, while ensuring that the base heuristic will be implemented after t + M .

Definition 2: The rollout policy π R M is defined as, for clock state τ ∈ Z >0 and channel vector ḡ

∈ H M +1 π R M (τ, ḡ) := arg b0 min b M j=0 δ j b j E 0 g j (10)
where b j ∈ {0, 1} for all j ∈ {0, 1, .., M } and b = (b 0 , b 1 , . . . , b M ) has to satisfy the following constraints. Let S j ( b) be the clock state after j time steps, where S 0 ( b) = τ by definition, and S j ( b) is defined for j ∈ {1, 2, . . . , M } as

S j ( b) :=    j + τ if b k = 0 ∀k ∈ {0, 1, .., j -1} j -max{k ∈ {1, . . . , j -1}|b k = 1} otherwise. ( 11
)
The vector b is such that

S j ( b) ≤ N ∀j ∈ {0, 1, .., M -1} (12)
and

S M ( b) ≤ N -(N τ + M N -τ -M ). (13)
where the notation y denotes the smallest integer greater than or equal to y (ceiling function). In Definition 2, b represents the vector of decisions that will be taken from t to t + M if the rollout policy is implemented when the clock state at t is τ . Assuming the decisions b from t to t + M are taken, then S j ( b) represents the clock state after j time steps and can be estimated by [START_REF] Knorn | Optimal energy allocation for linear control over a packet-dropping link with energy harvesting constraints[END_REF]. As the time triggering rule (1) has to be satisfied, we impose the constraint [START_REF] Quevedo | Energy efficient state estimation with wireless sensors through the use of predictive power control and coding[END_REF]. We also enforce an additional constraint [START_REF] Gatsis | Optimal power management in wireless control systems[END_REF] to avoid transmitting after the rollout horizon and before the schedule of the base heuristic. Implementing the rollout policy π R M results in an energy cost, which is at most, the energy cost of the base heuristic. This result is detailed in the following proposition.

Proposition 2: When Assumptions 1-3 hold, the rollout policy π R M leads to an energy cost that is less than or equal to the energy cost implementing π B M . Implementing π R M when M is large, requires an exhaustive search over all the possible decisions with a computational complexity of 2 M steps and dynamic programming can be used in order to reduce the computational complexity and solve the minimization problem in [START_REF] De Castro | On energyaware communication and control co-design in wireless networked control systems[END_REF]. Our numerical results, for the considered channel fading model, indicate that this may not essential, as the gain from increasing M is not significant beyond M = 5 when N = 10.

C. Channel distribution is known

While the rollout strategy may reduce the energy expenditure, the obtained cost is not optimal a priori. In this subsection, we aim at providing optimal policies. We assume for this purpose that the channel distribution information is known for all time and are independent and identically distributed random variables.

Assumption 5: The channel fading distribution P (h) : R + → R + is known such that h t ∼ P for all t, and the PDF of h t is given by P (h).

Assumption 5 is often made in the framework of wireless communications [START_REF] Lin | Atpc: adaptive transmission power control for wireless sensor networks[END_REF], [START_REF] Quevedo | Energy efficient state estimation with wireless sensors through the use of predictive power control and coding[END_REF], [START_REF] Gatsis | Optimal power management in wireless control systems[END_REF]. For any M , when the prob-ability distribution P (h) is known, we derive the optimal policy (optimal given the available information of M future channel states). Let v τ,ḡ (π M ) represent the expected energy cost while using policy π M for all future times while the clock state is τ and ḡ is the vector of known future channels. Define vτ (π

M ) := E ḡ [v τ,ḡ (π M )].
Proposition 3: Under Assumptions 1-3 and 5, the problem resolves into a Markov decision process (MDP) and the optimal policy π * M is given by iteratively solving the following equations

π * M (τ, ḡ) = arg b0 minb b 0 E0 g0 + M m=1 δ m b m E0 gm +δ M +1 vS M +1 ( b) (π * M ) (14
vτ (π * M ) = E ḡ π * M (τ, ḡ) E0 g0 + δπ * M (τ, ḡ)v 1 (π * M ) + δ(1 -π * M (τ, ḡ))v τ +1 (π * M )] (15)
Although iteratively solving equations ( 14) and ( 15) can be computationally heavy, this can be done offline and vτ (π * M ) can be computed. The expected energy cost for the policy π * M is ē(π * M ) = v1 (π * M ) (as we initialize with communication at t = 0). In general, the minimization problem in ( 14) is similar to the problem in the previous subsection, but also yields non-trivial results for M ∈ {0, 1}. Of special interest is the case of M = 0, where the future channel states are unknown, but their statistics are known, in which case the policy is given as follows.

Optimal policy for M = 0: The optimal policy obtained from ( 14) has a simple form in this case. Let gτ := E0 δvτ+1(π * 0 )-δv1(π * 0 ) and ( 14) can be simplified to be a threshold policy on the channel for each state τ :

π * 0 (τ, g 0 ) = 1 if g 0 ≥ gτ or τ = N ; 0 otherwise. ( 16
)
Hence, we compute gτ for all τ ∈ {1, 2, . . . , M } offline by iteratively solving ( 14) and ( 15), and we simply check on-line whether h t is bigger than gτ(t) , in which case a transmission is triggered.

When M > 0, it becomes more complex (in terms of computation) to find the optimal policy as we also have information on h t+1 , h t+2 , . . . , h t+M . The total number of decision variables are M + 1, and as in the previous section, this results in a computational complexity of 2 M +1 . Dynamic programming can be used to find the optimal decision policy π * M given the expected minimal energy cost function vτ (π * M (•, •)) with less computational complexity. So far, we have provided several policies to reduce or minimize the energy costs in a time triggered control system. In the next section, we provide some numerical results that illustrate the advantages and gains resulting from our proposed policies.

IV. NUMERICAL RESULTS

We use a Rayleigh model of channel fading for our numerical study, and generate channel realizations with the PDF P (h t ) = exp(-h t ) by considering unit variance (note that h for us, is in the signal power domain, and not amplitude, resulting in the exponential distribution). Additionally, we consider h min = 0.01 and consider all randomized h t = 0.01 if the randomly selected h t < 0.01. We take the parameters E 0 = 1 and δ = 0.99.

In Figure 1, we compare the energy cost by implementing the rollout policy with the optimal policy (w.r.t the available information) developed in Section III C. Observe that for N = 10, even when M = 0, the expected energy cost is reduced by about 74% when compared to the base policy (which is equivalent to rollout with M = 0). Figure 1 also shows that the reduction in energy cost by using M > 5 is not significant for neither the rollout and nor the optimal policy. Beyond this point, both the policies converge to costs that are not far from the optimal policy obtained by knowing all values of h t . This indicates that an exhaustive search is feasible to solve [START_REF] De Castro | On energyaware communication and control co-design in wireless networked control systems[END_REF] or [START_REF] Fouresti | Communication switching method, access point, network controller and associated computer programs[END_REF], and it is not essential to use advanced techniques like dynamic programming.

Figure 2 plots the thresholds gτ against the time since the last transmission (τ ), for the optimal policy with M = 0, i.e., for π * 0 (τ, g 0 ). This figure clearly shows how the optimal policy can be implemented when M = 0. If the channel realization h t ≥ gτ (with τ = τ (t)), the optimal decision would be to transmit, and not transmit otherwise. For a larger N , the channel realization much be much larger to transmit efficiently for the same τ , as you have the possibility to wait longer for a better channel.

V. CONCLUSION

We have studied the time triggered control of systems in which controller and the plant are connected through a wireless channel. The closed-loop system is such that, the controller requires an update on system state within N time instants from the previous update, in order to ensure desired properties, such as stability. This update is provided across the wireless network, which incurs an a minimum energy cost E0 ht for successful communication, where h t models the channel fading (the strength of the wireless channel). We study three models for the wireless channel and provide policies that determine when communication should be done, in order to minimize (when possible) the total discounted energy cost. The first case of interest is when the channel fading is a constant and we prove that to communicate after exactly N time instants from the previous communication instant is optimal. In the second case, the channels fading values are unknown in general but known for M future instants and we propose a sub-optimal rollout policy which is shown to provide large gains in energy cost through simulations. Finally, when the channel statistics remain a constant through time and are known, we find the optimal policy by modeling the problem as a Markov decision process. An important property of our analysis is that, the energy gains are independent of every property of the control system except for N , the MATI.

  ) where b j ∈ {0, 1} for all j ∈ {0, 1, .., M } and b = (b 0 , b 1 , . . . , b M ) satisfies the constraint (12) and S j ( b) is from Definition 2, and

Fig. 1 .

 1 Fig. 1. Expected energy cost with the rollout scheme ē(π R M ) (defined in Section III. B) or the optimal policy ē(π * M ) (defined in Section III. C) vs the number of known future channel values M .

Fig. 2 .

 2 Fig.2. Channel thresholds (gτ ) against time since last transmission (τ ) for the optimal policy with M = 0, i.e., for π * 0 (τ, g 0 ).

This work was supported by the ANR project 'Computation Aware Control Systems', ANR-13-BS03-004-02.


Roberta Ruffilli

M Berkani

P Dupuy

Stéphane Lefebvre

Y Weber

Marc Legros

In-depth investigation of metallization aging in power MOSFETs

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Power MOSFETs-based devices in the automotive industry have evolved beyond their initial electrical switch function as they integrate now several auto-diagnosis capabilities. At the same time, a better control of the fabrication process, materials purity and defect structure significantly improved their reliability. However, some parts of power components remain prone to electrical and/or thermo-mechanical aging and are thus critical for reliability assessment.

These parts have been identified as the metallic ones such as the die attach (where alternatives to lead-based solder are emerging [1,2]), and the source metallization, including the top metal and the bond wires attached to it [3][START_REF] Glavanovics | Proceedings of the 34th European Solid-State Device Research Conference[END_REF][START_REF] Pietranico | [END_REF][6]. The plastic deformation of the source metallization and wire bonds is linked to the difference in the coefficient of thermal expansion (CTE) between the Silicon (Si) chip and the metallic parts. Since Aluminum (Al) has a low elastic limit, the source metallization is expected to deform even for moderate temperature excursions (200°C). Cubased metallizations experience similar degradations [7] but seem to have a better overall endurance [8]. Deformations of the source metal have a clear impact on the drain-source resistance (R dson ), which increases over cycles. In turn, this resistance augmentation leads to larger thermal gradients.

In a previous study [9,10], we have shown that most of the metallization degradations during aging could be the result of intergranular diffusion and surface reconstruction.

This scenario [11] is however confronted to the fact that temperature cycles in a MOSFET are very abrupt and thus favor a dislocation-based plastic deformation.

Here, we follow the evolution of the microstructure of the Aluminum-based source metallization of power MOSFETs, during accelerated aging tests. We focus on the grain and grain boundary structure of the source layer away and just under the wire bonds. This buried zone is prone to failures [START_REF] Glavanovics | Proceedings of the 34th European Solid-State Device Research Conference[END_REF] but its fine microstructural characterization has proven complicated to perform so far. Here, we have used ion milling and microscopy, coupled with transmission electron microscopy, to map and quantitatively measure the microstructure aging in a MOSFET undergoing accelerated tests at these key locations.

Experimental

DUT and accelerated aging tests

The device under test (DUT) is a 24V Freescale's SmartMOS technology dedicated to truck application. The active zone is made of 2 MOS sectors, each connected by 3 Al wedge bond wires (Fig. 1). During the tests, only one sector is undergoing repeated electrical pulses, either in avalanche or short-circuit mode (energy density in the order of 3J/cm 2 for each test). Avalanche tests seem to induce a slower aging compared to shortcircuits, but more data is needed to verify this point. Electrical wave forms (current, voltage and power) recorded during tests are depicted in figure 2. During the short-circuit phase (600A at the beginning) the high current level induces a high power dissipation. R dson linearly increases during short circuit aging (Fig. 3). During these tests, the aging of Aluminum surface has been monitored at various stages (1k, 2k, 10k, 100k, 600k cycles) using SEM (Scanning Electron Microscopy).

Microstructural characterization

Surface observation and EBSD (Electron Back Scattered Diffraction) mapping were performed in a Helios 600 FIB/SEM. Figure 4 shows a weak change in the Al surface starting from 10k cycles, but it is only after 100k cycle that we observe a significant increase of the roughness. However, observation of the in-depth structure of the metallization and of the interface under the bond wires requires making cross sectional cuts of the device. This is done through both mechanical grinding (made at 45° of the surface, see Fig. 1, to let access to the ion beam) and Focused Ion Beam (FIB) cross-sectional cuts, performed perpendicular to the surface. These cross-sections are first observed using ionic channeling contrast (Fig. 5), which depends on grain orientation. This gives a first idea of the grain size (measured by the line intercept method [12]) in both the source metallization and the bond wire. It also allows measuring the deformation imposed to the initial Al layer by the wire bonding process and seeing how this interface behaves during aging. A TEM-lamella (Fig. 8) of the same zone is then prepared by removing matter behind the observed zone using the ion beam, lifting out the lamella and thinning it down to electron transparency with decreasing flux of ions (Fig. 7). TEM observations are performed in a JEOL 2010 and in a Philips™ CM20FEG equipped with a Digistar™ -ACOM (Automated Crystal Orientation Mapping) unit from NanoMEGAS™. This system captures the diffraction patterns of a given zone and returns the crystallographic orientation of each scanned point to build orientation maps of TEM samples as in Fig. 10b. EBSD and ACOM methods are complementary as they give surface or in depth information, respectively.

Results

Al metallization

Outside of the wire bonding area, the initial grain size is on the order or larger than the metallization thickness. The structure is called "bamboo" as most of the grain boundaries run perpendicular to the surface down to the substrate. An EBSD map of the initial metallization surface reveals a strong <111> texture (Fig. 9a) that is confirmed by a TEM cross section oriented through ACOM (Fig. 9b). This last image clearly shows that each grain orientation is conserved from the surface down to the transistor region. Aging seems to lower the average grain size (as measured by FIB in Fig 6 and observed elsewhere [13]), but ACOM mapping shows that most of the grain domains revealed by FIB have a small misorientation (less than 10°). Fig 10 illustrates this as two grains (1 and 2) visible in ionic contrast (Fig. 10a) have only a 8° misorientation when measured using the ACOM system (Fig. 10b). These are then subgrains potentially formed by the gathering of initial dislocations inside a single initially large bamboo grain [10]. Many cracks running from the surface to the Si substrate are observed (Fig. 10). They follow the grain boundaries and are probably the signature of a heavy Al self-diffusion process between the grains [10].

Al metallization under the wire bondings

Under the wire, the Al metallization is severely deformed, with plastic deformation ranging from 5 to 25%, in average, in the measured sections. The deformation is measured by taking the initial metallization thickness (away from the wire) in a non aged device as reference. The grain size is systematically smaller in these zones, as it can be seen in Fig. 6 and Fig. 11. In this figure, one can also note that grains in the Al wire are much larger. Upon aging, the amount of plastic deformation perpendicular to the interface does not change significantly, but grain growth is observed, at variance with what happens outside the wire-bonding area. The initial dislocation density is also higher in this zone, which forecasts larger rearrangements, cell formations and subsequent grain boundaries creation. The bonding between the metallization and the wire shows initial imperfections, probably due to Al oxide (visible in white contrast in Fig. 2). Cracks propagate along these imperfections during aging, causing a loss of contact (or a reduced contact area) between the wires and the metallization. This mechanism, coupled with cracks running perpendicularly to the interface (under and away from the bondings) must cause a R dson increase. This R dson increase implies that subsequent electrical pulses will generate more heat, thus more deformation, and crack propagation. The linear character of the resistance increase is however not linked yet to a total crack surface measurement that is unavailable so far.

Conclusion

Systematic observations of the Al-based source metallization of power MOSFETs, that underwent accelerated electro-thermal tests, revealed that aging occurs through a change in the Al grain microstructure. Under the wire bondings, the initial microstructure is much finer than elsewhere and a strong grain growth is observed. Away from the wire bonds, the metallization undergoes an apparent but limited grain growth. Cracks are observed to run perpendicular to the surface down to the substrate in bare metallization regions (following the grain boundaries), while they also propagate along the wire-metallization interface under the bondings. These mechanisms are probably linked to an enhanced self-diffusion of Al atoms along the boundaries and to a poor bonding of the wires due to the presence of Al oxide that is not fully broken during the bonding process. Both mechanisms explain why the R dson increases during electrothermal aging.

Fig. 1 .

 1 Fig. 1. Power module prepared for microstructural inspection after aging. The left sector is aged (avalanche mode, 400 kcycles) as the right one is as processed. The wires are cut and polished to 45° before being FIB-cut for interface observation.

Fig. 2 :

 2 Fig. 2 : Drain current, drain-to-source voltage and dissipated power during short-circuit phase, V DS =15V, V GS = 15V, T on = 44µs.

Fig. 3 :

 3 Fig. 3: On state resistance increase during repetitive short circuit tests, V DS =15V, V GS = 15V, T on = 44µs.

Fig. 4 .

 4 Fig. 4. SEM observation of the metallization surface after 0, 1k, 10k and 100k cycles. Scale bar 2.5 µm.

Fig. 5 .Fig. 6 .

 56 Fig. 5. FIB imaging of the naked metallization in an a) as-is and b) aged power module and of the wire-source metallization interface in an c) as-is and d) aged power module.

Fig. 7 .

 7 Fig. 7. Cartoon of a typical TEM-lamella preparation by FIB: a) deposition of a protective Platinum (Pt) layer on the area of interest, and b) matter removal behind the lamellae; c) cutting of lamella; d) lamella welding and lift out by Omniprobe; e) welding of lamella on TEM grid; f) final thinning and polishing. Scale bar 5 µm.

Fig. 8 .

 8 Fig. 8. Bright field TEM imaging of a FIB-prepared lamella from an as-is sample.

Fig. 9 .

 9 Fig. 9. EBSD mapping of a) the surface and b) the cross-section of an as is module, showing a strong 111 texture of the Al grains along the deposition direction.

Fig. 10 .

 10 Fig. 10. a) FIB imaging and b) ACOM orientation mapping of the source metal of an aged module (short circuit, 130k cycles) at the interface with the Si substrate. The plot represents the misorientation between the grains 1 and 2 along the white line in b).

Fig. 11 .

 11 Fig. 11. FIB imaging of the wire-source metallization interface in an aged power module (short circuit 130 kcycles) at a) the edge and b) in the middle of the wire. Scale bar 2.5 µm.

Freescale and the Freescale logo, are trademarks of Freescale Semiconductor, Inc., Reg. U.S. Pat. & Tm. Off. SMARTMOS is a trademark of Freescale Semiconductor, Inc.