CONTROL OF CONSTRAINED (MAX,+)-LINEAR SYSTEMS MINIMIZING DELAYS L. Houssin ∗ S. Lahaye ∗ J.L. Boimond ∗ ∗ Laboratoire d’Ingénierie des Systèmes Automatisés, 62, avenue Notre Dame du Lac, 49000 Angers, France Abstract: This paper deals with feedback controller synthesis for (max,+)-linear systems. We attempt to compute a feedback which ensures some given constraints while delaying as less as possible the system. The controller synthesis presented c here is based on fixed points results of antitone mappings. Copyright °2006 IFAC Keywords: Discrete Event Systems, (max, +) algebra, controller synthesis 1. INTRODUCTION In this paper, we study DEDS (Discrete Events Dynamic Systems) that can be modeled by a linear representation on (max, +) algebra. This class corresponds to TEG (Timed Event Graphs). A linear system theory has been developed for these particular systems in (Baccelli et al., 1992). Strong analogies then appear between the classical linear system theory and the (max, +)-linear system theory. Some control problems for these systems have previously been tackled. In all these works, the problematic was to compute an optimal solution in regards of the just-in-time criterion, indeed the proposed control laws satisfy some given control objectives while delaying as much as possible occurrences of input or internal events. In (Cottenceau et al., 2001), the authors compute a greatest feedback controller (which enables to delay as much as possible occurrences of input or internal events) in order that the controlled system behaves as close as possible to a given reference model. For our concern, the aim of the control is to delay as less as possible the system while ensuring some given specifications. For example, in a railway network, one can aim at limiting the number of trains in a path while minimizing the induced delays. Another possible application concerns production systems subject to critical time constraints, in which sojourn times of pieces must not exceed a given value at some stages. The control is formalized as a state feedback on state. This control structure has previously been considered in (Lüders and Santos-Mendes, 2002). Originalities of this paper lies in the considered criterion (minimization of delays instead of justin-time), the specification of the control objective (constraints instead of reference model) and the approach for the controller synthesis (new results on fixed points of antitone mappings instead of Residuation theory). In section 2, we recall some results from the dioid theory and introduce results concerning isotone and antitone mappings. Section 3 is devoted to the modeling of DEDS. The proposed control law is presented in section 4. 2. ALGEBRAIC TOOLS 2.1 Dioid theory A dioid (D, ⊕, ⊗) is a semi-ring in which the sum, denoted ⊕, is idempotent. The sum (resp. product) admits a neutral element denoted ε (resp. e). A dioid is said to be complete if it is closed for infinite sums and if product distributes over infinite sums too. The sum of all its elements is generally denoted ⊤ (for top). Example 1. The set Zmax = (Z∪{−∞}) endowed with the max operator as sum and the classical sum as product is a (non-complete) dioid. If we add ⊤ = +∞ (with convention ⊤ ⊗ ε = +∞ + (−∞) = −∞ = ε) to this set, the resulting dioid is complete and is denoted Zmax . Due to the idempotency of the sum, a dioid is endowed with a partial order relation, denoted º, defined by the following equivalence: a º b ⇔ a = a ⊕ b. A complete dioid has a structure of complete lattice (Baccelli et al., 1992, §4), i.e., two elements in a complete dioid always have a least upper bound, namely a ⊕Lb, and a greatest lower bound denoted a ∧ b = {x|x¹a, x¹b} x in the considered dioid. Let D and C be two complete dioids. A mapping f : D → C is said to be isotone (resp. antitone) if a, b ∈ D, a ¹ b ⇒ f (a) ¹ f (b) (resp. f (a) º f (b)). 2.2 Residuation theory Residuation theory (Blyth and Janowitz, 1972) defines ”pseudo-inverses” for some isotone mappings defined over ordered sets such as complete dioids (Cohen, 1998). More precisely, if the greatest element of set {x ∈ D|f (x) ¹ b} exists for all b ∈ C, then it is denoted f ♯ (b) and f ♯ is called residual of f . Dually, one may consider the least element satisfying f (x) º b, if it exists for all b ∈ C, it is denoted f ♭ (b) and f ♭ is called dual residual of f . Example 2. The mapping Ta : D → D; x 7→ a ⊕ x is dually residuated (proof is available in (Baccelli et al., 1992, §4.4.4)). The dual residual is denoted Ta♭ (b) = b − ◦ a. It should be clear that a º b ⇔ Ta♭ (b) = ε. If Ta is defined over Zmax then ( b ♭ Ta (b) = ε if b > a, otherwise. For an isotone mapping f , (Tarski, 1955) has shown that sets Ff , Pf and Qf are nonempty complete lattices. Moreover, it can be shown that the greatest (resp. least) fixed point coincides with the greatest (resp. least) element of Pf (resp. Qf ): Sup Pf = Sup Ff and Sup Ff ∈ Ff , Inf Qf = Inf Ff and Inf Ff ∈ Ff . In the following proposition, we specify to dioids a well known method to compute the greatest fixed point of an isotone mapping f . Proposition 1. If the following iterative computation y0 = ⊤ (2) yk+1 = f (yk ) converges in a finite number ke of iterations, then yke is the greatest fixed point of f . Concerning antitone mappings, properties about fixed points are not that well established, and only few works have tackled this problem (Baclawski and Björner, 1979), (Dacić, 1983). To the best of our knowledge, results presented in the sequel are original. However, proposition 6 has been inspired by (Dacić, 1983, th. A) Notice that if f is an antitone mapping then f 2 is isotone. Let us first characterize the structure of Pf and Qf . Proposition 2. Let f : D → D be an antitone mapping. Set Qf (resp. Pf ) is a complete upper semi-lattice (resp. complete lower semi-lattice). Proof : Let us consider two elements x, y ∈ Qf , we have f (x⊕y) ¹ f (x)∧f (y) ¹ f (x)⊕f (y) ¹ x⊕ y, and so x ⊕ y ∈ Qf . This assertion also applies to infinite sums. Set Pf is proved to be a complete lower semi-lattice by identical arguments. ✷ Proposition 3. Let f : D → D be an antitone mapping and x ∈ D. We have x ⊕ f (x) ∈ Qf , x ∧ f (x) ∈ Pf . 2.3 Fixed points of mappings defined over dioids Because of their lattice structure, properties about fixed points stated for lattices also apply over dioids. Notation 1. Let f : D → D with D a complete dioid, we use the following notations: Ff = {x ∈ D|f (x) = x}, Pf = {x ∈ L|f (x) º x}, Qf = {x ∈ D|f (x) ¹ x} and f 2 denotes f ◦ f . (1) Proof : ½ f (x) ⊕ x º x f (x) ⊕ x º f (x) which implies by antitony of f f (f (x) ⊕ x) ¹ f (x) ¹ f (x) ⊕ x. Respectively, f (x) ∧ x ∈ Pf since f (f (x) ∧ x) º f (x) º f (x) ∧ x. ✷ Proposition 4. Let f : D → D be an antitone mapping, y ∈ Pf and z ∈ Qf . For all x ∈ D such that x ¹ y (resp. x′ ∈ D such that x′ º z), we have x ∈ Pf (resp. x′ ∈ Qf ). The proof is based on the antitony of f : x ¹ y ⇒ f (x) º f (y) º y º x x′ º z ⇒ f (x′ ) ¹ f (z) ¹ z ¹ x′ Proposition 5. If x is a fixed point of an antitone mapping f : D → D, then x is a minimal (resp. maximal) element of Qf (resp. Pf ). Proof : Let x ∈ Ff , y ∈ Pf and z ∈ Qf such that y º x º z. Using antitony of f , we obtain f (y) ¹ f (x) ¹ f (z) ⇒ y ¹ f (y) ¹ x ¹ f (z) ¹ z hence y = x = z. We conclude that there is no element of Qf (resp. Pf ) which is less (resp. greater) than x. ✷ As a corollary of this proposition, notice that if f admits several distinct fixed points, then they are not comparable. Furthermore, remark that set Ff can be empty. Proposition 6. Let f : D → D be an antitone mapping. Denoting u = Inf Ff 2 and v = Sup Ff 2 , we have u ∈ Pf and v ∈ Qf . Proof : In fact, we show that f (u) = v and f (v) = u and then f (u) º u and f (v) ¹ v. The expression of f (u) leads to f (u) = f ( ^ x) º x∈Ff 2 ) M f (x) However, elements of {f (x)|x ∈ Ff 2 } are fixed points of f 2 too since f 2 (f (x)) = f (f 2 (x)) = f (x). So we can deduce that f|Ff 2 is a permutation, it can be proved by considering x, y ∈ Ff 2 , x 6= y and f (x) = f (y), we would obtain f 2 (x) = f 2 (y) and so x = y which is a contradiction. So last inequality can be rewritten: M ✷ Remark 1. For the following control problem, we are interested in the computation of minimal elements of Qf . The element v, which can be computed using proposition 1, constitutes an interesting approximation since any x ∈ Ff , minimal element of Qf (see proposition 5), is such that u ¹ x ¹ v (since x also belongs to Ff 2 ). As mentioned in the following corollary, v may sometimes be the ”best approximation”. Corollary 1. If v = u, then Ff = {v} and v is a minimal element of Qf . 3. MODELING DEDS USING DIOIDS 3.1 State and transfer representation Dioids enable one to obtain linear models for DEDS which involve (only) synchronization and delay phenomena (but not choice phenomena). It corresponds to the class of DEDS which can be modeled by Timed Event Graphs (TEG). The behavior of such systems can be represented by some discrete functions called dater functions. More precisely, a discrete variable x(·) is associated to an event labeled x (firing times of transition labeled x in the corresponding TEG). This variable represents the occurring dates of event x. Notice that a dual representation for these DEDS is called counter representation and it manipulates variables which represent the number of the last firing of transition x (see (Baccelli et al., 1992) for more details). The considered DEDS can be modeled by a linear state equation x(k) = Ax(k − 1) ⊕ Bu(k), (3) x∈Ff 2 (f antitone ⇒ f (a ∧ b) º f (a) ⊕ f (b)). f (u) º L to f (u) = y∈F 2 y = v. From last equality, we f obtain also f (f (u)) = u = f (v). y = v. y∈Ff 2 We previously remark that f (x) with x ∈ Ff 2 is a fixed point of f 2 so does f (u) and it leads where x and u are the state and the input vectors. An analogous transform to Z-transform (used to represent discrete-time trajectories in conventional theory) can be introduced for DEDS considered here: the γ, δ-transform. This transform enables to manipulate formal power series, with two commutative variables γ and δ, representing daters trajectories. The set of these formal series is a complete dioid denoted Max in Jγ, δK with e = γ 0 δ 0 as neutral element of product and ε as neutral element of sum (the construction of this dioid is detailed in (Baccelli et al., 1992)). In the following, we denote x the corresponding element of {x(k)}k∈Z in Max in Jγ, δK and we assume that Jγ, δK is represented by its minimum each x ∈ Max in representative (see (Baccelli et al., 1992, §5)). In Max in Jγ, δK, state representation (3) becomes x = Ax ⊕ Bu, (4) in which entries of matrices A and B are elements of Max in Jγ, δK. Considering the earliest functioning rule (an event occurs as soon as possible), we select the L least solution given by x = A∗ Bu with A∗ = i∈N Ai (Baccelli et al., 1992, Th 4.75), and A∗ B corresponds to the transfer between u and x. Afterwards, we assume that the input matrix B is a diagonal square matrix with entries equal to e or ε. This assumption is not restrictive since it can always be satisfied by extending the state vector. Remark that the assumed structure of B is such that B ¹ Id and B n = B for n ≥ 1. 3.2 Causality and causal upper approximation Variables x ∈ Max in Jγ, δK used to model TEG have the causality property (Baccelli et al., 1992). We introduce the notion of causal upper approximation. Definition 1. Let x ∈ Max in Jγ, δK, x is said to be causal if either x = ε or all exponents of x are in N. A matrix is said causal if its entries are all causal. The set of causal elements of Max in Jγ, δK is a complete dioid denoted Max+ Jγ, δK. in Proposition 7. Let x ∈ Max in Jγ, δK. The two following assertions are equivalent : (i) x has no negative exponent in γ, (ii) there exists a least x′ ∈ Max+ in Jγ, δK such that x′ º x. It means that there exists a causal upper approximation of x. Proof : If x is causal, the demonstration is obvious and x′ = x. We now consider x not causal. We can limit the proof to the case of monomials since a series is nothing more than a sum of monomials. (i)⇒(ii) : Let x = γ n δ t , with t < 0. It is easy to see that the monomials γ n δ 0 is the least element ′ ′ n 0 of Max+ in Jγ, δK such that x º x. So, x = γ δ . (ii)⇒(i) : If there exists a least x′ ∈ Max+ in Jγ, δK ′ ′ such that x′ º x with x′ = γ n δ t and x = γ n δ t , we have n′ ≤ n and t′ ≥ t. However x′ ∈ ′ Max+ ✷ in Jγ, δK, so n ≥ 0 and we obtain n ≥ 0. Fig. 1. 4. CONTROLLER SYNTHESIS 4.1 Problem statement Considering DEDS modeled by their state equation (4), we are interested in the synthesis of ”state feedback on state” controller. In this structure, a controller denoted F , is added between internal states (see figure 1). This structure is not usual in control theory, but has a specific interest for DEDS. In fact, if we assume that internal events are measurable, controller F uses this measure to possibly delay occurrences of some internal events. More precisely, if we consider a DEDS modeled by a TEG, then controller F can be realized by another TEG merged on the initial ones. In this controlled TEG, the additional arcs due to the controller authorize or prohibit the firing of the controlled transitions (see figure 2). This schema is comparable with some Petri nets methods for controlled DEDS ((Holloway et al., 1997)). The state evolution is then described by x = Ax ⊕ F x ⊕ Bu. (5) The least solution of this equation which corresponds to the earliest functioning, is given by x = (A ⊕ F )∗ Bu. Synthesis of feedback for DEDS in dioids has previously been tackled in (Cottenceau et al., 2001). The synthesis of state feedback on state controller has been considered in (Lüders and Santos-Mendes, 2002). In all these works, authors focus on just-in-time model reference control, that is, the synthesis of a feedback which delays as much as possible events in the system (i.e. the greatest feedback) such that the controlled system is not slower than a reference model. In this paper, the control objective is different : • we aim at ensuring some given constraints on state (rather than satisfying a reference model matching) for all input u. These constraints are defined by a matrix φ and are formulated as the implicit inequation : φx ¹ x, ∀u. (6) • we pursue a feedback which delays as less as possible the functioning of the system (rather than the just-in-time criterion). More precisely, we aim at computing the least feedback F such that the state of the controlled system given by (5) satisfies the constraints given by (6). 4.2 Constraints specification We now detail three kinds of constraints for DEDS described by a TEG, that can be formulated as an inequality (6): • Some inner variables can be subject to a minimum time separation between two firings. For a state variable xi and a time separation denoted ∆min , we claim that xi (k + 1) º ∆min xi (k). Then, the counterpart of this ∆min xi ¹ xi . constraint in Max in Jγ, δK is γδ • We can also aim at bounding the sojourn times of tokens in given paths of the TEG (critical time constraints). Let us consider a path from transition xi to transition xj containing initially α tokens, we denote τ the desired maximum sojourn time in this path. This imposes xj (k + α) − xi (k) ¹ τ , which can be formulated in Max in Jγ, δK by γ −α δ −τ xj ¹ xi . • We may also limit the number of tokens in paths of the TEG. Let us consider a path from xi to xj containing initially α tokens, we denote κ the desired maximum number of tokens in this path. This constraint can be specified by: κ º xi (t) − xj (t) + α, which κ−α leads in Max xj ¹ xi . in Jγ, δK to γ Proof : According to proposition 7, there exists a least causal matrix G such that G º (A ⊕ φ)∗ B if and only if each entry of (A⊕φ)∗ B has no negative exponent in γ. It is always possible to find a causal matrix F such that (A⊕F )∗ º G. Furthermore, by isotony of product, we have GB º (A ⊕ φ)∗ B 2 = (A ⊕ φ)∗ B since B 2 = B. The product GB is causal (since G and B are causal) and G is the least causal matrix such that G º (A ⊕ φ)∗ B, so we claim that GB º G. However B ¹ Id, one has that GB ¹ G. Therefore, and since B is causal, there exists a causal F such that (A ⊕ F )∗ B º GB = G. ✷ 4.4 Feedback computation From proposition 8, we aim at computing the least feedback F such that (A ⊕ F )∗ B º G in which G is the upper causal approximation of (A ⊕ φ)∗ B. Proposition 9. Solutions of equation (8) are elements of Qf (see notation 1) with f : F 7→ G− ◦ (A ⊕ F )∗ . 4.3 Formalization Proof : We have the following equivalences From (5), the state of controlled system is s.t. G ¹ (A ⊕ F )∗ B ⇔ G ¹ (A ⊕ F )∗ x º Ax ⊕ Bu. Furthermore, as control objective, we aim at satisfying (6), then since GB = G (see proof of prop. 8) and B ¹ Id ⇔ G ¹ (A ⊕ F )∗ ⊕ F since (A ⊕ F )∗ º F ⇔ G− ◦ (A ⊕ F )∗ ¹ F since T(A⊕F )∗ is dually residuated (cf. ex.2) ✷ x º (A ⊕ φ)x ⊕ Bu. Since we aim at delaying as less as possible the system, we seek the least controlled state x, that is the least x greater than the least solution x º (A⊕ φ)∗ Bu. The problem can then be formulated as the search for a least feedback F such that (A ⊕ F )∗ Bu º (A ⊕ φ)∗ Bu, ∗ (8) ∗ ∀u ⇔ (A ⊕ F ) B º (A ⊕ φ) B. Notice that mapping f is antitone. From proposition 6, the element v = Sup Ff 2 (which can be computed using proposition 1) belongs to Qf and is then a feedback satisfying (8). From corollary 1, v is a minimal element of Qf (i.e. a minimal feedback satisfying (8)) if v = u. Otherwise, as mentioned in remark 1, v can be used to approximate a minimal feedback satisfying (8). (7) Some constraints may be unsuitable, that is, there may not exist a causal feedback enabling to satisfy these constraints. The following proposition furnishes a test on given constraints φ, stating a necessary and sufficient condition for the existence of a causal feedback. Proposition 8. There exists a causal feedback F satisfying (7) if and only if each entry of (A⊕φ)∗ B has no negative exponent in γ. We then denote G the upper causal approximation of (A ⊕ φ)∗ B. 4.5 Example We consider the DEDS modeled by the TEG of fig. 2, and represented by the following matrices:   ε ε ε ε ε ε ε  δ3 γ 3 δ ε ε ε ε ε    ε ε ε ε ε ε ε   ε ε A=  ε ε δ ε5 ε ,  ε ε ε γδ  ε ε ε    ε δ 4 ε ε γ 2 δ 2 γδ 2 ε  ε ε ε ε ε δ3 ε v 6= u, and we hence can not argue thanks to corollary 1 that v is a minimal feedback. It can be checked that there exists a relevant feedback F ′ , defined by Fij′ = vij for (i, j) 6= (5, 3) and ′ F53 = ε, which is less than v. Nevertheless, let us point out that the controlled system with F ′ has the same transfer as the controlled system with v. This observation reinforces our suggestion that v constitutes a good approximated solution for our control problem (see remark 1). Fig. 2. A TEG (thick lines) merged with a realization of its controller (thin lines) and B is a diagonal matrix s.t. ( e if i ∈ {1, 3}, Bii = ε otherwise. In a first place, we aim at illustrating that all constraints defined as in 4.2, are not suitable. For example, we can not impose that tokens sojourn less than 2 time units in the place between transitions x5 and x6 for all input. In fact, if transition u1 is not fired, then initial tokens will not be removed from this place, and we can not find any relevant feedback. As stated in proposition 8, the computation of (A ⊕ φ)∗ B enables to detect this unsuitable constraint since it contains an entry with a negative exponent in γ. We now consider suitable constraints: • tokens must not sojourn more than 4 time units in the place between transitions x2 and x6 , then δ −4 x6 ¹ x2 , • the number of tokens between x5 and x4 must not exceed 3, so γ 2 x5 ¹ x4 . We have  ε ε  ε  φ= ε ε  ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε ε γ2 ε ε ε  ε ε δ −4 ε   ε ε  ε ε . ε ε  ε ε ε ε According to §4.4, we can compute the following feedback   ε ε ε εεεε  γδ 5 (γδ 2 )∗ ε γ 3 δ 4 (γδ 2 )∗ ε ε ε ε     ε ε ε ε ε ε ε   F =v= ε ε γ 3 δ 6 (γ 3 δ 5 )∗ ε ε ε ε     ε ε γ 4 δ 11 (γ 3 δ 5 )∗ ε ε ε ε     ε ε ε ε ε ε ε ε ε ε εεεε which satisfies both constraints. A realization of this controller is represented in thin lines on fig. 2. Let us note that, for this example, we have 5. CONCLUSION We have presented a new control problem in (max, +)-linear system theory: ensure some given constraints while delaying as less as possible the system. Using results on antitone and isotone mappings, a state feedback synthesis is proposed. However, it must be noted that the obtained controller is not necessarily minimal. In current works, we attempt to refine our control approach in that sense. We also plan to consider TEG with uncontrollable transitions and non linear constraints. REFERENCES Baccelli, F., G. Cohen, G. J. Olsder and J. P. Quadrat (1992). Synchronization and Linearity. Wiley. Baclawski, K. and A. Björner (1979). Fixed points in partially ordered sets. Advances in Mathematics 31(3), 263–287. Blyth, T. S. and M. F. Janowitz (1972). Residuation Theory. Pergamon press. Cohen, G. (1998). Residuation and Applications. In: Special issue on Ecole d’informatique théorique. INRIA. Noirmoutier. Cottenceau, B., L. Hardouin, J. L. Boimond and J. L. Ferrier (2001). Model reference control for timed event graphs in dioids. Automatica. Dacić, Rade M. (1983). On fixed edges of antitone self-mappings of complete lattices. Publications de l’Institut Mathématique. Holloway, L. E., B. H. Krogh and A. Giua (1997). A survey of petri net methods for controlled discrete event systems.. DEDS 7, 151–190. Lüders, R. and R. Santos-Mendes (2002). Generalized multivariable control of discrete event systems in dioid. In: Proceedings of WODES 2002. Zaragoza, Spain. Tarski, A. (1955). A lattice theorical fixed point theorem and its applications. Pacific Journal of Maths pp. 285–309.