Ret¸ele Petri

(1)

Curs 1

(2)

1 Informat¸ii curs

2 Ret¸ele Petri - introducere

3 Definit¸ia ret¸elelor Petri

4 Propriet˘at¸i comportamentale M˘arginire

Pseudo-viabilitate Blocaje

Viabilitate Reversibilitate

5 Leg˘atura dintre propriet˘at¸i ˆın ret¸ele Petri

(3)

Structura cursului

1 Informat¸ii curs

(4)

Contact

Titular curs: lect. Dr. Oana Captarencu Adresa email:[email protected]

Birou: C211 Pagina cursului:

http://profs.info.uaic.ro/~otto/pn.html

(5)

Evaluare

Punctaj final: 5·T + 5·LA

T- test scris in sesiune (notate cu o not˘a de la 1 la 10) Activitate laborator (LA) - notat˘a cu o not˘a de la 0 la 10:

activitatea laborator (20%) lucrare de laborator (50%) tem˘a laborator (30%)

Condit¸ii minimale: LA≥5,T ≥4 Punctaj final minim: 50 puncte.

(6)

Structura cursului

1 Informat¸ii curs

(7)

Ret¸ele Petri

Ret¸ele Petri: o metod˘a formal˘a (matematic˘a) folosit˘a pentru modelarea ¸si verificarea sistemelor (concurente/distribuite)

(8)

Ret¸ele Petri

Not¸iunea de sistem:

A regularly interacting or interdependent group of items forming a unified whole (Webster Dictionary)

A combination of components that act together to perform a function not possible with any of the individual parts (IEEE Standard Dictionary of Electrical and Electronic Terms)

(9)

Ret¸ele Petri

Not¸iunea de sistem:

A regularly interacting or interdependent group of items forming a unified whole (Webster Dictionary)

A combination of components that act together to perform a function not possible with any of the individual parts (IEEE Standard Dictionary of Electrical and Electronic Terms)

Sistemele:

alc˘atuite din componente care interact¸ioneaz˘a ˆındeplinesc o anumit˘a funct¸ionalitate

(10)

Ret¸ele Petri

Exemple de sisteme:

sisteme automatizate de product¸ie

sisteme de control al traficului (terestru,aerian) sisteme de monitorizare ¸si control ˆın industrie ret¸ele de comunicare

sisteme software distribuite etc...

(11)

Modelarea ¸si verificarea sistemelor

Verificarea sistemelor: are drept scop verificarea unor propriet˘at¸i dezirabile, ˆınca din stadiul de proiectare

Un model surprinde caracteristici esent¸iale ale sistemului Metode (formale) pentru modelarea ¸si verificarea sistemelor:

automate/sisteme tranzit¸ionale algebre de procese

logici temporale ret¸ele Petri etc...

(12)

Ret¸ele Petri

Carl Adam Petri, 1962 grafuri bipartite

reprezentare explicit˘a st˘arilor ¸si evenimentelor dintr-un sistem reprezentare grafic˘a intuitiv˘a

semantic˘a formal˘a

expresivitate (concurent¸˘a, nedeterminism, comunicare,sincronizare) existent¸a metodelor de analiz˘a a propriet˘at¸ilor

numeroase unelte software pentru editarea/verificarea propriet˘at¸ilor ret¸elelor Petri

(13)

Aplicat¸ii

Protocoale de comunicare, ret¸ele Sisteme software ¸si hardware Algoritmi distribuit¸i

Protocoale de securitate

Sisteme/procese din domenii precum: biologie, chimie, medicin˘a Domeniul economic (fluxuri de lucru)

etc..

(14)

Structura cursului

1 Informat¸ii curs

(15)

Ret¸ele Petri - Definit¸ie

Definit¸ie 1

O ret¸ea Petri este un 4-uplu N = (P, T, F, W) astfel ˆıncˆat :

1 P mult¸ime de locat¸ii, T mult¸ime de tranzit¸ii, P∩T =∅;

2 F ⊆(P×T)∪(T×P) relat¸ia de flux;

3 W : (P×T)∪(T ×P)→Nfunct¸ia pondere (W(x, y) = 0 ddac˘a(x, y)6∈F).

(16)

