Download GRAFCET and Petri Nets Outline Introduction GRAFCET
Transcript
Outline GRAFCET and Petri Nets introduction GRAFCET GEMMA Petri nets Prof. J.-D. Decotignie CSEM Centre Suisse d’Electronique et de Microtechnique SA Jaquet-Droz 1, 2007 Neuchâtel [email protected] Real-Time Programming Introduction Description of process evolution Description of process interaction Graphe de Commande Etape Transition (Step Transition Control Graph) 2 levels Functional specifications Requirements for automata ) GRAFCET Real-Time Programming © J.-D. Decotignie, 2007 GRAFCET ) Petri nets GRAFCET and Petri nets 2 GRAFCET and Petri nets 3 © J.-D. Decotignie, 2007 Functional specification Operational specification Described in the international standard IEC 848 under the name of function charts [Dav90] R. David, A. Alla, « Petri nets and Grafcet", Prentice Hall, 1992. R. David, Grafcet: a powerful tool for specification of logic controllers, IEEE Trans. on Control Systems Technology, vol. 3, Issue 3, Sept. 1995, pp.253 - 268 Real-Time Programming GRAFCET and Petri nets 4 © J.-D. Decotignie, 2007 GRAFCET GRAFCET - definition Definition Evolution rules Defining actions Taking time into account Defining transition conditions Execution algorithm Macrostep and macroactions Quadruple C = {S, TR, A, M0} N steps si ∈ S; each step si may be active (Xi= true) or not (Xi=false). M0 denotes the set of steps active at startup L transitions tri ∈ TR; to each transition is associated a boolean condition (receptivity) Steps and transitions are linked by arcs ai ∈ A L=1 GRAFCET and Petri nets 5 Real-Time Programming 1 Directed graph derived from PN © J.-D. Decotignie, 2007 Exercise - syntax b1 2 L=0 /b1 + EVOLUTION CONDITIONS GRAFCET and Petri nets 6 Real-Time Programming © J.-D. Decotignie, 2007 Exercise - syntax (2) a a A F Real-Time Programming B a G a a C D a b a H GRAFCET and Petri nets 7 b a E K a b I © J.-D. Decotignie, 2007 a L M O P a b N Real-Time Programming a GRAFCET and Petri nets 8 © J.-D. Decotignie, 2007 Exercise - syntax (3) GRAFCET – an example Loading place m request A a B OP G b D p a b a b Q a R Q 1 F O N C T I N A L Load used / waiting in A Load requested 2 Go to right Arrived at right 3 Control part m loading Loading terminated 4 a b Go to left GRAFCET and Petri nets 9 © J.-D. Decotignie, 2007 Evolution Conditions all steps immediately preceding the transition must be active, the transition is then enabled then, if receptivity is true, the transition may be cleared all transitions that may be cleared are cleared simultaneously clearing a transition leads to the activation of all immediately following steps and deactivation of all immediately preceding steps a step that is activated and deactivated remains active 1 2 D b 3 OP p 4 G a © J.-D. Decotignie, 2007 (1) © J.-D. Decotignie, 2007 5 3 a (2) 2 b (4) (3) 6 a=1 clearing 1 a (2) 7 6 4 7 b=1 clearing 5 5 (34) a (3) b (4) 6 b b b=1 clearing 3 Real-Time Programming 5 (34) a 4 2 GRAFCET and Petri nets 11 m Evolution Conditions (2) (1) Real-Time Programming 1 GRAFCET and Petri nets 10 Real-Time Programming Evolution is performed from the initial state defined as M0 by clearing transitions according to 5 rules: D G OP Operative part (wagon, door,... Arrived at left Real-Time Programming p O P E R A T I O N A L b b 7 GRAFCET and Petri nets 12 6 7 © J.-D. Decotignie, 2007 Exercise - transitions Exercise - transitions (2) A. enabled transitions; B. firable transitions if a=1 and b=0; C. state after clearing the transitions when possible a a /a /a A B C D A. enabled transitions; B. firable transitions if a=1 and b=0; C. state after transition when possible a./b a.b a a./b I /b /b G H GRAFCET and Petri nets 13 Real-Time Programming J K L a a./b F a./b E M © J.-D. Decotignie, 2007 Conflicts b N GRAFCET and Petri nets 14 Real-Time Programming © J.-D. Decotignie, 2007 Exercise: is there a conflict ? 5 (3) a 6 (4) b 1 7 4 /a.c a.b 5 (3) a./b 6 (4) b a./b 5 A /a.b ab 3 a.c a.b 6 8 B /a.b a 9 /a./b 10 C 7 6 Real-Time Programming 2 5 7 GRAFCET and Petri nets 15 7 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 16 © J.-D. Decotignie, 2007 Divider by 2 Examples of logical graphs a 1 m S a 1 (1) 2 (2) G (A) S 1 a (1) ↑a (1) 2 a' a S Controlling system ↑a (2) Real-Time Programming © J.-D. Decotignie, 2007 Example (2) b (1) b (3) ↑m.a 2 3 G a 1 V (2) a GRAFCET and Petri nets 18 Real-Time Programming V b © J.-D. Decotignie, 2007 Increment a counter m reservoir Initial conditions Tanks empty, valves closed Sensors and actuators Arrived on left ↑m 2 D 3 GRAFCET and Petri nets 17 (1) ↑m (2) Go to left 1 2 S Go to right Arrived on right 3 (3) (3) (B) 1 4 2 S 3 (4) D (2) a' (3) b ↑a a m pressed (1) Vi, Wi = 1 if open h1 hi, bi = 1 if level above sensor operations: tank 1 b1 Fill each tank until above hi, close valve Vi and open Wi until level below bi . Procees cannot be repeated before both tanks are empty Real-Time Programming V2 V1 h2 GRAFCET and Petri nets 19 =1 3 (3) a Stable situation (C←0)* ↑a (2) W2 © J.-D. Decotignie, 2007 (C←0)* 2 tank 2 b2 W1 1 (1) (C←C+1)* {2} {3} {2} {3} (C←C+1)* ↑a Real-Time Programming GRAFCET and Petri nets 20 © J.-D. Decotignie, 2007 Example (cont) (B) 4 (A) 2 (2) V1 h1 3 (3) (4) 6 4 V2 2 (2) W2 V1 h1 h2 (5) /b1 3 (3) 2 5 /b1 V2 (4) W1 h2 6 V1 h1 3 tank 1 (2) a 6 tank 2 (2) b T=10s X5 b X6 10s V2 5 h1 (4) t/6/10s h2 20s t/6/20s 34 W1if b1 67 W2if b2 b2 W1 /b1./b2 (6) W2 GRAFCET and Petri nets 21 Real-Time Programming W2 /b2 (D) V1 2 V2 b1 a 5 ↑m (1) h2 6 1 =1 h1 V2 h2 (3) m V1 5 (5) /b1 /b2 reservoir ↑m .X4 (4) W1 (3) W2 (5) /b2 7 (6) 7 ↑m .X7 (1") (2) 5 W1 ↑m (1) ↑m (1) 4 7 (1') 1 Taking time into account (C) © J.-D. Decotignie, 2007 GRAFCET and Petri nets 22 Real-Time Programming Timer behavior © J.-D. Decotignie, 2007 Continuous actions (à niveau) a 5 1 a (2) i Xi Δ Δ Δ Δ (3) a (1) T=Δ b a b Action A 2 (2) (3) X2 X4 a Action A if C 4 action A b Δ b 3 (4) b c action A t/i/Δ a 5 ↑t/i/Δ (5) a 6 (6) Real-Time Programming GRAFCET and Petri nets 23 © J.-D. Decotignie, 2007 a 7 b b (7) X6 T=Δ; ActionA if t/6/Δ Real-Time Programming t/6/Δ action A Δ b a 8 (8) GRAFCET and Petri nets 24 b X8 T=Δ; ActionA if (t/8/Δ)' t/8/Δ Δ action A © J.-D. Decotignie, 2007 Duration of a continuous action Pulse shaped actions c1 Continuous actions are only defined for stable situations 3 (2) (2) Action A 6 b c3 open P* c2 (4) X6 X4 (5) X5 c3 6 action A c4 X3 5 X5 a (3) (3) b 5 c1 4 a c2 close P* X6 open P* c4 close P* P open Real-Time Programming GRAFCET and Petri nets 25 © J.-D. Decotignie, 2007 Conditional Pulse Shaped Actions X3 (3) a Action A* if b 3 (4) c Continuous actions (à niveau) unconditional conditional A* if b=1 when ↑X3 A* when X3=1 as soon as b=1 A* when ↑(X3.b) A* if b is ambiguous. Unsufficient notation !! We shall not keep this capability Real-Time Programming GRAFCET and Petri nets 27 © J.-D. Decotignie, 2007 Actions types b GRAFCET and Petri nets 26 Real-Time Programming Pulse shaped actions © J.-D. Decotignie, 2007 Condition is a boolean variable Condition is based on a timer Always unconditional Real-Time Programming GRAFCET and Petri nets 28 © J.-D. Decotignie, 2007 Exercise: drilling machine Actions and outputs h: upper position Controlling part High speed E High speed up b1: end of approach Working speed h (calculations, timers,..) C* b1 D High speed b3 b1: end of approach Working speed High speed up High speed up Working speed m Operator or supervising system b2: end of deburring GRAFCET and Petri nets 29 © J.-D. Decotignie, 2007 Transition conditions Real-Time Programming Relative to the state of a step (Xi) State of the operative part (of the controlling part) condition Ci = boolean combination of variables event Ei = rising (falling) edge of an external variable (e always occurring event) GRAFCET and Petri nets 31 B* GRAFCET and Petri nets 30 © J.-D. Decotignie, 2007 ∀a ∈ {0,1} si a(t)=1 when t ∈ [t1, t2[ et t ∈ [t3, t4[ definition 1: ↑a occurs in t1 and in t3 definition 2: ↓a occurs in t2 and in t4 definition 3: ↑a.b occurs at the same instant as ↑a each time b=1 at this instant definition 4: ↑a.↑b occurs when ↑a and ↑b occur at the same instant receptivity Ri = Ci Ei Real-Time Programming A Coming from the process or from the external world relative to time (t/i/Δ) Internal boolean variables a (processus to control) External boolean variables (described by the graph) Events variables Control part of the controlling part Operative part b3: end of drilling Real-Time Programming b inputs: a,b,m actions: A, B*, D, C* outputs: A, B*, D, E h: upper position b3: end of drilling b2 Operative part of the controlling part © J.-D. Decotignie, 2007 Show that ↑a = ↓a' ↑a.↑a = ↑a Real-Time Programming ↑a.a = ↑a ↑a. ↑a' = 0 ↑a.a' = 0 ↑a.e = ↑a GRAFCET and Petri nets 32 ↓a.a = 0 © J.-D. Decotignie, 2007 Interpretation Algorithm (without stability search) Graph interpretation 1 2 persons in front of the same graph and assuming the same sequence of inputs should deduce the same sequence of outputs. 1. 2. 3. 4. Asumptions: c 2 uncorelated events may not occur at the same time The graph has enough time to reach a stable state before the occurrence of the next event 3 ↑b (7) 4 D =1 (6) G c m.a' (3) ↑a (2) 5 b 2 H D Read the state of the inputs evolve (one or more (1) ↑b simultaneous clearings) 7 G Execute actions (4) c a goto 1 (5) D 6 (8) d d H G GRAFCET and Petri nets 33 Real-Time Programming © J.-D. Decotignie, 2007 (1) 4 a 5 (2) (2) 6 (3) Real-Time Programming b 5 /b /b 6 ↑c (3) GRAFCET and Petri nets 34 © J.-D. Decotignie, 2007 1. initialization: activation initial step(s), execution of associated pulse shaped actions; go to 5 2. If an external event Ei occurs, determine the set T1 of transitions that can be cleared on Ei; if T1≠∅ goto 3, else modify conditional actions and goto 2 3. Clear transitions that can be. If, after clearing, the state is unchanged goto 6 4. Execute the pulse shaped actions that are associated to the step that were activated at step 3 (incl. timers) 5. Determine the set T2 of transitions that can be cleared on occurrence of e. If T2≠∅, goto 3 a ↑a (1) Real-Time Programming Interpretation Algorithm (with stability search) Iterated Clearing 4 D c Stable situation {4} {6} ↑c GRAFCET and Petri nets 35 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 36 © J.-D. Decotignie, 2007 Interpretation Algorithm (with stability search)(2) Interpretation Algorithm (with stability search)(3) 1 6. A stable situation has been reached 1. Determine the set A0 of continuous actions that must be deactivated (incl. conditional actions) 2. Determine the set A1 of continuous actions that must be activated (incl. conditional actions) 3. Set to 0 all the actions that belong to A0 and not to A1. Set to 1 all the actions that belong to A1 4. go to 2 GRAFCET and Petri nets 37 Real-Time Programming © J.-D. Decotignie, 2007 Non stable cycle 1 a (3) 5 (5) 2 a' (1) A a' 4 (6) ↑b (1) G 7 (4) 3 ↑b (7) c =1 (6) D 6 (8) d stage 4: no pulse shaped action stage 5: T2= {(6)} stage 3: clearing (6) stage 4: no pulse shaped action stage 5: T2=∅ stage 6: A0= {H,D}, A1= {D} ...... GRAFCET and Petri nets 38 Real-Time Programming D G 5 4 c (5) ↑a (2) m.a' (3) © J.-D. Decotignie, 2007 Exercise [Dav90] Let H1 and H2 be two wagons carrying goods from loading points C1 and C2 respectively to an unloaded point D. Variables c1,c2 and d correspond to end of track sensors. They turn to 1 when a wagon is present at the given point. Variable a1 turns to 1 when the front wheels of wagon H1 are on the tracks between A1 and D (same for a2 if wagon H2 is between A2 and D). If wagon H1 is in C1 and if button m1 is pressed, a cycle C1 → D → C1 starts with a possible wait in A1 until the track common to both wagons is free, then a wait in D during 100s. Wagon H2 performs the same on C2 → D → C2. The path C1-D is set when V equals 1, otherwise path C2-D is set. b' b (4) stage 1: situation {1,2} stage 5: (1) (2) et (3) enabled, cannot be cleared on e, T2=∅ stage 6: stable situation {1,2}, A0=∅, A1= {H,D} stage 2: m=1, on e, T1= {3} stage 3: clearing (3) stage 4: no pulse shaped action stage 5: T2=∅ stage 6: A0=∅=A1 stage 2: on ↑a, T1= {2} stage 3: clearing (2) 2 H D (2) B b' 12 a (3) 5 (5) (1) A a' b (4) 4 (6) m1 B b' m2 c1 C1 G1 D1 H1 A1 V G2 D2 H2 c2 A2 d D C2 Real-Time Programming GRAFCET and Petri nets 39 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 40 © J.-D. Decotignie, 2007 Macro-step Pseudo macro-step A 4 (4) (4) E30 A 4 6 ↑a' c b 34 D c'.d G 32 V1 31 B 33 V1 31 D 33 c 6 GRAFCET and Petri nets 41 © J.-D. Decotignie, 2007 P1 3 Stop units Normal operations 2 Globaly act on a GRAFCET Do not increase the expression power But ease specification Exhibit same properties as actions P2 5 restart end Forçage(forcing), figeage(freezing), masquage(masking) Pulse shaped Stop unit 2 6 GRAFCET and Petri nets 43 Stop unit 1 end end Continuous Stop request Stop request Real-Time Programming end Normal operations P2 5 Start unit 1 4 end 2 Start unit 2 end start Start of units © J.-D. Decotignie, 2007 System stopped start P51 GRAFCET and Petri nets 42 Real-Time Programming Macro actions 1 System stopped Represents a set of steps All arcs do not necessarily go to the same step (no need for a unique entry step) All arcs do not necessarily go to the same step (no need for a unique exit step) All arcs entering or leaving the pseudo macro-step need be represented G Pseudo macro-step 1 B 30' (5) b S30 Real-Time Programming V1 ↑a' c'.d c b c 34 B ↑a b V1 32 5 M30 (5) 30 B ↑a a.d' a.d' Forcer (force), masquer(mask), démasquer(unmask), figer(freeze), libérer(release) restart © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 44 © J.-D. Decotignie, 2007 Macroaction: Forcing (Forçage) 11 11 X5 a d 5 A 12 forçage G2:{12} b d' ⇔ d 13 B* 11 X5 a d d' 13 B* /a /a © J.-D. Decotignie, 2007 d Masquage G2:{A} 7 d' b ⇔ d 7 G1 G2 Real-Time Programming © J.-D. Decotignie, 2007 Macrocaction : Force (Forcer) 11 ↑X4 a d 12 A if /X7 b d' 13 B* A 12 forcer G2:{12} 4 ⇔ d 4 13 B* G1 © J.-D. Decotignie, 2007 Real-Time Programming G2 ↑X4 a A 12 b d' 13 B* /a /a G12 GRAFCET and Petri nets 47 /a./X6 GRAFCET and Petri nets 46 Real-Time Programming /a /a 13 B* 11 b d' 13 B* b./X6 d' G12 a A 12 A 12 6 13 B* 11 a d /a Macroaction: Masking (Masquage) 11 ⇔ G2 G1 GRAFCET and Petri nets 45 Real-Time Programming b X5 G12 a./X6 A 12 figeage G2 6 b./X5 11 a A 12 5 d' G2 G1 Macroaction: Freezing (Figeage) ↑X4 G12 GRAFCET and Petri nets 48 © J.-D. Decotignie, 2007 Outline GEMMA introduction GRAFCET GEMMA Petri nets Guide d'Etude des Modes de Marche et d'Arrêt Problems with GRAFCET Objectives Concepts How to use GEMMA Advantages Drawbacks GRAFCET and Petri nets 49 Real-Time Programming © J.-D. Decotignie, 2007 Problems with GRAFCET Not well suited to describe Create a graphical tool that can deal with: Emergency cases Manual modes Degraded modes Emergency cases Manual modes Degraded modes Does not favor a good separation of operating modes Does not give a clear vocabulary concerning modes Does not include any security aspect GRAFCET and Petri nets 51 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 50 Objectives of GEMMA inventors GRAFCET is good to describe normal operation but: Real-Time Programming © J.-D. Decotignie, 2007 Estblish a precise vocabulary Tool show present itself as a guide (checklist) Real-Time Programming GRAFCET and Petri nets 52 © J.-D. Decotignie, 2007 control part power off GEMMA concepts PC power on A OPERATIVE PART (OP) STOP PROCEDURES <put OP in initial state> A6 A7 Assumes that controlling part is operational Separate production states from other states Distinguishes 3 categories of operating modes CP power off Working procedures Stopping procedures Failure procedures A1 <put OP is a given state> PROCEDURES DE FONCTIONNEMENT F <initial state stop> A4 F4 <random test procedures> start request <stop reached> F2 F3 <start procedures> PRODUCTION <prepare for start after fail> A5 PC power on D2 <diagnostic/ failure treatment> A2 <stop requested at end of cycle D3 A3 <stop request in given state> F5 stop request F1 CP power off <degraded production> F6 PRODUCTION Real-Time Programming GRAFCET and Petri nets 53 © J.-D. Decotignie, 2007 OPERATIVE PART FAIL PROCEDURES Real-Time Programming How to use GEMMA <test procedures> <emergency stop> D1 D <ordered test procedures> < normal production> PRODUCTION control part power off <stop procedures> failure detect F WORKING PROCEDURES GRAFCET and Petri nets 54 © J.-D. Decotignie, 2007 Example – joint test bed Selection of modes Showing relationships Search for evolution conditions 3 tested values V, C, β Long tests on a typical run Periodic request for withdraw and check ß cardan Frein couple C V C β moteur vitesse V on off ack man. Real-Time Programming GRAFCET and Petri nets 55 © J.-D. Decotignie, 2007 AU Verrin pour réglage angle ß auto Real-Time Programming GRAFCET and Petri nets 56 © J.-D. Decotignie, 2007 partie commande hors énergie PROCEDURES D'ARRET DE LA PARTIE OPERATIVE (PO) A mise en énergie A6 <mise PO dans état A1 <arrêt dans état de PC all setpoints to 0 loader ready initial> A7 /manual check propeller power on OP, clear default vérification en désordre> F2 <marches demande de marche A4 <arrêt obtenu> ST OP Example – valve test F4 <marches de manual start initial> <mise PO dans état déterminé> PROCEDURES DE FONCTIONNEMENT F F3 de préparation> check feedback loops for V, C and ß by displaying min and max performances <marches de clôture> time setup auto. C C PRODUCTION A5 <préparation pour remise en route après défaillance> de PC stop stop D2 <diagnostic/traitement défaillance demande d'arrêt A3 <arrêt demandé dans état déterminé> A2 <arrêt demandé en fin de cycle> clear setpoints mise en énergie stop+/auto end of tests or end for check - setpoint in any case - display default and time display time&reason F1 < production normale> TEST according to program ²V/V or ²C/C or ²ß/ß>10% D3<production tout de même> de PC F6 - power off OP - brake PROCEDURES EN DEFAILLANCE DE LA PARTIE OPERATIVE Détection défaillances F D D A Em.Stop or Vmax or Cmax exceeded de PC D z y z y PRODUCTION from any state D1 <arrêt d'urgence> mise hors énergie <marches de test> E ack PRODUCTION partie commande hors énergie Tests with display of setpoints V,C and ß [duration test] auto.marche acquittement mise hors énergie E B V x PROCEDURES DE FONCTIONNEMENT Before feeding GRAFCET and Petri nets 57 Real-Time Programming © J.-D. Decotignie, 2007 After feeding GRAFCET and Petri nets 58 Real-Time Programming GUIDE DES MODES DE MARCHE ET D'ARRET (GEMMA) partie commande hors énergie A mise en énergie de PC PROCEDURES D'ARRET DE LA PARTIE OPERATIVE (PO) A6 <mise PO dans état initial> par boutons poussoirs avec les sécurités b+ si e- et a+ si /z /y F F4 <marches de vérification en désordre> initial> CI D2 F2 <marches demande de marche A4 <arrêt obtenu> état déterminé> de préparation> F3 A5 <préparation pour remise en route après défaillance> de PC A2 <arrêt demandé en fin de cycle> partie commande hors énergie mise en énergie de PC A6 <mise PO dans état initial> par boutons poussoirs avec les sécurités b+ si e- et a+ si /z /y initial> A4 <arrêt obtenu> F5 <marches de PROCEDURES DE FONCTIONNEMENT m2 F4 <marches de demande de marche vérification en désordre> par boutons poussoirs avec les sécurités b+ si e- et a+ si /y /z F2 <marches de préparation> F3 <marches de clôture> F5 <marches de PRODUCTION vérification dans l'ordre> F1 F /m2 A1 <arrêt dans état état déterminé> mise hors énergie demande d'arrêt PROCEDURES D'ARRET DE LA PARTIE OPERATIVE (PO) A7 <mise PO dans A3 <arrêt demandé dans état déterminé> A <marches de clôture> PRODUCTION mise hors énergie © J.-D. Decotignie, 2007 GUIDE DES MODES DE MARCHE ET D'ARRET (GEMMA) PROCEDURES DE FONCTIONNEMENT A1 <arrêt dans état A7 <mise PO dans B V x <préparation pour A5 remise en route après défaillance> < production normale> de PC A2 <arrêt demandé en fin de cycle> vérification dans l'ordre> A3 <arrêt demandé dans état déterminé> demande d'arrêt F1 < production normale> A6 FT D2 <diagnostic/trai- mise en énergie tement défaillance étalonnage du dispositif de contrôle D3 <production tout F6 <marches de même> de PC PRODUCTION cycle de test du dispositif de contrôle d'étanchéité de PC PROCEDURES EN DEFAILLANCE DE LA PARTIE OPERATIVE F PROCEDURES DE FONCTIONNEMENT partie commande hors énergie GRAFCET and Petri nets 59 F6 <marches de même> de test> PRODUCTION D1 <arrêt d'urgence> Détection défaillances de PC D PROCEDURES EN DEFAILLANCE DE LA PARTIE OPERATIVE F PROCEDURES DE FONCTIONNEMENT Système de test d'étanchéité de soupapes: marche manuelle Système de test d'étanchéité de soupapes: boucle de test Real-Time Programming D3 <production tout PRODUCTION mise hors énergie Détection défaillances D tement défaillance de PC D1 <arrêt d'urgence> mise hors énergie partie commande hors énergie PRODUCTION D2 <diagnostic/trai- mise en énergie de test> © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 60 © J.-D. Decotignie, 2007 GUIDE DES MODES DE MARCHE ET D'ARRET (GEMMA) GUIDE DES MODES DE MARCHE ET D'ARRET (GEMMA) partie commande hors énergie A mise en énergie de PC PROCEDURES D'ARRET DE LA PARTIE OPERATIVE (PO) CI A6 <mise PO dans état initial> par boutons poussoirs avec les sécurités b+ si e- et a+ si /z /y F PROCEDURES DE FONCTIONNEMENT A1 <arrêt dans état F4 <marches de initial> vérification en désordre> partie commande hors énergie A mise en énergie de PC m1 PROCEDURES D'ARRET DE LA PARTIE OPERATIVE (PO) A6 <mise PO dans état initial> par boutons poussoirs avec les sécurités b+ si e- et a+ si /z /y F /m2 A1 <arrêt dans état PROCEDURES DE FONCTIONNEMENT F4 <marches de m2 initial> CI m1 T A7 <mise PO dans état déterminé> F2 <marches demande de marche A4 <arrêt obtenu> de préparation> F3 D2 <marches de clôture> A7 <mise PO dans état déterminé> de PC A5 <préparation pour A2 <arrêt remise en route après défaillance> remise en pression PO et déclenchement du cycle de RAZ demandé en fin de cycle> demande d'arrêt mise en énergie mise hors énergie F1 < production normale> de PC cycle de contrôle de l'étanchéité des soupapes A5 <préparation pour remise en route après défaillance> remise en pression PO et déclenchement du cycle de RAZ D3 <production tout de même> de test> PRODUCTION A2 <arrêt demandé en fin de cycle> A3 <arrêt demandé dans état déterminé> partie commande hors énergie demande d'arrêt F1 < production normale> cycle de contrôle de l'étanchéité des soupapes D3 <production tout F6 <marches de même> de test> PRODUCTION PRODUCTION AU coupure de l'alimentation de la partie opérative PO PROCEDURES EN DEFAILLANCE DE LA PARTIE OPERATIVE F PROCEDURES DE FONCTIONNEMENT Système de test d'étanchéité de soupapes: arrêt d'urgence GRAFCET and Petri nets 61 Real-Time Programming D1 <arrêt d'urgence> mise hors énergie Détection défaillances de PC D vérification dans l'ordre> de PC RM mise hors énergie F5 <marches de /m1 D2 <diagnostic/traitement défaillance étalonnage du dispo sitif de contrôle mise en énergie PRODUCTION D1 <arrêt d'urgence> <marches de clôture> FT F6 <marches de PC RM F3 Fcyraz A6 D2 <diagnostic/traitement défaillance de préparation> PRODUCTION vérification dans l'ordre> A3 <arrêt demandé dans état déterminé> F2 <marches demande de marche F5 <marches de PRODUCTION Fcyraz mise hors énergie A4 <arrêt obtenu> © J.-D. Decotignie, 2007 Valve test - GRAFCET vérification en désordre> par boutons poussoirs avec les sécurités b+ si e- et A1 si /z /y partie commande hors énergie AU coupure de l'alimentation de la partie opérative PO Détection défaillances de PC D PROCEDURES EN DEFAILLANCE DE LA PARTIE OPERATIVE Real-Time Programming cycle de test du dispositif de contrôle de l'étanchéité F PROCEDURES DE FONCTIONNEMENT Système de testGRAFCET d'étanchéité de soupapes: GEMMA complet and Petri nets 62 © J.-D. Decotignie, 2007 GEMMA - analysis 1 2 m1./y./z output A stop concise and synthetic graphic Non ambiguous vocabulary Clearly shows manual parts Helps defining securities and operator commands May be used as user manual door closed, part in position, stop out 3 check proofness hold part bad 4 bad 8 mark t / 4 / t1 9 unhold shake valve t / 4 / t1 5 check proofness bad 6 valve free valve free & repeat unhold Drawbacks Difficult to use of complex cases Some of the limitations of GRAFCET valve free & no repeat 7 Advantages slip away stop stop in Real-Time Programming GRAFCET and Petri nets 63 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 64 © J.-D. Decotignie, 2007 How to manage an automation project Phases according to GEMMA tenants Define requirements Use GEMMA for start/stop operations Create GRAFCET Select control technology Technological realization Trial and commissioning GRAFCET and Petri nets 65 Real-Time Programming © J.-D. Decotignie, 2007 Petri nets Theoretical introduction GRAFCET GEMMA Petri nets Real-Time Programming GRAFCET and Petri nets 66 © J.-D. Decotignie, 2007 Petri Nets Invented by C. Petri in 1962 in his PhD thesis ("Kommunikation mit Automaten) J. Peterson, "Petri Net Theory and the Modelling of Systems", Prentice Hall, 1981. R. David, A. Alla, "Du Grafcet aux réseaux de Petri", Hermes, 1990. T. Murata, Petri nets: Properties, analysis and applications, Proc. of the IEEE, Vol. 77 (4), April 1989, pp.541 - 580 2 view points Outline Definitions and evolution rules Properties Definition Marking PN types Modelling with Petri nets Modelling synchronization and cooperation between tasks Design Analysis and validation Application to functional specifications Real-Time Programming GRAFCET and Petri nets 67 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 68 © J.-D. Decotignie, 2007 Petri nets - definition Directed graph tuple C={P, T, I, O} N places pi ∈ P L transitions ti ∈ T Input matrix I [LxN] places → transitions Output matrix O [LxN] transitions → places Petri net example p1 p2 p3 t1 p4 P = {p1, p2, p3, p4, p5} T = {t1, t2} © J.-D. Decotignie, 2007 Petri nets - marking p2 1 p3 2 p4 0 p5 0 t1 0 0 0 0 1 t2 p1 0 p2 0 p3 0 p4 1 p5 2 t1 #(pi, I(tj)) weight of arc pi → tj 0 0 1 0 0 t2 #(pi, O(tj)) weight of arc tj→ pi t1 Real-Time Programming t2 2 p4 GRAFCET and Petri nets 70 p5 © J.-D. Decotignie, 2007 PN – evolution rules p1 p3 2 I= p5 GRAFCET and Petri nets 69 p2 p1 1 O= Real-Time Programming p1 marking M = {m(p1),....., m(pi), ....., m(pN)} with m(pi) = number of tokens in place pi p4 Initial marking M0, example M0={2,1,3,0,1} Evolution by firing transitions Can then represent behavior (dynamic) p2 p3 2 t1 a transition ti may be fired iif for all i m(pi) ≥ #(pi, I(tj)) t2 2 p5 Only one transition may fired at a time A transition is fired instantaneously by: Removing in each place that immediately preceeds the transition a number of tokens equal the weight of arc that links them Adding in each place that immediately follows the transition a number of tokens equal the weight of arc that links them m(pi) := m(pi) - #(pi, I(tj)) + #(pi, O(tj)) EVOLUTION IS NOT DETERMINISTIC Real-Time Programming GRAFCET and Petri nets 71 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 72 © J.-D. Decotignie, 2007 Evolution rules p1 Exercise - syntax p2 For each of the graphs below, answer the following questions: 1. Is it a PN ? 2. What are the validated transitions ? 3. What will be the marking after firing ? 4. What are the validated transitions p3 2 t1 t2 2 p4 p1 p2 p5 p3 p1 p2 p3 2 t1 B C F G H D E 2 t2 t1 2 p4 A t2 2 p5 p4 GRAFCET and Petri nets 73 Real-Time Programming p5 © J.-D. Decotignie, 2007 Exercise – syntax (2) I GRAFCET and Petri nets 74 Real-Time Programming © J.-D. Decotignie, 2007 PN types For each of the graphs below, answer the following questions: 1. Is it a PN ? 2. What are the validated transitions ? 3. What will be the marking after firing ? 4. What are the validated transitions Generalized PNs There a weight on each arc Can be transformed into ordinary PN PNs with predicates Cannot be transformed into ordinary PN Marc J K L X Y father of X Y X t1 Y t1 Luc Real-Time Programming GRAFCET and Petri nets 75 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 76 © J.-D. Decotignie, 2007 PN types (2) PN types (3) t1 fired PNs with capacity t1 fired t1 p2 t1 t1 t2 t2 Tokens have colors Any colored PN with a finite number of colors may be transformed into an ordinary PN cap(p2)=2 t2 Can be transformed t1 into ordinary PN p2 t1 fired t1 fired t1 p2' t2 p2' p2' t2 GRAFCET and Petri nets 77 Real-Time Programming © J.-D. Decotignie, 2007 PN types (4) p1 Several types p2 p3 Cannot be transformed into ordinary PNs Continuous PNs The number of tokens can be a real number Cannot be transformed into ordinary PN © J.-D. Decotignie, 2007 Synchronized PNs Time PNs Stochastic PNs Stochastic Time PNs .... Transform this PN into an ordinary PN t1 t1 p1 t2 p2 2 p4 t2 p5 GRAFCET and Petri nets 79 t3 p3 t5 cap(p3)=3 t4 p4 Cannot be transformed into ordinary PNs Real-Time Programming GRAFCET and Petri nets 78 Real-Time Programming 2 No autononous PNs Cannot be transformed into ordinary PN Exercise PNs with inhibiting arcs PNs with priorities t1 t2 Colored PNs © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 80 © J.-D. Decotignie, 2007 Modelling with PNs actions associated to places Conditions « and" & « or" Activated by token presence actions associated to transitions (short duration) Activated by transition firing Task waiting p1 p2 type "AND" type "OR" Processor free Start of execution executing p1 p2 x1 p3 x2 p3 y p1 x3 p2 x1 t1 p3 x2 t1 x3 t3 t2 End of execution Tasked ended Real-Time Programming p4 p4 GRAFCET and Petri nets 81 © J.-D. Decotignie, 2007 Introduction of external conditions p4 GRAFCET and Petri nets 82 Real-Time Programming y © J.-D. Decotignie, 2007 Introduction of external conditions (2) p11 When synchronisation is required Task controlled system → waiting controlling system (.,begin_exec) Label on the transition executing (if condition, action) Transition may be fired iif (end_exec,.) external condition satisfied Task terminated Timers (extern or minimal sejourn duration in a place) Real-Time Programming GRAFCET and Petri nets 83 p1 p2 Processor free Task waiting p1 p2 Processor free t11 p13 (.,begin_exec) p15 t12 p3 executing p3 p4 © J.-D. Decotignie, 2007 Real-Time Programming t13 p14 p16 t14 (end_exec,.) Task terminated (begin_exec, .) p17 p4 (.,end_exec) GRAFCET and Petri nets 84 t15 © J.-D. Decotignie, 2007 Introduction of external conditions (3) p1 t1 Modelling task synchronisation mechanisms Mutual synchronisation (rendez-vous) (.,start_timer) A1 p3 t2 t3 t1 A2 © J.-D. Decotignie, 2007 Modelling task synchronisation mechanisms(2) B B1 B2 A A1 A2 B B1 B2 B2 p4 GRAFCET and Petri nets 85 A2 OR (end_timer,.) Real-Time Programming A1 B1 t2 timer A Real-Time Programming GRAFCET and Petri nets 86 © J.-D. Decotignie, 2007 Modelling task synchronisation mechanisms(3) mailbox Interrupt driven task As an external condition on a transition t1 Interrupt handler modeled using A 2 places A1 B1 t2 t3 t1 A2 Real-Time Programming A A1 A2 B B1 B2 B2 GRAFCET and Petri nets 87 © J.-D. Decotignie, 2007 Real-Time Programming p4 t2 p3 t5 GRAFCET and Petri nets 88 B (interrupt,...) t3 p2 t4 B (interrupt,...) p1 t6 © J.-D. Decotignie, 2007 Modelling task synchronisation mechanisms (4) Mutual exclusion S P(S) Modeled by a single token P(S): AND condition on a transition V(S) V(S): OR condition on a transition Critical section synchronized by an auxiliary place p1 Task waiting p0 © J.-D. Decotignie, 2007 Critical section t4 p6 GRAFCET and Petri nets 90 Real-Time Programming © J.-D. Decotignie, 2007 Producers - consumers s CONSUMERS p3 p5 t3 writing production t4 t1 p6 GRAFCET and Petri nets 91 PRODUCERS Task waiting t2 p4 S s p5 Real-Time Programming p4 S p5 p1 t3 p3 p1 p2 s p3 p1 t3 S Task waiting t2 Critical section t11 p2 WRITERS t1 reading p0 t1 Readers – writers problem READERS Task waiting t1 GRAFCET and Petri nets 89 Real-Time Programming Mutual exclusion through semaphore t2 messages p4 p1 s p2 p6 use t4 positions © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 92 © J.-D. Decotignie, 2007 Dining Philosophers Exercise t7 p11 eat t4 p3 p4 p5 t8 p10 p6 p12 t6 meditate t3 p8 t1 p7 p1 t2 p13 A consulate let its clients enter then the entrance door is closed and the client may be served. After being served, each client leaves the consulate through another door. The entrance door cannot be opened again before all the clients have left. p2 Design a PN with inhibitor arcs that represents this specification Modify the first solution so that only one client may enter at a time Describe the same case using an ordinary PN A maximum of 4 clients may enter before the door is closed. Model this case using an ordinary PN p5 t5 Real-Time Programming GRAFCET and Petri nets 93 © J.-D. Decotignie, 2007 Design and validation Real-Time Programming Structural properties © J.-D. Decotignie, 2007 Are only dependent on the topology Behavioral properties GRAFCET and Petri nets 95 © J.-D. Decotignie, 2007 Petri nets properties Petri nets properties Design by successive refinements Analysis by reduction Real-Time Programming GRAFCET and Petri nets 94 Depend on the initial marking Real-Time Programming GRAFCET and Petri nets 96 © J.-D. Decotignie, 2007 Structural properties Structural properties (2) State graph Event graph Without conflict Free choice Extended free choice simple pure Without loop Real-Time Programming GRAFCET and Petri nets 97 © J.-D. Decotignie, 2007 Without conflit t2 t1 t2 p3 p4 t1 Real-Time Programming t2 p4 t1 GRAFCET and Petri nets 99 ti ti p3 p2 p2 t1 ti t3 p1 tj t2 GRAFCET and Petri nets 98 © J.-D. Decotignie, 2007 t2 © J.-D. Decotignie, 2007 p3 Free choice p3 Each transition is involved in at most p 3 one conflict p1 iif each place has exactly one input pk and one output transition Real-Time Programming p2 simple p1 Structural properties (4) p3 Each place has at most one output transition iif each transition has exactly one input and one output place Event graph Structural properties (3) State graph In case of conflict, < pj, {t1, t2,..}> none of the transitions has another input place than pj t1 t2 p3 p4 t1 t2 Extended free choice In case of conflict, all the involved transitions have the same input places Real-Time Programming p3 GRAFCET and Petri nets 100 p4 t1 t2 © J.-D. Decotignie, 2007 Structural properties (5) Pure PN p3 Exercise - properties For each PN below, respond to the following questions: 1. Is it a state graph ? 2. Is it an event graph ? 3. Is it without conflict ? 4. It is simple ? 5. Is it pure ? 6. Is it without loop ? t1 t1' There is no transition that has an input place that is also an output place p3 p4 p0 If there exists tj and pi that is at the same time input and output place for tj then tj has at least another input place Real-Time Programming p3 GRAFCET and Petri nets 101 t1 t1 GRAFCET and Petri nets 103 p2 t2 p4 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 102 © J.-D. Decotignie, 2007 Reachability Reachability Boundedness Conservativeness Liveness Reversibility, home state Coverability Persistence Synchronic distance Fairness Real-Time Programming p1 p2 Behavioral properties t1 Without loop p1 t1'' Can the system reach a given state or exhibit a given behavior (correct or not) ? To answer this question, one has to find a sequence of firing that brings from M0 to Mi A marking Mi is said reachable from M0, if there exists a sequence of firings that transforms M0 in Mi Mi is said immediately reachable from M0, if there is a unique firing that transforms M0 en Mi R(M0): set of all reachable markings from M0 L(M0): set of all firing sequences from M0 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 104 © J.-D. Decotignie, 2007 Bounded and safe Bounded and safe (2) Places are often used to represent: p1 Information storage in communication systems and computers Products and tools in production systems GRAFCET and Petri nets 105 © J.-D. Decotignie, 2007 Exercise p3 p2 The boundedness property is useful to detect overflows in resource usage A PN is said k-bounded if the number of tokens whichever the place does not exceed k for all markings in R(M0) A PN is said safe if k=1 (1-bounded) Real-Time Programming p1 t2 p4 t3 t1 p3 p2 t2 p4 Real-Time Programming GRAFCET and Petri nets 106 © J.-D. Decotignie, 2007 Conservativeness 2 tasks T1 and T2 execute on the same processeur in time sharing (part of T1 is executed, then part of T2 is, then part of T1, …) Model the same behavior with 4 tasks Is the resulting PN bounded ? Real-Time Programming t3 t1 GRAFCET and Petri nets 107 © J.-D. Decotignie, 2007 In a real system, the number of resources is limited. If tokens represent resources, it may be a desired properties that the number of tokens remains constant whichever the marking in R(M0) A PN is said strictly conservative if the number of tokens is constant A PN is said conservative if there exists a weighting vector w=[w1,....., wi, ....., wN] such that for each marking in R(M0), ∑wi m(pi) remains constant. Real-Time Programming GRAFCET and Petri nets 108 © J.-D. Decotignie, 2007 Conservativeness - example Liveness p1 t3 t1 p3 PRODUCERS CONSUMERS p3 p5 p2 t2 p4 The idea of liveness is closely related to blocking and interblocking cases Necessary conditions (all 4 together) t3 production p4 t2 messages p1 p6 s p2 Real-Time Programming GRAFCET and Petri nets 109 © J.-D. Decotignie, 2007 Liveness (2) Once allocated, a resource cannot be withdrawn from the task Multiple requests t4 positions Resources can only be shared by a finite number of tasks No preemption use t1 Limited access Tasks already own resources when they additional resource requests The request graph has circular paths GRAFCET and Petri nets 110 Real-Time Programming © J.-D. Decotignie, 2007 Liveness - example A transition t of a PN is said : L0-live (dead) if t does not belong to any sequence of L(M0) L1- live (potentialy firable) if t may fired at least once in a sequence of L(M0) L2- live if t may be fired k times (k integer >1) in a sequence of L(M0) L3- live if t may be fired an infinite number of times in a sequence of L(M0) L4- live (live) if t is L1- live for any marking in R(M0) live p1 t3 t1 p2 p3 t2 t2, t3 are L1, L2 et L3 live t1 is L1 live p1 t3 p2 t1 t2 p3 Real-Time Programming GRAFCET and Petri nets 111 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 112 © J.-D. Decotignie, 2007 Exercise Reversibility and home state 2 computers share a common memory. It is assumed that each computer may be in one of the following states: For a real-time system, it is of prime importance to recover in case of error and then return to a correct state Does not need the shared memory Needs the shared memory, but it has not yet been assigned Uses the shared memory A PN is said reversible if the initial marking M0 may be reached from any marking in R(M0) A given state Mi of a PN is said « home state » if for any marking M of R(M0), Mi can be reached from M Your assignment Model this behavior Is the result conservative Show that the resulting PN is live GRAFCET and Petri nets 113 Real-Time Programming © J.-D. Decotignie, 2007 Reversibility and home state example reversible p1 t3 t1 p2 p1 t1 p3 t3 p2 p1 p1 p1 t1 t1 t1 t1 t2 t3 t1 4. conservative ? p1 t1 Not p reversible 1 p2 For each PN below, please indicate if it is: 1. bounded ? 2. live ? 3. Without blocking? t0 t2 © J.-D. Decotignie, 2007 Exercise - properties Home state p0 p3 GRAFCET and Petri nets 114 Real-Time Programming A B C p2 D p1 t2 E p4 t2 p3 Real-Time Programming GRAFCET and Petri nets 115 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 116 © J.-D. Decotignie, 2007 PN Properties Reachable marking A marking that can reached from M0 live Maximum number of tokens ∀place =K All transitions are live Well shaped live + bounded + reversible reversible K-bounded (if K=1, safe) PN Properties (2) M0 may be reached from any marking conservative (same weights, strictly conservative) Weighted sum of tokens in places = Constant Real-Time Programming GRAFCET and Petri nets 117 © J.-D. Decotignie, 2007 GRAFCET and Petri nets 118 Real-Time Programming Design by refinement © J.-D. Decotignie, 2007 Design by refinement (2) p1 First step p2 Simple net Complex tasks associated to transitions validation p3 t3 Transitions are replace by a block (a PN that begins with an initial transition and ends with a final transition) t11 p13 p15 validation t12 t13 p14 Repeat step 2 t11 t2 1st STEP Second step Following steps p2 p2 t1 t1 t2 p1 p1 t1 p13 p15 t12 p3 t3 t11 p13 t13 p14 p15 t12 p16 p14 p16 t14 1st STEP BLOCK p16 t14 t13 t14 p3 t3 BLOCK Real-Time Programming GRAFCET and Petri nets 119 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 120 © J.-D. Decotignie, 2007 Structure approach Analysis by reduction We only use blocks that have good properties Sequence simplification ti pk Eliminate sequences of places Concatenate parallel paths Suppress identity transitions tj ORIGINAL PROPERTIES MUST BE PRESERVED WHILE DO SEQUENCE IF THEN ELSE Real-Time Programming GRAFCET and Petri nets 121 © J.-D. Decotignie, 2007 Analysis by reduction (2) Real-Time Programming p1 p2 p1 Real-Time Programming Preserving boundedness and liveness properties R1: place substitution R2: implicit place R3: neutral transition R4: identical transitions p1 p1 © J.-D. Decotignie, 2007 Reduction techniques p1 p2 GRAFCET and Petri nets 122 Ra: non pure transition for ordinary PN Rb: pure transition for ordinary PN p1 GRAFCET and Petri nets 123 Preserving invariants © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 124 © J.-D. Decotignie, 2007 Reduction R1: place substitution Reduction R1- example Place Pi can be removed if it complies with the 3 following conditions P1 P2 T1 Pi output transitions have no other input place than Pi There is no transition Tj that is at the same time input and output transition of Pi At least one output transition of Pi is not a sink transition P2 P1 T2 T23 T13 P3 T3 T4 P4 P4 T14 T24 P5 P5 Keeps: bounded, safe, live, without blocking, home state, conservative. However, bound and home state are not always known Real-Time Programming GRAFCET and Petri nets 125 © J.-D. Decotignie, 2007 Reduction R2: implicit place GRAFCET and Petri nets 126 Real-Time Programming Reduction R2- example Place Pi is implicit if it fulfils the following 2 conditions Marking of this place may never block the firing of its output transitions Its marking may be deducted from the marking of other places according to P1 P1 T1 P3 P2 T1 P2 p2 p2 t2 p1 t2 p3 p3 t3 t3 k ≠i GRAFCET and Petri nets 127 t1 t1 M ( Pi ) = ∑ α k M ( Pk ) + β Real-Time Programming © J.-D. Decotignie, 2007 Keeps: bound, live, without blocking, home state, conservative. May be safe after reduction even if original is not. It is not always possible to know the home state and the bound. © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 128 © J.-D. Decotignie, 2007 Reduction R3: neutral transition Transition T is neutral iif the set of all its input places is identical to the set of all its output places T1 T3 P1 P2 T5 T2 T1 2 transtions are identical if they have the same set of input places and the same set of output places p3 T3 P1 P2 T2 T4 Reduction R4 – identical transitions p4 t1 p3 t2 Keeps: bounded, safe, live, without blocking, home state, conservative. It is not always possible to know the home state and the bound. GRAFCET and Petri nets 129 © J.-D. Decotignie, 2007 Reduction Ra – non pure transition Transition Tj with place Pi and arcs Tj->Pi and Pi->Tj Reduction Suppress arcs Tj->Pi and Pi->Tj Suppress transition Tj if it is isolated p3 P2 T1 P2 P1 T3 P1 T3 T2 P2 T2 P2 Real-Time Programming GRAFCET and Petri nets 131 Keeps: bounded, safe, live, without blocking, home state, conservative. It is not always possible to find the home state and the bound. Real-Time Programming GRAFCET and Petri nets 130 © J.-D. Decotignie, 2007 Reduction Rb – pure transition T1 t1 T4 p3 Real-Time Programming p4 The transition must possess at least one input and one output place p1 Reduction Suppress transition Each couple of places Pi,Pk such that Pi is an input place and Pk is an output place, is replaced by a place Pi+Pk (union of places) p1 p2 p1 p1 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 132 © J.-D. Decotignie, 2007 Reduction Rb- example Exercise p1 T1 T2 P1 T1 Reduce the following PN p2 T2 t11 P2 P1+4 T5 P4 t1 p13 P1+3 P2+4 P2+3 p15 t12 t13 p14 P3 p16 t14 T3 T4 T3 T4 p3 t3 GRAFCET and Petri nets 133 Real-Time Programming © J.-D. Decotignie, 2007 Exercise © J.-D. Decotignie, 2007 PN Formal analysis Reduce the PN below and find its place invariants Systematic evolution from the initial marking Gives the set of reachable markings t1 From which the properties are derived 3 techniques Reachability graph Reachability tree Matrix analysis P1 t2 P3 P2 t3 Real-Time Programming GRAFCET and Petri nets 134 Real-Time Programming GRAFCET and Petri nets 135 © J.-D. Decotignie, 2007 Real-Time Programming Place invariant Transition invariant GRAFCET and Petri nets 136 © J.-D. Decotignie, 2007 Reachability graph We create a graph of reachable markings Exhaustive search Reachability tree p1 t2 t3 t1 p2 Risk of combinatorial explosion p3 t1 t3 [2,0,0] Real-Time Programming t2 [1,0,1] t1 [0,1,1] GRAFCET and Petri nets 137 [1,0,0] © J.-D. Decotignie, 2007 Analyis by reachability tree Real-Time Programming GRAFCET and Petri nets 138 © J.-D. Decotignie, 2007 Matrix analysis The tree is always finite The tree permits to check the following properties Not bounded if there exsists M1>M Conservative if the number of tokens is constant L1-Live is each transitions appears at least once in the tree Reversibility and home state p1 If we want to show that the PN is not bounded, t2 t3 t1 it might be useless to continue p2 p3 This is the case if M1 that has been reached from M, [1,0,0] M1≥M (∀i: m1(pi) ≥m(pi)) t1 if M1=M, we are back to the [0,1,1] same marking t3 t2 if M1>M, it is possible to repeat [1,1,0] [1,0,1] the same firing sequence and increment again the number of tokens Complex to use Uses I and O matrices Look for a non trivial solution to | O-I |.xT=0 avec x= | x1, ...., xi, ...., xN | (1) Let M et M1 be two successive markings M1 = M + O[tj] – I[tj] after firing tj (2) Let ρ = | ρ1, ...., ρi, ...., ρN | be a solution of (1) Let multiply each term of (2) by ρi and sum up on i ∑ m1( pi )ρi = ∑ ρi m( pi ) + ∑ ρi [O(t j , pi ) − I (t j , pi )] Real-Time Programming GRAFCET and Petri nets 139 © J.-D. Decotignie, 2007 N N N i =1 i =1 i =1 Real-Time Programming GRAFCET and Petri nets 140 © J.-D. Decotignie, 2007 Place invariant result: Place invariant - example N N ∑ m1( pi )ρi = ∑ ρi m( pi ) i =1 I= i =1 O= If all ρi have the same sign and are non zero The PN is conservative (strictly is ρi are all equal) The PN is bounded 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 ⏐O-I⏐.x = If all ρi have the same sign and some are zero A subset of the PN is conservative GRAFCET and Petri nets 141 Real-Time Programming © J.-D. Decotignie, 2007 Exercise – readers-writers READERS WRITERS p0 p2 Task waiting s t1 t3 Real-Time Programming p3 s GRAFCET and Petri nets 143 1 0 -1 0 -1 0 1 0 p5 t3 production t1 t2 messages p4 p1 p6 utilisation t4 s p2 positions 0 -1 0 1 0 1 0 -1 . xT=0 Possible solution xi =1 , invariant = s+2; bounded, strictly conservative Real-Time Programming Task waiting t2 p4 S s -1 1 0 0 CONSOMMATEURS p3 GRAFCET and Petri nets 142 © J.-D. Decotignie, 2007 Transition invariant p1 reading 1 -1 0 0 T PRODUCTEURS Look for a non trivial solution to | O-I |T.xT=0 avec x= | x1, ...., xi, ...., xM | (1) M is the number of transitions Gives an indication of liveness Sequence of transitions that can be fired repeatedly writing t4 © J.-D. Decotignie, 2007 Real-Time Programming GRAFCET and Petri nets 144 © J.-D. Decotignie, 2007 Interesting information http://www.informatik.uni-hamburg.de/TGI/PetriNets/ http://home.arcor.de/henryk.a/petrinet/e/hpsim_e.htm Real-Time Programming GRAFCET and Petri nets 145 © J.-D. Decotignie, 2007