1

– Cosa sono le reti di Petri?

Uno strumento grafico e teorico. Sono state introdotte da Carl Adam Petri nel 1962.

– A cosa servono le reti di Petri?

Le reti di Petri posto/transizione hanno i seguenti scopi:

– Modellare

– Analizzare

– Valutare le prestazioni

– Controllare

i sistemi ad eventi discreti.

Introduzione

2

Una rete di Petri è un grafo orientato, bipartito e pesato.I due tipi di vertici sono detti POSTI e TRANSIZIONI.

P= (p1,p2,....pm) è l’insieme dei postiT=(t1,t2, .....tn) è l’insieme delle transizioni

Le relazioni tra posti e transizioni sono rappresentate da archi diretti.

Gli archi possono essere rappresentati da due matrici:Pre: PT NPost : P T N.

3

Pre: PT N è la funzione preincidenza che specifica gli archi diretti dai posti alle transizioni e viene rappresentata mediante una matrice mxn

Post : P T N.è la funzione post incidenza che specifica gli archi diretti dalle transizioni ai posti e viene rappresentata mediante una matrice mxn.

Le matrici Pre e Post sono matrici di interi non negativi.

Data una rete N=(P,T,Pre,Post) con m posti ed n transizioni, lamatrice di incidenza C: P T Z è la matrice mxn definita comeC=Post-Pre, cioè il generico elemento di C éC(p,t)=Post(p,t)-Pre(p,t)

4

Insiemi di postit={pP Pre(p,t)>0} è l’insieme dei posti in ingresso a tt={pP Post(p,t)>0}è l’insieme dei posti in uscita da t

Insiemi di transizionip={tT Post(p,t)>0} è l’insieme delle transizioni in ingresso a pp={tT Pre(p,t)>0}è l’insieme dei delle transizioni in uscita da p

Alcune definizioni

5

Marcatura di una rete: mediante la marcatura è possibile definire lo stato di una rete

Una marcatura è una funzione M: P N che assegna ad ogni posto un nr. Intero non negativo di marche o gettoni.

6

Una rete N con una marcatura iniziale M0 è detta una rete marcata o sistema di rete, e viene indicata come <N, M0>

Abilitazione o scatto:

Una transizione t è detta abilitata dalla marcatura M se M>Pre(.,t), cioè se oni posto p della rete contiene un numero di marche pari o superiore a Pre(p,t).

Per indicare che t è abilitata da M si scrive Mt>. Per indicare che t’ non è abilitata da M si scrive Mt’>.

7

Una transizione abilitata da una marcatura M può scattare.Lo scatto di t rimuove Pre(p,t) marche da ogni posto pP e aggiunge Post(p,t) in ogni posto p, determinando una marcatura M’.

Cioè vale:

M’=M-Pre(.,t)+Post(.,t)=M+C(.,t)

Una sequenza abilitata s viene detta sequenza di scatto e ad essa corrisponde una traiettoria.

Equazione di scatto: M=M0+Cs

8

Modellazione con Reti di Petri

Sequenzialità: gli eventi si succedono in un ordine determinato

Parallelismo (concorrenza): Gli eventi possono avvenire senza un ordine determinato.

Sincronizzazione: Più eventi paralleli devono essere verificati per poter procedere.

Scelta (conflitto): Un solo evento tra tanti può verificarsi.

9

Posto k-limitatoUn posto di una rete di Petri (PN) si dice k-limitato se in tutte le marcature raggiungibili dalla rete il numero di token presenti nel posto non supera mai un valore prefissato k.

Rete k-limitata e limitataUna rete si dice k-limitata se tutti i posti sono k-limitati. Una rete si dice limitata se è limitata per qualche k finito.Una rete 1-limitata si dice sana o binaria.

Proprietà comportamentali (I)

RaggiungibilitàProblema della raggiungibilità: data una rete marcata <N,M0>, è possibile raggiungere M da M0?

Limitatezza

10

Una rete marcata <N,M0> è limitata se e solo se ha un insiemedi raggiungibilità finito.

Proprietà comportamentali (II)

Reversibilità:Una rete di Petri con marcatura iniziale M0 è detta reversibile seper ogni marcatura M raggiungibile da M0, M0 è raggiungibile daM.

11

Conservatività strettaUna rete marcata è strettamente conservativa se per ogni marcaturaraggiungibile MR(N,M0) il nr. di gettoni che la rete contiene non varia:

pP M(p)= pPM0 (p)

ConservativitàUna rete marcata è conservativa se esiste un vettore di interi positivi x tale per ogni marcatura raggiungibile M R(N,M0) vale:

xTM=xTM0

Cioè il numero di gettoni pesato con x non varia.

Se una rete marcata è conservativa allora essa è limitata.

Proprietà comportamentali (III)

12

VIVEZZA

Transizione quasi vivaUna transizione t è quasi viva se e solo se esiste almeno una marcatura MR(N,M0) tale che t è abilitata in M.

Transizione vivaUna transizione t è viva se e solo se per ogni MR(N,M0)esiste M’ raggiungibile da M tale che t è abilitata in M’.

Transizione mortaUna transizione t è morta se e solo se non esiste MR(N,M0) tale che t è abilitata in M.

Proprietà comportamentali (IV)

13

VIVEZZA

Rete mortaUna rete R(N,M0) è morta se ogni t è morta.

Rete quasi vivaUna rete R(N,M0) è quasi viva se e solo se tutte le transizioni sono quasi vive

Rete vivaUna rete R(N,M0) è viva se tutte le transizioni sono vive.

Rete bloccanteUna rete R(N,M0) è bloccante se esiste una transizioneraggiungibile morta (in cui nessuna transizione è abilitata).

Proprietà comportamentali (V)

14

