Strumento per la modellistica dei sistemi ad eventi discreti presentato per la prima volta nel 1962 da Carl Adam Petri.
Le reti di Petri (RdP) sono un formalismo grafico e matematico allo stesso tempo.
Permettono di rappresentare in maniera “compatta” sistemi con grande spazio di stato.
Sono uno strumento modulare. I modelli di sottosistemi possono essere semplicemente “uniti” per rappresentare il modello di un sistema complesso.
Le RdP hanno un potere “espressivo” maggiore rispetto agli automi a stati finiti, vale a dire permettono di rappresentare il comportamento di una classe più ampia di sistemi.
Rete posto/transizione
Una rete di Petri è un grafo bipartito orientato, in cui i due tipi di vertici sono detti posti e transizioni. Formalmente è definita dalla 4-pla
dove:
Osservazioni
Matrice di incidenza
Data una rete con
posti e
transizioni la matrice di incidenza
è definita come
È importante notare che nel compattare l’informazione contenuta nelle matrici e
, spesso la matrice di incidenza
perde qualche informazione sulla struttura della rete.
Data una transizione si indica con
– preset di t, insieme dei posti in ingresso a t
– postset di t, insieme dei posti in uscita da t
Dato un posto si indica con
– preset di p, insieme delle transizioni in ingresso a p
– postset di p, insieme delle transizioni in uscita da p
La marcatura consente di definire lo stato di una rete di Petri
Una marcatura (marking) è una funzione
che assegna ad ogni posto della rete un numero intero di gettoni (o token).
La coppia costituita da una rete e dalla sua marcatura iniziale
è detta sistema rete di Petri o rete marcata, e viene indicata con
.
I gettoni si indicano graficamente con dei cerchi neri
La marcatura può essere indicata mediante un vettore colonna con componenti (se
sono i posti della rete)
In particolare per la rete di esempio si ha:
L’evoluzione della marcatura di una rete di Petri al seguito del verificarsi di eventi determina l’evoluzione dinamica dello stato di un SED modellato con un sistema rete.
Pertanto è necessario definire delle regole per l’evoluzione della marcatura di una rete di Petri.
Si tenga presente che si è soliti associare gli eventi di un SED alle transizioni di una rete di Petri.
Condizione di abilitazione di una transizione
Data una rete e una marcatura
, una transizione
è abilitata da
se
vale a dire se ogni posto della rete contiene un numero di gettoni maggiore o uguale al peso dell’arco che collega quel posto alla transizione .
Una transizione abilitata da una marcatura
può scattare.
Lo scatto di una transizione rimuove
gettoni da ogni posto e aggiunge
ad ogni posto, determinando una nuova marcatura
indica che a partire da
, lo scatto della transizione
determina la marcatura
.
Scatto di una sequenza σ di transizioni abilitate
Una sequenza di transizioni è abilitata da una marcatura
se
indica che
è abilitata da
, mentre
indica che lo scatto di
a partire da
determina la marcatura
La sequenza è abilitata da
e il suo scatto determina la marcatura
Scatto della sequenza .
Linguaggio generato da una sistema rete
Il linguaggio (o comportamento) di una rete marcata è l’insieme
Dato un sistema rete , una marcatura
si dice raggiungibile da
se esiste una sequenza
tale che
.
Pertanto l’insieme di raggiungibilità di una rete marcata è dato da
Sequenza vuota -Osservazione
Per definizione si ha che
e
Quindi e
.
Definizione di vettore di scatto
Data una rete e una sequenza
, si definisce vettore di scatto (firing count vector) associato a
il vettore
, la cui generica componente
indica quante volte la transizione
compare in
.
Esempio: ,
e
.
Sia una rete marcata e sia
la sua matrice di incidenza. Se
è raggiungibile da
attraverso lo scatto delle transizioni nella sequenza
, allora vale
Se ,
e
,
, allora
Se , allora se
è abilitata sotto
lo è anche sotto
, vale a dire
Conflitto strutturale
Due transizioni si dicono in conflitto strutturale se
.
Conflitto effettivo
Due transizioni si dicono in conflitto effettivo se
e
, ma
Una rete etichettata (o labeled net) è una 4-pla
Dove la coppia è un sistema rete e:
Estensione alle sequenze della funzione etichetta
È possibile estendere la funzione etichetta a sequenze di transizioni. In particolare
con
Linguaggio generato e marcato da una rete etichettata
Data una rete etichettata è possibile definire il linguaggio generato
il linguaggio marcato
Composizione concorrente tra RdP
La composizione concorrente tra due RdP etichettate si ottiene fondendo le transizioni con la stessa etichetta.
Se è la rete ottenuta facendo la composizione concorrente, allora:
Ingressi e Uscite
Ingressi: due reti etichettate ,
con ,
Uscita: rete composizione concorrente , con
a) se e
, allora
e
e
b) se e
, allora
e
e
c) Sia un evento tale che
. Se
etichetta
transizioni in
e
transizioni in
, allora si introducono
transizioni
, ognuna associata ad una coppia
3. , e
e
4. se
allora
con
1. Introduzione ai sistemi ad eventi discreti
3. Operazioni sugli automi e linguaggi regolari
4. Automi deterministici temporizzati
5. Automi temporizzati stocastici e catene di Markov
6. Reti di Petri – Definizioni e proprietà
7. Reti di Petri – Grafo di raggiungibilità e grafo di copertura
8. Proprietà comportamentali delle reti di Petri
9. Reti di Petri – Stima dell'insieme di raggiungibilità e classificazione
10. Reti di Petri temporizzate
11. Introduzione al controllo di supervisione
12. Controllo di Supervisione - Parte Prima
13. Controllo di Supervisione - Parte Seconda
Capitolo 4, paragrafi 4.1 e 4.2 da Di Febbraro-Giua.
1. Introduzione ai sistemi ad eventi discreti
3. Operazioni sugli automi e linguaggi regolari
4. Automi deterministici temporizzati
5. Automi temporizzati stocastici e catene di Markov
6. Reti di Petri – Definizioni e proprietà
7. Reti di Petri – Grafo di raggiungibilità e grafo di copertura
8. Proprietà comportamentali delle reti di Petri
9. Reti di Petri – Stima dell'insieme di raggiungibilità e classificazione
10. Reti di Petri temporizzate
11. Introduzione al controllo di supervisione
12. Controllo di Supervisione - Parte Prima
13. Controllo di Supervisione - Parte Seconda
14. Controllo di Supervisione - Parte Terza
15. Controllo supervisivo mediante posti monitor
I podcast del corso sono disponibili anche su iTunesU e tramite Feed RSS.