Romain Jacob
email: rjacob@ens-cachan.fr

Saïd Amari
email: samari@ens-cachan.fr

Output feedback control for partially observable linear Max-Plus systems under temporal constraints

Keywords: Output feedback control, Timed event graphs, Max-Plus algebra, Timed-Petri nets, Control of constrained systems, Discrete Event Systems in Manufacturing

Combined use of Timed Event Graphs (TEG) and Max-Plus algebra is a well-known approach for handling timed behavior of discrete event systems. It has been used to tackle control problems with temporal constraints on the system states. However, in the current literature, most of the control approaches assume that system models are fully observable, which is a strong limitation in practice. Hence, we propose in this paper an output feedback control approach aiming to preserve time and robustness performances. We demonstrate that we can derive an efficient control law satisfying a set of constraints given easy-to-check a priori sufficient conditions on the system model. We illustrate our approach on a small traffic light problem.

Introduction

A control problem commonly involves some temporal constraints to satisfy. They can take diverse forms (e.g., deadline, time intervals, validity duration, synchronization. . . ), which are encountered in a wide range of applications (e.g., semiconductor industry [START_REF] Kim | Feedback control of cluster tools for regulating wafer delays[END_REF], automotive industry [START_REF] Abdourrahmane M Atto | Control of discrete event systems with respect to strict duration: Supervision of an industrial manufacturing plant[END_REF], chemical treatments [START_REF] Kim | Schedule stabilization and robust timing control for time-constrained cluster tools[END_REF], rail transport [START_REF] Kersbergen | Towards railway traffic management using switching max-plus-linear systems[END_REF], robotics [START_REF] Lopes | Modeling and control of legged locomotion via switching max-plus models[END_REF], communication networks [START_REF] Addad | Analytic calculus of response time in networked automation systems[END_REF]. . . ).

A Timed Event Graph (TEG) is a subclass of Timed Petri nets which is useful for modeling timed behavior. It turns non-linearity of timed dynamics into a linear system of equations over the Max-Plus algebra [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]. Combined use of TEG and Max-Plus is a well-known approach in the literature initiated back in the 1960's [START_REF] Raymond A Cuninghame-Green | Process synchronisation in a steelworks-a problem of feasibility[END_REF] and it is still a very active field of research. This framework has been successfully applied to solve diverse control problems, such as dynamic scheduling [START_REF] Bonhomme | Scheduling and control of real-time systems based on a token player approach[END_REF][START_REF] Kersbergen | Towards railway traffic management using switching max-plus-linear systems[END_REF][START_REF] Kim | Schedulability analysis of timeconstrained cluster tools with bounded time variation by an extended petri net[END_REF], synchronization of switching models [START_REF] Lopes | Modeling and control of legged locomotion via switching max-plus models[END_REF][START_REF] Gabriel | On the synchronization of cyclic discrete-event systems[END_REF], the disturbance decoupling problem [START_REF] Shang | An integrated control strategy in disturbance decoupling of max-plus linear systems with applications to a high throughput screening system in drug discovery[END_REF], or just-in-time control [START_REF] Houssin | Just in time control of constrained (max,+)-linear systems[END_REF][START_REF] Lhommeau | A nonlinear set-membership approach for the control of discrete event systems[END_REF]. Both open loop [START_REF] Lhommeau | Interval analysis and dioid: application to robust controller design for timed event graphs[END_REF][START_REF] Andrey | On the model reference control for max-plus linear systems[END_REF] and feedback [START_REF] Andrey | On the control of max-plus linear system subject to state restriction[END_REF][START_REF] Shang | An integrated control strategy in disturbance decoupling of max-plus linear systems with applications to a high throughput screening system in drug discovery[END_REF] control have been considered in order to solve model matching problems.

In this paper, we focus on the feedback control of Max-Plus linear systems under temporal constraints defined as maximal time laps set on the system states (e.g., the stripping time of a piece by immersion in an acid bath is defined by a time interval, it requires a minimum soak time but must not exceed a maximum time). This kind of problem has been addressed either using a temporal approach based on daters like in [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF][START_REF] Garcia | Traffic light coordination of urban corridors using max-plus algebra[END_REF][START_REF] Katz | Max-plus (a, b)-invariant spaces and control of timed discrete-event systems[END_REF][START_REF] Kim | Feedback control of cluster tools for regulating wafer delays[END_REF][START_REF] Andrey | Some results on the feedback control of max-plus linear systems under state constrains[END_REF][START_REF] Andrey | A super-eigenvector approach to control constrained max-plus linear systems[END_REF] or its transformed version based on power series [START_REF] Hardouin | Discrete-event systems in a dioid framework: Control theory[END_REF][START_REF] Houssin | Control of (max,+)-linear systems minimizing delays[END_REF], which is similar to Z-transform for conventional linear system theory. Even though they do address the control of temporal constraints, these previous works suffer from a strong limitation: they consider the system to control as fully observable, which is never the case in practice. Hence, we aim to derive an output feedback controller which preserves as much as possible the performances of the system (i.e., the cycle time and the robustness again disturbances) while only output events are considered as observable.

Hardouin et al. presented an observer design for Max-Plus linear systems which could solve our observability problem [START_REF] Hardouin | Max-plus linear observer: application to manufacturing systems[END_REF][START_REF] Hardouin | Observer design for (max,+) linear systems[END_REF]. However, in the general case, this approach provides an under-estimation of the states (i.e., x ≤ x). We will show later on that we would need instead an over-estimation of the state in order to solve our control problem (see Rem. [START_REF] Kim | Feedback control of cluster tools for regulating wafer delays[END_REF]). Equality is only obtained under restrictive conditions. In [START_REF] Vinicius | An observer for tropical linear event-invariant dynamical systems[END_REF], the authors suggested to observe an expression W • x instead of the full state x, which can lead to an exact estimate un-der slightly less restrictive conditions than in [START_REF] Hardouin | Observer design for (max,+) linear systems[END_REF] (even though still quite restrictive). Starting from a conventional state feedback control u(k) = F • x(k -1), it allows to perform output feedback control by observing directly the expression of interest (i.e., F •x(k-1)). However, this approach neglects the preservation of the cycle time and lead to poor time performances. Moreover, approaches from [START_REF] Vinicius | An observer for tropical linear event-invariant dynamical systems[END_REF][START_REF] Andrey | Some results on the feedback control of max-plus linear systems under state constrains[END_REF] assume full controllability over the system which is not necessary in general. Finally, there are no simple interpretation of the sufficient conditions suggested in [START_REF] Vinicius | An observer for tropical linear event-invariant dynamical systems[END_REF][START_REF] Hardouin | Observer design for (max,+) linear systems[END_REF][START_REF] Andrey | Some results on the feedback control of max-plus linear systems under state constrains[END_REF]. In other words, one can compute and test the conditions, but it gives no insight on reconfiguration strategies to solve the control problem if the conditions do not hold.

In this paper, we present an approach to directly derive an output feedback controller which is an extension of the state feedback approach from [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF] and [START_REF] Kim | Feedback control of cluster tools for regulating wafer delays[END_REF]. Instead of using observers to cope with partially observable models, we formulate sufficient conditions for the control to enforce the constraints and then express it into a realizable output feedback control law (i.e., expressed by a causal function). In comparison with previous work, we only need the internal subgraph of our TEG (i.e., the subgraph obtained by deleting input and output transitions together with the arcs connecting them to other transitions) to be strongly connected. However, we will justify in Sect.2.3 that this is not a strong restriction: an open-loop event graph can be made strongly connected without modifying its original cycle time. The advantage of our approach is that it does not rely on observers to perform output feedback, which straighten our guarantees in terms of controllability, time and robustness performances, while handling partially observable models. Plus it does not need full controllability over the system to control it, which is an improvement from [START_REF] Andrey | Some results on the feedback control of max-plus linear systems under state constrains[END_REF] and [START_REF] Vinicius | An observer for tropical linear event-invariant dynamical systems[END_REF]. We use a simple traffic light example to illustrate our approach and show that output feedback control can be achieved more efficiently than in previous works.

We introduce useful background on Max-Plus and TEG in Section 2. Section 3 starts with a summary of our modeling hypothesis and control problem and then details our control approach and the derivation of our output feedback control theorem. Finally, we present an illustrative example in Section 4, including discussions on control performances and comparisons with previous results.

Preliminaries

Max-Plus Algebra

A monoid is a set, say D, endowed with an internal law, noted ⊕, which is associative and has a neutral element, denoted ε. A semiring is a commutative monoid endowed with a second internal law, denoted ⊗, which is associative, distributive with respect to the first law ⊕, has a neutral element, denoted e, and admits ε as absorbing element (i.e., ∀a ∈ D, a ⊗ ε = ε ⊗ a = ε). A dioid is a semiring with an idempotent internal law (i.e., ∀a ∈ D, a ⊕ a = a). The dioid is said to be commutative if the second law ⊗ is commutative. Max-Plus algebra is defined as (R ∪ {-∞}, max, +). This semiring, denoted R max , is a commutative dioid, the law ⊕ is the operator max with neutral element ε = -∞, and the second law ⊗ is the usual addition, with neutral element e = 0. ⊗ is abbreviated by • (dot). (+, ×) refer to the usual addition and multiplication.

Given matrices of appropriate dimensions, ⊕ and ⊗ operations are defined as follow:

(A ⊕ B)(i, j) = max(A(i, j), B(i, j)) (A • B)(i, j) = n k=1 (A(i, k) • B(k, j)) = max k∈[1..n] (A(i, k) + B(k, j))
The unit matrix I has diagonal entries equal to e and ε elsewhere. M p is the p th power of matrix M in R max (e.g., M 2 = M • M ) and M 0 = I. The Kleene star of a square matrix M is denoted by M * and defined as M * = i∈N M i . Refer to [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF] for details.

Definition 1 (Similar vectors) Two vectors u and v are similar in R max if they share the same zero-elements regarding to the law ⊗. If they are of size n then

∀r ∈ [1..n], ( u(r) = ε ⇔ v(r) = ε ) Proposition 2 Similarity is distributive over the law ⊗. Given three vectors u, v, w ∈ R max , (u, v) similar ⇒ (u • w, v • w) similar Proof u • w = ε ⇔ n r=1 u(r) • w(r) = ε ⇔ [ ∀r ∈ [1..n], u(r) = ε ⇒ w(r) = ε ] Since (u, v) are similar, ⇔ [ ∀r ∈ [1..n], v(r) = ε ⇒ w(r) = ε ] ⇔ v • w = ε 2 2.

TEG and Linear Max-Plus Models

An event graph is an ordinary Petri net where each place has exactly one upstream and one downstream transition. A timed event graph (TEG) is an event graph with delays associated to places (holding times) or transitions (firing times). Transitions without downstream places are outputs, those without upstream places are inputs. Others are simply called internal transitions. We distinguish inputs that are controllable, the controls, from those which are not, the disturbances. Disturbances will not be explicitly modeled but can be implemented in simulations (see Sect.4).