Ret¸ele Petri - Definit¸ie

Definit¸ie 1

O ret¸ea Petri este un 4-uplu N = (P, T, F, W) astfel ˆıncˆat :

1 P mult¸ime de locat¸ii, T mult¸ime de tranzit¸ii, P∩T =∅;

2 F ⊆(P×T)∪(T×P) relat¸ia de flux;

3 W : (P×T)∪(T ×P)→Nfunct¸ia pondere (W(x, y) = 0 ddac˘a(x, y)6∈F).

P={p1, p2, p3, p4} T ={t1, t2, t3}

F={(p1, t1),(p2, t1),(t1, p3), (p3, t3),(t3, p1),(t3, p4),(t2, p2)}

W(p1, t1) = 1,W(p2, t1) = 2,W(t1, p3) = 1 W(t1, p3) = 1,W(p3, t3) = 1,

W(t3, p4) = 1,W(t3, p1) = 1,W(t2, p2) = 1

(17)

Ret¸ele Petri - Definit¸ie

Dac˘a x∈P∪T, atunci:

- Premult¸imea lui x (sau mult¸imea elementelor input pentru x):

•x={y|(y, x)∈F};

- Postmult¸imea lui x (sau mult¸imea elementelor output pentrux):

x•={y|(x, y)∈F}.

(18)

Ret¸ele Petri - Definit¸ie

•x={y|(y, x)∈F};

x•={y|(x, y)∈F}. Definit¸ie 2

O ret¸ea este pur˘a dac˘a, pentru orice x∈P ∪T,•x∩x•=∅.

(19)

Ret¸ele Petri - Definit¸ie

•x={y|(y, x)∈F};

x•={y|(x, y)∈F}. Definit¸ie 2

O ret¸ea este pur˘a dac˘a, pentru orice x∈P ∪T,•x∩x•=∅.

Definit¸ie 3

O ret¸ea este f˘ar˘a elemente izolate, dac˘a, pentru orice x∈P ∪T,

(20)

Marcarea unei ret¸ele Petri

Definit¸ie 4 (Marcare, ret¸ele marcate)

Fie N = (P, T, F, W)o ret¸ea Petri. O marcare a luiN este o funct¸ie M :P →N.

Fie N = (P, T, F, W)o ret¸ea Petri ¸si M₀ :P →N. Atunci (N, M0) se nume¸ste ret¸ea Petri marcat˘a.

M= (1,0,0,0)

Distribut¸ia punctelor ˆın locat¸iile unei ret¸ele = marcarea ret¸elei (starea sistemului modelat)

(21)

Ret¸ele Petri

Tranzit¸ii: reprezint˘a act¸iuni sau evenimente din sistemul modelat Locat¸iile input (pentru o tranzit¸ie): parametri, variabile, tipuri de resurse necesare producerii unei act¸iuni, precondit¸ii pentru producerea unui eveniment

Punctele din locat¸ii (marcarea): pot modela resurse sau valori ale parametrilor/variabilelor reprezentate de locat¸ia respectiv˘a

Ponderea unui arc input (al unei tranzit¸ii): cˆate resurse de un anumit tip sunt necesare producerii act¸iunii (valoarea minim˘a pe care trebuie sa o aib˘a o variabil˘a pentru ca o act¸iune s˘a se produc˘a)

(22)

Exemplu

Sistem de product¸ie: sistemul (SP) produce piese (P) utilizˆand componente (C), furnizate de c˘atre alt sistem (SC).

Dac˘a SP este ”idle” (nu este implicat deja in product¸ia unei piese) ¸si exist˘a disponibile 2 componente C, va produce piesa P (”consumˆand” cele 2 componente) si va trece intr-o nou˘a stare (SP a produs o pies˘a);

Dup˘a ce SP a produs piesa P, va depozita piesa ˆıntr-un buffer ¸si este preg˘atit pentru producerea unei noi piese (”idle”);

SP2 poate furniza ˆın orice moment cˆate o component˘a C;

(23)

Exemplu

Sistem de product¸ie: sistemul (SP) produce piese (P) utilizˆand componente (C), furnizate de c˘atre alt sistem (SC).

