A Class of Periodic Minplus Homogeneous Dynamical Systems

A Class of Periodic Minplus Homogeneous Dynamical Systems Nadir Farhi∗ INRIA - Paris - Rocqencourt

Domaine de Voluceau, 78153, Le Chesnay, Cedex France.

Abstract We characterize a class of additive 1-homogeneous systems not necessarily monotone which have periodic asymptotic behavior. Such a system is composed of a dynamic programming system which influences another dynamic programming one in such a way that the whole system stays additive 1-homogeneous but not necessarily monotone. The simplest situation is formulated in the minplus algebra: {uk+1 = D ⊗ uk , xk+1 = A(uk ) ⊗ n×n r×r r xk ⊕B(uk )⊗uk }, with uk ∈ Rrmin , xk ∈ Rn min , D ∈ Rmin , A : Rmin → Rmin n×r r and B : Rmin → Rmin , where A and B are two additive 0-homogeneous maps. We show in addition that every linear time-variant periodic system can be realized by a 1-homogeneous one. We give an interpretation of these results in terms of discrete and continuous Petri nets with an application to traffic.

1

Introduction

We present a subclass of additive 1-homogeneous dynamical systems which behave asymptotically as periodic monotone additive 1-homogeneous systems. A map f : Rn → Rn is said to be additive 1-homogeneous (abbreviated by 1homogeneous) when it satisfies: ∀x ∈ Rn , ∀a ∈ R, f (a1 + x) = a1 + f (x), where 1 , t (1, 1, . . . , 1). In this case, the dynamical system xk+1 = f (xk ) is also said to be 1-homogeneous. These systems are often encountered in optimal control problems, deterministic [2] or stochastic [17], in game problems [15] and in discrete event systems models [2, 4, 10, 7, 11]. A large class of 1-homogeneous systems studied in practice contains systems of the form: xk+1 = min max([M uv xk + cuv ]i ), ∀1 ≤ i ≤ n, i u∈U v∈V

(1.1)

where U and V are sets of indices corresponding, in general, to controls, M uv , uv for u ∈ U, and v ∈ V, are stochastic matrices (satisfy Mij ≥ 0 and M uv 1 = 1), ∗ Current address: University of Texas at Dallas, 800 West Campbell Road, Richardson, TX 75080, USA. [email protected]

1

and cuv , for u ∈ U, and v ∈ V, are vectors in Rn . These systems are dynamic programming equations (written with inverted time) of stochastic games of two players. When V is reduced to a singleton, we obtain: xk+1 = min([M u xk + cu ]i ), ∀1 ≤ i ≤ n, i u∈U

(1.2)

which is a stochastic dynamic programming equation. If, in addition, the matrices M u , u ∈ U have boolean entries, then we obtain a linear minplus system: xk+1 = A ⊗ xk ,

(1.3)