We further introduce the following notations and definitions

• p ij denotes the place linking t j to t i when it exists,

• A path is an oriented alternating sequence of transitions and places successively connected by an arc, • The token number of a path is the sum of tokens in all places along the path, • The delay of a path is the sum of holding and firing time of all places and transitions along the path, • Given two transitions t i and t j and a token number m ij , several m ij -token paths connecting t j to t i can exist in general.

t j mij ,τij
-→ t i denotes the maximal of such paths (i.e., the m ij -token path with maximum delay τ ij ),

• A primal path contains exactly one token in the first place along the path, • An empty path contains no token, • A circuit around t i is a path connecting t i to itself, • An elementary path does not contain any place or transition more than once, • An event is the firing of a transition, • A transition t j is controllable if it is linked directly from a control (i.e., a place p jus exists), • A transition t i is observable if it is linked directly to an output, (i.e., a place p yri exists).

A Petri net is said to be live for an initial marking if all transitions can always be enabled by a future marking [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]. An autonomous event graph contains only internal transitions. A nonautonomous event graph is said to be live if its internal subgraph (or autonomous subgraph, that is pruned of input/output transitions) is live.

Theorem 3 (from [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]) An autonomous event graph is live if and only if every circuit contains at least one token with respect to the initial marking.

Definition 4 (Realizable output feedback) An output feedback expression is said to be realizable if it depends linearly on controls and outputs events associated to non-negative delays. In other words, C is realizable if

C = m,r,t (δ m,r • y r (k -m) ⊕ µ m,s • u s (k -m))
where {δ m,r , µ m,s } m,r,s = ε or ≥ e.

The dynamics of a TEG are described by the following Max-Plus equation It is shown that for a live TEG, after eventually extended the state vector, (1) can be rewritten under the following explicit form, [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF] for details.

x(k) = m (A m • x(k -m) ⊕ B m • u(k -m)) (1
� � � � � � � � � (�, �) � � * (�, �) � ⋅ � �, � ∶ empty path � � � � � � (�, �) � � * (�, �) empty path � � � � � � � � (�, �) � � * (�, �) � � �, � ∶ empty path � � � � � � (�, �) � � * (�, �) � �, � � �, �
x(k) = A • x(k -1) ⊕ B • u(k) (2) where A = A * 0 • A 1 and B = A * 0 • B 0 . See
Finally, for any integer φ such that 1 ≤ φ ≤ k, by doing φ substitutions in (2), we obtain

x(k) = A φ • x(k -φ) ⊕ φ-1 k =0 A k • B • u(k -k ) (3)
Remark 5 Graphical interpretations of A and B are illustrated in Fig. 1. Matrices' coefficients represent the maximal delay along paths that depend on the matrix. For instance, A(i, j) = (A * 0 • A 1 )(i, j), thus A(i, j) is the maximal delay of paths connecting t j to t i , primal (because of A 1 ) and then going through an arbitrary number of empty places (because of A * 0 ). It equals ε if no such path exists. A k contains delays of "longer" paths (i.e., with more tokens) as k increases. Hence, A k will tend to "grow" with k. Note that these paths are not elementary (i.e., they can pass through the same transition several times). Definition 6 (Cycle time [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]) The cycle time λ of a live TEG is the maximum of its cycle means over all circuits in the graph. If S is the set of transitions included in a circuit then λ computes

λ = j, tj ∈S τ jj m jj (4)
For the systems we control, we usually want to maximize the throughput (the inverse of the cycle time). Hence, a controller should delay the original system as few as possible while ensuring the constraints are meet.

Definition 7 (Optimal control) A control policy is said to be optimal if the controlled system respects all constraints and have the same cycle time as the autonomous system.

Model of cyclic processes

Many real life applications follow cyclic sequences of actions (e.g., a manufacturing assembly line). When we model these systems by means of a graph, the resulting graph is said to be strongly connected.

Definition 8 (Strongly connected graph) A graph is said to be strongly connected if for any pair of nodes i and j, there exists an oriented path from j to i.

Hence, a timed event graph is strongly connected if for any pair of internal transitions (t i , t j ), there exists

m ij ∈ N such that a path t j mij ,τij -→ t i exists, which yields x i (k) ≥ τ ij • x i (k -m ij ).
We mentioned in the introduction that a TEG could be made cyclic without modifying its original cycle time. The proof is similar to that of Th.6.55 from [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]. Assume we need to connect t i to t j in order to make a TEG strongly connected. To do so, one adds a new place p ji with m ji -tokens and τ ji -delay (with t i observable and t j controllable). Hence, as it already exists a path t j mij ,τij -→ t i , we are creating a new circuit of m ij + m ji tokens with τ ij +τ ji delay, so having a cycle mean of λ new = τij +τji mij +mji (see [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]). Therefore, we can choose τ ji = 0 and m ji as big as necessary for λ new to be smaller than the previous critical cycle means from the original graph. Hence, we cycle time is not modified. We illustrate this in Sect.4.

Temporal constraints

In a TEG, the holding time represents the minimal time a token has to sojourn in a place. If one wants to account for a maximal duration, a specific constraint has to be added. An approach to solve this modeling problem is presented in [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF]. The sojourn time of tokens in place p ij is minimized by the holding time τ ij and must not exceed a maximal delay, denoted τ max ij . Hence, a time interval [τ ij , τ max ij ] can be associated with the place p ij subject to a strict time constraint. This additional temporal constraint is expressed by the following Max-Plus inequality

x i (k) ≤ τ max ij • x j (k -m ij ) (5)
It is illustrated in the example from Sect.4 (see Fig. 2).

3 Output feedback control

Modeling hypothesis and control problem definition

In the remaining of this paper, we consider a single input single output (SISO) TEG containing N internal transitions, live, without circuit of null delay, and such that its internal subgraph is strongly connected. The output is set as y = x j for a given j ∈ [1.

.N ] and the dynamics of the TEG are described by (2) :

x(k) = A • x(k -1) ⊕ B • u(k) It yields A, B belong to R N ×N max and R N ×1 max respectively.
We are interested in modeling manufacturing systems.

Holding time represents length of processes and thus are non-negative. We set firing times equal to 0 and we consider the earliest firing rule (i.e., transitions fire as soon as possible). Firing epochs with negative index are set to ε (∀k < 0, x(k) = ε). We further assume there is no token in the places under time constraint (m ij = 0) and we will see in Sect.3.2 that we need an empty path from the control to the place under constraint (B(j) = ε) to ensure controllability. These modeling assumptions are not restrictive in general. For instance, in a production plant, it simply means that at initial state, there is no product in process. We control the system before than the production starts.

We consider that the firing sequence of the control u(k) can be arbitrary defined. Our control problem consists in deriving a realizable output feedback for u enforcing time constraints the type of (5) while preserving time and robustness performances.

A previous work already presented output feedback control derivation in similar settings [START_REF] Vinicius | An observer for tropical linear event-invariant dynamical systems[END_REF] but without taking care of time performances of the controlled system, which resulted in poor time performances. To avoid the same pitfall, we start by giving tight sufficient conditions for the control, presented in Sect.3.2. However, these conditions are non realizable and thus non suitable to solve our control problem. In addition, we show in Sect.3.3 that a realizable upper-bound can always be derived for any expression. Hence, combining these two results, we obtain our control theorem, presented in Sect.3.4. This approach results in better time performances and equivalent robustness properties. This will be illustrated and discussed in Sect.4.

Sufficient conditions for constraints enforcement

Prop.9 provides tight sufficient conditions for the satisfaction of a constraint of type [START_REF] Bonhomme | Scheduling and control of real-time systems based on a token player approach[END_REF] where m ij = 0 (see Sect.3.1 for motivations).

Proposition 9 If there exists an empty path t u 0,B(j)

-→ t j , then ensuring u(k) ≥ C = (-B(j)) • (-τ max ij ) • x i (k) (6)
is a sufficient condition for the control to enforce the constraint

x i (k) ≤ τ max ij • x j (k) for any k > 0.
Proof The time constraint to satisfy is expressed by 5) with m ij = 0). We can observe from Rem.5 that existence of an empty path t u 0,B(j) -→ t j is equivalent to B(j) = ε. Therefore, C is well-defined in R max (otherwise (-B(j)) equals +∞, which does not belong to R max ).

