Plasa Petri

Exemplu de plasă Petri

O rețea Petri (cunoscută și sub numele de rețea loc / tranziție sau rețea P / T ) este una dintre reprezentările matematice ale unui sistem distribuit discret. Ca limbaj de modelare , descrie structura unui sistem distribuit ca un grafic bipartit cu adnotări. Au fost inventate în 1962 în timpul tezei de doctorat a autorului Carl Adam Petri .

Descriere

Noțiuni de bază

O rețea Petri PT (Place / Tranziție) este un grafic orientat cu două tipuri de noduri, locuri și tranziții , conectate prin arcuri directe. Locurile sunt reprezentate grafic prin cercuri, iar tranzițiile prin dreptunghiuri.

Un arc poate uni noduri de diferite tipuri, deci pot exista arcuri între locuri și tranziții - dar nu între locuri și locuri sau tranziții și tranziții. Un loc din care un arc începe să se termine într-o tranziție se numește locul de intrare de tranziție; un loc în care un arc ajunge dintr-o tranziție se numește locul de ieșire de tranziție.

Locațiile pot conține un număr de jetoane sau mărci . O distribuție de jetoane pe toate locurile din rețea se numește marcare . Tranzițiile acționează asupra jetoanelor primite conform unei reguli, numită regulă de tragere . O tranziție este activată dacă poate fi declanșată, adică dacă există jetoane în fiecare loc de intrare. Când o tranziție se declanșează, consumă jetoane din locurile sale de intrare, efectuează sarcini și plasează un număr specificat de jetoane în fiecare dintre locurile sale de ieșire. Acest lucru se întâmplă automat, de exemplu într-un singur pas nepreentiv. Execuția rețelelor Petri este nedeterministă . Aceasta înseamnă două lucruri:

dacă mai multe tranziții sunt activate în același timp, oricare dintre ele poate fi declanșată
nu este garantată declanșarea unei tranziții activate; o tranziție activată poate fi declanșată imediat, după orice timp de așteptare (atâta timp cât rămâne activată), sau deloc declanșată.

Deoarece declanșarea unei tranziții nu este previzibilă a priori, plasele Petri sunt foarte potrivite pentru modelarea comportamentului unui sistem concurent .

Definiție formală

O rețea Petri este o extensie a clasei de rețele elementare:

Definiția 1 : o rețea este un triplu $N=(P,T,F)$ ${\ displaystyle N = (P, T, F)}$ ${\ displaystyle N = (P, T, F)}$ unde este:

$P.$ ${\ displaystyle P}$ $P.$ este un ansamblu de stări numite locuri.
$T.$ ${\ displaystyle T}$ $T.$ este un set de tranziții.
$F\subset (P\times T)\bigcup (T\times P)$ ${\ displaystyle F \ subset (P \ times T) \ bigcup (T \ times P)}$ $F \ subset (P \ times T) \ bigcup (T \ times P)$ este un set de fluxuri relaționale numite „arcuri”. Astfel de fluxuri sunt posibile numai între locuri și tranziții sau invers.

O rețea este un grafic bipartit, unde $P.$ ${\ displaystyle P}$ $P.$ este o partiție și $T.$ ${\ displaystyle T}$ $T.$ si celalalt. Mai exact, pentru fiecare $t$ ${\ displaystyle t}$ $t$ în $T.$ ${\ displaystyle T}$ $T.$ exista $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ în $P.$ ${\ displaystyle P}$ $P.$ astfel încât $(p,t)$ ${\ displaystyle (p, t)}$ ${\ displaystyle (p, t)}$ Și $(t,q)$ ${\ displaystyle (t, q)}$ ${\ displaystyle (t, q)}$ apartine $F.$ ${\ displaystyle F}$ $F.$ și pentru fiecare $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ în $P.$ ${\ displaystyle P}$ $P.$ de sine $(p,t)$ ${\ displaystyle (p, t)}$ $(p, t)$ Și $(t,q)$ ${\ displaystyle (t, q)}$ $(t, q)$ sunt în $F.$ ${\ displaystyle F}$ $F.$ asa de $p\neq q$ ${\ displaystyle p \ neq q}$ $p \ neq q$ . În formulă:

$\forall t\in T\,\,\exists p,q\in P\,\,t.c.\,\,(p,t),(t,q)\in F\,p\neq q$ ${\ displaystyle \ forall t \ în T \, \, \ există p, q \ în P \, \, tc \, \, (p, t), (t, q) \ în F \, p \ neq q }$ $\ forall t \ in T \, \, \ există p, q \ în P \, \, t.c. \, \, (p, t), (t, q) \ în F \, p \ neq q$

Întregul $P\bigcup T$ ${\ displaystyle P \ bigcup T}$ ${\ displaystyle P \ bigcup T}$ conține elementele rețelei. Setul de locuri definește stările locale ale rețelei, cu toate acestea, starea globală a unei rețele poate fi definită prin subseturi de locuri.

Definiția 2 : dată o rețea $N=(P,T,F)$ ${\ displaystyle N = (P, T, F)}$ ${\ displaystyle N = (P, T, F)}$ , o configurație este un set $C\subseteq P$ ${\ displaystyle C \ subseteq P}$ ${\ displaystyle C \ subseteq P}$ .

Definiție 3 : O rețea elementară este o rețea de formă $EN=(N,C)$ ${\ displaystyle EN = (N, C)}$ ${\ displaystyle EN = (N, C)}$ unde este:

$N=(P,T,F)$ ${\ displaystyle N = (P, T, F)}$ ${\ displaystyle N = (P, T, F)}$ este o rețea.
$C\subseteq P$ ${\ displaystyle C \ subseteq P}$ ${\ displaystyle C \ subseteq P}$ este o configurație.