where A is the square minplus matrix satisfying: ( u minu∈U cui if ∃u ∈ U | Mij = 1, Aij = +∞ otherwise. The minplus algebra [2] is the idempotent commutative semiring (R∪{+∞}, ⊕, ⊗) denoted by Rmin , where the operations ⊕ and ⊗ are defined by: a ⊕ b = min{a, b} and a ⊗ b = a + b. The zero element is +∞ denoted by ε and the unity element is 0 denoted by e. We have the same structure on the set of square matrices. If A and B are two minplus matrices of size n × n, the addition ⊕ and the L product ⊗ are defined by: (A ⊕ B)ij = Aij ⊕ Bij , ∀i, j, and (A ⊗ B)ij = k [Aik ⊗ Bkj ]. The zero and the unity matrices are also denoted by ε and e respectively. In (1.2), if the set U is reduced to a singleton, then we obtain a standard affine system: xk+1 = M xk + c, (1.4) where ker(M − Id ) 6= {0}. A map f : Rn → Rn is said to be monotone if it satisfies ∀x, y ∈ Rn , x ≤ y ⇒ f (x) ≤ f (y), where x ≤ y means xi ≤ yi ∀1 ≤ i ≤ n. The properties of 1-homogeneity and monotonicity when combined become strong. Indeed, we know [3] that if f is 1-homogeneous and monotone, then it is non expansive (or 1-Lipschitz) for the sup. norm, i. e. ∀x, y ∈ Rn , ||f (x) − f (y)||∞ ≤ ||x − y||∞ . In this case an oriented graph G(f ) is associated to f [8] which is defined by the set of nodes {1, 2, . . . , n} and by a set of arcs such that there exists an arc from a node i to a node j if limν→∞ fi (νej ) = ∞, where ej is the j th vector of the canonical basis of Rn . We give below an important result about the existence of eigenvalues of 1-homogeneous monotone maps. Theorem 1.1. [7] If f : Rn → R is 1-homogeneous and monotone and if G(f ) is strongly connected then f admits an (additive) eigenvalue, i.e. ∃λ ∈ R, ∃x ∈ Rn : f (x) = λ + x. Another result [12] says that if f is 1-homogeneous and monotone and if it admits an eigenvalue λ then we have χ(f ) = λ1, where χ(f ) denotes the growth rate of the dynamical system xk+1 = f (xk ) defined by: χ(f ) = limk→∞ f k (x)/k. 2

If in addition a non expansive map f : Rn → Rn is piecewise affine, then [13] there exists a unique vector α ∈ Rn and a unique vector β ∈ Rn such that: ∀k ≥ 0, f (β + kα) = β + (k + 1)α. Another particular case is when f : Rn → Rn is 1-homogeneous monotone and convex. This case is studied in [1]. We are interested in this paper in the 1-homogeneous not necessarily monotone systems. We study a class of 1-homogeneous systems where a 1-homogenous monotone system is parameterized by an output of another 1-homogeneous monotone system in such a way that the resulting system stays 1-homogeneous but not necessarily monotone. We study first the special case when the two monotone 1-homogenous systems are minplus linear, then we generalize to the case where they are dynamic programming systems associated to stochastic optimal control problems. In both cases the asymptotic periodicity of the upstream system leads to the asymptotic periodicity of the downstream system. We give below the principal results in the simple case where the monotone systems are minplus linear. We say that a system is linear periodic if it has the form: xk+1 = Ak ⊗ xk , (1.5) where {Ak }k∈N is a periodic sequence of minplus square matrices. We say that a system is triangular 1-homogeneous when it has the form: ( uk+1 = D ⊗ uk , (1.6) xk+1 = A(uk ) ⊗ xk ⊕ B(uk ) ⊗ uk , where D is an irreducible minplus square matrix, A is a 0-homogeneous map r from Rrmin to Rn×n min (which means ∀λ ∈ R, ∀u ∈ Rmin , A(λ ⊗ u) = A(u)) and n×r r B is a 0-homogeneous map from Rmin to Rmin (which means ∀λ ∈ R, ∀u ∈ Rrmin , B(λ ⊗ u) = B(u)). The two principal results say that: – Every triangular 1-homogeneous system behaves asymptotically as a linear periodic system. – Every linear periodic system (1.5) whose matrices Ak have one same support is realizable by a triangular 1-homogeneous system.

2

Linear periodic systems

Let us take x ∈ Rnmin and A ∈ Rn×n min . If A is irreducible (i.e. when his associated graph is strongly connected), then it admits [9, 2] a unique eigenvalue λ associated to one or more than one eigenvector x, that is: ∃λ 6= ε, x 6= ε : A⊗x = λ⊗x. Moreover the system xk+1 = A⊗xk is [2] asymptotically periodic: ∃K ∈ N, T ∈ N∗ : ∀k ≥ K, xk+T = λT ⊗ xk . This means that the growth rate of the system is unique. Indeed, after a finite time, the trajectories of all the strongly connected components grow in a periodic way around lines of slope λ. When the matrix A is not irreducible, it can admit more than one eigenvalue. In this case, we denote by C1 , C2 , . . . , Cm the strongly connected components 3

of the graph G(A) associated to A, and we write Ci  Cj if there exists a path in G(A) from a node of Cj to a node of Ci . The matrix A admits q eigenvalues (1 ≤ q ≤ m) which are necessarily eigenvalues of minplus matrices associated to strongly connected components of G(A). More precisely, if we denote by ρi , 1 ≤ i ≤ m the minimum weight of the circuits of Ci , 1 ≤ i ≤ m respectively, then [6]: λ ∈ spec(A) ⇔ λ = ρi = min{ρj , Cj  Ci }.

In this case, starting from a finite vector x0 , the growth rate vector χ of the system xk+1 = A ⊗ xk satisfies: ∀ l ∈ Ci ,

χl = min{ρj , Ci  Cj }.

(2.1)

Let A(i) , i = 0, . . . , r − 1, be r minplus square matrices which do not have ε as an eigenvalue. We denote by A(p) the matrix: A

(p)

=

p+r−1 O

A(i) ,

i=p

p, i ∈ N/rN.

The matrices A(p) , p = 0, . . . , r − 1, have the same eigenvalues. Indeed, let λ be an eigenvalue of A(0) , associated to an eigenvector x 6= ε: A(0) ⊗ x = λ ⊗ x. We have: A(p) ⊗

p−1 O i=0

A(i) ⊗ x =

p−1 O i=0

A(i) ⊗ A(0) ⊗ x = λ ⊗

p−1 O i=0

A(i) ⊗ x .

Np−1 So λ is an eigenvalue of A(p) associated to the eigenvector i=0 A(i) ⊗ x. Let us suppose now that the matrices A(i) , i = 0, . . . , r − 1, have the same (p) (q) support, i.e. ∀p, q ∈ {0, 1, . . . , r − 1}, ∀i, j ∈ {1, 2, . . . , r} : Aij = ε ⇔ Aij = ε. We associate to these matrices the matrix A¯ defined by: r−1

1 X (i) A . A¯ = r i=0 Since the matrices A(i) , i = 0, . . . , r − 1 have the same support, the matrices ¯ ⊗r have the same unweighed graph. We denote A(0) , A(1) , · · · , A(r−1) and (A) ep (c) (resp. λ(c)) ¯ by C the set of circuits of this graph, and by λ the average weight of a circuit c ∈ C in the weighted graph associated to A(p) (resp. to ¯ ⊗r ). (A) Proposition 2.1. ∀c ∈ C, Proof. It is easy to see that:

¯ ep (c). λ(c) ≥ min0≤p≤r−1 λ r−1

∀c ∈ C,

1 Xe ¯ λp (c) = λ(c). r p=0 4

We show this on the simple case r = 2 with a circuit c of three arcs: 1 → 2 → 3 → 1 in the graph associated to the matrices A(p) , p = 0, 1, · · · , r − 1. Thus the circuit has six arcs in the graph associated to the matrices A(i) , i = 0, 1, · · · , r−1. We have: 1 ¯ λ(c) = [(A¯⊗2 )12 + (A¯⊗2 )23 + (A¯⊗2 )31 ] , 3 1 ¯ ¯ ¯ ¯ ¯ ¯ = [[(A) 1i + (A)i2 ] + [(A)2j + (A)j3 ] + [(A)3l + (A)l1 ]] , 3 1 (1) (2) (1) (2) (1) (2) (1) (2) = [(A1i + A1i + Ai2 + Ai2 ) + (A2j + A2j + Aj3 + Aj3 ) 6 (1) (2) (1) (2) + (A3l + A3l + Al1 + Al1 )]. Similarly, we have : ep (c) = 1 [A(p) + A(p) + A(p) ], p = 1, 2 , λ 23 31 3 12 1 (p) (p+1) (p) (p+1) (p) (p+1) = [(A1i + Ai2 ) + (A2j + Aj3 ) + (A3l + Al1 )], p = 1, 2 . 3 The result is then deduced from the inequality : r−1

1 Xe ep (c) λp (c) ≥ min λ p r p=0 Corollary 2.2. If A(i) , i = 0, . . . , r − 1, are irreducible and have the same support, then for every p in {0, 1, . . . , r − 1}, the growth rate of the system ¯ ⊗r ⊗ xk . xk+1 = A(p) ⊗ xk is less than or equal to that of the system xk+1 = (A) Proof. It follows directly from the proposition 2.1

3

Parameterized linear systems

We study a minplus linear system depending on a signal u which is an output of another minplus linear system. Overall the system is only homogeneous. We show that the whole system behaves asymptotically as a periodic timevariant minplus linear system. We give some corollaries, mainly a result on the realization of periodic time-variant linear systems. We interpret these results on examples of Petri nets. The first result is about the behavior of triangular 1-homogeneous systems (systems (1.6)). On these systems, the 0-homogeneity of the maps A and B is tantamount to the existence of two families (αij ) and (βij ) of vectors in Rr satisfying αij 1 = 0 and βij 1 = 0 and two families (aij ) and (bij ) of scalars in Rmin such that:  A(u)ij = t αij u + aij , (3.1) B(u)ij = t βij u + bij . 5

By abuse of language, we say that the map A is irreducible if there exists u in Rrmin such that A(u) is irreducible. Theorem 3.1. Every triangular 1-homogeneous system behaves asymptotically as a linear periodic system. Proof. The matrix D being irreducible, we have : ∃K, T ∈ N, λ 6= ε : ∀k ≥ K, uk+T = λT ⊗ uk , hence ∀k ≥ K, A(uk+T ) = A(uk ) and B(uk+T ) = B(uk ). So the system is asymptotically linear periodic Below we illustrate this result by an example which we interpret in terms of Petri net dynamics. To do this we give a brief recall of Petri nets. A Petri net is a graph with two types of nodes called places and transitions, and two types of arcs called production arcs and synchronization arcs. Places and transitions are symbolized by circles and bars respectively. Tokens are supposed to be in places at the initial time. The production arcs go from transitions to places while the synchronization arcs go from places to transitions. We consider here only deterministic Petri nets whose each place has only one downstream synchronization arc. Weights (or multiplicities) are associated to the production arcs. The Petri net dynamics is defined by what is called the firing of transitions. At each time, a transition is fired if in each upstream place of the transition there exists at least one token (or a positive real number in the continuous case, where the number of tokens is not necessarily integer) which has been in the place since at least one unit of time. When a transition fires it takes (consumes) one token from each upstream place and generates (produces) a number of tokens, in each downstream place, equals to the weight of the corresponding production arc. When the weight is negative the production becomes a consumption. Thus the Petri net dynamics is defined by either the displacements of tokens or the firing of transitions (dually). Example 3.2. Let us consider the triangular 1-homogeneous system given by:    p    1u1 /u2 ε 1 ε u2 /u1 ε e . ε ε , B(u) = ε D= , A(u) =  e ε 1 1 ε e ε ε ε p We recall that 1u1 /u2 and u2 /u1 are written in the standard algebra 1+u1 −u2 and (u2 − u1 )/2 respectively. This system is the dynamics of the deterministic Petri net given on the left of Figure 1, where we denote by uk1 , uk2 , xk1 , xk2 , xk3 respectively the cumulated numbers of firing of the transitions u1 , u2 , x1 , x2 , x3 up to time k. We can check that if u0 = t [e e] then the triangular 1-homogeneous system behaves as the linear periodic system, of period 2, given by:     u uk+1 = E k ⊗ k , k ∈ N/2N, xk xk+1 6

u1

u1

u2

u2

−1/2 3/2 0 ; 1/2

−1 x3

x1

x3

x1

x2

1;0

x2

Figure 1: On the left : a ”triangular” Petri net. On the right : the corresponding periodic time-variant Petri net.

where:



ε e 1 1  E0 =  ε e ε ε ε ε

ε ε 1 e ε

ε ε ε ε e

 ε ε  1 , ε ε



 ε e ε ε ε 1 1 ε ε ε  √  1 E = 1 e ε 1 ε . ε ε e ε ε ε ε ε e ε

The linear periodic system corresponds to the dynamics of the time-variant Petri net given on the right of Figure 1 In the following we give a theorem about the growth rate of the triangular 1homogeneous systems. If the map A is irreducible, then the growth rates of the variables xi , 1 ≤ i ≤ n, are the same and depend only on the initial condition u0 . We denote this quantity by µx (u0 ), and we call minplus cyclic matrix, a square minplus matrix (r × r) satisfying: ( Dij 6= ε if i = j + 1 (modulo r), ∀ 1 ≤ i, j ≤ r : Dij = ε elsewhere. Theorem 3.3. In a triangular 1-homogeneous system, if D is a minplus cyclic matrix and A is an irreducible map, then : maxu∈Rrmin µx (u) = µx (¯ u), where u ¯ is the unique additive eigenvector of D. Proof. We can check that the unique additive eigenvector of D (or the unique Pr−1 minplus eigenvector of D seen as a minplus matrix) is given by: u ¯ = 1r k=0 uk . P r−1 Let us define the matrix A¯ by : A¯ = A(¯ u). We obtain : A¯ = 1r k=0 A(uk ). Thus we have the two cases : 1. If u0 6= u ¯, then the sequence (uk )k≥0 is periodic of period r. The dynamics

7

of (xk )k∈N is : k+r

x

=

r−1 O

A(u

k+l

l=0

!

)

⊗ xk ⊕ E(u) ⊗ uk ,

where E(u) is a matrix depending on uk , uk+1 , · · · , uk+r . If we denote by Nr−1 Ak the matrix l=0 A(uk+l ) then we have:  k+r   ⊗r   k D ε u u = ⊗ k . (3.2) E(u) Ak xk+r x 2. If u0 = u ¯, then the dynamics of (xk )k∈N is written : ¯ r ⊗ xk ⊕ E(¯ xk+r = (A) u) ⊗ u k , where E(¯ u) is a matrix depending on u ¯. We obtain:  k+r   ⊗r   k u u D ε = ⊗ k . E(¯ u) A¯⊗r xk+r x

(3.3)

We denote by λ(D⊗r ), λ(Ak ) and λ(A¯⊗r ) respectively the eigenvalues of the matrices D⊗r , Ak and A¯⊗r , which are also the growth rates of the corresponding systems, since these matrices are irreducible. From Corollary 2.2, we know that: λ(Ak ) ≤ λ(A¯⊗r ). It is easy to check that if u0 = ε then: µx (¯ u) = λ(A¯⊗r ) ≥ λ(Ak ) = µx (u0 ). Let us take u0 6= ε and use (2.1) to compare the systems (3.2) and (3.3). • If λ(D⊗r ) ≤ λ(Ak ) ≤ λ(A¯⊗r ) then:

µx (u0 ) = µx (¯ u) = λ(D⊗r ), • If λ(Ak ) ≤ λ(D⊗r ) ≤ λ(A¯⊗r ) then: µx (¯ u) = λ(D⊗r ) ≥ λ(Ak ) = µx (u0 ), • If λ(Ak ) ≤ λ(A¯⊗r ) ≤ λ(D⊗r ) then: µx (¯ u) = λ(A¯⊗r ) ≥ λ(Ak ) = µx (u0 ). Thus, µx (¯ u) ≥ µx (u), ∀u ∈ Rrmin Example 3.4. Let us take the triangular 1-homogeneous system given by the matrix D and the maps A and B:     u1 /u2 ε 1 ε 1 ε ε , B(u) = ε3×2 . D= , A(u) =  e e ε ε e ε

This system is the dynamics of the deterministic Petri net of Figure 2. 8

u1 x3 x1 x2

−1

u2 Figure 2: Growth rate optimization.

1. If u0 = t [e e], then the dynamics of x is written xk+1 = E k ⊗xk , k ∈ N/2N with :     e ε 1 1 ε 1 E 0 = e ε ε and E 1 = e ε ε . ε e ε ε e ε √ The average growth rate of (xk )k∈N is µ = λ (µ = λ/2 in standard notation) where λ is the unique eigenvalue of the matrix E 0 ⊗ E 1 , which √ √ 4 is 1 (1/2 in standard notation). We obtain µ = 1 (1/4 in standard notation). √ 2. If u0 = t [ √1 e] which is the eigenvector of D associated to the unique eigenvalue 1, then the dynamics of x is written xk+1 = E ⊗ xk , with :  √ 1 ε 1 E =  e ε ε . ε e ε The average growth rate of (xk )k∈N is the unique eigenvalue of E which √ 3 is µ = 1 (µ = 1/3 in standard notation)

Theorem 3.5. Every linear periodic system y k+1 = E k ⊗ y k whose matrices E k , k ∈ N/rN have the same support, is realizable by a triangular 1homogeneous system. Before giving the proof of Theorem 3.5, we give an example which may help to understand the proof. k+1 Example 3.6. = E k ⊗xk , k ∈ N/2N where:   The linear periodic system: x ε ai Ei = , i ∈ N/2N, describes the dynamics of the periodic time-variant bi ε Petri net given on the left of Figure 3. This system is realized by the triangular 1-homogeneous system given by the matrices: # "   a /a a /a ε 1 ε a0 u1 1 0 u2 0 1 , B(u) = ε(2×2) , D= , A(u) = b /b b /b e ε ε b0 u11 0 u20 1

where the initial condition on u is taken: u01 = u02 6= ε. 9

u1

a = a 0 ; a1

u2

b = b 0; b1

a− a0 1

b −b a − a1

b − b0

0

a

x2

b

a0

0

1

1

x2

b0

x1

x1 Figure 3: Realization of a periodic time-variant Petri net by a triangular deterministic one.

This system describes the dynamics of the triangular deterministic Petri net given on the right of Figure 3 Proof. Let r be the period of the linear periodic system. The matrix D and the maps A and B are given as follows: – D is the r × r minplus matrix given by :   e if i = j + 1,  ε     e  1 if i = 1 and j = r, Dij = D=  ε     ε ε otherwise.

ε ε .. .

··· ···

···

e

 1 ε  ..  , . ε

– A : Rr → Rn×n is given by : X A(u)ij = (E s+1 − E s )ij us+1 + (E 0 )ij , s∈N/rN

– B : Rr → Rn×r is the null map i.e. ∀u ∈ Rr , B(u) = εn×r , when the initial condition on u is taken: u0 = t [α, α, · · · , α], for any α ∈ R

4

Generalization

In this section we give the generalization of Theorem 3.1 and Theorem 3.5 to nonlinear systems defined by polyhedral convex monotone homogeneous operators. These systems are interpretable as dynamic programming equations of stochastic optimal control problems.

10

Let f : Rn → Rn be a 1-homogeneous monotone and convex map. The sub-differential of f in x, given by the set ∂f (x) = {P ∈ Rn×n , f (y) − f (x) ≥ P (y − x), ∀y ∈ Rn }, has been used in [1] to obtain some properties of the graph associate to f . We can check that the matrices P of ∂f (x) are stochastic matrices (they satisfy Pij ≥ 0 ∀i, j and P 1 = 1). When a convex monotone 1-homogeneous map f admits an eigenvector v, the critical graph of f , denoted by G c (f ), is defined by the union of the final graphs of the stochastic matrices P ∈ ∂f (v), where a final graph of a stochastic matrix is the restriction of its graph to the set of final classes. We denote by G1 , G2 , . . . , Gs the strongly connected components of G c (f ), by c(Gi ), which we call the cyclicity of Gi , the gcd of the circuit lengths of G1 , G2 , . . . , Gs , and by c(f ), which we call the cyclicity of f , the lcm of the cyclicities of G1 , G2 , . . . , Gs . Let us give the system: xk+1 = min([M u xk + cu ]i ), ∀1 ≤ i ≤ n. i u∈U

(4.1)

Stochastic dynamic programming operators associated to stochastic optimal control problems (4.1) are convex monotone 1-homogeneous maps. For such operator, if in the set U of controls is finite, then the operator is piecewise affine. Let us denote by P the set of stochastic dynamic programming operators associated to ergodic stochastic optimal control problems with finite set of controls. The following result will be used to generalize Theorem 3.1. Theorem 4.1. [14, 16] If f is in P then for every x in Rn , the sequence {f kc (x) − kcλ}k∈N converges, where c and λ are respectively the cyclicity and the eigenvalue of f . A convex monotone homogeneous dynamical system xk+1 = f (xk ) is said to be periodic (we abbreviate by saying periodic convex system) if it can be written: = fik (xk ) = min[M k,u xk + ck,u ]i , k ∈ N/rN, ∀1 ≤ i ≤ n , xk+1 i u∈U

where ∀u ∈ U, k ∈ N/rN, M k,u is a stochastic matrix of size n × n and ck,u is a vector in Rn . The system xk+1 = f (xk ) is said to be of periodic costs if it can be written: = fik (xk ) = min[M u xk + ck,u ]i , k ∈ N/rN, ∀1 ≤ i ≤ n , xk+1 i u∈U

(4.2)

where ∀u ∈ U, k ∈ N/rN, M u is a stochastic matrix of size n × n and ck,u is a vector of Rn . The system xk+1 = f (xk ) is said to be triangular if it can be written: ( vik+1 = hi (v k ) = minu∈U ([Du v k + du ]i ), ∀1 ≤ i ≤ r , (4.3) xk+1 = fi (v k , xk ) = minw∈W ([Aw xk + B w v k + cw ]i ), ∀1 ≤ i ≤ n , i with the following assumptions: 11

(H1): The matrices Du , u ∈ U are stochastic and irreducible, (H2): The matrices Aw , w ∈ W are sub-stochastic1 and ∀w ∈ W, [Aw B w ]1 = 1. The system (4.3) is homogeneous because Du , u ∈ U are stochastic and Aw , w ∈ W and B w , w ∈ W satisfy [Aw B w ]1 = 1. It is not necessarily monotone because B w , w ∈ W can have negative entries. Thus such a system can not be interpreted as a dynamic programming equation of stochastic optimal control problem. The following theorem is a generalization of Theorem 3.1. Theorem 4.2. Every triangular convex system is asymptotically representable as a system of periodic costs. Proof. For all w ∈ W, we put B w = B1w + B2w in such a may that (B1w )ij ≥ 0, ∀i, j and [B1w Aw ]1 = 1. This gives B2w 1 = 0. So we have: xk+1 = min [(Aw xk + B1w v k ) + (B2w v k + cw )]. w∈W

If we denote Υ = U × W and define:  u  D 0 Eν = , z = t [v x], bνk = t [du B1w Aw

B2w v k + cw ],

ν = (u, w) ∈ Υ ,

then the system (4.3) can be written: z k+1 = min[E ν z k + bνk ] ,

(4.4)

ν∈Υ

where E ν are stochastic matrices. From the assumption (H1) and Theorem 1.1 we deduce that the map h admits an (unique) eigenvalue, i.e. ∃λ ∈ R, ∃¯ v ∈ Rr , min([Du v¯ + du ]i ) = λ + v¯i , u∈U

∀1 ≤ i ≤ r .

From Theorem 4.1, the sequence (hks − ksλ)k∈N , where s is the cyclicity of h converges, i.e. ∃a ∈ R, lim (v ks − ksλ) = a, k→∞

so : lim (v (k+1)s − v ks ) = sλ ,

k→∞

so : lim B2w v k+s + cw = lim B2w (v k + sλ) + cw = lim B2w v k + cw ,

k→∞

k→∞

k→∞

hence : lim |bνk+s − bνk | = 0 ,

k→∞

This means that the sequence (bνk )k∈N is asymptotically periodic of period s. Thus the triangular system is asymptotically periodic (of periodic costs) 1A

∈ Rn×n is sub-stochastic if it satisfies A1 ≤ 1 and Aij ≥ 0 ∀ 1 ≤ i, j ≤ n.

12

The following theorem is a generalization of Theorem 3.5. Theorem 4.3. Every convex system with periodic costs is realizable by a triangular convex system. Proof. We modify the proof of Theorem 3.5. Giving the following convex system with periodic costs of period r: xk+1 = min([E u xk + bk,u ]i ), i

∀i = 1, · · · , n, k ∈ N/rN .

u∈U

A triangular convex system realizing the system (4.5) is : ( v k+1 = Dv k + d , xk+1 = minu∈U [Au xk + B u v k + cu ]i , ∀i = 1, · · · , n , i

(4.6)

where: • v 0 = 0Rr , • D is the r × r matrix:

 0 0 1 0   D = 0 1  .. .. . . 0 0

··· ··· ..

.

0 0 0 .. . 1

 1 0  0 , ..  . 0

• d is the column vector of size r given by : d = t (1, 0, · · · , 0), • Au = E u ,

∀u ∈ U,

• (B u )u∈U is the family of matrices of size n × r given by : (j+1),u

u Bij = bi

i.e.

• cu = b0,u ,

− bj,u i ,

 1,u b1 − b0,u 1    1,u b2 − b0,u 2  Bu =   ..   .   0,u b1,u n − bn

∀u ∈ U, ∀1 ≤ i ≤ n, j ∈ N/rN ,

1,u b2,u 1 − b1

···

1,u b2,u 2 − b2

···

.. . 1,u b2,u n − bn

∀u ∈ U

13

··· ···

(r−1),u

b0,u 1 − b1

(4.5)



  (r−1),u   b0,u − b 2 2  ,  ..   .   (r−1),u − b b0,u n n

u1 ϕ

ϕ

4

1

xn−1 an−1

an−1

u2 −1

xn z2

b1

z1

an an

u4

3

u3 −1

b0

bm

bm

ϕ2

a0

ϕ

bm−1

zm

z m−1 bm−1

x1

a1 x2

Figure 4: Traffic light intersection without possibility of turning.

5

Application to traffic

The traffic on a system of two circular roads with an intersection without possibility of turning is modeled by a triangular 1-homogeneous system. The intersection is controlled with a signal light. On the Petri net of Figure 4, we have a vertical road of n sections and a horizontal one of m sections. On the vertical (resp. horizontal) road, each section i, 1 ≤ i ≤ n (resp. j, 1 ≤ j ≤ m) is modeled by one transition xi (resp. zj ), and by two places ai and a ¯i (resp. bj and ¯bj ). The presence of one vehicle on the section i (resp. j) is indicated by one token in the place ai (resp. bj ) and zero token in the place a ¯i (resp. ¯bj ). Thus we have a ¯i = 1 − ai , 1 ≤ i ≤ n and ¯bj = 1 − bj , 1 ≤ j ≤ m. The firing of a transition xi (resp. zj ) corresponds to a vehicle moving from the section i − 1 (resp. j − 1) to the section i (resp. j). The traffic light is modeled by the subsystem corresponding to the transitions u1 , u2 , u3 and u4 , which has no input coming from the rest of the system. The dynamics of this subsystem is minplus linear. The initial condition u0 is taken u0 = (0, 0, 0, 0). The number of tokens in the places a0 and b0 stays boolean and periodic of period 4. This period is the cycle of the traffic light. Thus a cycle is partitioned in four phases which are given in the Table 1. The junction has a buffer place in each direction (a1 , b1 ) to avoid blocking. The phases 2 and 4 allow to free the junction by closing the two roads in order to avoid the crossing of vehicles coming from the North with vehicles coming from the East. Tokens do not stay more than one unit of time in the places an and bm . The green durations of phase 1 and 3 are the sojourn times of tokens in the places ϕ1 and ϕ3 . The phases 2 and 4 have a duration of one time unit. 14

Phase 1 2 3 4

a0 1 0 0 0

b0 0 0 1 0

Vertical light color green red red red

Horizontal light color red red green red

Table 1: Traffic light phases.

Proposition 5.1. The dynamics of the Petri net of Figure 4 is giving by the triangular 1-homogeneous system :   ε ε ε ϕ4   k  k+1   ϕ1 ε A1 (uk ) ε x ε ε x k k+1   = ⊗ k , ⊗u , u = ε ϕ2 ε ε z ε A2 (uk ) z k+1 ε ε ϕ3 ε where

A1 (u)i,j

( a0 u1 /u2 = independent of u

if (i, j) = (n, n), elsewhere .

A2 (u)i,j

( b0 u3 /u4 = independent of u

if (i, j) = (m, m), elsewhere.

and

It is possible to explicit the asymptotic flows on the two roads. Indeed, the asymptotic flow on the vertical (resp. horizontal) road is given by : lim xki /k, ∀1 ≤ i ≤ n

k→∞

(resp. lim zjk /k, ∀1 ≤ j ≤ m). k→∞

Thus in the particular case where all the phases have the duration of one time unit : ϕi = 1, ∀1 ≤ i ≤ 4, we obtain : Theorem 5.2. The average flow on the vertical [resp. horizontal] road is given √ by 4 λ (or λ/4 in standard notation) where λ is the unique eigenvalue of the N3 N3 k irreducible minplus matrix k=0 A1 (uk ) [resp. k=0 A2 (u )].

More details of the traffic modeling by Petri nets, minplus algebra and 1homogeneous systems can be found in [5].

References [1] M. Akian and S. Gaubert, Spectral theorem for convex monotone homogeneous maps, and ergodic control, Nonlinear Analysis, TMA, vol. 52, no. 2, pp. 637–679, 2003. 15

[2] F. Baccelli, G. Cohen, G. J. Olsder and J.-P. Quadrat, Synchronization and linearity : an algebra for discrete event systems, John Wiley and Sons, 1992. [3] M. G. Candrall and L. Tartar, Some relations between non expansive and order preserving maps, Proceedings of the AMS, vol. 78, no. 3, 1980, pp. 385-390. [4] G Cohen, S. Gaubert and J.-P. Quadrat, Asymptotic throughput of continuous timed Petri nets, In proceedings of the 34th IEEE - CDC, New Orleans, 1995. [5] N. Farhi, Mod´elisation minplus et commande du trafic de villes r´eguli`ere, Thesis dissertation, Universit´e Paris 1 Panth´eon - Sorbonne, 2008. [6] S. Gaubert, Th´eorie des syst`emes lin´eaires dans les dioides, Thesis disser´ tation, Ecole des Mines de Paris, 1992. [7] S. Gaubert and J. Gunawardena, A non-linear hierarchy for discrete event dynamical systems, In Proceedings of the 4th IEE - WODES, Cagliari, 1998. [8] S. Gaubert and J. Gunawardena, Existence of Eigenvectors for Monotone Homogeneous Functions, Hewlett-Packard Technical Report HPL-BRIMS99-08, 1999. [9] M. Gondran and M. Minoux, Graphs and Algorithms, John Wiley and Sons, 1986. [10] J. Gunawardena, Idempotency, Publications of the Isaac Newton Institute. Cambridge University Press, 1998. [11] J. Gunawardena, From max-plus algebra to nonexpansive maps: a nonlinear theory of discrete event systems, Theoritical Computer Science, 2001. [12] J. Gunawardena and M. Keane, On the existence of cycle times for some nonexpansive maps, Technical Report HPL-BRIMS-95-003, HewlettPackard Labs, 1995. [13] E. Kohlberg, Invariant helf-lines of nonexpansive piecewise-linear transformations, Math. Oper. Res., vol. 5, no. 3, pp. 366–372, 1980. [14] E. Lanery, Etude asymptotique des syst`emes markovien a ` commande, Rev. Fran¸caise Informat. Rech. Op´er., vol. 1, no. 5, pp. 3–56, 1967. [15] D. Rosenberg and S. Sorin, An operator approach to zero-sum repeated games, Israel J. Math., vol. 121, pp. 221–243, 2001. [16] , P. J. Schweitzer and A. Federgruen, The asymptotic behaviour of undiscounted value iteration in Markov descision problems, Math. Oper. Res., vol. 2, no. 4, pp. 360–381, 1977. [17] P. Whittle Optimization over time, vol. 2, Wiley, 1986.

16

All in-text references underlined in blue are linked to publications on ResearchGate, letting you access and read them immediately.