x i (k) ≤ τ max ij • x j (k) ((
The state equation ( 2) applied to state j gives ∀k > 0, x j (k) = A(j, :) -→ t i , and for any ν ∈ R, there exists q 0 ∈ N, ∀q ≥ q 0 , ∀p ∈ N * , ν • A p+mij +q×mii (i, :) ≥ A p (j, :) Proposition 12 For any (i, j) ∈ [1..N ] 2 such as there exist paths t j mij ,τij -→ t i and t i mji,τji -→ t j , there exists p 0 ∈ N * such that, 12.1 : ∀p ≥ p 0 , ∀q ∈ N, (A p+q×mii (i, :), A p (i, :)) similar, 12.2 : ∀p ≥ p 0 + m ji , (A p+mij (i, :), A p (j, :)) similar, 12.3 : ∀p ≥ p 0 + m ji , ∀q ∈ N, (A p+q×mii+mij (i, :), A p (j, :)) similar, where m ii = m ij + m ji . Lemma 13 For any (i, j) ∈ [1..N ] 2 such as there exist paths t j mij ,τij -→ t i and t i mji,τji -→ t j , and for any ν ∈ R,

• x(k -1) ⊕ B(j) • u(k) ⇒ x j (k) ≥ B(j) • u(k) Hence, if u(k) ≥ C, one deduces ⇒ x j (k) ≥ B(j) • (-B(j)) • (-τ max ij ) • x i (k) ⇒ x j (k) ≥ (-τ max ij ) • x i (k) ⇒ x i (k) ≤ τ max ij • x j (k)
∃ p ∈ N * , q ∈ N, δ ∈ R + , ∀k ≥ (p + q), ν • x i (k) ≤ δ • x j (k -q) ⊕ p+q-1 k =0 (µ k • u(k -k ))
where

µ k = ν • (A k • B)(i).
Hence, given any delay ν (even negative) and state x i , we can always derive a realizable upper-bound depending solely on past control events u(k) and past firings of one other transition events x j (k) associated with nonnegative delay δ. In the following section, we combine this result and the sufficient condition from Prop.9 to obtain our control theorem.

Output feedback control theorem

For a general TEG under assumptions of Sect.3.1, we now present our theorem for deriving a realizable output feedback control law enforcing any set of time constraints.

Theorem 14 Any constraint of from (5) such that there exists an empty path t u 0,B(j) -→ t j and B(i) ≤ B(j) • τ max ij can be enforced for any k ≥ (p + q) by setting u(k) as

u(k) ≥ δ • y(k -q) ⊕ p+q-1 k =1 µ + k • u(k -k ) (7)
which defines a realizable output feedback control where p, q, δ and (µ + k ) are returned by Algorithm 1 and m yu is the smallest token number of paths t u -→ t y .

Proof The time constraint to satisfy is expressed by

x i (k) ≤ τ max ij • x j (k) ((5) with m ij = 0).
Existence of an empty path t u 0,B(j) -→ t j is equivalent to B(j) = ε (refer to Rem.5). According to Prop.9, it is sufficient to set u(k

) ≥ C = (-B(j)) • (-τ max ij ) • x i (k) in order to satisfy the constraint.
Moreover, u(k) must respect the state equations, hence

x i (k) = A • x(k) ⊕ B(i) • u(k) ⇒ x i (k) ≥ (B(i) • (-B(j) • (-τ max ij )) • x i (k) ⇒ (B(i) • (-B(j) • (-τ max ij )) ≤ 0 ⇒ B(i) ≤ B(j) • τ max ij
Consider a "worst-case scenario" where only one transition is observable, say x l (i.e., y(k) = x l (k), the system has a single output). Assuming the internal subgraph of our TEG is strongly connected, we can apply Lemma 13 to expression C (existence of paths t l m il ,τ il -→ t i and

t i m li ,τ li -→ t l is assured by strong connectiveness), ∃ p ∈ N * , q ∈ N, δ ∈ R + , ∀ k ≥ (p + q), C = (-B(j)) • (-τ max ij ) • x i (k) ≤ C = δ • x l (k -q) ⊕ p+q-1 k =0 (µ k • u(k -k )) where µ k = (-B(j)) • (-τ max ij ) • (A k • B)(i) Furthermore, B(i) ≤ τ max ij • B(j) implies µ 0 = ε, and we have set y(k) = x l (k), therefore C rewrites C = δ • y(k -q) ⊕ p+q-1 k =1 (µ k • u(k -k )) Let set µ + k = µ k if µ k > 0, ε otherwise. Thus µ + k ≥ µ k .
Sequence of firing epochs are non-decreasing, so for any

µ ≤ 0, u(k) ≥ µ • u(k -k )
u(k) ≥ C + ⇔ u(k) ≥ C ⇒ u(k) ≥ C
which is sufficient to prove that u(k) enforces the constraint according to Prop.9.

2

Remark 15 Implementing this control creates new cycles in the controlled graph. In particular, we add a path t y q, δ -→ t u . Hence if we call m yu the smallest token number of paths t u -→ t y then according to Thm.3 we need to satisfy: m yu + q ≥ 1 (or q ≥ 1 -m yu ) for the controlled system to remain live. This is implemented in the initialization of q (see line 5 in Alg.1).

Remark 16

In feedback control of Max-Plus models, conditions for the control are expressed as u(k) ≥ C where C is a given expression (e.g., F • x(k -1) in usual state feedback, or given by Prop.9 in our case). If we use the observer from [START_REF] Hardouin | Observer design for (max,+) linear systems[END_REF] on C, we obtain C ≤ C. Hence, setting u(k) ≥ C does not guarantee u(k) ≥ C and thus is not a proper solution for our control problem.

About sufficient conditions, extensions and modeling assumptions

We present here sufficient conditions for solving our control problem. We mentioned in the introduction (and illustrate in Sect.4) that a model can be made strongly connected altering its cycle time. Thus strong connectiveness is not a strong limitation. The two other conditions (B(i) ≤ B(j) • τ max ij and empty path from u to t j ) are not necessary in general (counter-examples can be found), but there are for our approach. In other words, if we set u(k) ≥ C according to Prop.9 to enforce the constraint, no realizable control satisfying the state equation can be found if these conditions do not hold. However, these conditions depend on the system architecture (strong connectiveness and B(i) ≤ B(j) • τ max ij ) or on initial conditions (empty path from u to t j ), which are all easy-to-check a priori on the uncontrolled model. This is a real improvement from a design perspective compared to previous work [START_REF] Vinicius | An observer for tropical linear event-invariant dynamical systems[END_REF][START_REF] Hardouin | Observer design for (max,+) linear systems[END_REF][START_REF] Andrey | Some results on the feedback control of max-plus linear systems under state constrains[END_REF], in which conditions have no such clear and simple interpretation on the system model.

Our control approach easily handles multiple constraints in the same fashion as in [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF] and [START_REF] Kim | Feedback control of cluster tools for regulating wafer delays[END_REF]. For each constraint, one derives a suitable control u s (k). All constraints will be enforced by u(k) = u s (k). This is further discussed in Sect.4. These results can also be extended to models with tokens in the constrained places like in [START_REF] Kim | Feedback control of cluster tools for regulating wafer delays[END_REF].

Finally, one should note that the SISO assumption is not a limitation. As previously mentioned in [START_REF] Kim | Feedback control of cluster tools for regulating wafer delays[END_REF], we have sufficient conditions relating one control transition to one constraint (B(i) ≤ B(j) • τ max ij ). In other words, if one control cannot enforce a constraint by itself, no combination of controls will do. Multiple controls can however be useful to control multiple constraints if one control does not satisfy sufficient conditions for all constraints simultaneously. Our approach is perfectly suitable to this setting. From this prospect, our approach is more general than [START_REF] Andrey | Some results on the feedback control of max-plus linear systems under state constrains[END_REF] and [START_REF] Vinicius | An observer for tropical linear event-invariant dynamical systems[END_REF] which assume full controllability over the system. Besides, a single output is a "worst-case scenario" for a feedback controller. We have information on one of the system state only.

Algorithmic procedure

Algorithm 1 computes the coefficients for the control defined by Th.14. It takes as input the system dynamics (matrices A and B), the definition of the system output (y), the upstream and downstream transitions of the constrained place (i and j), the constraint value (τ max ij ), and the smallest token number of paths t u -→ t y (m yu ). It returns all necessary coefficients to define a realizable output feedback control (p, q, δ and (µ + k )) given that sufficient conditions are satisfied. Th.14 guarantees that the procedure terminates.

Illustrative example -Traffic lights

Model and control derivation

We illustrate our approach using a simple example from the literature [START_REF] Garcia | Traffic light coordination of urban corridors using max-plus algebra[END_REF][START_REF] Vinicius | An observer for tropical linear event-invariant dynamical systems[END_REF][START_REF] Andrey | Some results on the feedback control of max-plus linear systems under state constrains[END_REF]. It describes a road section with two traffic lights which is illustrated on Fig. 2 (white area). Transitions {x i } i∈{1,2} indicate events of the semaphore i turning on green light and {x i } i∈{3,4} events of turning on red light. Minimal timing of each phase is indicated by the place. We assume that we can increase the red time of the first light in order to respect our specifications and that the only observable event for the controller is the second light turning green. Therefore, we have one input transition t u connected to q ← max( 0, 1 -m yu ) while majoration(A, i, y, ν, p, q) is False do q ← q + 1 end while while similarity(A, i, y, p, q) is False do 10:

p ← p + 1 end while δ ← max r∈[1..N ] A p (y,r) =ε (ν • A p+q (i, r) -A p (y, r)) for k ∈ [1..p + q -1] do µ k ← (A k • B)(i) -B(j) -τ max ij 15:
µ + k ← max (µ k , 0) end for return (p, q, δ, (µ + k )) end procedure 20: function majoration(A, i, y, ν, p, q) if ν • A p+q (i, :) ≥ A p (y, :)) then return True else return False end if end function 25: function similarity(A, i, y, p, q) if (A p+q (i, :), A p (y, :))similar then return True else return False end if end function t 1 and one output transition t y connected from t 2 . For traffic regulation purposes, it is relevant to cap the time laps between the two lights turning green (C1) and the time duration of green lights (C2 and C3). Hence, we have 3 constraints of type [START_REF] Bonhomme | Scheduling and control of real-time systems based on a token player approach[END_REF], each of 15 time units, added on places p 21 , p 31 , and p 42 . However, it is clear here that C2 and C3 will always be satisfied (without external disturbances). Indeed, there is nothing keeping t 3 or t 4 to fire once a token has completed its sojourn time in the upstream place. Hence we will focus on C1.

The internal subgraph of this model is not strongly connected, hence results from Sect.3 cannot be applied directly. However, as discussed in Sect.2.3, we can turn our model into strongly connected form without modifying the original cycle time. There are two circuits in the original model (one for each light) with respective cycle means λ 1 = 9 and λ 2 = 12 (use relation ( 4)). One can make this model strongly connected by linking t 2 to t 1 through a place p 12 , with delay τ 12 and m 12 tokens, which creates a new circuit of cycle mean

λ new = τ21 • τ12 m21 • m12 = 10 • τ12 0 • m12 .
Hence, it suffices to set τ 12 = 0 and m 21 = 1 to get λ new = 10 ≤ max(λ 1 , λ 2 ). The resulting addition to the nominal model is shown in with ε is replaced by a . for the sake of readability. More detailed examples of system dynamics derivations can be found in [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF], [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF] or [START_REF] Kim | Feedback control of cluster tools for regulating wafer delays[END_REF]. ). Hence, we can derive a realizable output feedback control using Alg.1, which returns u

Conditions of

(k) ≥ 9 • y(k -2) ⊕ 7 • u(k -1) ⊕ 19 • u(k -2)
This feedback control is shown in the grey area on Fig. 2.

Remark 17 Th.14 can also be applied to C2 and C3. It results in strictly less restrictive conditions for the control law. This is not surprising as we already mentioned these constraints are nominally satisfied. If it were not the case, it would suffice to take the sum of the control obtained for each constraint, as explained at the end of Sect.3.4.

Discussions on control optimality and performance

The cycle time of the autonomous model is λ = max(λ 1 , λ 2 ) = 12 time units. Using relation (4), one quickly sees that our feedback control creates new circuits with cycle mean of (10 • 9)/2, 7/1 and 19/2 respectively. Therefore, our the control does not increase the system cycle time. According to Th.14 and Def.7, this is an optimal control for this problem.

Remark 18 Note that it is not always the case. The cycle time of the controlled system might increase depending on the system architecture, the constraints values, and the output definition. Moreover, our output feedback controller eventually delays the system more than a state feedback controller would. This is not surprising, as we have some extra restrictions on the information available. Performing feedback control is usually interesting because of its robustness against disturbances. However, doing output feedback (instead of state feedback) weaken the robustness of the controlled system, so does preserving the cycle time. This is illustrated on Fig. 3. We implemented two arbitrary disturbances on the controlled system from different approaches with initial conditions x(0) = [0, 0, 0, 0] T : k = 9 Delay of 12 and 20 time units on x 2 and x 4 , k = 14 Delay of 8 and 30 time units on x 1 and x 2 .

We plot the error e(k) which is the difference between the actual firing epochs of t 2 and the upper-bound of constraint C1 (i.e., e(k) = max(x 2 (k) -(x 1 (k) + 15), 0). In other words, it is a quantification of the violation of C1. The legend indicates the cycle time of the controlled system for each approach.

State feedback from [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF] is of form u(k) = F • x(k -1) and guarantees to reject any disturbance in one step but increases the cycle time. To preserve λ new = 12, [START_REF] Andrey | Some results on the feedback control of max-plus linear systems under state constrains[END_REF] implements a feedback u(k) = F •x(k-2), but it can then take up to two steps to reject a disturbance, as we can see on that example. The output feedback approach from [START_REF] Vinicius | An observer for tropical linear event-invariant dynamical systems[END_REF] does not give explicit guarantees on robustness nor on the cycle time preservation and loses on both aspects here. Finally, Th.14 guarantees that our output feedback control rejects any disturbance in (p + q) time steps at most (here Alg.1 returns (p + q) = 3), although it might be faster (2 and 1 time steps for the first and second disturbance respectively). It also manages to preserve the cycle time, even though that might be always the case (see Rem.18) and does not require full controllability over the system (only t 1 needs to be controlled).

Conclusions

This paper presents an output feedback control approach handling temporal constraints on partially observable TEG. We propose an efficient control approach showing good time and robustness performances, under conditions that are comparably restrictive to previous works but are much more explicit and can be check easily on the system model. However, our control is not minimally restrictive. That is, the control law returned by Alg.1 might increase the system cycle time while it is sometimes possible to derive another output feedback control that does not. A systematic approach for the derivation of such minimally restrictive control would be a relevant perspective. It is also believed that robustness guarantees from Th.14 can be tighten to disturbance rejection in at most (q) steps. This implies η i q+1 ≤ η i q , hence (η i q ) q∈N is decreasing. Moreover, (η i q ) q∈N is obviously minimized by 0, so (η i q ) q∈N converges. Since it takes discrete values, the sequence reaches its limit at a given step l ≥ 0. Thus ∃ l ∈ N, ∀q ∈ N, η i l+q = η i l Combined with (A.2), this yields [ A (l+q)×mii (i, r) = ε ⇔ A l×mii (i, r) = ε ] Finally, one can define p 0 ← l × m ii , and rewrites ∃ p 0 ∈ N * , ∀ q ∈ N, [ A p0+q×mii (i, :) = ε ⇔ A p0 (i, :) = ε ] (A.3)

Finally, taking Prop.2 into account, (A.3) holds true for any p ≥ p 0 , which concludes the proof of 12.1. 2

Similarly, applying Prop.10 to t i mij ,τij -→ t j and t j mji,τji -→ t i , one obtains ∀p ∈ N * , A p+mij (i, :) ≥ A p (j, :)

A p+mji (j, :) ≥ A p (i, :) ⇒ ∀p ∈ N * , A p+mij +mji (i, :) ≥ A p+mji (j, :) ≥ A p (i, :) ⇒ ∀p ∈ N * , A p+mii (i, :) ≥ A p+mji (j, :) ≥ A p (i, :) One can choose p ← p 0 = l × m ii and rewrites A (l+1)×mii (i, :)

x ≥ A l×mii+mji (j, :) y ≥ A l×mii (i, :) Thus, for any r ∈ [1..N ],

x ⇒ A (l+1)×mii (i, r) = ε ⇒ A l×mii+mji (j, r) = ε y ⇒        A l×mii+mji (j, r) = ε ⇒ A l×mii (i, r) = ε ⇒ A p0 (i, r) = ε [(A.3) with q = 1] ⇒ A mii+p0 (i, r) = ε [p 0 = l × m ii ] ⇒ A (l+1)×mii (i, r) = ε       
One can combine these two implications to get the following equivalence

[ A (l+1)×mii (i, :) = ε ⇔ A l×mii+mji (j, :) = ε ] ⇔ [ A p0+mij +mji (i, :) = ε ⇔ A p0+mji (j, :) = ε ] One can set p 0 ← p 0 + m ji and rewrites [ A p0+mij (i, :) = ε ⇔ A p0 (j, :) = ε ] (A.4)

Figure 1 .

 1 Figure 1. Graph interpretation of A and B matrices

Algorithm 1 deriveControlCoef

 1 Require: A, B, y, i, j, τ max ij , m yu procedure ControlDefinition ν ← (-B(j)) • (-τ max ij )

Figure 2 .

 2 Figure 2. Model of the traffic lights -On the nominal model (white area) we show in grey the TEC section added to obtain a strongly connected graph; our output feedback controller is represented within the grey area. grey on Fig.2, in the white area. The system dynamics are then expressed by x(k) = A • x(k -1) ⊕ B • u(k) and y(k) = x 2 (k)

  Th.14 are satisfied for constraint C1 (i.e., B(1) = 0 = ε and B(2) = 10 ≤ 15 = B(1) • τ max 21

Figure 3 .

 3 Figure 3. Quantified violation of the C1 constraint for the different state (SFC) and output feedback controllers (OFC)

  )

	𝑡 𝑗 𝑨 𝒊, 𝒋 ∶	𝑡 𝑘	empty path	𝑡 𝑖	𝑡 𝑢 𝑠 𝑩 𝒊, 𝒔 ∶	𝑡 𝑘	empty path	𝑡 𝑖
	𝑨 𝟏 (𝒌, 𝒋)	𝑨 𝟎	* (𝒊, 𝒌)		𝑩 𝟎 (𝒌, 𝒔)	𝑨 𝟎	* (𝒊, 𝒌)
					empty path

  by definition. So if one defines C + as C with µ + k replacing µ k , it is equivalent for u(k) to be bigger than C + or C . Moreover, C + is a realizable output feedback expression and

A Proofs of Section 3.3 properties

Proof [Proof of Prop.10] For any p ∈ N * and r ∈ [1..N ], we have either A p (j, r) = τ jr ( = ε) or = ε. In the latter case, the result trivial holds. In the former case, taking Rem.5 into account, there exists a primal path t r p,τjr -→ t j . If there exists a path t j mij ,τij -→ t i , then there also exists a path t r p,τjr -→ t j mij ,τij -→ t i , which reduces to t r p•mij ,τij •τjr -→ t i . Hence, there exists a (p + m ij )-primal path (not necessarily unique) with delay τ ij • τ jr . Considering again Rem.5, it follows that for any p ∈ N * ,

This holds true for any r ∈ [1..N ], hence the property is true for all and A p+mij (i, :) ≥ τ ij • A p (j, :).

2

Proof [Proof of Prop.11] Prop.10 can be applied to any path. In particular if there exists a circuit t i mii,τii -→ t i , then for any p ∈ N * , A p+mii (i, :) ≥ τ ii • A p (i, :). As this is true for any p ∈ N * , one can recursively set p ← p + m ii and easily show that for any q ∈ N and any p ∈ N * , A p+q×mii (i, :) ≥ (q × τ ii ). • A p (i, :) We can further take p ← p + m ij , which gives A p+mij +q×mii (i, :) ≥ (q × τ ii ) • A p+mij (i, :) Similarly, we can apply Prop.10 to the path t j mij ,τij

Combining these two results, we obtain that for any p ∈ N * and q ∈ N,

We justified in Sect.3.1 that we do not consider circuits with null delay. Hence, τ ii > 0 and therefore for any ν ∈ R, there exists q 0 ∈ N such that ν+(q 0 ×τ ii +τ ij ) ≥ 0. Using (A.1), it follows that for any q ≥ q 0 , ν • A p+mij +q×mii (i, :) ≥ (ν + q × τ ii + τ ij ) • A p (j, :) Hence, for any ν ∈ R, q ≥ q 0 and p ∈ N * , ν • A p+mij +q×mii (i, :) ≥ A p (j, :) which concludes the proof. 2

Proof [Proof of Prop.12.1 to Prop.12.3] If there exists t j mij ,τij -→ t i and t i mji,τji -→ t j then there exists at least one circuit t i mii,τii -→ t i where m ii = m ij + m ji . For any of such circuit, let (η i q ) q∈N be the sequence counting the number of ε-element in A q×mii (i, :).

We can apply Prop.10 to t i mii,τii -→ t i , which yields for any p ∈ N * that A p+mii (i, :) ≥ τ ii • A p (i, :). Since delays of circuits are non-negative, it further implies A p+mii (i, :) ≥ A p (i, :). One can set p ← q × m ii and obtain A (q+1)×mii (i, :) ≥ A q×mii (i, :). From this last relation, one deduces the following:

Taking Prop.2 into account, (A.4) holds true for any p ≥ p 0 = p 0 + m ji , which concludes the proof of 12.2. 2

Finally, 12.1 holds for all p ≥ p 0 , so it holds in particular for all p ≥ p 0 . Therefore, for all q ∈ N and p ≥ p 0 , (A p+q×mii (i, :), A p (i, :)) similar,

From (A.5), the right-hand side is contained in the lefthand side and there are both similar according to (A.6). These two terms are then comparable. The remaining of the proof consists in deriving an upper-bound for the left-hand side using the right-hand side.

Let set p ← p 0 and q ← m ij + q 0 × m ii for convenience and define,

Note that we need to be careful here in the definition of δ because (-ε) = +∞ does not belong to R max . From (A.5), we have δ ≥ 0 and it follows that ∀r ∈ [1.

.N ], A p (j, r) = ε, ν • A p+q (i, r) ≤ δ • A p (j, r) Taking (A.6) into account, this holds for any r ∈ [1..N ], hence we deduce, ν • A p+q (i, :) ≤ δ • A p (j, :) (A.7)

Furthermore, the state equation of form (3) with φ = p gives, for any k ≥ p,

By neglecting the terms from the sum and shifting the index k to k -q, one deduces the following inequalities ∀ k ≥ (p + q), x j (k -q) ≥ A p (j, :)

Taking into account (A.7), one deduces ν

Finally, using again the state equation of form (3) but with φ = p + q, we obtain that for any ν ∈ R and any k ≥ (p + q), ν

Using relation (A.8), one obtains

One can then set µ k ← ν • (A k • B)(i) for all k ∈ [0..p + q -1] and conclude the proof of the lemma. 2


Romain Jacob
email: rjacob@ens-cachan.fr

Saïd Amari

Observable Feedback Control of discrete processes under time constraint: Application to Cluster Tools

Keywords: Output feedback control, Time event graph, Manufacturing control systems, Optimal Control, Dynamic production control, Semiconductor manufacture, Petri nets, Discrete event simulation

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

Introduction

This paper presents a control approach for temporal constraints which aims to be workable even though the controller has partial information over the occurrences of the system's events. The objective is to minimize the number of sensors needed to satisfy a given set of specifications, and thus cut down the costs. In the general case, our approach cannot be used if the system's model is not cyclic. However, a manufacturing plant model can easily be "made" cyclic by considering a maximal capacity for instance. We also need the system to be conflict-free, which is a much harder limitation to overcome. Further relaxation of this limitation is to be considered. However, giving that the system model satisfies those hypothesis, our approach provides a formal control strategy ensuring any set of temporal constraints (such as not burning parts in an oven) will be satisfied while preserving the throughput of the plant as much as possible.

It is common than a control problem involves some temporal constraints to satisfy. For example, consider a work-piece which processing includes chemical reactions. The stripping time of a piece by immersion in an acid bath is precise, or at least defined by a time interval (where it requires a minimum soak time but must not exceed a maximum time). Such temporal restrictions can take diverse forms (e.g., deadline, time intervals, validity duration, . . . ), which are encountered in a wide range of applications (e.g., semiconductor industry [START_REF] Kim | Feedback Control of Cluster Tools for Regulating Wafer Delays[END_REF], automotive industry [START_REF] Martinez | Sizing of an industrial plant under tight time constraints using two complementary approaches:(max,+) algebra and computer simulation[END_REF], thermal or chemical treatments [START_REF] Kim | Schedule stabilization and robust timing control for time-constrained cluster tools[END_REF], rail transport [START_REF] Wang | Optimal trajectory planning for trains-A pseudospectral method and a mixed integer linear programming approach[END_REF], networked control systems [START_REF] Diouri | Accommodation of delays for networked control systems using classification of service[END_REF]).

Even complex industrial processes are efficiently modeled by Discrete-Event Systems (DES). Especially, Petri nets have been extensively used, as they are very efficient to capture the sequential behavior of complex dynamic systems. However, explicit consideration of time (synchronization, delay, . . . ) is still a challenging topic. A Timed Event Graph (TEG) is a specific Timed Petri net [START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF]) which is useful for modeling timed behavior. It captures the non-linearities of timed dynamics and expresses them into a linear equations system over the Max-Plus algebra [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF].

Combined use of TEG and Max-Plus is a well-known approach in the literature, with applications to different kinds of time-related issues. Among others, it includes scheduling for large scale systems [START_REF] Bonhomme | Scheduling and control of real-time systems based on a token player approach[END_REF][START_REF] Goverde | Railway timetable stability analysis using max-plus system theory[END_REF]) and just-in-time control, which aims to delay the system's input as much as possible without increasing the overall cycle time [START_REF] Houssin | Just in time control of constrained (max,+)-linear systems[END_REF][START_REF] Lhommeau | A non-linear set-membership approach for the control of Discrete Event Systems[END_REF]. The other way around, other works focus on satisfying time constraints with minimum delay. The control approach can be similar to supervision [START_REF] Martinez | Sizing of an industrial plant under tight time constraints using two complementary approaches:(max,+) algebra and computer simulation[END_REF][START_REF] Houssin | Control of (max,+)-linear systems minimizing delays[END_REF] or performed by state-feedback, as for linear continuous systems [START_REF] Maia | Some results on the feedback control of max-plus linear systems under state constrains[END_REF][START_REF] Maia | On the control of max-plus linear system subject to state restriction[END_REF][START_REF] Katz | Max-plus (A, B)-invariant spaces and control of timed discrete-event systems[END_REF]. All these approaches aim to design a controller which guarantees that the system evolves without violating any of the time constraints, usually imposed on the system's states. Another method for the synthesis of such feedback control law was presented in [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF]. It is defined as a Max-Plus linear inequality, causal, which corresponds to a state feedback from the system. Kim andLee (2012, 2015) extend [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF] by relaxing some modeling hypothesis, for the specific setting of cluster tools. Even though they do address the control of temporal constraints, previous works suffer from a strong limitation. They consider the system to control as fully observable, which is never the case in practice. This paper generalizes [START_REF] Kim | Feedback Control of Cluster Tools for Regulating Wafer Delays[END_REF] by relaxing the observability hypothesis.

The main contribution of this paper is the demonstration that for any strongly connected system model, one can derive a valid controller expressed under an observable feedback form (i.e., which depends solely on past control and output events) and satisfies any set of time constraints. Furthermore, we apply our method to the control of a cluster tool, a wellknown industrial case of study from the literature [START_REF] Wu | A closed-form solution for schedulability and optimal scheduling of dual-arm cluster tools with wafer residency time constraint based on steady schedule analysis[END_REF]Kim andLee 2012, 2015) and compare our control policy with previous results.