Definiția 4 : O rețea Petri este o rețea teoretică a rețelei Petri . Proprietățile teoretice ale rețelelor Petri au fost studiate pe larg. Un motiv principal pentru utilizarea rețelelor Petri în modelarea sistemelor concurente este abilitatea de a delimita și decide în mod formal proprietățile dorite ale sistemului, cum ar fi vietatea (de exemplu, într-un sistem care nu trebuie să se blocheze niciodată) sau limitarea (de exemplu, resursele ale unui sistem precum CPU sunt limitate). Desigur, aceeași proprietate într-un context diferit poate lua un sens complet diferit.

Un marcaj într-o rețea Petri este accesibil dacă, începând de la marcajul inițial, există o secvență de declanșare care îl produce. O rețea Petri este delimitată dacă există o limită superioară a numărului de jetoane în marcajele sale accesibile.

Principalele tipuri

Principalele tipuri de plase Petri.

Există șase tipuri principale de plase Petri:

Mașină de stat finit (SM) - în care fiecare tranziție are un singur arc de intrare și unul de ieșire. Acest lucru implică faptul că nu poate exista concurență, dar poate exista conflict (adică atunci când apare întrebarea: unde merge un simbol de scaun? Într-una sau alta tranziție?). Matematic: $\forall t\in T:|t\bullet |=|\bullet t|=1$ ${\ displaystyle \ forall t \ in T: | t \ bullet | = | \ bullet t | = 1}$ $\ forall t \ in T: | t \ bullet | = | \ bullet t | = 1$
Grafo Marcato (Marked Graph - MG) - unde fiecare loc are un singur arc de intrare și un arc de ieșire. În acest caz nu există conflicte, dar există competiții . Matematic: $\forall p\in P:|p\bullet |=|\bullet p|=1$ ${\ displaystyle \ forall p \ în P: | p \ bullet | = | \ bullet p | = 1}$ $\ forall p \ in P: | p \ bullet | = | \ bullet p | = 1$
Libera alegere (Free choice - FC) - în care arcul este fie singurul arc care merge dintr-un loc, fie singurul arc intră într-o tranziție. Cu alte cuvinte, pot exista atât concurență, cât și conflicte, dar nu în același timp . Matematic: $\forall p\in P:(|p\bullet |\leq 1)\vee (\bullet (p\bullet )=\{p\})$ ${\ displaystyle \ forall p \ in P: (| p \ bullet | \ leq 1) \ vee (\ bullet (p \ bullet) = \ {p \})}$ $\ forall p \ in P: (| p \ bullet | \ leq 1) \ vee (\ bullet (p \ bullet) = \ {p \})$
Free Extended Choice (Extended free choice - EFC) - o rețea Petri care poate fi transformată într-un FC.
Alegerea asimetrică ( Alegerea asimetrică - AC) - competiție și conflict (pe scurt, confuzie), dar nu asimetric. Matematic: $\forall p_{1},p_{2}\in P:(p_{1}\bullet \cap p_{2}\bullet \neq 0)\to [(p_{1}\bullet \subseteq p_{2}\bullet )\vee (p_{2}\bullet \subseteq p_{1}\bullet )]$ ${\ displaystyle \ forall p_ {1}, p_ {2} \ în P: (p_ {1} \ bullet \ cap p_ {2} \ bullet \ neq 0) \ to [(p_ {1} \ bullet \ subseteq p_ {2} \ bullet) \ vee (p_ {2} \ bullet \ subseteq p_ {1} \ bullet)]}$ $\ forall p_ {1}, p_ {2} \ în P: (p_ {1} \ bullet \ cap p_ {2} \ bullet \ neq 0) \ to [(p_ {1} \ bullet \ subseteq p_ {2} \ bullet) \ vee (p_ {2} \ bullet \ subseteq p_ {1} \ bullet)]$

Extensii

Există multe extensii ale plasei Petri. Unele dintre ele sunt complet compatibile înapoi (de exemplu, rețelele Petri colorate) cu rețeaua Petri originală, altele adaugă proprietăți care nu pot fi modelate în rețeaua Petri originală (de ex. Rețele Petri temporizate). Dacă pot fi modelate în rețeaua Petri originală, nu sunt extensii reale, ci sunt modalități convenabile de a arăta același lucru și pot fi transformate cu formule matematice adecvate în rețeaua originală, fără a pierde sensul. Extensiile care nu pot fi transformate sunt uneori reprezentări foarte puternice, dar de obicei pierd multe instrumente matematice disponibile pentru a analiza rețelele Petri normale.

Termenul rețea Petri la nivel înalt este folosit pentru multe formalisme ale rețelei Petri care extind formalismul de bază P / T. Aceasta include, de asemenea, plasele Petri ierarhizate colorate și toate celelalte extensii menționate în această secțiune.

O listă scurtă a posibilelor extensii:

