Observer design and feedback controller synthesis with observer in idempotent semiring

Abstract

In this paper, we present an observer design and a feedback controller with observer for a discrete event system involving synchronization phenomena. These systems can be described by linear models in the idempotent semiring. The approach follows the same principle as the Luenberger observer used in continuous systems. Theoretical results are applied to an industrial process and simulation results are reported to show the effectiveness of these methods in the estimation for min max plus linear systems using Scilab.

1. INTRODUCTION

A discrete event system (DES) is a dynamic system whose behavior can be described by means of a set of time-consuming activities, performed according to a prescribed ordering. Events correspond to starting or ending some activity (Cassandras (1999); Cohen (1984) ). These systems can represent a great number of processes characterized as being concurrent, asynchronous, distributed or parallel, such as flexible manufacturing systems, multiprocessor systems or transportation networks. If the concerned systems are characterized by delay and synchronization phenomena, the Timed Event Graphs (TEG) constitute interesting models. Timed Event Graphs are a subclass of timed Petri Net in which all places have a single transition upstream (A single upstream transition means that there is no competition in either consumption or supply of token in TEG) and a single one downstream (means that all potential conflicts in using tokens in places have been already arbitrated). This class of system plays an important role because of its deterministic temporal behavior.

In opposition to continuous systems, Timed Event Graphs are not modeled through differential or difference equations. An appropriate model is developed to describe the behavior of these systems and provide a framework for analytical techniques to meet the goals of design, control and performance evaluation. For about 30 years, a particular algebraic structure, called Dioids has motivated the elaboration of a new linear system theory ( Baccelli (1992) ; Cuninghame-Green (1979) ; Cohen (1984) ). This theory offers a striking analogy with conventional linear system theory such as state representation, transfer matrices, corrector synthesis and identification theory ( Cohen (1999) ; Lhommeau (2003) ; Cottenceau (1999)).

In control theory, a state observer is a system that provides an estimate of the internal state of a given real system from measurements of the input and output of the real system. the observer was first proposed and developed in ( Luenberger (1964 , 1966)). Since these early papers, which concentrated on observers for purely deterministic continuous linear systems, observer theory has been extended by several researchers to include discrete event dynamic systems, in particular Timed Event Graph.

The observer design problem of Timed Event Graph has received much attention over the last few years. A first problem considered is to estimate state in presence of disturbances for max-min plus linear system initially developed by ( Laurent (2010) ). Here, the main approach is based on the dioid of series Mianx[ ; ]. A second objective is to use an observer to feedback controller in order to obtain a desired behavior.

In this paper, the approaches are applied to an industrial process. Simulation results using Scilab are reported.

The article is organized as follows. In section 2 we recall basic notions and results about idempotent semiring and residuation theory ( Cohen (1998 a)). A brief description of the industrial plant is given, and we then introduce the modeling of Timed Event Graph in the dioid of formal series Mianx[ ; ] in section 3. In section 4, the observer is designed by analogy with the classical Luenberger observer for linear systems and controller synthesis with observer is obtained by considering residuation theory which allows the inversion of mapping in section 5. Finally, an example of production process is given in section 6.

2. PRELIMINARIES

In this section we give the notations and some algebraic tools concerning the dioid and residuation theories.

2.1. Definitions

Definition 1 (Monoid). A Monoid is a set D, endowed with an internal law noted , which is associative and has a neutral element, denoted , 8a 2 D; a = a = a: Definition 2 (Dioid or idempotent semiring). A dioid (D; ; ) is an algebraic structure, endowed with two internal operations, denoted by and . The operation is associative, commutative and idempotent, that is a a = a. The operation is associative (but not necessarily commutative), and distributive at left with respect to : 8 a; b; c 2 D; (a b) c = (a c) (b c), and at right: 8 a; b; c 2 D; a (b c) = (a b) (a c). The neutral elements of and are represented by and e respectively, and is absorbing for : 8 a 2 D; a = a = One says that the dioid is commutative provided that the law is commutative.