Section 2 presents useful background on Max-Plus, TEG, and the modeling of temporal constraints. Section 3 summaries our modeling hypothesis and motivations. In Section 4 we introduce some intermediate results before addressing the control derivation in Section 5. The practical application of our approach is presented in Section 6, including comparison with previous results and performances discussions. Finally, some conclusions and perspectives are drawn in Section 7.

Preliminaries

Max-Plus Algebra

A monoid is a set, say D, endowed with an internal law, noted ⊕, which is associative and has a neutral element, denoted ε. A semiring is a commutative monoid endowed with a second internal law, denoted ⊗, which is associative, distributive with respect to the first law ⊕, has a neutral element, denoted e, and admits ε as absorbing element, i.e., ∀a ∈ D, a ⊗ ε = ε ⊗ a = ε. A dioid is a semiring with an idempotent internal law, i.e., ∀a ∈ D, a ⊕ a = a. The dioid is said to be commutative if the second law ⊗ is commutative. Max-Plus algebra is defined as (R ∪ {-∞}, max, +). This semiring, denoted R max , is a commutative dioid, the law ⊕ is the operator max with neutral element ε = -∞, and the second law ⊗ is the usual addition, with neutral element e = 0. We use the following notations • M (r, :) refers to the r th row of matrix M ,