Într-o rețea Petri standard, jetoanele nu se disting. Într-o rețea Petri colorată , fiecare jeton are o valoare. În instrumentele populare pentru rețelele Petri colorate, cum ar fi Instrumentul CPN , valoarea jetonului este tastată și poate fi testată și manipulată cu un limbaj de programare funcțional . O filială a rețelelor Petri colorate sunt rețele Petri bine formate , unde expresiile de arc și de control sunt constrânse pentru a face analiza rețelei mai ușoară.
O altă extensie populară a rețelei Petri este ierarhia : ierarhia sub forma mai multor vederi care susțin diferite niveluri de rafinament și abstractizare au fost studiate de Fehling . O altă formă de ierarhizare se găsește în așa-numitele rețele Petri orientate obiect sau sisteme orientate obiect, în care o rețea Petri poate conține mai multe rețele ca jetoane, stabilind o ierarhie de rețele Petri altoite care comunică prin sincronizarea tranzițiilor la diferite niveluri. A se vedea [1] pentru o introducere informală a rețelelor Petri orientate obiect.
Un sistem de adăugare vectorială cu state (VASS) poate fi văzut ca o generalizare a unei rețele Petri (dar cu ceva mai puțin). Luați în considerare un automat cu stare finită în care fiecare tranziție este tradusă într-o tranziție netă Petri. Prin urmare, rețeaua Petri urmărește evoluția automatului, adică o tranziție în automat este efectuată în același timp în tranziția corespunzătoare în rețeaua Petri. Este posibil să efectuați o tranziție în automat numai dacă tranziția corespunzătoare din rețea este activată; este posibil ca tranziția din rețeaua Petri să se fixeze numai dacă există o tranziție de la starea actuală a automatului etichetat de aceasta. Ceea ce nu pot reprezenta automatele de stare finită sunt situațiile de sincronizare care sunt prezente în rețeaua Petri: de exemplu, când două locuri așteaptă o tranziție și tranziția nu poate fi declanșată până când cele două locuri nu răspund constrângerilor tranziției.
Rețelele Petri cu prioritate adaugă mecanisme prioritare tranzițiilor, prin care o tranziție nu se poate declanșa dacă este activată o tranziție cu prioritate mai mare. Tranzițiile sunt împărțite în grupuri prioritare, de exemplu grupul prioritar 3 poate fi declanșat numai dacă toate tranzițiile din grupul 1 și grupul 2 sunt dezactivate. Cu un grup prioritar, filmarea este încă nedeterministă.
Proprietatea nedeterministă are o mare importanță, deoarece permite utilizatorului să extragă un număr mare de proprietăți (depinde de utilizarea rețelei). În unele cazuri, este, de asemenea, necesar să adăugați o sincronizare la model.

Astfel se nasc rețelele Petri temporizate , în care există tranziții temporizate și altele care nu (de obicei tranzițiile fără temporizări au o prioritate mai mare decât cele temporizate). A se vedea, de asemenea, rețelele Petri stochastice care adaugă un timp nedeterminist pentru a reda un concept aleatoriu al tranzițiilor. Distribuția aleatorie exponențială este de obicei utilizată pentru a „cronometra” astfel de rețele. În acest caz, graficul de accesibilitate al rețelei devine un lanț markov .

Există multe alte extensii la rețeaua Petri, dar este important să ne amintim că, cu cât crește complexitatea rețelei în ceea ce privește proprietățile extinse, cu atât este mai dificil să se utilizeze instrumente standard pentru a evalua anumite proprietăți ale rețelei. Din acest motiv, este o idee bună să utilizați cel mai simplu tip de rețea posibil pentru un anumit proces de modelare.

Modele succesive de concurență

În urma invenției rețelelor Petri, au fost introduse alte modele de concurență, care se bazează pe schimbul de mesaje și comportamentul compozițional. Robin Milner și Carl Hewitt au susținut într-adevăr că lipsa capacității de compoziție a rețelei este o limitare serioasă a Petri, deoarece modularitatea este limitată.

În plus, Hewitt a susținut că rețelele Petri nu au localitate, deoarece jetoanele de intrare ale unei tranziții dispar simultan, ceea ce limitează realismul modelului. Hewitt a știut răspunsul imediat la observația sa, care este că utilizarea corectă a plaselor Petri este de a respecta constrângerea evenimentului unic , fiecare tranziție ar trebui să modeleze un singur eveniment. Dar fără a lua în considerare timpul necesar evenimentului sau timpul necesar operațiunii asociate tranzacției. formă $PN=(N,M,W)$ ${\ displaystyle PN = (N, M, W)}$ ${\ displaystyle PN = (N, M, W)}$ , care extinde rețeaua elementară astfel încât:

$N=(P,T,F)$ ${\ displaystyle N = (P, T, F)}$ ${\ displaystyle N = (P, T, F)}$ este o rețea.
$M:P\rightarrow Z$ ${\ displaystyle M: P \ rightarrow Z}$ ${\ displaystyle M: P \ rightarrow Z}$ este un set multiplu .
$W:F\rightarrow Z$ ${\ displaystyle W: F \ rightarrow Z}$ ${\ displaystyle W: F \ rightarrow Z}$ este un multiset de margini.

Semantică

Un grafic net Petri este de patru ori $(S,T,F,W)$ ${\ displaystyle (S, T, F, W)}$ ${\ displaystyle (S, T, F, W)}$ , unde este:

$S.$ ${\ displaystyle S}$ $S.$ este un set finit de locuri
$T.$ ${\ displaystyle T}$ $T.$ este un set finit de tranziții, cu $S\cap T=\varnothing$ ${\ displaystyle S \ cap T = \ varnothing}$ ${\ displaystyle S \ cap T = \ varnothing}$
$F:(S\times T)\cup (T\times S)\to \mathbb {N}$ ${\ displaystyle F: (S \ times T) \ cup (T \ times S) \ to \ mathbb {N}}$ ${\ displaystyle F: (S \ times T) \ cup (T \ times S) \ to \ mathbb {N}}$ este un multiset de margini (relație de curgere)
$W:F\rightarrow \mathbb {N} \backslash \lbrace 0\rbrace$ ${\ displaystyle W: F \ rightarrow \ mathbb {N} \ backslash \ lbrace 0 \ rbrace}$ ${\ displaystyle W: F \ rightarrow \ mathbb {N} \ backslash \ lbrace 0 \ rbrace}$ este funcția de greutate a unui arc

Relația de flux este un set de margini $F=\{(x,y)\mid W(x,y)>0\}$ ${\ displaystyle F = \ {(x, y) \ mid W (x, y)> 0 \}}$ ${\ displaystyle F = \ {(x, y) \ mid W (x, y)> 0 \}}$ . În multe texte, muchiile pot avea multiplicitate 1. Vom folosi convenția de a folosi $F.$ ${\ displaystyle F}$ $F.$ in loc de $W$ ${\ displaystyle W}$ $W$ obținându-se astfel că un grafic net Petri este un multigraf bipartit $(S\cup T,F)$ ${\ displaystyle (S \ cup T, F)}$ ${\ displaystyle (S \ cup T, F)}$ .