Definition 3 (Complete dioid). A dioid D is said to be complete if it is closed for infinte for infinite sums and if the product disitributes over infinte sums. A dioid is said complet 2.1.1. Example 1. ((max; +)algebra).Rmax = (R [ f 1g [ f+1g; max; +) is a commutative dioid with zero element equal to 1, and the unit element e equal to 0. We adopt the usual notation, so that the symbol stands for the max operation, and stands for the addition. Notice that (+1) = ( 1) + (+1) = = ( 1) in Rmax. 2.1.2. Example 2. ((min; +)algebra).Rmin = (R [ f 1g [ f+1g; min; +) is also a commutative dioid, for which equals to +1, and e equals to 0. We shall denote the min operation in the sequel, and the symbol will stand for the addition. Notice that ( 1) = (+1) + ( 1) = = (+1) in Rmin. 2.1.3. Remark.

Most of the time the symbol will be omitted as in conventional algebra, moreover ai = a ai 1 and a0 = e.

Definition 4 (Order relation). A set D is said to be ordered if there exisists a binary relation such that the following conditions are satisfied for all a, b and c in D:

Reflexive: every element is in relation with itself (a a);

Antysymmetric: if a b and b

a ) a = b.

Transitive: if a b and b

c ) a c.

In a dioid, the relation associated with max application is an oreder relation which correspond to the usual order , a b , b = a b , a b. The relation associated with min application is an oreder relation which correspond to the reverse of the usual order , a b , b = a b , a b. Definition 5 (Majorant and minorant). Let (D; D) be an ordered set, C D a non-empty subset of D, and a, b 2 C.

An element x 2 D satisfying 8b 2 C, b called majorant of set C.

An element y 2 D satisfying 8b 2 C, y called minorant of set C. x is b is In particular, if the upper bound (i.e. the least majorant) or/and lower bound (i.e. the greatest minorant) of set a; b exist, we denote them by a _ b and a ^ b, respectively.

2.2. Matrix dioid

Let (D; ; ) be a given dioid, and denote Dn n the set of square n n matrices with entries over D. The sum and the product over D extend as usually over Dn n as follows: (A B)ij = Aij Bij

n (A B)ij = M(Aik Bkj):

k=1 One can see that (Dn n; ; ) is a dioid. The neutral matrix for the law is the matrix with entries equal to , the identity matrix for the law is the matrix with entries equal to e on the diagonal and elsewhere. Notice that the products of matrices in Rmax and in Rmin are not equal, and do not equal the usual sum of matrices.

Theorem 1 (Kleene star operator). Over a complete dioid D, the implicit equation x = ax b admits x = a b as least solution. where a = L i In the following this operator will so mi2eNtimaes be represented by the mapping K : D ! D,x 7! x . Furthermore, letting a; b 2 D, Kleene star operator satisfies the following well known properties : : (a ) = a ; a a = aa ; a(ba) = (ab) a (1) (a b) = (a b) = (a b ) = (a b ) (2) Thereafter, the operator a+ = Li2N+ ai = aa = a a is also considered, it satisfies the following properties: a+ a ; (a+) = a ; (ab )+ = a(a b) (3) Inversion of mappings is an important issue in many control applications. Unfortunately, in general manner, mappings defined over idempotent semiring do not admit inverse. However the residuation theory allows to characterize the solution set of an inequality such as f(x) b. The reader may consult Cohen (1998 a) to obtain a complete presentation of this theory.

Definition 6 (Isotone mapping). f is an isotone mapping if it preserves order, that is, a b ) f(a) f(b).

Definition 7 (Residuated mapping). An isotone mapping f : D ! C, where D and C are ordered sets, is a residuated mapping if for all b 2 C there exists a greatest element x that satisfies the inequality f(x) b. This greatest element is denoted by f](b) and mapping f] is called the residual of f. Dually, if there exists a least element x for the inequality f(x) b, it is denoted by f[(b). Mapping f[ is called the dual residual of f.

Corollary 1 The mappings La : x 7! a x and Ra : x 7! x a defined over a complete idempotent semiring D are both residuated Cohen (1998 a). Their residuals are isotone mappings denoted respectively by L]a(x) = a x and Ra](x) = x a, were and are the left and right residuation respectively.

Theorem 2 The mappings x 7! a x and x 7! x a satisfy the following properties: a a = (a a) ;

a a = (a a) ; a(a (ax)) = ax;

((xa) a)a = xa; b a x = (ab) x;

x a b = x (ba); a (a x) = a x;