x(r) refers to the r th element of vector x,

• (+, ×) are the usual addition and multiplication,

• (⊕, ⊗) are the operator max and the usual addition,

• ⊗ is abbreviated by

• (dot), • M p is the p th power of matrix M in R max (i.e., M 2 = M • M ). For (p, q) ∈ N 2 , (V, W ) ∈ (R p×q max ) 2 , V ⊕ W denotes the matrix with components (V ⊕ W )(i, j) = max(V (i, j), W (i, j)).
Given n ∈ N, and matrices (A, B) ∈ (R p×n max × R n×q max ), A ⊗ B (or abbreviated A • B) represents the result of matrices multiplication, defined by the formula

(A ⊗ B)(i, j) = n k=1 (A(i, k) ⊗ B(k, j)) = max k∈[1..n] (A(i, k) + B(k, j))
The Kleene star of a square matrix M ∈ R n×n max , written M * , is defined as

M * = i∈N M i
where M 0 equals the unit matrix, with entries equal to e on the diagonal, and ε elsewhere.

Definition 1 (Similar vectors). Two vectors (u, v) ∈ (R n max ) 2 are similar if they share the same zero-elements regarding to the law ⊗, i.e.,

∀r ∈ [1..n], ( u(r) = ε ⇔ v(r) = ε )
Remark 1. In some references, similar vectors (or matrices) are said to have same support [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF].

Proposition 1. Similarity is distributive over the law ⊗. Given three vectors (u, v, w)

∈ (R n max ) 3 , (u, v) similar ⇒ (u • w, v • w) similar Proof. u • w = ε ⇔ n r=1 u(r) • w(r) = ε ⇔ [ ∀r ∈ [1..n], u(r) = ε ⇒ w(r) = ε ] Since (u, v) are similar, ⇔ [ ∀r ∈ [1..n], v(r) = ε ⇒ w(r) = ε ] ⇔ v • w = ε 2.

TEG and Linear Max-Plus Models

An event graph is an ordinary Petri net where each place has exactly one upstream and one downstream transition. It is also referred to as a decision free Petri net, as one token never enable more than one transition at a time. A timed event graph (TEG) is an event graph with extra delays associated to places (holding times) or transitions (firing times).

We distinguish transitions having at least one upstream place (t 1 . . . t n ) and those having none (t u1 . . . t uq ) also called source transitions. The former are referred to as standard transitions, while the latter are said to be input transitions, which can be fired following any arbitrary non-decreasing sequence of epochs.

We further introduce the following notations and definitions

• p ij denotes the place linking t j to t i when it exists, • A path is an oriented alternating sequence of transitions and places successively connected by an arc, • The token number of a path is the sum of tokens in all places along the path,

• The delay of a path is the sum of holding and firing time of all places and transitions along the path, • Given two transitions t i and t j and a token number m ij , several m ij -token paths connecting t j to t i exist in general.

t j mij ,τij
-→ t i denotes the maximal of such paths, i.e., the m ij -token path with maximum delay τ ij , • A primal path contains exactly one token in the first place along the path, • An empty path contains no token, • A circuit around t i is a path connecting t i to itself, • An elementary path does not contain any transition more than once, • An event is the firing of a transition. A control (resp. output) event refers to the firing of one of the system's input (resp. output) transitions, • An event is said observable if the occurrence of the associated firing can be detected and used by the controller. Control events are considered observable, • A transition which firing is observable is called an output transition. Thus output events are observable by definition.

A Petri net is said to be live for an initial marking if all transitions can always be enabled by a future marking [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]. A Petri net not live is said to be deadlocked. An event graph containing only standard transitions is said to be autonomous. A nonautonomous event graph is said to be live if its autonomous subgraph (i.e., pruned of input transitions) is live.

Theorem 1 (from [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]). An autonomous event graph is live if and only if every circuit contains at least one token with respect to the initial marking.

Definition 2 (Valid control). If a live autonomous system remains live after the implementation of the control law, the control is said to be valid. → A valid control does not deadlocked a system. Definition 3 (Observable feedback control). A control law is said to be observable if it depends on controls' and outputs' events, associated to non-negative delays.

The state variable x i (k) of a TEG is the epoch when standard transition t i fires for the k th time. We call x(k) = (x i (k)) the system's state vector. The input vector u(k) is defined likewise. The dynamic behavior of a TEG in Max-Plus is described by the evolution equation

x(k) = m≥0 (A m • x(k -m) ⊕ B m • u(k -m)) (1)
where A m (i, j) = τ if p ij exists, contains m tokens, and has holding time τ ε otherwise.

B m is defined likewise for places between input and standard transitions. Example 1. Consider the TEG in Fig. 1(a). The firing epochs of t 1 are defined by the following equation

It yields (A m , B m ) ∈ R n×n max × R n×q max . � � 2 � � 1 5 � 1 � � 3 � 2 (a) Original model � � 2 � � 1 5 � 1 � � 3 � 2 � � 3 � � 4 0 � 5 (b) Extended model
x 1 (k) = max(2 + u 1 (k -1), 5 + u 2 (k -1) , 3 + x 2 (k -2)) which rewrites into linear form in Max-Plus x 1 (k) = 2 • u 1 (k -1) ⊕ 5 • u 2 (k -1) ⊕ 3 • x 2 (k -2) Setting x(k) = [x 1 (k), x 2 (k)] and u(k) = [u 1 (k), u 2 (k)] ,
the full TEG behavior is expressed by