Presetarea unei tranziții $t$ ${\ displaystyle t}$ $t$ , este setul locurilor sale de intrare: $^{\bullet }t=\{s\in S\mid W(s,t)>0\}$ ${\ displaystyle ^ {\ bullet} t = \ {s \ în S \ mid W (s, t)> 0 \}}$ $^ {\ bullet} t = \ {s \ în S \ mid W (s, t)> 0 \}$ ; post-setul este un set de locuri de ieșire: $t{}^{\bullet }=\{s\in S\mid W(t,s)>0\}$ ${\ displaystyle t {} ^ {\ bullet} = \ {s \ în S \ mid W (t, s)> 0 \}}$ $t {} ^ {\ bullet} = \ {s \ în S \ mid W (t, s)> 0 \}$ . Cele două definiții sunt similare.

Marcarea unei rețele Petri este un set multiplu de locuri, adică o cartografiere $M:S\to \mathbb {N}$ ${\ displaystyle M: S \ to \ mathbb {N}}$ $M: S \ to \ mathbb {N}$ . Prin urmare, vom spune că marcajul atribuie un număr de simbol.

O plasă Petri este un cuplu $(S,T,W,M_{0})$ ${\ displaystyle (S, T, W, M_ {0})}$ ${\ displaystyle (S, T, W, M_ {0})}$ , unde este:

$(S,T,W)$ ${\ displaystyle (S, T, W)}$ ${\ displaystyle (S, T, W)}$ este un grafic net Petri;
$M_{0}$ ${\ displaystyle M_ {0}}$ $M _ {{0}}$ este marcajul inițial.

Semantica execuției

Comportamentul unei rețele Petri este definit prin relațiile dintre marcaje, rețineți că marcajul poate fi adăugat ca orice multiset: $M+M'\ {\stackrel {D}{=}}\ \{s\to M(s)+M'(s)\mid s\in S\}$ ${\ displaystyle M + M '\ {\ stackrel {D} {=}} \ \ {s \ to M (s) + M' (s) \ mid s \ in S \}}$ $M + M '\ {\ stackrel {D} {=}} \ \ {s \ to M (s) + M' (s) \ mid s \ in S \}$

Executarea unui grafic net Petri $G=(S,T,W)$ ${\ displaystyle G = (S, T, W)}$ ${\ displaystyle G = (S, T, W)}$ poate fi definit prin relația de tranziție $\to _{G}$ ${\ displaystyle \ to _ {G}}$ $\ to _ {G}$ pe marcaje, după cum urmează:

pentru fiecare t in $T:M\to _{G,t}M'\ {\stackrel {D}{\Leftrightarrow }}\ \exists M'':S\to \mathbb {N} :M=M''+{\textstyle \sum _{s\in S}W(s,t)\ \wedge \ M'=M''+{\textstyle \sum _{s\in S}W(t,s)}}$ ${\ displaystyle T: M \ to _ {G, t} M '\ {\ stackrel {D} {\ Leftrightarrow}} \ \ există M' ': S \ to \ mathbb {N}: M = M' '+ {\ textstyle \ sum _ {s \ in S} W (s, t) \ \ wedge \ M '= M' '+ {\ textstyle \ sum _ {s \ in S} W (t, s)}}}$ $T: M \ to _ {G, t} M '\ {\ stackrel {D} {\ Leftrightarrow}} \ \ există M' ': S \ to \ mathbb {N}: M = M' '+ {\ textstyle \ sum _ {s \ in S} W (s, t) \ \ wedge \ M '= M' '+ {\ textstyle \ sum _ {s \ in S} W (t, s)}}$
$M\to _{G}M'\ {\stackrel {D}{\Leftrightarrow }}\ \exists t\in T:M\to _{G,t}M'$ ${\ displaystyle M \ to _ {G} M '\ {\ stackrel {D} {\ Leftrightarrow}} \ \ există t \ în T: M \ to _ {G, t} M'}$ $M \ to _ {G} M '\ {\ stackrel {D} {\ Leftrightarrow}} \ \ există t \ în T: M \ to _ {G, t} M'$

In cuvinte:

Declanșați o tranziție $t$ ${\ displaystyle t}$ $t$ într-un marcaj $M.$ ${\ displaystyle M}$ $M.$ consumă $W(s,t)$ ${\ displaystyle W (s, t)}$ ${\ displaystyle W (s, t)}$ jeton din fiecare dintre locurile de intrare $s$ ${\ displaystyle s}$ $s$ din $t$ ${\ displaystyle t}$ $t$ , și produce $W(t,s)$ ${\ displaystyle W (t, s)}$ ${\ displaystyle W (t, s)}$ simbol pentru fiecare dintre locurile de ieșire $s$ ${\ displaystyle s}$ $s$ din $t$ ${\ displaystyle t}$ $t$ .
O tranziție este activată (ar putea declanșa) dacă există suficiente jetoane în locurile sale de intrare pentru a face posibilă consumarea acestora, adică dacă și numai dacă $\forall s:M(s)\geq W(s,t)$ ${\ displaystyle \ forall s: M (s) \ geq W (s, t)}$ ${\ displaystyle \ forall s: M (s) \ geq W (s, t)}$ .