Insieme potenzialmente raggiungibile di <N, M0>

PR(N,M0)={Mm | yn : M=M0+Cy Ovvero l’insieme dei vettori M per cui esiste y che soddisfa l’equazione di statoVale:R(N,M0)PR(N,M0)

ANALISI MEDIANTE EQUAZIONE DI STATO

L’insieme PR(N,M0) può aiutare a verificare la raggiungibilitàdi una marcatura. Ad esempio se l’equazione M=M0+Cy non ammette soluzione allora M non è raggiungibile.

Insieme di raggiungibilità di <N, M0>

R(N,M0)={Mm | T* : M0[>M Ovvero l’insieme delle marcature che possono essere raggiunte dalla marcatura iniziale.

15

P-invarianteSi dice P-invariante di una PN un vettore colonna x di m elementi non negativi tale che xTC=0.

Tale equazione può avere infinite soluzioni: se x è un P-invariante anche kx è un P-invariante

Il supporto di un P-invariante x è l’insieme dei posti corrispondenti agli elementi non-nulli di x.

Analisi basata sulla matrice di incidenza (I)

P-invariante a supporto minimoUn P-invariante è a supporto minimo se il suo supporto non contiene quello di nessun altro P-invariante della rete.

16

Analisi basata sulla matrice di incidenza (I)

Sia <N, M0> una PN e sia X=x1 x2…xk la matrice formata dalle colonne dei p-invarianti xi per i=1,…,k.

L’insieme X-invariante di <N, M0> èIX(N,M0)={Mm | XT M=XT M0 Ovvero l’insieme dei vettori M tali che xi

T M=xiT M0 per

ogni xi

Vale:R(N,M0)PR(N,M0) IX(N,M0)

17

Proprietà strutturali (I)

Rete coperta da P-invariantiUna rete si dice coperta da p-invarianti se ogni posto della reteappartiene al supporto di almeno un p-invariante.

N è strutturalmente strettamente conservativa se il vettore 1 è un p-invariante.

N è strutturalmente conservativa se esiste un vettore p-invariante x il cui supporto contenga tutti i posti.

18

T-invarianteSi dice T-invariante di una rete un vettore colonna y di dimensione n soluzione della seguente equazioneCy=0ovvero M=M0+Cy=M0

Un T invariante indica che se fosse possibile fare scattare ognitransizione del supporto di y, tante volte quante indicate da y, la rete tornerebbe alla marcatura iniziale.

19

Classi di reti di Petri

Una PN è detta:

• Ordinaria se ogni arco ha molteplicità unitaria cioè Pre(p,t)=0 o =1 e Post(p,t)=0 o =1 .

• Pura se per ogni posto p e t vale Pre(p,t)Post(p,t)=0, cioè se la rete non contiene alcun cappio.

• Ristretta se è pura e ordinaria.

• Una macchina di stato è una rete ordinaria in cui ogni transizione ha esattamente un arco in ingresso ed un arco in uscita.

• Un grafo marcato è una rete ordinaria in cui ogni posto ha esattamente un arco in ingresso ed uno in uscita.

20

Insiemi di postit={pP Pre(p,t)>0} è l’insieme dei posti in ingresso a tt={pP Post(p,t)>0}è l’insieme dei posti in uscita da t

Insiemi di transizionip={tT Post(p,t)>0} è l’insieme delle transizioni in ingresso a pp={tT Pre(p,t)>0}è l’insieme dei delle transizioni in uscita da p

Alcune definizioni

21

Si vogliono caratterizzare le situazioni in cui sequenze di transizioniportano ad incrementare alcune componenti della marcatura.

Si considera allora un nuovo vettore con il simbolo che si puòpensare come un simbolo di infinito.

Si dice una -marcatura di una rete un vettore M in cui una o piùcomponenti può assumere il valore .Per determinare se t è abilitata da una -marcatura M>Pre(.,t) si deve tener conto che per ogni n N vale >n e ±n=.

Perdendo alcune informazioni sulla raggiungibilità, si costruisce il grafo di copertura.

Il grafo di copertura

22

Grafo di copertura

1-Si parta dalla marcatura iniziale M0

2-Si consideri una marcatura M senza etichetta 2.1 - per ogni t abilitata da M

- si calcoli M’ raggiunta da M scattando t- si consideri il cammino che parte dal nodo radice e arriva a M’, se questo cammino ha un nodo M*<M’ allorasi sostituisca ad M’ il nodo M’ il vettore ottenuto da M’ in cui tutte le componenti strettamente maggiori delle componenti di M’ si sostituiscono con il simbolo

- si aggiunga un arco t tra M e M’

- se esiste già un nodo M’ nel grafo si elimini il nuovo nodo e si aggiunga l’arco tra M e M’ già esistente 2.2 -si etichetti come vecchio il nodo M e si torni a 2

23

Grafo di copertura: alcune proprietà

• Data una marcatura M si dice che è -coperta da M se M(p)=M(p) per ogni p tale che M(p)tale relazione si indica con MM.

• M è raggiungibile allora esiste nel grafo M che copre M.

• M è raggiungibile se M è un nodo del grafo.• Se MR(N,M0) esiste nel grafo un cammino

orientato da M0 ad M, con M coperta da M.• MR(N,M0) solo se esiste nel grafo un cammino

orientato da M0 ad M.

24

Una rete marcata <N,M0> è limitata se e solo se ha un insiemedi raggiungibilità finito.

Si consideri la rete marcata <N,M0> ed il suo grafo di copertura: un posto p è k-limitato se e solo se per ogni M0 vale M(p)<k.

La rete marcata è limitata se e solo se nessun nodo del grafo contiene il simbolo (il grafo di copertura è un grafo di raggiungibilità).

Proprietà comportamentali con il grafo di copertura