x(k) = . . 2 . x(k) ⊕ . 3 . . x(k -2) ⊕ 2 5 . . u(k -1) A 0 A 2 B 1
We will further assume that places connecting input to standard transitions contain no token. It yields B k = ε for all k > 0. This is no restriction as one can add an extra place between such transitions, such that the first place is empty and the second contains tokens. Moreover, as for regular linear systems, the initial recurrence (1) can be transformed into an equivalent recurrence of order 1 by extending the state vector. This consists in expanding all places with marking m > 1 into m places with marking equal to 1. Hence, for each of such places, (m -1) intermediate transitions are added and the resulting extended state vector

x(k) belongs to R N max with N = n + (m -1). Fig. 1 is a simple example of both model extensions. It follows, x(k) = Â0 • x(k) ⊕ Â1 • x(k -1) ⊕ B0 • u(k)
The (.) notation will be further omitted for the sake of readability.

Furthermore, it is shown that if the event graph is live, A * 0 reduces to n i=1 A i 0 [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]. Hence one can derive the standard state-space equation,

x(k) = A • x(k -1) ⊕ B • u(k) (2)
where [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF] for details. Finally, for any integer φ such that 1 ≤ φ ≤ k, by doing φ substitutions in (2), we obtain

A = A * 0 • A 1 and B = A * 0 • B 0 . See
x(k) = A φ • x(k -φ) ⊕ φ-1 k =0 A k • B • u(k -k ) (3)
Remark 2. Graph interpretation of A and B is illustrated in Fig. 2. Matrices' coefficients represent the maximal delay along some paths, depending on the matrix under consideration. For instance,

A(i, j) = (A * 0 • A 1 )(i, j), thus A(i, j)
is the maximal delay of paths connecting t j to t i , primal (because of A 1 ) and then going through an arbitrary number of empty places (from A * 0 ). It equals ε if no such path exists.

A k contains delays of "longer" paths (i.e., with more tokens) as k increases. Hence, A k will tend to "grow" with k. Note that these paths do not need to be elementary (i.e., they can pass through the same transition several times).

� � � � � � � � (�, �) � � * (�, �) � �, � ∶ empty path � � � � � � � � � (�, �) � � * (�, �) � ⋅ � �, � ∶ empty path � � � � � � (�, �) � � * (�, �) empty path � � � � � � � � � (�, �) � � * (�, �) � �, � ∶ empty path � � � � � � � � (�, �) � � * (�, �) � � �, � ∶ empty path � � � � � � (�, �) � � * (�, �) � �, � � �, �
Example 2. Back to Example 1, consider the extended TEG represented in Fig. 1(b). Its dynamics are expressed by the following standard form

x(k) =       . . 2 5 3 . . 4 7 5 . . . . . . . . . . . 0 . . .       x(k -1) ⊕       . . . . 0 . . 0 . .       u(k) A B
Remark 3. One should remember that the state variables (x i ) represent firings of transitions.

Hence, when we refer to state-feedback, the state is the set of last firing epochs of the system's transitions. This differs from the notion of state in the Petri net formalism, which is usually the marking of the net.

Model of cyclic processes

In many real life applications, automated systems we aim to control are cyclic. When we model these systems by means of a graph, the resulting graph is said to be strongly connected.

Definition 4 (Strongly connected graph). A graph is said to be strongly connected if for any pair of nodes i and j, there exists an oriented path from i to j.

Proposition 2. If an event graph is strongly connected, then, for any pair of transitions (t i , t j ), there exists m ij ∈ N such that a path t j mij,τij -→ t i exists.

Proof. Existence of paths between t j and t i is direct from Def. 4. Then, for any possible token number m ij , there exists at least one with maximal delay τ ij .

Remark 4. If the event graph is live, the token number of every circuit is at least 1 (Thm. 1). Thus, adding strong connectivity, one can note that for any k ∈ N and any pair of transitions, there always exists a (possibly non-elementary) k -token path, k ≥ k, connecting these two transitions.

Definition 5 (Cycle time [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]). Given a live TEG under standard form (2), its cycle time λ is the maximal cycle mean of the state matrix A. It computes where (.) 1/j represents in Max-Plus the division by j in the conventional sense.

λ = n j=1 trace(A j ) 1/j (4) � � � � [� �� , � ] �� ��� (a) � � ′ � � [� �� , � ] �� ��� � � � (b)

Temporal constraints

Strict time constraints are frequent in industry. It is crucial to model them efficiently to be able to ensure they are satisfied during the process. In a TEG, holding time represents the minimal time a token has to sojourn in a place. If one wants to account for a maximal duration, another constraint has to be added. An approach to solve this modeling problem was suggested in [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF]. The sojourn time of tokens in place p ij is minimized by the holding time τ ij . In addition, it must not exceed another time delay, denoted τ max ij . Hence, a time interval [τ ij , τ max ij ] can be associated with the place p ij subject to a strict time constraint. This additional temporal constraint is expressed by the following Max-Plus inequality

x i (k) ≤ τ max ij • x j (k -m ij ) (5)
This is illustrated in Fig. 3.

Model description and motivations

In the remaining of this paper, we consider a nonautonomous TEG with a single input transition t u and N standard transitions, live, with no 0-delay circuit, and such that its autonomous subgraph is strongly connected. The dynamics of this TEG are described by the standard form equation (2) :

x(k) = A • x(k -1) ⊕ B • u(k). It yields A and B belong to R N ×N
max and R N ×1 max respectively. We are interested in modeling manufacturing systems, in which holding times represent length of processes and thus are non-negative. We set firing times of transitions to 0 and we consider the following evolution rules for our TEG (a) transitions fire as soon as they are enabled, (b) a token starts enabling the downstream transition as soon as it has completed its place's holding time, (c) we consider the following (compatible -refer to [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]) initial conditions

x(k) = e if k = 0 ε if k < 0
Assuming firing epochs of the input sequence u(k) can be arbitrary defined, we aim to derive such a sequence (later referred to as the control) valid (i.e., which does not deadlocked the system), under observable feedback form (i.e., expressed by means of non-negative delays and past observable events), such that preset temporal constraints (the kind of (5)) are satisfied.

Intermediate results

This Section introduces Lemma 1, which justifies that, under Section 3's assumptions, the firing epochs of any standard transition can be overestimated using solely the input sequence and previous firings of any other standard transition. We start with three intermediate propositions, which are prerequisites for the demonstration of the Lemma. All proofs are provided in Appendix A.

Proposition 3. For any (i, j) ∈ [1..N ] 2 , if there exists a path t j mij,τij

-→ t i , ∀p ∈ N * , A p+mij (i, :) ≥ τ ij • A p (j, :)
Proposition 4. For any (i, j) ∈ [1..N ] 2 such as there exist a path t j mij,τij -→ t i and a circuit t i mii,τii -→ t i , and for any ν ∈ R,

∃q 0 ∈ N, ∀q ≥ q 0 , ∀p ∈ N * , ν • A p+mij+q×mii (i, :) ≥ A p (j, :)
Proposition 5. For any (i, j) ∈ [1..N ] 2 such as there exist paths t j mij,τij -→ t i and t i mji,τji -→ t j , there exists p 0 ∈ N such that, 5.1 : ∀p ≥ p 0 , ∀q ∈ N, (A p+q×mii (i, :), A p (i, :)) similar, 5.2 : ∀p ≥ p 0 + m ji , (A p+mij (i, :), A p (j, :)) similar, 5.3 : ∀p ≥ p 0 + m ji , ∀q ∈ N, (A p+q×mii+mij (i, :), A p (j, :)) similar, where m ii = m ij + m ji .

Lemma 1. For any (i, j) ∈ [1..N ] 2 such as there exist paths t j mij,τij -→ t i and t i mji,τji -→ t j , and for any ν ∈ R, there exist δ ∈ R + , (p 0 , q 0 ) ∈ N 2 , and (µ 0 , .., µ p+q-1 ) ∈ R p+q max such that, ∀p ≥ p 0 , ∀q ≥ q 0 , ν

• x i (k) ≤ δ • x j (k -q) ⊕ p+q-1 k =0 µ k • u(k -k )
Remark 5. Lemma 1 is the core theoretical result of this paper. Given any (even negative) delay ν and state x i , it guarantees we can find an observable upper bound, that is an expression depending solely on past control events u(k) and any other transition's events x j (k), associated with a non-negative delay (δ) on x j .

In the next section, we will set the system's output y as x j and use the Lemma to derive a valid and observable control law.

Observable feedback control

We consider a TEG under assumptions of Section 3. Lets take one of its standard transitions as output, which firing epochs are referred to as y(k).

Demonstration of observable controlability

Theorem 2. Consider a live TEG with no 0-delay circuit which autonomous subgraph is strongly connected (Section 3 hypothesis), with a single place p ij (containing m ij tokens) subjects to a temporal constraint of form (5). Given that, (i) There exists an empty path t u 0,B(j)

-→ t j , (ii) ∀k , 0 ≤ k < m ij , (A k • B)(i) = ε, (iii) (A mij • B)(i) ≤ τ max ij • B(j), it is sufficient to set u(k) ≥ C = (-B(j)) • (-τ max ij ) • x i (k + m ij ) (6)
to obtain a control which guarantees to satisfy the constraint for all k ≥ m ij .

Furthermore, one can always derive an upper-bound of C of the following form, such as it defines a valid and observable feedback control,

C ≤ δ • y(k + m ij -q) ⊕     p+q -1-mij k =1 µ + k +mij • u(k -k )     (7)
where (p, q) ∈ N 2 with q ≥ 0 ⊕ (1 + m ij -m yu ), m yu is the smallest token number of paths t u -→ t y , coefficients p, q, δ and (µ + k ) are returned by Alg. 1.

Proof. The time constraint to satisfy is expressed by ( 5) :

x i (k) ≤ τ max ij • x j (k -m ij ).
Existence of an empty path t u 0,B(j)

-→ t j is equivalent to B(j) = ε (refer to Rem.2). Therefore, C is well-defined in R max . (2) : x j (k) = A(j, :) • x(k -1) ⊕ B(j) • u(k) ⇒ x j (k) ≥ B(j) • u(k) u(k) ≥ C ⇒ x j (k) ≥ B(j) • (-B(j)) • (-τ max ij ) • x i (k + m ij ) ⇒ x j (k) ≥ (-τ max ij ) • x i (k + m ij ) ⇒ ∀k ≥ m ij , x i (k) ≤ τ max ij • x j (k -m ij )
Moreover, u(k) must respect the state equations system, especially, for any φ ∈ N:

(3) ⇒ x i (k) = A φ (i, :) • x(k -φ) ⊕ φ-1 k =0 (A k • B)(i) • u(k -k ) ⇒ ∀k ∈ N, x i (k) ≥ ν k • x i (k + m ij -k ) ( * ) where ν k = (A k • B)(i) • (-B(j)) • (-τ max ij )
Note that x i (k) is a non decreasing sequence. Hence x i (k) ≤ x i (k + p) for any p ≥ 0. Therefore, we can assure that ( * ) will be satisfied if

∀k < m ij , ν k = ε ⇔ (ii) : ∀k < m ij , (A k • B)(i) = ε and 0 ≥ (A mij • B)(i) • (-B(j)) • (-τ max ij ) ⇔ (iii) : (A mij • B)(i) ≤ τ max ij • B(j)
Note that the two conditions are sufficient but the second is also necessary (( * ) cannot be true if (iii) does not hold).

Moreover, under the Theorem's assumptions, we can apply Lemma 1,

∃δ ∈ R + , ∃(p 0 , q 0 ) ∈ N 2 , ∀p ≥ p 0 , ∀q ≥ q 0 , (-B(j)) • (-τ max ij ) • x i (k) ≤ δ • y(k -q) ⊕ p+q-1 k =0 (µ k • u(k -k )) where µ k = (-B(j)) • (-τ max ij ) • (A k • B)(i) ⇒ C ≤ δ • y(k + m ij -q) ⊕ p+q-1 k =0 (µ k • u(k + m ij -k )) = C Furthermore, if (i) and (ii) are satisfied, µ k = ε for 0 ≤ k ≤ m ij , therefore, C = δ • y(k + m ij -q) ⊕ p+q-1 k =mij+1 (µ k • u(k + m ij -k )) = δ • y(k + m ij -q) ⊕ p+q-1-mij k =1 µ k +mij • u(k -k ) Lets set µ + k = µ k if µ k > 0, ε otherwise. ∀k ≥ 0, µ ≤ 0 ⇒ u(k) ≥ µ • u(k -k ) by definition. Thus, if one defines C + as C with µ k replaced by µ + k , it follows u(k) ≥ C + ⇔ u(k) ≥ C ⇒ u(k) ≥ C ⇒ u(k) satisfies the constraint. Finally, u(k) ≥ C + implies u(k) ≥ δ • y(k + m ij -q)
. Therefore, implementing this control results in adding a path t y (q-mij), δ -→ t u . According to Thm. 1, for the controlled system to remain live, we ultimately need to satisfy

m yu + m uy ≥ 1 ⇒ m yu + (q -m ij ) ≥ 1 ⇒ q ≥ 1 + m ij -m yu
Remark 6. This method easily extends to multiple constraints, in the exact same fashion as in [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF]) and [START_REF] Kim | Feedback Control of Cluster Tools for Regulating Wafer Delays[END_REF]. For each constraint, one derives a suitable control u s (k). All constraints will be satisfied by u(k) ≥ u s (k).

Remark 7. Note that, even though demonstrated starting from the standard form (2), Theorem 2 is not restricted to constraint places with zero or one token.

Consider the example of Fig. 3(b). After expansion, the temporal constraint reads

x i (k) ≤ τ max ij • x j (k -1). But since x j (k) = x j (k -1), it is equivalent to x i (k) ≤ τ max ij • x j (k -2)
, from which our method can be applied.

Algorithmic procedure for the control derivation

Coefficients from control's definition of Theorem 2 are computed by Algorithm 1. It takes as input the state equations system (matrices A and B), the input and output transitions of the constrained place (i and j) and its token number (m ij ), the constraint value (τ max ij ), the output transition of the system (y), and the smallest token number of paths t u -→ t y (m yu ). It returns all coefficients defining a valid and observable feedback control lower-bound which satisfies the constraint (p, q, δ and (µ + k )) when sufficient conditions are satisfied, and a failure otherwise. Theorem 2 guarantees that the procedure terminates.

Observable control of cluster tools

Semiconductor manufacturing industry is an good example of practical need for precise temporal control of processing. A commonly used technology is low pressure chemical vapor deposition (LPCVD), which as a strict time limit on maximum acceptable wafer delays. Pushed by opti-