În general, suntem interesați de ceea ce s-ar putea întâmpla dacă tranzițiile sunt declanșate în ordine arbitrară. Să spunem un marcaj ${M.}^{'}$ ${\ displaystyle M '}$ $M '$ se poate ajunge printr-un marcaj $M.$ ${\ displaystyle M}$ $M.$ într-un singur pas însă $M\to _{G}M'$ ${\ displaystyle M \ to _ {G} M '}$ $M \ to _ {G} M '$ , spunem, de asemenea, că este accesibil din $M.$ ${\ displaystyle M}$ $M.$ de sine $M\to _{G}^{*}M'$ ${\ displaystyle M \ to _ {G} ^ {*} M '}$ $M \ to _ {G} ^ {*} M '$ , unde este $\to _{G}^{*}$ ${\ displaystyle \ to _ {G} ^ {*}}$ $\ to _ {G} ^ {*}$ este închiderea reflexivă și tranzitivă a $\to _{G}$ ${\ displaystyle \ to _ {G}}$ $\ to _ {G}$ dacă se poate ajunge în 0 sau mai mulți pași.

Pentru o rețea Petri (marcată) $N=(S,T,W,M_{0})$ ${\ displaystyle N = (S, T, W, M_ {0})}$ ${\ displaystyle N = (S, T, W, M_ {0})}$ , suntem interesați de fotografiile care pot fi făcute începând cu marcajul inițial $M_{0}$ ${\ displaystyle M_ {0}}$ $M _ {{0}}$ . Definim setul de marcaje accesibile: $R(N)\ {\stackrel {D}{=}}\ \{M'\mid M_{0}\to _{(S,T,W)}^{*}M'\}$ ${\ displaystyle R (N) \ {\ stackrel {D} {=}} \ \ {M '\ mid M_ {0} \ to _ {(S, T, W)} ^ {*} M' \}}$ $R (N) \ {\ stackrel {D} {=}} \ \ {M '\ mid M_ {0} \ to _ {(S, T, W)} ^ {*} M' \}$

Graficul de accesibilitate al lui N este relația de tranziție $\to _{G}$ ${\ displaystyle \ to _ {G}}$ $\ to _ {G}$ limitat la marcaje realizabile $R(N)$ ${\ displaystyle R (N)}$ ${\ displaystyle R (N)}$ .

O succesiune de fotografii pentru o rețea Petri, un grafic G și un semn inițial $M_{0}$ ${\ displaystyle M_ {0}}$ $M _ {{0}}$ este o secvență de tranziții ${\vec {\sigma }}=\langle t_{i_{1}}\ldots t_{i_{n}}\rangle$ ${\ displaystyle {\ vec {\ sigma}} = \ langle t_ {i_ {1}} \ ldots t_ {i_ {n}} \ rangle}$ ${\ vec {\ sigma}} = \ langle t_ {i_ {1}} \ ldots t_ {i_ {n}} \ rangle$ astfel încât $M_{0}\to _{G,t_{i_{1}}}M_{1}\wedge \ldots \wedge M_{n-1}\to _{G,t_{i_{n}}}M_{n}$ ${\ displaystyle M_ {0} \ to _ {G, t_ {i_ {1}}} M_ {1} \ wedge \ ldots \ wedge M_ {n-1} \ to _ {G, t_ {i_ {n}} } M_ {n}}$ $M_ {0} \ to _ {G, t_ {i_ {1}}} M_ {1} \ wedge \ ldots \ wedge M_ {n-1} \ to _ {G, t_ {i_ {n}}} M_ { n}$ . Setul de secvențe de fotografii notate cu $L(N)$ ${\ displaystyle L (N)}$ ${\ displaystyle L (N)}$ .

Rețelele Petri ca vectori și matrice

Marcare pentru plasele Petri $(S,T,W,M_{0})$ ${\ displaystyle (S, T, W, M_ {0})}$ ${\ displaystyle (S, T, W, M_ {0})}$ poate fi cel mai bine apreciat ca un vector de numere întregi de lungime non-negative $|S|$ ${\ displaystyle | S |}$ ${\ displaystyle | S |}$ .

Relația de tranziție poate fi descrisă de o pereche de matrice de dimensiuni $|S|\times |T|$ ${\ displaystyle | S | \ times | T |}$ $| S | \ ori | T |$ :

$W^{-}$ ${\ displaystyle W ^ {-}}$ ${\ displaystyle W ^ {-}}$ definit de $\forall s,t:W^{-}[s,t]=W(s,t)$ ${\ displaystyle \ forall s, t: W ^ {-} [s, t] = W (s, t)}$ ${\ displaystyle \ forall s, t: W ^ {-} [s, t] = W (s, t)}$
$W^{+}$ ${\ displaystyle W ^ {+}}$ ${\ displaystyle W ^ {+}}$ definit de $\forall s,t:W^{+}[s,t]=W(t,s)$ ${\ displaystyle \ forall s, t: W ^ {+} [s, t] = W (t, s)}$ ${\ displaystyle \ forall s, t: W ^ {+} [s, t] = W (t, s)}$

Apoi diferența lor:

$W^{T}=W^{+}-W^{-}$ ${\ displaystyle W ^ {T} = W ^ {+} - W ^ {-}}$ ${\ displaystyle W ^ {T} = W ^ {+} - W ^ {-}}$

poate fi folosit pentru a descrie marcarea realizabilă în termeni de produs între matrice după cum urmează:

Pentru fiecare secvență de tranziții $w$ ${\ displaystyle w}$ $w$ , noi scriem $o(w)$ ${\ displaystyle o (w)}$ ${\ displaystyle o (w)}$ pentru vectorul care mapează fiecare tranziție la numărul său de apariție în w. Deci avem:

$R(N)=\{M\mid \exists w:M=M_{0}+W^{T}\cdot o(w)\wedge w\;{\grave {e}}\;una\;sequenza\;di\;scatto\;di\;N\}$ ${\ displaystyle R (N) = \ {M \ mid \ există w: M = M_ {0} + W ^ {T} \ cdot o (w) \ wedge w \; {\ grave {e}} \; a \; secvență \; din \; clic \; din \; N \}}$ $R (N) = \ {M \ mid \ există w: M = M_ {0} + W ^ {T} \ cdot o (w) \ wedge w \; {\ grave {e}} \; a \; \; of \; click \; of \; N \}$