(a x) a = a x; (a x) ^ (a y) = a (x ^ y); (x a) ^ (y a) = (x ^ y) a: (4) (5) (6) (7) (8) (9) The sum, the product and the residuation of matrices are defined after the sum, product and the residuation of scalars in D.

3. TIMED EVENT GRAPH

A Timed Event Graph (TEG) is a subclass of timed Petri Net where each place has a single input transition and a single output transition. For more details about Petri net see David and Alla (1997) . The process we study here (see Martinez (2003) ; Amari (2004) ) is composed of three conveyor belts connected by loops. the parts are made on an extruding machine in loop 3. Loop 1 and loop 2 are both similar one to each other. they are dedicated to a thermal processing of the parts. Loop 3 processes parts that are conveyed on pallets to one of the other loops. we study loop 2 Figure 2 (identical process for loop1). Parts arrive from loop 3 at point A and an operator fixes them to point I. Here they enter inside the furnace. This element is a channel divided into two sections. Inside the former section parts are heated and they are next cooled down inside the latter. Once, pallets come outside the furnace (point O), they are transferred to a second operator who removes parts from the pallets. Thus, parts are taken away at point E according to the external resources. Finally, the free pallets are released and transfer to point A.

The main problem is to achieve the thermal treatment on loop 1 or loop 2 without major failures. In figure 1, d and l are assumed to be the durations of operations and the conveyor capacities respectively. This physical process (loop2) is modelled thanks to a TEG. Transition u1 models parts arrivals from loop3, u2 models the necessity of a resource to carry the terminated part and Transition y represents the departure of an achieved part. Figure 2 shows a model of the plant.

3.2. Timed Event Graph description in dioids

Timed Event Graph can be expressed by linear relations over some dioids Cohen (1999) . By associating with each transition x a dater function, in which x(k) is equal to the date when which the firing numbered k occurs, it is possible to obtain a linear state representation in Rmax. there is another representation of TEG in Rmin, a function of time t, corresponding to the cumulated number of firings of the transition at time t. such a function is called a counter. A two-dimensional representation of input-output maps called Mianx[ ; ] is considered here Cohen (1998 b), where is an indeterminate which may also be considered as the backward shift operator in the event domain, and is the backward shift operator in the time domain. this property means that each entry can be written as an expression of the form s = p qr in which p and q are polynomials in ( ; ) which represent the transient behavior and the repeated pattern respectively. whereas r is a monomial which reproduces the pattern q along the slope . Considering the Timed Event Graph in Figure2. The dynamic behavior of this system can be expressed as follow: x1(k) = max(x7(k 5)+4; x2(k 1); u1(k)), x2(k) = max(x1(k) + 1; x3(k 2)), x3(k) = max(x2(k)+3; x4(k 2); w1(k)), x4(k) = max(x3(k)+ 10; x5(k 2)), x5(k) = max(x4(k) + 10; x6(k 3)), x6(k) = max(x5(k) + 3; x7(k 1)), x7(k) = max(x6(k) + 2; x1(k 2); u2(k); w2(k)), y(k) = x7(k). In terms of Max Plus notation, we obtain the following linear equations: x1(k) = 4 x7(k 5) x2(k 1) u1(k), x2(k) = 1 x1(k) x3(k 2), x3(k) = 3 x2(k) x4(k 2) w1(k), x4(k) = 10 x3(k) x5(k 2), x5(k) = 10 x4(k) x6(k 3)), x6(k) = 3 x5(k) x7(k 1), x7(k) = 2 x6(k) x1(k 2) u2(k) w2(k)), y(k) = x7(k). consequently, The transitions are related as follows ax[ ; ]: over Min x1 = 5 4x7 x2 u1, x2 = x1 2x3, x3 = 3x2 2x4 w1, x4 = 10x3 2x5, x5 = 10x4 3x6, x6 = 3x5 x7, x7 = 2x6 2x1 u2 w2; y = x7.

We obtain the following state space representation over Mianx[ ; ]: x = Ax

Bu

Rw = A Bu

A Rw y = Cx = CA Bu

CA Rw

3.3. Periodicity, causality and asymptotic slope

Definition 8 (Periodicity) A series s 2 Mianx[ ; ] is said to be periodic if it can be written as s = p q( ) with p and q two polynomials and ; 2 N . A matrix is said to be periodic if all its entries are periodic.

