APPROCHE DE SYNTHESE EN LIGNE BASÉE SUR UNE MODELISATION STRUCTURÉE DE LA PARTIE OPERATIVE ON-LINE SYNTHESIS APPROACH BASED ON A STRUCTURED PLANT MODELLING A. Philippot, A. Tajer, F. Gellot, V. Carré-Ménétrier Centre de Recherche en STIC (CReSTIC), Moulin de la Housse B.P. 1039, 51687 REIMS Cedex 2, FRANCE. Tel: +33.3.26.91.32.26, Fax: +33.3.26.91.31.06 {alexandre.philippot, abdelouahed.tajer, francois.gellot, veronique.carre}@univ-reims.fr Résumé: Les travaux présentés dans cet article reposent sur une approche de synthèse de commande optimale basée sur la spécification de la commande en grafcet et sur les modèles de la partie opérative et des contraintes à respecter par le système. Pour améliorer la praticabilité de l’approche sur des systèmes complexes et réels, nous proposons une méthodologie de modélisation de la partie opérative ainsi qu’une approche en ligne de la synthèse de la commande. Ces deux points sont formalisées dans l’article et traités à travers un exemple. Abstract: This paper is based on an approach of synthesis and optimal control. For a given Grafcet, a plant and constraints models, this method must respect the process evolution. We developed two improvements of this approach to be used on complex real systems. The new results obtain concern the plant modelling and the on-line synthesis. Formal algorithms and an example are presented in the paper. Keywords: Automata, Grafcet, Control synthesis, Plant modelling, Supervisory control theory, On-line synthesis. 1. INTRODUCTION The objective of our work is to generate the required correct controller implementation for a given Grafcet (IEC 60848, 2002). This controller must to respect a number of safety and liveness constraints related to the modelled plant. The method is based on the use of a supervisor and a controller. The supervisor enforces the given safety constraints, whereas the controller directs the system to accomplish a specific set of tasks. An intuitive presentation of the different steps involved is given below, the formal algorithms can be found in (Carré-Ménétrier, et al., 1999). The first step consists of modelling the plant behaviour, the safety and liveness constraints using automata. The specification of the control behaviour is described by Grafcet. The second step is used to generate the optimal controller by an intersection. This step is realised between the controller, the plant and constraints models (Carré- Ménétrier, et al., 1999). The maximum reactive non-blocking execution controller is then generated. The last step consists of implementing the correct controller by taking into account the constraints. The proposed implementation architecture executes the correct controller and correspondingly updates the state of Grafcet. This step allow to visualise the execution of the control model and to highlight the corrections induced by the synthesis framework. We showed the applicability of this method on several examples (Carré-Ménétrier, et al., 1999), (Philippot, et al., 2003). However, to be practicable on complex real systems, this approach encounters two problems. The first is lied in the plant modelling which is realised without methodology. The second in computational complexity of the oof- line synthesis. The aspects related to the plant modelling are presented around an example (fig. 1) in Section 2 by an adaptation of Chandra modelisation (Chandra and Kumar, 2001). Section 3 is dedicated to a particular synchronisation algorithm which proposes an off-line synthesis approach. The contribution of the present paper is the establishment of the on-line synthesis formalization in Section 4. 2. METHOD OF PLANT MODELLING Our previous works showed that some knowledge of plant behaviour is required to be able to identify and to treat deadlocks. It is necessary to make the image of the plant explicit, by connecting an appropriate abstract model for each of its elements. Hence, a modular approach is required to extract a simple model for each of the elements of the plant. Such a model can be derived using automata that accept the control actions, and react by changing the logical values of Grafcet inputs. The behaviour of the plant is modelled by means of the spontaneous event generators of the supervisory control theory (Wonham and Ramadge, 1987). However, this requires the use of an adequate methodology for the modelling of the plant, which is proposed in this paper. This methodology can be considered as an adaptation of Chandra’s approach (Chandra and Kumar, 2001) to be concistence with ours. The activation and deactivation of Grafcet actions correspond to controllable events ∑c. This because of the possibility to prevent their occurrence by an appropriate conditioning of Grafcet actions. Uncontrollable events, ∑u, are initiated by the plant. These events (∑c and ∑u), which cannot be disabled by control action, are associated with the rising and falling edges of Grafcet inputs. This interpretation can be considered as an adaptation of Balemi’s scheme (Balemi, et al., 1993) to the case of Grafcet. The adapted methodology is based on occurrence rules and precedence relations. These rules define the interactions between controllable or uncontrollable events. The precedence relations specify the links between the uncontrollable events. The user define the rules and relations which are translated into automata compatible with our synthesis approach. 2.1. Occurrence Rules and precedence relations To determine the occurrence rules, it is necessary : (i) to fix the initial conditions of the system from the inputs vector of the controller model, (ii) to determine all the events related to the element of plant, (iii) to define with rules, the influence of the activation and the deactivation of the controllable events on the uncontrollable events. Each rule is a "cause/consequence". The cause relates the controllable event to the consequence (uncontrollable event). For each occurrence rule with the same cause, the chronology between the consequent uncontrollable events are established with precedence relations. For the pneumatic gripper example (fig. 1), the complete model consists of 3 automata. They describe respectively the horizontal movement, the vertical movement and the movement of aspiration. These models take account of the cylinders technology. For the horizontal movement, there are two controllable events GO_RIGHT and GO_LEFT, and two uncontrollable events left and right. In initial situation, the cylinder is on the left and no order is sent to the plant. To define the occurrence rules, the consequences of the sent Movement with aspiration without aspiration Grip position Removal position GO_LEFT GO_RIGHT GO_DOWN A pneumatic gripper system illustrated this paper. This system takes a pinion in a drawer and put down the pinion on an axis. The catch is carried out by a venturi. The complete characteristics are given in http://www.lurpa.ens-cachan.fr/cosed/. Fig. 1. Characteristics of the pneumatic gripper orders must be observed. The GO_RIGHT order activation makes possible the displacement of the cylinder to move towards the line and to leave the left position. The chronology of the uncontrollable events is the following one : deactivation of left then activation of right. The parameters are presented in table 1. Initial Conditions Occurrence rules Precedence relations ↓ GO_RIGHT ↑GO_RIGHT → ↓ left ↑GO_RIGHT → ↑right ↓ left precede ↑right ↓ GO_LEFT ↑GO_LEFT → ↓right ↑GO_LEFT → ↑left ↓ right precede ↑ left ↓ right ↓GO_RIGHT → ↑ right nothing ↑left ↓GO_LEFT → ↑left nothing Table 1. Parameters of the horizontal movement 2.2. Plant automaton construction The plant automaton construction is based on rules and relations which is carried out according to 4 following steps : 1. To build the automaton with 2n states (n is the number of controllable events) describing all the possible evolutions of the controllable events starting from the initial conditions. 2. To add to this automaton the uncontrollable events resulting from occurrence rules, 3. To build a precedence automaton starting from the precedence relations and initial situation between the uncontrollable events, 4. To make the synchronous cross product of the automaton resulting from the occurrence rules and the precedence automaton. This method of modelling is carried out for each part of the system. The complete model of plant is obtained then by asynchronous composition of all the elementary models. For the horizontal movement, the one step consists in establishing a 4 states automaton. The evolutions between states are related to activation or deactivation of the GO_RIGHT and GO_LEFT orders (fig. 2.a). The second step respects the occurrence rules defined by the user and permits to supplement this automaton by the uncontrollable events left and right (fig. 2.b). With the precedence relations, the third step gives the second automaton 0 1 ↑ GO_RIGHT ↓ GO_RIGHT ↑ GO_LEFT 2 ↓ GO_LEFT ↑ GO_LEFT 3 ↓ GO_LEFT ↑ GO_RIGHT ↓ GO_RIGHT 2 1 ↑ left ↑ right 0 ↓ left ↓ right Σc Σc Σc 1) Automaton of the controllable events 2) Automaton with the taking into account of the uncontrollable events 3) Precedence automaton 4) Final automaton of the horizontal movement ↓ left ↑ right ↑ left ↓ right 0 1 ↑ GO_RIGHT ↓ GO_RIGHT ↑ GO LEFT 2 ↓ GO_LEFT ↑ GO LEFT 3 ↓ GO_LEFT ↑ GO_RIGHT ↓ GO_RIGHT ↓ left ↑ right ↑left ↓right ↑ right ↑ right ↑ left ↑ left ↓ left ↑ right ↓right 0 1 ↑ GO_RIGHT ↓ GO_RIGHT 2 ↓ GO LEFT ↑ GO_LEFT 3 ↑ GO_RIGHT ↓ GO_RIGHT ↑ GO_LEFT ↓ GO LEFT 4 6 ↑ GO_RIGHT ↓ GO_RIGHT 5 ↓ GO LEFT ↑ GO_LEFT 8 ↑ GO_RIGHT ↓ GO_RIGHT ↑ GO_LEFT ↓ GO LEFT 7 10 ↑ GO_RIGHT ↓ GO_RIGHT 9 ↓ GO LEFT ↑ GO_LEFT 11 ↑ GO_RIGHT ↓ GO_RIGHT ↑ GO_LEFT ↓ GO LEFT ↑ right ↑ left ↓ left ↓ right ↑ right ↑ right ↑left Fig. 2. Horizontal movement automaton presented figure 2.c. Each state of this automaton authorizes all the events related to the plant element model. A synchronous cross product between the automaton resulting from step 2 and the precedence automaton resulting from step 3 allow to obtain the final automaton (fig. 2.d). The movement is then described in a complete way independently of the controller through 12 states and 35 transitions. The automata of the vertical movement and aspiration movement are established in an identical way. The plant automaton is obtained by asynchronous product cross of these elementary models and corresponds to an automaton of 288 states and 2184 transitions. 2.3. Modelling of the constraints We can use this methodology for the modelling of the constraints. We need only to extend the definitions of the occurrence rules and the precedence relations given previously. The occurrence rules define a link between the controllable events and the uncontrollable events and these events can be “cause” or “consequence”. The precedence relations relate the same types of events. (Philippot et al, 2004). We defined two types of constraints. The safety constraints between controllable events themselves use directly precedence relations. The liveness constraints establish a link between controllable events and uncontrollable events. Consequently, the modelling depends on the type of constraints to model. The plant and constraints models are used to obtain the automaton SUP. This automaton corresponding to the supremal language of the supervised plant by applying the synthesis algorithm proposed in (Kumar, 1991). The transition structure of SUP represents the maximum permissible behaviour of the controlled plant with respect to the given constraints. At the same time, the automaton of stable situations, GSS, of Grafcet, deterministic and reactive, is extracting by applying the algorithm given in (Roussel, 1994). 3. PRINCIPE OF OFF-LINE SYNTHESIS The synthesis framework is based on the use of a controller and a supervisor. A dedicated intersection algorithm extracts the sequences of events that can be generated both by the controller, GSS, and by the supervisor, SUP. This algorithm results in an event-based automaton SYNC. A reduction algorithm allow to remove the deadlocks of SYNC and to generate the control-execution model. The intersection step generate the automaton SYNC representing the behaviour common to the automata SUP and GSS. The evolutions of the control model, GSS, are authorised by the supervisor, SUP. Each state in GSS is associated with the orders of the corresponding situation of Grafcet. The transitions of GSS are given in terms of logical expressions combining input variables and their edges. On the other hand, SUP is an elementary automaton whose transitions correspond to simple events. The intersection algorithm goes through the events that can be accepted by GSS and SUP to construct SYNC. Only the control evolutions that are acceptable by the supervisor are retained in automaton SYNC. The states of SYNC relating transitions are grouped into a region, which corresponds to the given Grafcet situation. The intra-region transitions correspond to controllable events and the inter-region transitions represent uncontrollable events. The interleaving of parallel orders, inside a region, is used here to provide an event-based semantics to SYNC. This, in view of simplifying the formal development of the intersection procedure. The reduction step is used to generate the maximum reactive non-blocking execution controller by removing all the blocking situations from SYNC. The resulting automaton (OPT) represents the most permissive sub-set of the behaviour of Grafcet. OPT is both non-blocking, and satisfies the given safety and liveness specifications. Each state of this automaton corresponds to an aggregation of the states of a region of SYNC after the removal of blocking evolutions. The states of OPT correspond to the stable situations of the controller to be implemented. They contain information about the active Grafcet steps. The outputs are simultaneously activated and deactivated in the corresponding situation. The transitions of OPT correspond to uncontrollable events whose effect is to drive the controller from one stable situation to another. In the worst case, the size of the automaton OPT is proportional to |GSS|×|SUP|×2Σu/2 , where |GSS| and |SUP| represent the number of states of the automaton GSS and SUP respectively. Here, the off-line synthesis approach results in an exhaustive control implementation model. This one requires a very large memory in the case of complex systems. An alternative on-line synthesis approach has therefore been proposed to reduce the size of such an exhaustive model. The on-line synthesis proceeds by successive calculations of a partial control implementation model for a temporal window. 4. ON-LINE SYNTHESIS Partial intersection window of size N=2 region 0 region 4 region 3 Controllable transition Uncontrollable transition Deadlock state region 2 Fig. 3. Semantic model of a partial intersection In 1992, (Chung, et al., 1992) implements an on- line scheme which is basis of an N-step ahead projection of the behaviour of the process. For us, the on-line synthesis is based on the three steps of the off-line approach among which the first (modelling, synthesis and extraction) is identical to the off-line. Consequently, the procedure of control generation is based on a partial intersection step between SUP and GSS for a number of anticipated future evolutions. The step of treatment of blocking situations results from this partial intersection. A partial automaton represents the anticipated control implementation model of anticipated future evolutions. 4.1. Principle of the partial intersection. The partial intersection procedure consists to construct the common behaviour of GSS and SUP starting from their current state from anticipated future evolutions. The method give in result an automaton SYNCN where N represents the step of calculation. N is the future possible reactions of the plant from courant situation of the system. For a partial intersection window where the size is limited by the value of N, the automaton SYNCN , like SYNC, is constituted by regions, intra-regions transitions and inter-regions transitions. The SYNCN construction is in real time on a limited part of the controller and gives an unfinished automaton (fig. 3). Thus, while being interested only in the number of uncontrollable events Σu, the automaton SYNCN is constructed compared to futures reachable situations of Grafcet. Consequently, for a region reached, all actions associate to the corresponding Grafcet situation are taken into account. The states of SYNCN with no output transition are blocking states. 4.2. Formalization of the partial intersection The automaton SYNCN is defined by a 9-uplet (Σ, ST, TR, st0, r0, f0, BLOC, EM, RD) with: - Σ = Σc ∪ Σu, Σc = ↑Z ∪ ↓Z et Σu = ↑E ∪ ↓E. In the continuation, ↑z corresponds to an element of ↑Z, ↓z with an element of ↓Z, ↑e with an element of ↑E and ↓e with an element of ↓E. - ST is the whole of the states of SYNCN . ST is partitioned in subsets called regions. A state st∈ST corresponds to a single configuration of the 3-uplet (q, y, E). q is a state of SUP, y a state of GSS and E the whole of the logical values (0 or 1) of the inputs of Grafcet. All the states corresponding to a situation of Grafcet and a single configuration of its inputs variables are grouped in a region. These regions can be grouped in a window of partial intersection whose size depends on N. - TR: ST × Σ → ST is a partial function representing the transitions from SYNC. A transition is defined by a triplet (st, σ, st') ∈TR. - st0 ∈ ST is the initial state which is given by (q0, y0, E0). q0 is the initial state of SUP, y0 the initial state of GSS and E0 corresponds to the whole of the initial values of the inputs of Grafcet. - r0 ⊂ ST is the initial region corresponding to the initial situation y0 of GSS and to the initial values E0 of its inputs variables. This region includes the initial state st0. - BLOC ⊂ ST contains the whole of the blocking states, i.e. those not having outgoing transitions. - EM ⊂ ST contains the whole of the states and the marked regions. - RD ⊂ ST contains the whole of the already developed regions. The automaton SYNCN is generated by means of the following iterative algorithm (Philippot, 2002). When no window of intersection can be created anymore, the procedure is terminated. Step 1: To develop the window of initial partial intersection f0 starting from the initial region r0. Step 2: To develop a window of partial intersection unspecified fc. This algorithm receives as an input the automaton SUP, GSS and the initial structure of the automaton SYNCN , given by (Σ, {st0}, ∅, st0, {st0}, {st0}, ∅, ∅, ∅). SUP = (Σ, Q, ∆, q0) corresponds to the supervisor generated by the synthesis step. The automaton GSS = (E, S, Y, T, y0) is the equivalent of the Grafcet. In the following, the current state of SYNCN is characterised by the current state of SUP, the current situation of GSS, as well as the current valuation of the input variables. The iterative procedure corresponding to step (n) is given in figure 4. This procedure creates the states and the transitions of the initial region r0. In the second step (o), as long as the number of uncontrollable events running Ncou is lower or equal to N, it is about: A) To develop the inter-regions transitions and to create the first state of each regions downstream. If Ncou = N-1 then the states and the regions upstream of the transition are safeguarded in the set of marked states EM. The regions downstream are gathered in the set of developed regions RD to avoid the developments for the next step. B) To safeguard the states blocking in BLOC. Ncou = 0 n /* To develop the initial region */ ∀st = (q, y0, E0) ∈ r0 such as r0 ∈ f0, ∀(q, Σ, q') ∈ ∆ such as (Σ = ↑Z ∧ Z ∈ Zy0) Do : i) ST = ST ∪ st' with st' = (q', y0, E0); ii) TR = TR ∪ {(st, Σ, st')}; iii) r0 = r0 ∪ {st'}; iv) f0 = f0 ∪ r0; ∀st = (q, y0, E0) ∈ r0 such as r0 ∈ f0, ∀(q, Σ, q') ∈ ∆ such as (Σ = ↓Z ∧ Z ∉ Zy0) Do : i) ST = ST ∪ st' with st' = (q', y0, E0); ii) TR = TR ∪ {(st, Σ, st')}; iii) r0 = r0 ∪ {st'}; iv) f0 = f0 ∪ r0; o While Ncou ≤ N Do : A) /* To develop the inter-region transitions supported by the events ΣU and to create a new region */ ∀st = (q, y, E) ∈ rr Do : 1 ∀(q, ↑e, q') ∈ ∆ such as (e∈ E ∧ e = 0) Do : - If ∃ (((y, f(E), y') ∈ T) such as will f(E) = vrai) Then st' = (q', y'', E') ∧ (y'' = y') Else st' = (q', y'', E') ∧ (y'' = y) where the value of E' is distinguished from E only by the value of E which becomes 1 instead of 0; - TR = TR ∪ {(st, ↑E, st')}; - If st' ∉ ST Then i) ST = ST ∪ {st'}; ii) to create the region r = {st'} ⊂ ST; iii) f0 = f0 ∪ r; - If Ncou = N-1 Then EM = EM ∪ {st}, EM = EM ∪ {rr}, RD = RD ∪ {r}; /* marking for the future intersection */ 2 ∀(q, ↓e, q') ∈ ∆ such as (e∈ E ∧ e = 1) Do : - If ∃ (((y, f(E), y') ∈ T) such as will f(E) = true) Then st' = (q', y'', E') ∧ (y'' = y') Else st' = (q', y'', E') ∧ (y'' = y) where the value of E' is distinguished from E only by the value of E which becomes 0 instead of 1; - TR = TR ∪ {(st, ↓E, st')}; - If st' ∉ ST Then i) ST = ST ∪ {st'}; ii) to create the region r = {st'} ⊂ ST; iii) f0 = f0 ∪ r; - If Ncou = N-1 Then EM = EM ∪ {st}, EM = EM ∪ {rr}, RD = RD ∪ {r}; /* marking for the future intersection */ B) If ¬( ∃ (st, σ, st') ∈ TR) Then BLOC = BLOC ∪ {st} /* To memorize the blocking states */ C) /* To develop an unspecified region rC such as f0 = f0 ∪ rC */ 1 ∀(q, yC, EC) ∈ rC such as rC ∈ f0, ∀(q, Σ, q') ∈ ∆ such as (Σ = ↑Z ∧ Z ∈ Zyc) Do : - If st' ∉ ST with st' = (q', yC, EC) Then i) ST = ST ∪ {st'}; ii) rC = rC ∪ {st'}; iii) f0 = f0 ∪ rC; - TR = TR ∪ {(st, Σ, st')}; 2 ∀(q, yC, EC) ∈ rC such as rC ∈ f0, ∀(q, Σ, q') ∈ ∆ such as ( Σ = ↓Z ∧ Z ∉ Zyc) Do : - If st' ∉ ST with st' = (q', yC, EC) Then i) ST = ST ∪ {st'}; ii) rC = rC ∪ {st'}; iii) f0 = f0 ∪ rC; - TR = TR ∪ {(st, Σ, st')}; D) Ncou = Ncou + 1/* To increment the number of ΣU running */ Fig. 4. Development of the initial window f0 C) To develop each region downstream according to a principle similar to n, these new regions belong to the initial window of partial intersection. The algorithm associated at the development of an unspecified window breaks up into 2 steps (fig. 5). The first step (n) consists in recovering the information already developed in the preceding partial intersection. It is about: A) To recover the states and the regions marked in the intersection preceding and pertaining to EM. B) To recover the already developed regions assemble in RD. C) To initialise sets EM and RD for the future safeguards for the development of another unspecified window fc. The second step (o) corresponds to o algorithm of development of the initial window (fig. 4). Ncou = 0 n /* Recovery of the information calculated by the preceding intersection */ A) /* Recovery of the states and the region marked */ - ∀st = (q, y, E) ∈ rC such as {st, rC} ∈ EM Do : fC = fC ∪ rC; B) /* Recovery of the already developed region */ - ∀(st, ↑e, st')∈TR such as (st ∈rC and rC∈EM) and (st'=(q',y',E')∈r and r∈RD) and E' is distinguished from E only by the value E which becomes 1 instead of 0 Do : fC = fC ∪ r; - ∀(st, ↓e, st')∈TR such as (st ∈rC and rC∈EM) and (st'=(q',y',E')∈r and r∈RD) and E' is distinguished from E only by the value E which becomes 0 instead of 1 Do : fC = fC ∪ r; C) EM = ∅ and RD = ∅ ; /* Initialization of sets EM and RD */ o While Ncou ≤ N Do : A) /* To develop the inter-region transitions and to create a new region */ B) /* To memorize the blocking states */ C) /* To develop an unspecified region rc such as fc= fc ∪ rC */ D) Ncou = Ncou + 1; /* Incrementing of the number ∑u running */ Fig. 5. Development of an unspecified window fc 4.3. Treatment of deadlocks and generation of the automaton of partial controller By analogy with the off-line synthesis, the principle of treatment of deadlocks consists in withdrawing the blocking states of SYNCN . This states are identified by the set BLOC, as well as the transitions making it possible to reach these states. The removal of these blocking evolutions can possibly generate a controller for a number of evolutions lower than N. This step makes it possible to generate the automaton of partial controller OPTN . The reduction of the size of the automaton of controller OPTN is significant compared to an off- line approach. In the case of a on-line synthesis, in worst case, the number of states proportional to (|Σu|/2)N . For complexes systems, the profit memory capacity is then considerable. Concretely, as soon as the process generates an output, a new partial intersection/reduction is developed for a step moreover, and the automaton is updated. Consequently, the architecture of establishment rests on the execution in parallel of two modules. The first module of on-line calculation of the controller carries out during the execution of the controller, a development for a step moreover. The second module of execution of the elaborate controller. Thus, the computing time of SYNCN and OPTN influences the least possible the reactivity of the order. However, in spite of the optimisation of the size memory, the on-line synthesis does not guarantee the absence of deadlocks during operation. Indeed, since a partial intersection takes into account only one limited window of future evolutions of the system, no detectable deadlocks in the current window can occur at the time of the following partial intersections. By increasing size N of the window, these possible blocking states will be avoided or detected sufficiently early to be able to anticipate actions of correction. Consequently, the choice of N constitutes a compromise between the risk of deadlocks and the memory capacity necessary to the establishment of the elaborate controller. The objective is now to establish a comparison between off-line and on-line synthesis for highlighting the profit in memory capacity.The table 2 recapitulates the sizes of the various automata for the pneumatic gripper. GSS Process Constraints SUP 11 states 13 trans. 288 states 2184 trans. 64 states 880 trans. 96 states 416 trans. Table 2. Result of the various automata For the simple example of pneumatic gripper, the step of generation of the order calculated off-line provides an automaton SYNC made up of 106 … Off-line synthesis 30 states, 106 transitions 52 states, 106 transitions SYNC OPT OPT2 SYNC2 4 states, 3 transitions 3rd partial intersection 2nd partial intersection 1st partial intersection On-line synthesis 5 states, 5 transitions 6 states, 6 transitions 6 states 6 transitions 6 states, 6 transitions 11 states, 10 transitions … … Table 3. Automata generated off-line and on-line transitions and 52 states grouped in 30 regions. The controller automaton OPT includes 30 states and 62 transitions. For a window of N=2 steps, the first partial intersections is given table 3. We represented the optimal controller (OPT2 ) in the figures 6.a and 6.b. In each state is associated the set with the orders to send (ORD) and to prohibit by OPT (PROH). These sets are used to inform the user about the orders, which are maintained, or not by the synthesis procedure. The first region of SYNC corresponds to state 0 of OPT (fig. 6.a) where no order is sent. The two states of the second region are aggregate in a single state1 where the order sent during the execution is GO_DOWN, no order is prohibited. {{ GO_DOWN, VENTURI}, ∅} ↑dcy ↓dcy ↓high 4 1 0 2 a ↑low ↓high 6 5 ↓high 4 1 2 b ↓dcy ↓dcy {∅, ∅} {{GO_DOWN },∅} {∅, ∅} {{ GO_DOWN }, ∅} {{ GO_DOWN }, ∅} {∅, ∅} {∅, ∅} {{ GO_DOWN }, ∅} In each state is associated {ORD, PROH} Fig. 6. Partial automata of controller (OPT2 ) The increase in the size of the window generates an increase in the number of states and transitions. Also a reduction in the number of intersection is a risk of reappearance of the problems involved in the off-line synthesis. A study on the choice of value N remains to be developed. 5. CONCLUSION This paper present an approach for off-line and on- line synthesis of an optimal control implementation. This method must respect a number of safety and liveness constraints for a given Grafcet. The resulting controller can be viewed as a programing executing Grafcet in accordance with deterministic and reactive semantics. Our current research proposes to enhance the practicability of the proposed formal framework. This, by adapting a dedicated assistance methodology for the modelling of the plant and an extension for the constraints. The user specifies the occurrence rules and the precedence relations. These rules are automatically translated into automata compatible with the supervisory theory. For complex systems, the off-line synthesis approach requires a "huge" memory size for the implementation. We present the formalization of the on-line approach which overcomes this limitation. However, deadlocks are not guaranteed to be avoided in this case. Our future work must implement an heuristics to choose a pertinent value for the number of required evolutions. This, in the aim to avoid deadlocks and to guarantee a maximum "acceptable" size of the partial implementation. 6. REFERENCES Balemi S., Hoffmann G.J., Gyugyi P., Wong H., Franklin G.F., "Supervisory control of has rapid thermal multiprocessor", IEEE Transactions one Automatic Control, vol. 38, n°7, p. 1040-1059, 1993. Carré-Ménétrier V., Ndjab-Hagbebell C., Gellot F., Zaytoon J., "A case tool for the synthesis of optimal control implementation of Grafcet", IEEE International Conference on Systems, Man and Cybernetics, Tokyo-Japan, p.796-801, october 1999. Chandra V., Kumar R., "A Discrete Event Systems Modeling Formalism Based one Event Occurrences Rules and Precedences", IEEE Transactions one Robotics and Automation, vol. 17, n°6, 2001. Chung S.L., Lafortune S., Lin F., Limited lookahead policies in supervisory control of discrete event systems. IEEE Transactions on Automatic Control, vol. 32, Issue : 12, p.1921- 1935, December 1992 IEC 60848 (International Electrotechnical Commission), Preparation of function charts for control systems. Publication 848, 2002. Kumar R., "Supervisory Synthesis Techniques for Discrete Event Dynamical Systems", Thesis for pH D. degree, University of Texas, August 1991. Philippot A., "Implantation d’une commande sûre dans un Automate Programmable Industriel à partir d’une spécificationexprimée en Grafcet", Memory of DEA, Reims, September 2002. Philippot A., Tajer A., Gellot F., Carré-Ménétrier V., "Synthèse de la commande spécifiée en Grafcet : application à un préhenseur pneumatique", MSR' 03, Metz, France, p.61-75, 2003. Philippot A., Tajer A., Gellot F., Carré-Ménétrier V., "Méthodologie de modélisation dans le cadre de la synthèse formelle des SED", submitted to CIFA’04, 2004. Roussel J.M., "Analyse de Grafcet par Génération logique de l’Automate Equivalent", Thesis for pH D. Degree, ENS Cachan, 1994. Wonham W. M., Ramadge P.J., "On the supremal controllable sublanguage of a given language", SIAM J Control Optimization, flight 25, n°3, p.637-659, 1987. Acknowledgments: A first version of this paper was published at IFAC Workshop on Discrete Event Systems, WODES'04, 22-24 September 2004.