Rețineți că este necesar ca $w$ ${\ displaystyle w}$ $w$ este o rată de cadre, permițând secvențe de tranziții fără restricții să producă în general un ansamblu foarte mare.

(b) Exemplu de plasă Petri

$W^{+}={\begin{bmatrix}*&t1&t2\\p1&0&1\\p2&1&0\\p3&1&0\\p4&0&1\end{bmatrix}}$ ${\ displaystyle W ^ {+} = {\ begin {bmatrix} * & t1 & t2 \\ p1 & 0 & 1 \\ p2 & 1 & 0 \\ p3 & 1 & 0 \\ p4 & 0 & 1 \ end {bmatrix}}}$ $W ^ {+} = {\ begin {bmatrix} * & t1 & t2 \\ p1 & 0 & 1 \\ p2 & 1 & 0 \\ p3 & 1 & 0 \\ p4 & 0 & 1 \ end {bmatrix} }$ $W^{-}={\begin{bmatrix}*&t1&t2\\p1&1&0\\p2&0&1\\p3&0&1\\p4&0&0\end{bmatrix}}$ ${\ displaystyle W ^ {-} = {\ begin {bmatrix} * & t1 & t2 \\ p1 & 1 & 0 \\ p2 & 0 & 1 \\ p3 & 0 & 1 \\ p4 & 0 & 0 \ end {bmatrix}}}$ $W ^ {-} = {\ begin {bmatrix} * & t1 & t2 \\ p1 & 1 & 0 \\ p2 & 0 & 1 \\ p3 & 0 & 1 \\ p4 & 0 & 0 \ end {bmatrix} }$ $W^{T}={\begin{bmatrix}*&t1&t2\\p1&-1&1\\p2&1&-1\\p3&1&-1\\p4&0&1\end{bmatrix}}$ ${\ displaystyle W ^ {T} = {\ begin {bmatrix} * & t1 & t2 \\ p1 & -1 & 1 \\ p2 & 1 & -1 \\ p3 & 1 & -1 \\ p4 & 0 & 1 \ end {bmatrix}}}$ ${\ displaystyle W ^ {T} = {\ begin {bmatrix} * & t1 & t2 \\ p1 & -1 & 1 \\ p2 & 1 & -1 \\ p3 & 1 & -1 \\ p4 & 0 & 1 \ end {bmatrix}}}$ $M_{0}={\begin{bmatrix}1&0&2&1\end{bmatrix}}$ ${\ displaystyle M_ {0} = {\ begin {bmatrix} 1 & 0 & 2 & 1 \ end {bmatrix}}}$ $M_ {0} = {\ begin {bmatrix} 1 & 0 & 2 & 1 \ end {bmatrix}}$

Accesibilitate

Graficul de accesibilitate în rețea al exemplului (a). Rețineți că rețeaua este 2-limitată și, prin urmare, poate avea doar maximum 9 (

3^{2}

{\ displaystyle 3 ^ {2}}

3 ^ {2}

) Statele.

Toate statele la care poate fi atinsă o rețea $Nu.$ ${\ displaystyle N}$ $Nu.$ cu marcare inițială $M_{0}$ ${\ displaystyle M_ {0}}$ $M _ {{0}}$ sunt indicate cu $R(N,M_{0})$ ${\ displaystyle R (N, M_ {0})}$ ${\ displaystyle R (N, M_ {0})}$ . Problema de accesibilitate este următoarea: este adevărat că $M_{w}\in R(N,M_{0})$ ${\ displaystyle M_ {w} \ în R (N, M_ {0})}$ $M_ {w} \ în R (N, M_ {0})$ ? Aceasta este situația în care $M_{w}$ ${\ displaystyle M_ {w}}$ ${\ displaystyle M_ {w}}$ este o stare „greșită”, care nu trebuie atinsă, de exemplu trecerea unui tren când bariera trecerii la nivel este ridicată sau ascensiunea unui lift când ușile sunt deschise.

Accesibilitatea stărilor poate fi reprezentată cu un grafic de accesibilitate în care sunt indicate stările și arcurile reprezintă tranzițiile între două stări. Graficul este construit după cum urmează: starea inițială este considerată mai întâi ( $M_{0}$ ${\ displaystyle M_ {0}}$ $M_ {0}$ ) și toate tranzițiile posibile din această stare sunt explorate, apoi tranzițiile din stările găsite și așa mai departe. Algoritmul cu care este construit graficul este cel al căutării în lățime , deoarece graficul poate avea lățime infinită, astfel încât o căutare în adâncime-întâi nu poate găsi toate stările posibile, chiar dacă este efectuată de un număr infinit de ori. Observăm că rețeaua Petri este delimitată intrinsec (vezi mai jos) dacă și numai dacă graficul său de accesibilitate are un număr finit de stări.

În timp ce accesibilitatea pare a fi o metodă bună pentru găsirea stărilor „greșite”, pentru problemele practice, graficul construit are de obicei prea multe stări de calculat. Pentru a atenua această problemă, logica temporală liniară (LTL) este adesea utilizată împreună cu metoda tableau pentru a demonstra că anumite stări nu pot fi atinse. LTL folosește tehnica de semi-decizie pentru a afla dacă într-adevăr se poate ajunge la o stare, căutând un set de condiții necesare pentru atingerea statului și dovedind că aceste condiții nu pot fi îndeplinite.

Viața

O plasă Petri este vie sau vie , oricare ar fi marcajul $m$ ${\ displaystyle m}$ $m$ ajuns de atunci $m_{0}$ ${\ displaystyle m_ {0}}$ $m_ {0}$ , din $m$ ${\ displaystyle m}$ $m$ este întotdeauna posibil să declanșezi orice tranziție a rețelei, urmând o succesiune suplimentară de fotografii.