Definition 9 (Causality) A series s 2 Mianx[ ; ] is causal if s = . The set of causal elements of ax[ ; ] has a complete dioid structure denoted by Min Mianx+[ ; ] Definition 10 (asymptotic slope) The asymptotic slope of a periodic series s = p q( ) denoted 1(s) is defined as the ratio 1(s) = = Let s1 and s2 be two periodic series such that 1, 2 6= 0 et 1, 2 6= 0), then 1(s1 1(s1 s2) = min( 1(s1); s2) = min( 1(s1); 1(s2)); 1(s2)); If 1(s1)

1(s2) then otherwise s2 s1 = .

1(s2 s1) = 1(s1)

4. OBSERVER DESIGN

The system evolves according to its state vector equations. Or, In many systems of practical importance, the entire state vector is not available for measurement. When faced with this difficulty , a solution is to provide an estimate of the internal state of the given plant from measurements of the input and output of the real system. By analogy with the classical Luenberger observer Luenberger (1964 , L1 = (A B) (CA B) L2 = (A R) (CA R)

L = L1 ^ L2 The greatest observer matrix such that x^ x is: 1966), we present an observer design (inspired from the work of ( Laurent (2010) ) for Timed Event Graph modeled in Mianx[ ; ]. Figure3 depicts the observer structure whose equations are: x^ = Ax^ Bu L(y^ y) = Ax^ Bu LCx^ LCx (12) y^ = Cx^ (13)

Where L is an observer gain matrix.

Using equation (10), we obtain the following structure: x^ = Ax^ Bu LCx^ LC(A Bu A Rw) x^ = (A LC)x^ Bu LCA Bu LCA Rw x^ = (A LC) Bu (A LC) LCA Bu

(A LC) LCA Rw By applying Kleene star properties we are: (A

LC) = A (LCA ) (14) Replacing (14) in previous equation, we obtain: x^ = A (LCA ) Bu A (LCA ) LCA Bu

A (LCA ) LCA Rw and by recalling that (LCA ) LCA = (LCA )+, this equation may be written as follows: x^ = A (LCA ) Bu A (LCA )+Bu A (LCA )+Rw Equation (3) yields: (LCA )+ (LCA ) Then the observer equation may be written as follows: x^ = A (LCA ) Bu

A (LCA )+Rw (16) (17) (18) (19)

5. FEEDBACK CONTROLLER SYNTHESIS WITH

OBSERVER

Now, we consider a problem of controller synthesis with an observer, for TEG, in an objective of reference model matching. This problem can be described in the following way: Taking a TEG of which one knows the transfer matrix, we estimate a state and we compute a controller which leads to a closed loop system whose behavior is as close as possible to the given reference model Gref . The input output transfet function is expressed by: y = Hu; such that H = CA B

The observer equation is given by:

Firstly, we calculate the observer matrix Lopt = (A B) (CA B). Then, within the framework of feedback controller synthesis, we have to find for a given Gref , a greatest Kopt with respect to the residuation theory. Proof 1 We calculate the greatest solution Kopt in order that the controlled system (with estimate state) will behave as close as possible to a given reference model. Using the residuation properties, the following equivalences are given :

CA B(K(A , (K(A , K(A In order to illustrate results presented previously, we consider a Timed Event Graph depicted in figure, 2. Transitions w1 and w2 represent uncontrollable inputs. each one corresponds to a transition which delays or disables the firing of internal transition of the graph. In our example, w1 corresponds to a failure at entry inside the furnace, the beginning of the thermal process, is modeled by x3, the firing of this transition is reported to time 25 instead of time 15. w2 means that the operator removes parts from the pallets at time 45 instead of time 39. Then, the state are delayed by disturbances whose trajectories are as follows : The simulation results are Shown in figure (Fig. 5, Fig. 6). The estimated states of Timed Event Graph x^1; x^2; x^3; x^4; x^5; x^6; x^7 are compared to the actual state. x1; x2; x3; x4; x5; x6; x7. We remark a little difference between some state and corresponding estimated state : x^3 and x3, x^4 and x4, x^5 and x5, x^6 and x6. it implies that the disturbances applied for transition x3 reduce the system performances, but these disturbances are not acknowledge by the observer. it is assumed that the model and the initial state correspond to the fastest behavior, ie. y^ and y are equivalent, and there are equality between asymptotic slope of the state and the one of estimated state, 1(y^) = 1(y) = 5=33. Consider a problem of controller synthesis with observer, we propose to compute a greatest K so that the system has a transfer relation close to a given reference transfer Gref .

The objective of the reference model is to impose a desired behavior Gref to a given system H, then in our example, we consider Gref = H.Using Scilab, we calculate H: H11 = 29 H12 = For Lopt obtained, we compute the greatest realizable feedback Kopt using the expression: therefore, we can compute the controller and the output of the system: u = (K(A In this paper, we have applied to an industrial process an observer design and the synthesis of controller with observer. this system is modeled by Timed Event Graph which can be described by linear equations in idempotent semiring. Firstly, The estimation state in presence of perturbation based on Luenberger observer, is considered, and the effectiveness of this method is shown by simulation results given by the use of Scilab. Afterwards, A synthesis of controller with observer for TEG in a model reference is presented, we have shown that it is possible to preserve its own transfer with a greatest realizable feedback control.

References

Amari , S. , Demongodin , I. and Loiseau , J.J. ( 2004 ) Sizing, cycle time and plant control using dioid algebra . Springer, pp. 77 - 85 .

Baccelli , F. , Cohen , G. , Olsder , G. and Quadrat , J. ( 1992 ) Synchronization and Linearity: An Algebra for Discrete Event Systems . Wiley and Sons.

Cassandras , C.G. and Lafortune , S. ( 1992 ) Introduction to discrete event systems . Kluwer Academic.

Cohen , G. , Moller , P. , Quadrat , J.P. and viot, M. ( 1984 ) Linear system theory for discrete event systems . In 23rd IEEE Conf. on Decision and Control , Las Vegas, Nevada.

Cohen , G. ( 1998a) Residuation and applications,In Alge´bres Max-plus et applications en informatique, Ecole de printemps d'informatique the`orique , Noirmoutier, France.

Cohen , G. ( 1998b)Two-dimentional domain representation of timed event graphs,In alge´bres Max-Plus et applications en informatique et automatique, Ecole de printemps d'informatique the´orique , Noirmoutier, France.

Cohen , G. , Gaubert , S. and Quadrat , J. ( 1999 ) Max-plus algebra and system theory,Where we are and where to go now, Annuel Reviews in control ,( 23 ),pp. 207 - 219 .

Cuninghame-Green , R.A. Minimax Algebra . (1979) Number 166 in Lecture notes in Economics and Mathematical Systems , Springer.

David , R. and Alla , H. ( 1997 ) Du Grafcet aux re ´seaux de Petri. Ed. Hermes, 2e e´dition revue et augmente´e.

Houssin , L. ( 2003 ) Contribution a´ l'e´tude des syste`mes e´ve´nements discrets dans l'alge´bre des dio¨ıdes. Applications aux syste´mes de transport . Rapport de stage de DEA, DEA Automatique et informatique Applique´e, Nantes-Angers, France.

Laurent , H. , Carlos , A.M. , Bertrand , C. and Mehdi , L. ( 2010 ) observer design for (max; +)linear systems . IEEE Transactions on Automatic Control , VOL. 55 .

Lhommeau , M. ( 2003 ) Etude de syste`mes a´ e´ve´nements discrets dans l'Alge´bre (max; +): Synthe`se de correcteurs robustes dans un dio¨ıde d'intervalles , Synthe`se de correcteurs en pre´sence de perturbation. Phd Thesis , Angers University.

Luenberger , D G. ( 1964 ) Observing the State of a Linear System , IEEE Trans. on Military Electronics , Vol. MIL-8 ,pp. 74 - 80 , April 1964 .

Luenberger , D G. ( 1964 ) Observers for multivariable Systems , IEEE Trans. on Automatic Control , Vol. AC-II,NO.2 , pp. 190 - 197 , April 1966 .

Martinez , C. and Castagna , P. ( 2003 ) Sizing of an industrial plant using tight time constraints using complementary approaches: (max; +) algebra and computer simulation . Simulation Modelling Practice and Theory, Elsevier , Vol. 11 ,pp. 75 - 88 .