� 6 � 3 � 2 � 4 � 5 � 1 � 11 � 10 � 9 � 8 � 7 � 12 � 13 LL unload PM1 load Rotate PM1 unload Move to PM1 Move to PM2 PM2 unload Rotate PM2 load Move to LL LL load Move to LL PM2 Proc [���, ���] ��� � PM1 Proc ��� � � � � � � � � � � � � � � (

Presentation of the system

We introduce thereafter the TEG model of a radial dual-armed cluster tool, which description is mostly taken from [START_REF] Kim | Feedback Control of Cluster Tools for Regulating Wafer Delays[END_REF]. We present how to apply our method to derive a valid and observable feedback control ensuring the satisfaction of wafer residency time constraints.

A cluster tool, as illustrated in Fig. 4(a), consists of several single wafer processing chambers which are also called process modules (PMs), a wafer handling robot, and loadlocks (LLs) for loading and unloading of wafer cassettes in a closed environment. Cluster tools are widely used for various semiconductor manufacturing processes including etching, sputtering, chemical vapor deposition and so on. PMs and LLs are mostly radially arranged around a robot. A robot performs loading and unloading a wafer at a PM or a LL through radial moves. The swap sequence (illustrated in Fig. 4(b)) is a well-known simple robot task sequence for dual-armed cluster tools. It is known to be optimal for most practical cases. It repeats a swap operation at each PM in order of wafer flow. The swap operation unloads a wafer from a PM into the empty arm, rotate the robot arms, and unloads the wafer on the other arm into the PM. This sequence can be modeled by the TEG of Fig. 4(c).

As mentioned in Section 2, firing of transition t i triggers the beginning of actions associated to the downstream place(s). Note that in this model, there are two process tasks to perform. Nominal duration of P M 1 is 100 time units while P M 2 takes 240 times units, but can be processed on two modules, hence the two tokens in the lower-side loop. In order to derive the standard state equation (2), this place (in grey on Fig. 4(c)) has been decomposed into two places containing 1 token each, in the fashion of Fig. 1.

Processing task P M 1 is subject to a time constraint, i.e., a wafer must not stay longer than 110 time units in P M 1 . We assume the firing of transition t 6 (starting P M 1 ) is a controllable event, which is represented by the input transition t u connected to t 6 on Fig. 4(c). It follows that the dynamics of this TEG are expressed by the following state-space equation

x(k) = A.x(k -1) ⊕ B.u(k) where A =                      . . . .
                     , B =                      . . . . . 0 5 10 15 20 25 30 .                     
and ε is replaced by a . for the sake of readability.

Observable control of the system

We consider the unloading of a processed part in one of the loadlocks LL as the system's output. Hence, we will consider y = x 12 , that is to say firing of t i (i = 12) are considered to be unobservable events.

Remark 8. Note that the choice of x 12 is arbitrary. Our approach can be applied with any of the system's events, as long as Theorem 1's conditions are satisfied.

P M 1 's time constraint is expressed by the following inequality

x 3 (k) ≤ τ max 36 • x 6 (k -1) = 110 • x 6 (k -1) (8)
The system's model satisfies hypothesis of Theorem 2. It is live with no 0-delay circuit and its autonomous subgraph is strongly connected. Furthermore, (i) there exists an empty path t u 0,B(j)

-→ t j , (ii) (B)(3) = ε, (iii) (A • B)(3) = 100 ≤ 110 + 0 = τ max 36 • B(6).
It follows that constraint (8) is satisfied by

u(k) ≥ C = -(B(6) + τ max 36 ) • x 3 (k + 1) = -110 • x 3 (k + 1) � = � 12 � 6 � 3 � 2 � 4 � 5 � 1 � 11 � 10 � 9 � 8 � 7 LL unload
u(k) ≥ 100 • y(k -1) ⊕ 105 • u(k -1) ⊕ 205 • u(k -2)
satisfies constraint (8). Implementation of this control law is represented on Fig. 5. One can note that this control law is valid (controlled system is still live -see Theorem 1) and causal (delays are non-negative).

Discussions on control performance and optimality

To evaluate control performance in our setting, the natural parameter to consider is the system's cycle time (i.e., the inverse of the throughput). An optimal control could be defined as a control which does not increase the cycle time of the uncontrolled system.

Let λ and λ be the cycle times of the uncontrolled and controlled systems respectively. Applying relation (4) to our control returns λ = 127.5 time units, and λ = 130 time units > λ Thus, our control might not be obtimal, as it affects the system's cycle time.

In our work, as in previous approaches from the literature, we derive sufficient conditions for controlability of temporal constraints the kind of (5). There are no proof (at least so far) that such control strategies are minimally restrictive. This could be true if sufficient conditions from Theorem 2 are also necessary. This remains an open question.

Although this was only partially presented in this paper, we have implemented our control method in simulation and tested it on several manufacturing scenarios from the literature [START_REF] Atto | Control of discrete event systems with respect to strict duration: Supervision of an industrial manufacturing plant[END_REF][START_REF] Kim | Feedback Control of Cluster Tools for Regulating Wafer Delays[END_REF]. As one can expect, compared to the fullobservability case, our control approach tends to increase more the cycle time of the controlled system. This is natural as we have some extra restrictions on the information available. It is the price one has to pay to control under partial observability.

Note that it is not always the case. The cycle time will increase depending on the system's architecture, the constraints values, and the choice of the state variable set as output.

Remark 9. For instance, in our example, one can derive an observable control law which is also optimal (i.e., which does not increase the system's cycle time) by considering x 5 as the system's output. The resulting control law is then

u(k) = 105 • u(k -1) ⊕ 220 • u(k -2) ⊕ 335 • u(k -3) ⊕ 135 • y(k -1)
which preserves λ = 127.5 time units. However, up to this point in our research, there is no proof this can always be achieved.

Comparison with previous approaches

On Fig. 5, we also represent the control law derived in [START_REF] Kim | Feedback Control of Cluster Tools for Regulating Wafer Delays[END_REF], showed in grey. Compared to our approach, this control uses as input firings of transitions t 12 but also t 6 and t 10 . Until the present contribution, the control dependence with these events could not be handled. If only one of such events is unobservable, we could not guarantee the controllability of the system. In introduction, we claimed our control method to be an extension of this of [START_REF] Kim | Feedback Control of Cluster Tools for Regulating Wafer Delays[END_REF]. Indeed, while stated otherwise, their approach consists simply in expressing (6) (refer to Thm. 2) into feedback form. This is done easily by using relation (3) with φ = m ij + 1,

x i (k + m ij ) = (A mij+1 )(i, :) • x(k -1) ⊕ mij k =0 A k • B • u(k + m ij -k )
Under hypothesis (ii) and (iii) of Thm. 2, terms in u simplify and we get

u(k) ≥ ((A mij+1 )(i, :) • (-B(j)) • (-τ max ij )) • x(k -1)
The problem here is that such expression uses possibly all state variables in its definition, while some of them might not be observable. Therefore, our approach consists in pushing further the order of φ. We showed that, if one looks "far enough" in the past, firing epochs of any state variable of interest (x i in this setting) can be over-estimated by previous firings of any other state variable (e.g., the output y) and some positive delays. This is Lemma 1's result.

Theorem 2 shows how to use this result to derive a valid and observable feedback control, which can be further implemented on the system.

Conclusions

Max-Plus models are useful to capture time dependencies of discrete-event systems. In the literature, several approaches address the control of such models, especially in cases of strict time constraints (e.g., [START_REF] Amari | Max-plus control design for temporal constraints meeting in timed event graphs[END_REF][START_REF] Atto | Control of discrete event systems with respect to strict duration: Supervision of an industrial manufacturing plant[END_REF]; [START_REF] Maia | Some results on the feedback control of max-plus linear systems under state constrains[END_REF]; [START_REF] Kim | Feedback Control of Cluster Tools for Regulating Wafer Delays[END_REF]). It was demonstrated that one can derive a control sequence u(k) which ensures such constraints are met. However, in these works, all events are assumed to be observable, which means all transitions firing epochs can be used to feed the control. This is a strong limitation in practice.

In this paper, we relax that hypothesis. In other word, we tackle the synthesis of a controller under partial observability. We demonstrate that for any strongly connected TEG, one can always derive a valid and observable feedback control (i.e., depending on output and the control events only), ensuring a given set of temporal constraints will be satisfied. The procedure to derive such a control law is provided. Furthermore, we use the practical example of a dual-armed cluster tool to demonstrate the use of our method and discuss its performance.

As a final contribution related to this work, we are currently developing a plug-in for the TINA (TIme petri Net Analyzer) software tool [START_REF] Berthomieu | The tool TINA-construction of abstract state spaces for Petri nets and time Petri nets[END_REF]. Taking the TEG to control as input (under textual or graphic form), it returns the control policy, adds it to the model and evaluates the cycle time of the controlled system. This tool is also interesting because of another (already existing) plug-in performing LTL model-checking on Time and Timed Petri nets. For example, it allows one to verify the controller we have derived does indeed verify our constraints.

To push further our synthesis approach, it would be interesting to further investigate conditions for an optimal control, that is, whether or not one can derive an observable feedback control which will not increase the system's cycle time, or at least no more that a fully-observable control does. Other perspectives include the more general study of necessary conditions for contolability, the satisfaction of time constraints on paths instead of places, relaxing the empty-path hypothesis ((i) in Thm. 2), or the efficient control of systems using multiple inputs (i.e., multiple control transitions). Finally, the fundamental limitation of our approach is the inability (or at least inefficiency) of TEGs for handling conflicts. It would be interesting to consider extensions of such control approaches to sets of TEGs with conflicts, in the fashion of [START_REF] Addad | Analytic calculus of response time in networked automation systems[END_REF].

∀p ∈ N * , A p+mii (i, :) ≥ τ ii • A p (i, :)

{Prop. 3} One can recursively set p := p + m ii and easily show that ⇒ ∀p ∈ N * , ∀q ∈ N, A p+q×mii (i, :) ≥ (q × τ ii ) • A p (i, :)

One can further set p := p + m ij , ⇒ ∀p ∈ N * , ∀q ∈ N, A p+mij+q×mii (i, :) ≥ (q × τ ii ) • A p+mij (i, :) Plus: ∃ t j mij,τij -→ t i ⇒ ∀p ∈ N * , A p+mij (i, :) ≥ τ ij • A p (j, :) {Prop. 3} ⇒ ∀p ∈ N * , ∀q ∈ N, A p+mij+q×mii (i, :) ≥ (q × τ ii + m ij ) • A p (j, :)

As we assumed no 0-delay circuits, τ ii > 0, therefore, ∀ν ∈ R, ∃q 0 ∈ N, ν + (q 0 × τ ii + m ij ) ≥ 0 ⇒ ∀q ≥ q 0 , ν • A p+mij+q×mii (i, :) ≥ (ν + q × τ ii + m ij ) • A p (j, :) ⇒ ∀ν ∈ R, ∀q ≥ q 0 , ∀p ∈ N * , ν • A p+mij+q×mii (i, :) ≥ A p (j, :)

Proof of Prop. 5.

Existence of both t j mij,τij -→ t i and t i mji,τji -→ t j implies there exists at least one circuit t i mii,τii -→ t i where m ii = m ij + m ji . For any of such circuit, let (η i q ) q∈N be the sequel counting the number of ε-element in A q×mii (i, :). ∀p ∈ N * , A p+mii (i, :) ≥ τ ii • A p (i, :) {Prop. 3} ⇒ A p+mii (i, :) ≥ A p (i, :) {non-negative delays} ⇒ A (q+1)×mii (i, :) ≥ A q×mii (i, :)

{p := q × m ii } ⇒ ∀r ∈ [1..N ], (A (q+1)×mii (i, r) = ε ⇒ A q×mii (i, r) = ε) ⇒ η i q+1 ≤ η i q ⇒ (η i q ) q∈N is decreasing, plus it is minimized by 0, ⇒ (η i q ) q∈N converges. Since it takes only discrete values, the sequel reaches its limit at a given step l ≥ 0. ⇒ ∃ l ∈ N, ∀q ∈ N, η i l+q = η i l ⇒ [ A (l+q)×mii (i, r) = ε ⇔ A l×mii (i, r) = ε ] One can set p 0 := l × m ii , ⇒ ∃ p 0 ∈ N, ∀ q ∈ N, [ A q×mii+p0 (i, :) = ε ⇔ A p0 (i, :) = ε ] (A1) which concludes proof of 5.1 by use of Prop. 1.

Furthermore, as there exist both t i mij,τij -→ t j and t j mji,τji -→ t i paths, ∀p ∈ N * , A p+mij (i, :) ≥ A p (j, :) A p+mji (j, :) ≥ A p (i, :) {Prop. 3}

⇒ ∀p ∈ N * , A p+mij+mji (i, :) ≥ A p+mji (j, :) ≥ A p (i, :) ⇒ ∀p ∈ N * , A p+mii (i, :) ≥ A p+mji (j, :) ≥ A p (i, :) One can set p := p 0 = l × m ii , ⇒ A (l+1)×mii (i, :)

x ≥ A l×mii+mji (j, :) y ≥ A l×mii (i, :) Thus, for any r ∈ [1..N ]:

x ⇒ A (l+1)×mii (i, r) = ε ⇒ A l×mii+mji (j, r) = ε

y ⇒      A l×mii+mji (j, r) = ε ⇒ A l×mii (i, r) = ε ⇔ A p0 (i, r) = ε (A1):q=1 ⇔ A mii+p0 (i, r) = ε ⇔ A (l+1)×mii (i, r) = ε     

Figure 1 .

 1 Figure 1. Example of TEG; (a) a general model and (b) its extension

Figure 2 .

 2 Figure 2. Graph interpretation of A and B matrices

Figure 3 .

 3 Figure 3. (a) Example of temporal constraint and (b) its extension

  Figure 4. Modeling of a dual-armed cluster tool performing a swap sequence

Figure 5 .

 5 Figure 5. Observable feedback controlled TEG

  . . . . . . . 5 . . . . . . . . . . . . 10 . . . . . . 100 . . . . . 15 . . . . . . 105 . . . . . 20 . . . . . . 110 . . . . . 25 . . . . . . 115 . . . . . 30 . . . . . . 120 . . . . . 35 240 . . . . . 125 . . . . . 40 245 . . . . . 130 . . . . . 45 250 . . . . . 135 . . . . . 50 255 . . . . . 140 . . . . . 55 260 . . . . . 145 . . . . . 60 265 . . . . . . . . . 0 . . .

Algorithm 1 deriveControlCoef Require: A, B, i, j, m ij , τ max ij , y, m yu %Tests for sufficient conditions if B(j) = ε or

while majorationTest is false do q := q + 1 ; end while%q = q 0 from Prop. 4 has been reached. while similarityTest is false do p := p + 1 ; end while%p = p 0 from Prop. 5.3 has been reached.

%Compute the remaining coefficients

mization concerns over the past 20 years, there has been a lot of work done oriented toward this type of industry, from process design and performance evaluation [START_REF] Srinivasan | Modeling and performance analysis of cluster tools using Petri nets[END_REF], to optimized scheduling [START_REF] Kim | Schedulability analysis of time-constrained cluster tools with bounded time variation by an extended Petri net[END_REF][START_REF] Wu | A closed-form solution for schedulability and optimal scheduling of dual-arm cluster tools with wafer residency time constraint based on steady schedule analysis[END_REF][START_REF] Jung | An efficient mixed integer programming model based on timed Petri nets for diverse complex cluster tool scheduling problems[END_REF][START_REF] Jung | A branch and bound algorithm for cyclic scheduling of timed Petri nets[END_REF][START_REF] Wu | A Petri-net-based scheduling strategy for dual-arm cluster tools with wafer revisiting[END_REF], multirobot cluster tools [START_REF] Zuberek | Timed Petri net models of multi-robot cluster tools[END_REF], and control (Kim andLee 2012, 2015).

In this section, we present the model of a cluster-tool we use as a case of study and show how to use our method in practice, plus an evaluation of the control performance. Final discussion includes a comparison with previous results from the literature.

Appendix A. Proofs of Section 4 properties and lemma

Else, if A p (j, r) = ε, the result trivially holds. In any case, property holds true for any r, thus it holds for all.

Proof of Prop. 4.

There exists a circuit t i mii,τii

⇒ ∀p ≥ p 0 , (A p+mij (i, :), A p (j, :)) similar, which concludes 5.2's proof.

Finally, 5.1 holds for all p ≥ p 0 , so it holds in particular for all p ≥ p 0 . Therefore, for all q ∈ N and p ≥ p 0 , (A p+q×mii (i, :), A p (i, :)) similar,

Prop. 1 ⇒ (A p+q×mii+mij (i, :), A p+mij (i, :)) similar,

5.2

⇒ (A p+q×mii+mij (i, :), A p (j, :)) similar, which proves 5.3. -→ t i . Then, from Lemma's hypothesis, Prop. 4 and 5 provide, ∀ν ∈ R, ∃(p 0 , q 0 ) ∈ N 2 , ∀p ≥ p 0 , ∀q ≥ q 0 , (i) : ν • A p+mij +q×mii (i, :) ≥ A p (j, :) → Right-hand side's terms are contained in the left-hand side's.

Proof of

(ii) : (A p+mij +q×mii (i, :), A p (j, :)) similar → Both vectors have the same support (i.e., the same non-ε elements).

Note that we need to be careful in δ definition as (-ε) = +∞ does not belong to R max , hence the rejection of r such that A p (j, r) = ε.

which concludes the proof by setting µ k = ν • (A k • B)(i).