Sunt definite diferite niveluri de viață (în literatură și vivacitate sau vitalitate ), de la $L_{0}$ ${\ displaystyle L_ {0}}$ $L_ {0}$ la $L_{4}$ ${\ displaystyle L_ {4}}$ $L_ {4}$ . O tranziție t a unei rețele Petri ( $N,M_{0}$ ${\ displaystyle N, M_ {0}}$ $N, M_ {0}$ ) Și:

$L_{0}$ ${\ displaystyle L_ {0}}$ $L_ {0}$ viu sau mort dacă și numai dacă nu poate trage, adică dacă nu se află în nicio secvență de fotografiere ${\vec {\sigma }}$ ${\ displaystyle {\ vec {\ sigma}}}$ ${\ vec {\ sigma}}$ unde este ${\vec {\sigma }}\in L(N,M_{0})$ ${\ displaystyle {\ vec {\ sigma}} \ în L (N, M_ {0})}$ ${\ vec {\ sigma}} \ în L (N, M_ {0})$
$L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ viu , sau cvasi-viu , dacă și numai dacă are posibilitatea de a trage, adică dacă se află într-o secvență de fotografiere ${\vec {\sigma }}$ ${\ displaystyle {\ vec {\ sigma}}}$ ${\ vec {\ sigma}}$ Unde ${\vec {\sigma }}\in L(N,M_{0})$ ${\ displaystyle {\ vec {\ sigma}} \ în L (N, M_ {0})}$ ${\ vec {\ sigma}} \ în L (N, M_ {0})$
$L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ trăiește dacă și numai dacă pentru fiecare k întreg pozitiv, t poate trage de cel puțin k ori într-o secvență de fotografiere ${\vec {\sigma }}$ ${\ displaystyle {\ vec {\ sigma}}}$ ${\ vec {\ sigma}}$ Unde ${\vec {\sigma }}\in L(N,M_{0})$ ${\ displaystyle {\ vec {\ sigma}} \ în L (N, M_ {0})}$ ${\ vec {\ sigma}} \ în L (N, M_ {0})$
$L_{3}$ ${\ displaystyle L_ {3}}$ $L_ {3}$ live dacă și numai dacă există o secvență de fotografiere ${\vec {\sigma }}\in L(N,M_{0})$ ${\ displaystyle {\ vec {\ sigma}} \ în L (N, M_ {0})}$ ${\ vec {\ sigma}} \ în L (N, M_ {0})$ unde t se fixează la infinit
$L_{4}$ ${\ displaystyle L_ {4}}$ $L_ {4}$ trăi sau pur și simplu trăi dacă și numai dacă se află într-o stare accesibilă M (adică $\forall M\in R(N,M_{0})$ ${\ displaystyle \ forall M \ în R (N, M_ {0})}$ $\ forall M \ în R (N, M_ {0})$ ), t este $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ Viva.

Observăm că acestea sunt cerințe din ce în ce mai stricte, de exemplu dacă este o tranziție $L_{3}$ ${\ displaystyle L_ {3}}$ $L_ {3}$ live , este automat $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ și $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ trăi . Ca exemple, (b) prezintă o rețea Petri live cu o stare inițială dată, dar cu o altă stare inițială (de exemplu, complet goală) toate tranzițiile pot fi moarte. Pe de altă parte, (a) arată toate tranzițiile unei rețele Petri $L_{3}$ ${\ displaystyle L_ {3}}$ $L_ {3}$ trăiește indiferent de starea inițială - nu sunt $L_{4}$ ${\ displaystyle L_ {4}}$ $L_ {4}$ live , deoarece atunci când starea este (0.2) sau (2.0), una dintre tranzițiile sale poate eșua, deoarece rețeaua este limitată de 2.

O plasă Petri este $L_{k}$ ${\ displaystyle L_ {k}}$ $L_ {k}$ trăiește dacă și numai dacă există o tranziție cu ea $L_{k}$ ${\ displaystyle L_ {k}}$ $L_ {k}$ trăi .

Prescripţie

Există rețele Petri în care numărul maxim de jetoane conținute într-un singur loc este limitat - în acest caz, îngustimea este o proprietate intrinsecă a rețelei. Cu toate acestea, rețelele Petri pot fi definite fără a avea proprietatea de limitare ; atunci limitarea este o posibilă proprietate a rețelei Petri. Se spune că o rețea Petri este legată de k dacă există un întreg pozitiv k (finit) astfel încât numărul de jetoane din fiecare loc din rețea să fie mai mic sau egal cu k pentru fiecare marcă accesibilă de $M_{0}$ ${\ displaystyle M_ {0}}$ $M_ {0}$ O rețea Petri este sigură sau sigură dacă este limitată la 1. Desigur, limitarea depinde de marcarea stării inițiale $M_{0}$ ${\ displaystyle M_ {0}}$ $M_ {0}$ (adică putem pune inițial 10 jetoane în fiecare loc, ceea ce face imposibilă existența unei rețele cu 2 limitări). De asemenea, se remarcă faptul că exemplul (b) nu este limitat deoarece P4 poate avea un număr infinit de jetoane, dacă secvența de declanșare (T1, T2) se repetă la nesfârșit. Cu toate acestea, rețeaua exemplului (a) este în mod inerent limitată de k pentru k = 2 în toate locurile și acest lucru este arătat în toate stările posibile.

Exemplu de transformare a scaunelor. Scaunul gri care inițial era delimitat în mod intrinsec a fost „transformat” în două locuri: scaunul gri original și un stâlp