Dac˘a SP este ”idle” (nu este implicat deja in product¸ia unei piese) ¸si exist˘a disponibile 2 componente C, va produce piesa P (”consumˆand” cele 2 componente) si va trece intr-o nou˘a stare (SP a produs o pies˘a);

Dup˘a ce SP a produs piesa P, va depozita piesa ˆıntr-un buffer ¸si este preg˘atit pentru producerea unei noi piese (”idle”);

SP2 poate furniza ˆın orice moment cˆate o component˘a C;

(24)

Regula de producere a tranzit¸iilor

Definit¸ie 5

Fie N = (P, T, F, W) o ret¸ea Petri,M o marcare a lui N ¸sit∈T o tranzit¸ie a lui N.

(25)

Regula de producere a tranzit¸iilor

Definit¸ie 5

Tranzit¸ia teste posibil˘a la marcareaM (M[tiN) dac˘a W(p, t)≤M(p),pentru orice p∈ •t.

(26)

Regula de producere a tranzit¸iilor

Definit¸ie 5

Tranzit¸ia teste posibil˘a la marcareaM (M[tiN) dac˘a W(p, t)≤M(p),pentru orice p∈ •t.

Dac˘at este posibil˘a la marcareaM, atuncitse poate produce, rezultˆand o nou˘a marcare M^′ (M[tiNM^′), unde

M^′(p) =M(p)−W(p, t) +W(t, p),

pentru tot¸i p∈P.

(27)

Exemplu

o tanzit¸ie este posibil˘a dac˘a locat¸iile input cont¸in suficiente puncte:

p1

p2

t1

t2

p3

p4

t3 p5

2

3

2

(28)

Exemplu

p1

p2

t1

t2

p3

p4

t3 p5

2

3

2

(29)

Exemplu

p1

p2

t1

t2

p3

p4

t3 p5

2

3

2

Producerea unei tranzit¸ii modific˘a marcarea ret¸elei

(30)

Exemplu I

Model sistem de product¸ie:

C introduce moneda

monezi ofera

produs

reincarca monezi

introduse

A accepta A respinge moneda A repaus

(38)

Exemplu II

produse

produse consumate

C introduce moneda

monezi acceptate ofera

produs

reincarca monezi

introduse

A accepta moneda A respinge moneda A repaus

(39)

Exemplu II

produse

C introduce moneda

monezi ofera

produs

reincarca monezi

introduse

(40)

Exemplu II

produse

produse consumate

C introduce moneda

produs

reincarca monezi

introduse

(41)

Exemplu II

produse

C introduce moneda

monezi ofera

produs

reincarca monezi

introduse

(42)

Exemplu II

produse

produse consumate

C introduce moneda

produs

reincarca monezi

introduse

(43)

Exemplu II

produse

C introduce moneda

monezi ofera

produs

reincarca monezi

introduse

(44)

Exemplu II

produse

produse consumate

C introduce moneda

produs

reincarca monezi

introduse

(45)

Exemplu II

produse

C introduce moneda

monezi ofera

produs

reincarca monezi

introduse

(46)

Secvent¸e de aparit¸ie a tranzit¸iilor

Extinderea regulii de producere a unei tranzit¸ii la secvent¸e de tranzit¸ii Fie secvent¸au∈T^∗,t∈T ¸si marcareaM.

secvent¸a vid˘a de tranzit¸iiǫeste secvent¸˘a de tranzit¸ii posibil˘a la M ¸si M[ǫiM;

dac˘aueste secvent¸˘a de tranzit¸ii posibil˘a laM, M[uiM^′ ¸siM^′[tiM^′′, atunciuteste secvent¸˘a de tranzit¸ii posibil˘a laM ¸siM[utiM^′′.

(47)

Secvent¸e de aparit¸ie a tranzit¸iilor

Extinderea regulii de producere a unei tranzit¸ii la secvent¸e de tranzit¸ii Fie secvent¸au∈T^∗,t∈T ¸si marcareaM.

secvent¸a vid˘a de tranzit¸iiǫeste secvent¸˘a de tranzit¸ii posibil˘a la M ¸si M[ǫiM;

dac˘aueste secvent¸˘a de tranzit¸ii posibil˘a laM, M[uiM^′ ¸siM^′[tiM^′′, atunciuteste secvent¸˘a de tranzit¸ii posibil˘a laM ¸siM[utiM^′′. Dac˘aσ ∈T^∗ ¸siM[σi,σ se mai nume¸ste secvent¸˘a de aparit¸ie (posibil˘a) din M.

Dac˘a exist˘a σ∈T^∗ astfel ˆıncˆatM[σiM^′, se mai noteaz˘aM[∗iM^′

(48)

Notat¸ii

Fie γ = (N, M0) o ret¸ea Petri marcat˘a . Se definesc urm˘atoarele funct¸ii:

t⁻:P →N,t⁻(p) =W(p, t),∀p∈P t⁺:P →N,t⁺(p) =W(t, p),∀p∈P

∆t:P →Z,∆t(p) =W(t, p)−W(p, t)

Dac˘a σ∈T^∗ este o secvent¸˘a de tranzit¸ii, se define¸ste∆σ:P →Z: Dac˘aσ =ǫ, atunci∆σ este funct¸ia identic0.

Dac˘aσ =t₁, . . . , t_n, atunci∆σ=Pn i=1∆ti.

(49)

Secvent¸e de aparit¸ie

p1

p2

p3

t1 3

2

t⁻₁(p1) = 2, t⁻₁(p2) = 1, t⁻₁(p3) = 0 t⁺₁(p1) = 1, t⁺₁(p2) = 3, t⁺₁(p3) = 1

∆t1(p1) =−1,∆t1(p2) = 2,∆t1(p3) = 1

(50)

Secvent¸e de aparit¸ie

p1

p2

p3

t1 3

2

t⁻₁(p1) = 2, t⁻₁(p2) = 1, t⁻₁(p3) = 0 t⁺₁(p1) = 1, t⁺₁(p2) = 3, t⁺₁(p3) = 1

∆t1(p1) =−1,∆t1(p2) = 2,∆t1(p3) = 1

Propozit¸ie 1

Fie t o tranzit¸ie,σ ∈T^∗ ¸siM, M^′ marc˘ari.

Dac˘aM[tiM^′, atunciM^′=M+ ∆t.

Dac˘aM[σiM^′, atunciM^′=M+ ∆σ

(51)

Marc˘ ari accesibile

Definit¸ie 6

Fie γ = (N, M₀) o ret¸ea Petri marcat˘a. O marcareM^′ este accesibil˘a din marcarea M, dac˘a exist˘a o secvent¸˘a finit˘a de aparit¸ieσ astfel ˆıncˆat:

M[σiM^′.

(52)

Marc˘ ari accesibile

Definit¸ie 6

M[σiM^′.

Mult¸imea marc˘arilor accesibile dintr-o marcare M, ˆın γ, se noteaz˘a [Miγ

(53)

Marc˘ ari accesibile

Definit¸ie 6

M[σiM^′.

Definit¸ie 7

Marcarea M este accesibil˘a ˆınγ, dac˘aM este accesibil˘a din marcarea init¸ial˘a M .

(54)

Marc˘ ari accesibile

Definit¸ie 6

M[σiM^′.

Definit¸ie 7

Marcarea M este accesibil˘a ˆınγ, dac˘aM este accesibil˘a din marcarea init¸ial˘a M₀.

Mult¸imea marc˘arilor accesibile ˆınγ se noteaz˘a[M0iγ

(55)

Propriet˘ at¸i pentru secvent¸e de aparit¸ie

Propozit¸ie 2

Fie M o marcare ¸si σ o secvent¸˘a finit˘a de aparit¸ie, astfel ˆıncˆatM[σiM^′. Dac˘a σ^′ este o secvent¸˘a de aparit¸ie (finit˘a sau infinit˘a) posibil˘a la marcarea M^′, atunciσσ^′ este secvent¸˘a de aparit¸ie posibil˘a laM.

(56)

Propriet˘ at¸i pentru secvent¸e de aparit¸ie

Propozit¸ie 2

Fie M o marcare ¸si σ o secvent¸˘a finit˘a de aparit¸ie, astfel ˆıncˆatM[σiM^′. Dac˘a σ^′ este o secvent¸˘a de aparit¸ie (finit˘a sau infinit˘a) posibil˘a la marcarea M^′, atunciσσ^′ este secvent¸˘a de aparit¸ie posibil˘a laM.

Propozit¸ie 3

O secvent¸˘a infinit˘a de aparit¸ie σ este posibil˘a la o marcare M ddac˘a orice prefix finit al luiσ este posibil laM.

(57)

Propriet˘ at¸i pentru secvent¸e de aparit¸ie

Propozit¸ie 4

Fie M,M^′ ¸siL marc˘ari,σ ∈T^∗ o secvent¸˘a de tranzit¸ii, posibil˘a la M. Dac˘aσ finit˘a ¸siM[σiM^′, atunci(M+L)[σi(M^′+L).

Dac˘aσ infinit˘a ¸siM[σi, atunci(M +L)[σi

Demonstrat¸ie:

σfinit˘a: induct¸ie dup˘a|σ|=n.

σinfinit˘a: se arat˘a c˘a orice prefix finit al luiσeste posibil laM+L.

(58)

Propriet˘ at¸i pentru secvent¸e de aparit¸ie

Definit¸ie 8

Fie M ¸siM^′ dou˘a marc˘ari.

M ≥M^′ ddac˘aM(p)≥M^′(p),∀p∈P.

M > M^′ ddac˘aM ≥M^′ ¸si∃p∈P :M(p)> M^′(p).

(59)

Propriet˘ at¸i pentru secvent¸e de aparit¸ie

Definit¸ie 8

Fie M ¸siM^′ dou˘a marc˘ari.

M ≥M^′ ddac˘aM(p)≥M^′(p),∀p∈P.

M > M^′ ddac˘aM ≥M^′ ¸si∃p∈P :M(p)> M^′(p).

Propozit¸ie 5

Fie M ¸siM^′ dou˘a marc˘ari astfel ˆıncˆatM^′ ≥M. Atunci orice secvent¸˘a de tranzit¸ii posibil˘a la marcarea M este posibil˘a ¸si la marcarea M^′.

U ={t1, t₂},V ={t3, t₄} M = (0,1,0,1,0) σ =t₂t₄t₃t₁t₄

M = (1,0,1,0)[t₂t₄t₃t₁t₄i(0,0,2,0,2) =M^′ M[t₂t₁t₄t₃t₄iM^′

(67)

Structura cursului

1 Informat¸ii curs

(68)

Proprietatea de m˘ arginire

Definit¸ie 9 (m˘arginire)

Fie γ = (M, M₀) o ret¸ea Petri marcat˘a.

O locat¸ie p este m˘arginit˘adac˘a:

(∃ n∈N)(∀M ∈[M₀i)(M(p)≤n)

(69)

Proprietatea de m˘ arginire

Definit¸ie 9 (m˘arginire)

Fie γ = (M, M₀) o ret¸ea Petri marcat˘a.

O locat¸ie p este m˘arginit˘adac˘a:

(∃ n∈N)(∀M ∈[M₀i)(M(p)≤n)

Ret¸eaua marcat˘aγ este m˘arginit˘adac˘a orice locat¸ie p∈P este m˘arginit˘a.

(70)

M˘ arginire-exemple

p1 t1

p2 t2

(71)

M˘ arginire-exemple

p1 t1

p2 t2

ret¸eaua este m˘arginit˘a:M(p)≤1,∀p∈P

(72)

M˘ arginire-exemple

p1 t1

p2 t2

p1

p2 t1

p3 t2

(73)

M˘ arginire-exemple

p1 t1

p2 t2

p1

p2 t1

p3 t2

ret¸eaua este nem˘arginit˘a:

p2poate cont¸ine o infinitate de puncte!

(74)

Propozit¸ie 6

Propozit¸ie 7

Dac˘a γ = (N, M₀) este m˘arginit˘a, nu exist˘a dou˘a marc˘ari M₁, M₂ ∈[M₀i astfel ˆıncˆat M₁[∗iM₂ ¸siM₂ > M₁.

Dac˘aM1[σiM2¸siM2> M1=⇒M2[σiM3(prop. 5) ¸siM3> M2. DeciM3[σiM4, M4> M3, etc.

(78)

Definit¸ie pseudo-viabilitate

Definit¸ie 10 (pseudo-viabilitate)

Fie γ = (N, M₀) o ret¸ea Petri marcat˘a.

O tranzit¸ie t∈T este pseudo-viabil˘a din marcarea M, dac˘a exist˘a o marcareM^′∈[Mi astfel ˆıncˆat M^′[ti.

O tranzit¸ie t∈T este pseudo-viabil˘a dac˘a este pseudo-vaibil˘a din M₀ (exist˘a o marcare accesibil˘a M ∈[M₀i astfel ˆıncˆatM[ti). O tranzit¸ie care nu este pseudo-viabil˘a se nume¸ste moart˘a.

Ret¸eaua marcat˘aγ este pseudo-viabil˘a dac˘a toate tranzit¸iile sale sunt pseudo-viabile.

(79)

Exemple

(80)

Exemple

t₁ este tranzit¸ie moart˘a t₂ pseudo-viabil˘a t₃ este tranzit¸ie moart˘a t₄ pseudo-viabil˘a

(81)

Propriet˘ at¸i: blocaje

Fie γ = (N, M0) o ret¸ea Petri marcat˘a.

Definit¸ie 11 (blocaje)

O marcare M a ret¸elei marcateγ este moart˘a dac˘a nu exist˘a o tranzit¸iet∈T astfel ˆıncˆatM[ti.

Ret¸eaua γ este f˘ar˘a blocaje, dac˘a nu exist˘a marc˘ari accesibile moarte.

(82)

Exemple

(83)

Exemple

Marcarea (0,0,0,0,1) este moart˘a, deci ret¸eaua are blocaje.

(84)

Propriet˘ at¸i: viabilitate

Definit¸ie 12 (viabilitate)

Fie N = (P, T, F, W) o ret¸ea de tip Petri ¸siγ = (N, M₀) o ret¸ea Petri marcat˘a.

O tranzit¸ie t∈T este viabil˘adac˘a∀M ∈[M₀i,teste pseudo-viabil˘a dinM (∃M^′∈[Mi astfel ˆıncˆatM^′[ti).

Ret¸eaua marcat˘aγ este viabil˘adac˘a orice tranzit¸ie t∈T este viabil˘a.

(85)

Exemple

2 2

p1 t1 p2

t2 p3

t3

Ret¸ea pseudo-viabil˘a, viabil˘a si f˘ar˘a blocaje.

(86)

Exemplu

(87)

Exemplu

t₁,t₂,t₃: nu sunt viabile t₄,t₅: viabile

(88)

Marc˘ ari acas˘ a

Definit¸ie 13

Fie γ = (N, M0) o ret¸ea marcat˘a ¸siH marcare a sa. H este marcare acas˘a dac˘a pentru orice M ∈[M₀i,H∈[Mi.

(89)

Marc˘ ari acas˘ a

Definit¸ie 13

Fie γ = (N, M0) o ret¸ea marcat˘a ¸siH marcare a sa. H este marcare acas˘a dac˘a pentru orice M ∈[M₀i,H∈[Mi.

(90)

Reversibilitate

Definit¸ie 14

Ret¸eaua marcat˘aγ este reversibil˘adac˘a marcarea sa init¸ial˘a este marcare acas˘a.

(91)

Reversibilitate

Definit¸ie 14

(92)

Reversibilitate

Definit¸ie 14

2 2

p1 t1 p2

t2 p3

t3

Propozit¸ie 8

O ret¸ea este reversibil˘a ddac˘a orice marcare accesibil˘a este marcare acas˘a.

(93)

Structura cursului

Propozit¸ie 13

O ret¸ea marcat˘a reversibil˘a este f˘ar˘a blocaje.

(100)

Exemplu

p1

p2 t1

p3 t2

Ret¸ea viabil˘a, care nu este reversibil˘a:

(1,0,0,)[t₁i(0,1,1)[t₂i(1,1,0)[t₃i.

Marcarea init¸ial˘a(1,0,0)nu este accesibil˘a din(1,1,0).

(101)

Exemplu

ret¸ea f˘ar˘a blocaje, nu este reversibil˘a