Limitarea unui anumit loc într-o rețea intrinsecă limitată poate fi reprezentată într-un mod echivalent cu o rețea nelimitată expres de o „transformare a locului”, adică prin inserarea unui loc nou (numit contra-loc ) și provocarea tuturor tranzițiilor care pun x jetoane în locul inițial iau jetoane de pe ghișeu și toate tranzițiile care îndepărtează x jetoane de locul original, pun apoi x jetoane în ghișeu. Numărul de jetoane din $M_{0}$ ${\ displaystyle M_ {0}}$ $M _ {{0}}$ acum vor trebui să satisfacă ecuația + locul de numărare = limitarea. Prin urmare, realizarea unei transformări de locuri pentru toate posturile din rețeaua limitată și forțarea stării de pornire $M_{0}$ ${\ displaystyle M_ {0}}$ $M _ {{0}}$ pentru a se adapta la egalitatea menționată anterior, o rețea limitată poate fi pur și simplu transformată într-o rețea nelimitată. Astfel, o analiză utilizată pentru o rețea inerent nelimitată poate fi utilizată și pentru rețelele delimitate.

P-invariant

Invarianții P corespund unui set de locuri astfel încât suma ponderată a jetoanelor care îl conțin rămâne constantă pentru toate marcajele accesibile de rețea. Dat $C.$ ${\ displaystyle C}$ $C.$ matricea de incidență a rețelei Petri e $X$ ${\ displaystyle x}$ $X$ vector coloană de dimensiune | P |, invarianții P sunt soluțiile întregi ale următoarei ecuații: $x^{T}C=0$ ${\ displaystyle x ^ {T} C = 0}$ $x ^ {T} C = 0$

Dove, per esempio per una rete di Petri avente 5 posti, abbiamo il seguente vettore $x^{T}=[x_{1},x_{2},x_{3},x_{4},x_{5}]$ $x^{T}=[x_{1},x_{2},x_{3},x_{4},x_{5}]$ $x^{T}=[x_{1},x_{2},x_{3},x_{4},x_{5}]$

T-invariante

In modo duale ai P-invarianti, i T-invarianti rappresentano possibili sequenze di scatti che riportano la rete alla marcatura iniziale. Dato $C$ ${\displaystyle C}$ $C$ matrice di incidenza della rete di Petri e $y$ ${\displaystyle y}$ $y$ vettore colonna di dimensione |T|, i T-invarianti sono le soluzioni intere della seguente equazione: $Cy=0$ ${\displaystyle Cy=0}$ $Cy=0$

Sifoni e Trappole

Sono delle strutture fondamentali per riconoscere la vivezza di una rete di Petri.

Sifoni

Un sifone, è un insieme di posti che, durante l'evoluzione della rete, tende a perdere gettoni e non è più capace di acquistarne di nuovi. Dato S un insieme di posti della rete di Petri, il sifone è definito: $\bullet S\subseteq S\bullet$ $\bullet S\subseteq S\bullet$ $\bullet S\subseteq S\bullet$

Trappole

Sono il duale dei sifoni, è un insieme di posti che, durante l'evoluzione della rete, tende ad acquisire gettoni e non è più in grado di smarcarsi completamente. Dato S un insieme di posti della rete di Petri, la trappola è definita: $S\bullet \subseteq \bullet S$ $S\bullet \subseteq \bullet S$ $S\bullet \subseteq \bullet S$

Aree di applicazione

Ingegneria Informatica
Workflow management
Data analysis
Concurrent programming
Affidabilità
Diagnosi (Intelligenza Artificiale) per trovare l'errore originale in una riga di errore
Chimica e Biochimica per modellare (e simulare) sistemi di reazioni

Tools di programmazione

Vedi anche Lista dei tool per le reti di Petri .

Bibliografia

Janette Cardoso , Heloisa Camargo , Fuzziness in Petri Nets , Physica-Verlag, ISBN 3-7908-1158-0 .
Kurt Jensen , Coloured Petri Nets , Springer Verlag, ISBN 3-540-62867-3 .
András Pataricza , Formális moódszerek az informatikában (Formal methods in informatics) , TYPOTEX Kiadó, 2004, ISBN 963-9548-08-1 .
Peterson, James L., Petri Nets , in ACM Computing Surveys , vol. 9, n. 3, 1977, pp. 223–252.
James Lyle Peterson , Petri Net Theory and the Modeling of Systems , Prentice Hall, ISBN 0-13-661983-5 .
Petri, Carl A., Kommunikation mit Automaten (Ph.D. Thesis), University of Bonn, 1962.
Wolfgang Reisig , A Primer in Petri Net Design , Springer-Verlag, ISBN 3-540-52044-9 .
Robert-Christoph Riemann , Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus , Herbert Utz Verlag, ISBN 3-89675-629-X .
Harald Störrle , Models of Software Architecture - Design and Analysis with UML and Petri-Nets , Books on Demand, ISBN 3-8311-1330-0 .
Mengchu Zhou , Frank Dicesare , Petri Net Synthesis for Discrete Event Control of Manufacturing Systems , Kluwer Academic Publishers, ISBN 0-7923-9289-2 .
Mengchu Zhou , Kurapati Venkatesh , Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach , World Scientific Publishing, ISBN 981-02-3029-X .

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file su rete di Petri

Collegamenti esterni

Petri Nets World ottima fonte di informazioni, si può trovare tutto ciò che riguarda una rete di Petri
^{[ collegamento interrotto ]} dalla stessa fonte precedente, un linguaggio markup per le reti di Petri
Interactive Tutorials on Petri Nets dalla stessa fonte, una raccolta di reti di Petri interattive
Routing Language interscambiabile
Citazioni da CiteSeer

Controllo di autorità	Thesaurus BNCF 6134 · LCCN ( EN ) sh85100346 · GND ( DE ) 4045388-1 · BNE ( ES ) XX548185 (data)

Portale Informatica

Portale Matematica