Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Gianmaria De Tommasi » 6.Reti di Petri – Definizioni e proprietà


Sommario della lezione

  • Reti di Petri: definizioni
  • Equazione di stato di una rete di Petri
  • Linguaggi generati dalle reti di Petri
  • Linguaggi di Petri

Generalità

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.

Definizione di rete di Petri

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

N=\bigl(P\,,T\,,Pre\,,Post\bigr)

dove:

  • P è l’insieme degli m posti (rappresentati con dei cerchi)
  • T è l’insieme delle n transizioni (rappresentate con delle barre)
  • Pre: P\times T\mapsto\mathbb{N} è la funzione di pre-incidenza
  • Post: P\times T\mapsto\mathbb{N} è la funzione di post-incidenza

Definizione di rete di Petri (segue)

Osservazioni

  • P\cap T = \emptyset
  • P\cup T\neq\emptyset
  • La funzione di pre-incidenza può essere rappresentata attaverso una matrice \mathbf{Pre}\in\mathbb{N}^{m\times n} in cui l’elemento \mathbf{Pre}\bigl(p\,,t\bigr) indica il peso dell’arco che collega il posto p alla transizione t
  • La funzione di post-incidenza può essere rappresentata attaverso una matrice \mathbf{Post}\in\mathbb{N}^{m\times n} in cui l’elemento \mathbf{Post}\bigl(p\,,t\bigr) indica il peso dell’arco che collega la transizione t al posto p

Esempio

P=\bigl\{p_1\,,p_2\,,p_3\bigr\}

T=\bigl\{t_1\,,t_2\,,t_3\,,t_4\bigr\}

\mathbf{Pre}=\left(\begin{array}{cccc}1 & 1 & 0 & 0\\0 & 0 & 1& 0\\0 & 0& 0& 2\end{array}\right)

\mathbf{Post}=\left(\begin{array}{cccc}0 & 0 & 0 & 2\\1 & 0 & 0 & 0\\0 & 1& 1& 0\end{array}\right)

Rappresentazione grafica di una rete di Petri posto/transizione

Rappresentazione grafica di una rete di Petri posto/transizione


Matrice di incidenza

Matrice di incidenza \mathbf{C}

Data una rete N=\bigl{P\,,T\,,\mathbf{Pre}\,,\mathbf{Post}\bigr} con m posti e n transizioni la matrice di incidenza \mathbf{C}\in\mathbb{Z}^{m\times n} è definita come

\mathbf{C}=\mathbf{Post}-\mathbf{Pre}

Matrice di incidenza – osservazione

È importante notare che nel compattare l’informazione contenuta nelle matrici \mathbf{Pre} e \mathbf{Post}, spesso la matrice di incidenza \mathbf{C} perde qualche informazione sulla struttura della rete.

\mathbf{Pre}=\left(\begin{array}{ccc}1 & 1 & 0\\0 & 0 & 1\end{array}\right)
\mathbf{Post}=\left(\begin{array}{ccc}1 & 0 & 1\\0 & 1 & 0\end{array}\right)
\mathbf{C}=\left(\begin{array}{rrr}\mathbf{0} & -1 & 1\\0 & 1 & -1\end{array}\right)


Reti di Petri – Notazione

Data una transizione t\in T si indica con

^\bullet t=\bigl\{p\in P\ |\ \mathbf{Pre}(p\,,t)>0 \bigr\} – preset di t, insieme dei posti in ingresso a t
t^\bullet=\bigl\{p\in P\ |\ \mathbf{Post}(p\,,t)>0 \bigr\} – postset di t, insieme dei posti in uscita da t

Dato un posto p\in P si indica con

^\bullet p=\bigl\{t\in T\ |\ \mathbf{Post}(p\,,t)>0 \bigr\} – preset di p, insieme delle transizioni in ingresso a p
p^\bullet=\bigl\{t\in T\ |\ \mathbf{Pre}(p\,,t)>0 \bigr\} – postset di p, insieme delle transizioni in uscita da p

Marcatura di una rete di Petri

La marcatura consente di definire lo stato di una rete di Petri

Una marcatura (marking) è una funzione

\mathbf{m}: P\mapsto \mathbb{N}

che assegna ad ogni posto della rete un numero intero di gettoni (o token).

La coppia costituita da una rete N e dalla sua marcatura iniziale \mathbf{m}_0 è detta sistema rete di Petri o rete marcata, e viene indicata con \langle N\,,\mathbf{m}_0\rangle.

Esempio di rete marcata

I gettoni si indicano graficamente con dei cerchi neri

La marcatura può essere indicata mediante un vettore colonna con m componenti (se m sono i posti della rete)

In particolare per la rete di esempio si ha:

\mathbf{m}_0=\bigl[1\ 0\ 2\bigr]^T

Esempio di rete marcata

Esempio di rete marcata


Evoluzione dinamica di un sistema rete

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.

Abilitazione di una transizione

Condizione di abilitazione di una transizione

Data una rete N e una marcatura \mathbf{m}, una transizione t\in T è abilitata da \mathbf{m} se

\mathbf{m}\geq \mathbf{Pre}(\cdot\,,t)

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 t.

  • \mathbf{m}\bigl[t\rangle indica che t è abilitata da \mathbf{m}
  • \mathbf{m}\neg\bigl[t\rangle indica che t non è abilitata da \mathbf{m}

Scatto di una transizione

Una transizione t abilitata da una marcatura \mathbf{m} può scattare.

Lo scatto di una transizione t rimuove \mathbf{Pre}(p\,,t) gettoni da ogni posto e aggiunge \mathbf{Post}(p\,,t) ad ogni posto, determinando una nuova marcatura

\mathbf{m} '=\mathbf{m}+\mathbf{Post}(\cdot\,,t)-\mathbf{Pre}(\cdot\,,t) =\mathbf{m}+\mathbf{C}(\cdot\,,t)

\mathbf{m}\bigl[t\rangle\mathbf{m} ' indica che a partire da \mathbf{m} ', lo scatto della transizione t determina la marcatura \mathbf{m}'.

Scatto di una sequenza di transizioni

Scatto di una sequenza σ di transizioni abilitate

Una sequenza di transizioni \sigma=t^1t^2\ldots t^r\in T^\ast è abilitata da una marcatura  \mathbf{m} se

  • \mathbf{m}\bigl[t^1\rangle ~~~e ~~~\mathbf{m}\bigl[t^1\rangle\mathbf{m}_1<br />
  • \mathbf{m}_1\bigl[t^2\rangle ~~e~~ \mathbf{m}_1\bigl[t^2\rangle\mathbf{m}_2
  • \mathbf{m}_{r-1}\bigl[t^r\rangle ~~e~~ \mathbf{m}_{r-1}\bigl[t^r\rangle\mathbf{m}_r

\mathbf{m}\bigl[\sigma\rangle indica che \sigma è abilitata da \mathbf{m}, mentre \mathbf{m}\bigl[\sigma\rangle\mathbf{m}' indica che lo scatto di \sigma a partire da \mathbf{m} determina la marcatura \mathbf{m}'

Scatto di una sequenza – Esempio

La sequenza \sigma=t_4t_1 è abilitata da \matbf{m}=\bigl[1\ 0\ 2\bigr]^T e il suo scatto determina la marcatura

\mathbf{m}'=\bigl[2\ 1\ 0\bigr]^T

Scatto della sequenza \sigma=t_4t_1.

Scatto della sequenza

Scatto della sequenza


Linguaggio di una rete marcata

Linguaggio generato da una sistema rete

Il linguaggio (o comportamento) di una rete marcata \langle N\,,\mathbf{m}_0\rangle è l’insieme

L(N\,,\mathbf{m}_0)=\bigl\{\sigma\in T^\ast\ |\ \mathbf{m}_0\bigl[\sigma\rangle\bigr\}

Insieme di raggiungibilità di un sistema rete

Dato un sistema rete \langle N\,,\mathbf{m}_0\rangle, una marcatura \mathbf{m} si dice raggiungibile da \mathbf{m}_0 se esiste una sequenza \sigma\in L(N\,,\mathbf{m}_0) tale che \mathbf{m}_0\bigl[\sigma\rangle\mathbf{m}.

Pertanto l’insieme di raggiungibilità di una rete marcata \langle N\,,\mathbf{m}_0\rangle è dato da

R(N\,,\mathbf{m}_0)=\bigl\{\mathbf{m}\in\mathbb{N}^m\ |\ \exists\ \sigma\in L(N\,,\mathbf{m}_0)\ \text{tale che}\ \mathbf{m}_0\bigl[\sigma\rangle\mathbf{m}\bigr\}

Sequenza vuota

Sequenza vuota \varepsilon -Osservazione

Per definizione si ha che

\mathbf{m}\bigl[\varepsilon\rangle\quad \forall\ \mathbf{m}\in\mathbb{N}^m

e

\mathbf{m}\bigl[\varepsilon\rangle\mathbf{m}

Quindi \varepsilon\in L(N\,,\mathbf{m}_0) e \mathbf{m}_0\in R(N\,,\mathbf{m}_0).

Vettori di scatto

Definizione di vettore di scatto \mathbf{\sigma}

Data una rete N e una sequenza \sigma\in T^\ast, si definisce vettore di scatto (firing count vector) associato a \sigma il vettore \mathbf{\sigma}\in\mathbb{N}^n, la cui generica componente \mathbf{\sigma}_i=\mathbf{\sigma}(t_i) indica quante volte la transizione t_i compare in \sigma.

Esempio: T=\bigl\{t_1\,,t_2\,,t_3\bigr\}, \sigma=t_3t_1t_1t_3t_2 e \mathbf{\sigma}=\bigl[2\ 1\ 2\bigr]^T.

Equazione di stato

Sia \langle N\,,\mathbf{m}_0\rangle una rete marcata e sia \mathbf{C} la sua matrice di incidenza. Se \mathbf{m} è raggiungibile da \mathbf{m}_0 attraverso lo scatto delle transizioni nella sequenza \sigma, allora vale

\mathbf{m}=\mathbf{m}_0+\mathbf{C}\cdot\mathbf{\sigma}

Proposizione 1

Se \mathbf{m}_1\bigl[\sigma\rangle, \mathbf{m}_2\bigl[\sigma\rangle e \mathbf{m}_1\bigl[\sigma\rangle\bar{\mathbf{m}}_1, \mathbf{m}_2\bigl[\sigma\rangle\bar{\mathbf{m}}_2, allora

\bar{\mathbf{m}}_1-\mathbf{m}_1=\bar{\mathbf{m}}_2-\mathbf{m}_2

Proposizione 2

Se \mathbf{m}_1\geq\mathbf{m}_2, allora se \sigma è abilitata sotto \mathbf{m}_2 lo è anche sotto \mathbf{m}_1, vale a dire

L(N\,,\mathbf{m}_2)\subseteq L(N\,,\mathbf{m}_1)

Conflitto

Conflitto strutturale
Due transizioni t_1\,,t_2 si dicono in conflitto strutturale se ^\bullet t_1\cap ^\bullet t_2\neq \emptyset.

Conflitto effettivo
Due transizioni t_1\,,t_2 si dicono in conflitto effettivo se \mathbf{m}\geq \mathbf{Pre}(\cdot\,,t_1) e \mathbf{m}\geq \mathbf{Pre}(\cdot\,,t_2), ma \mathbf{m}\ngeqslant \mathbf{Pre}(\cdot\,,t_1)+\mathbf{Pre}(\cdot\,,t_2)

Rete etichettata

Una rete etichettata (o labeled net) è una 4-pla

N_l=\bigl(N\,,\mathbf{m}_0\,,l\,,F\bigr)

Dove la coppia \langle N\,,\mathbf{m}_0\rangle è un sistema rete e:

  • l: T\mapsto E è la funzione etichetta (labeling function) che associa ad ogni t\in T un evento dell’alfabeto E
  • F è un insieme finito di marcature finali

Estensione della funzione l

Estensione alle sequenze della funzione etichetta

È possibile estendere la funzione etichetta a sequenze di transizioni. In particolare

l:T^\ast \mapsto E^\ast
con

  • l(\varepsilon)=\varepsilon
  • l(\sigma t)=l(\sigma)l(t)

Linguaggio di Petri

Linguaggio generato e marcato da una rete etichettata N_l

Data una rete etichettata è possibile definire il linguaggio generato
\mathcal{L}\bigl(N_l\bigr)=\bigl\{w\in E^\ast\ |\ \exists\ \sigma\in L(N\,,\mathbf{m}_0)\,, w=l(\sigma)\bigr\}

il linguaggio marcato
\mathcal{L}\bigl(N_l\bigr)=\bigl\{w\in E^\ast\ |\ \exists\ \sigma\in L(N\,,\mathbf{m}_0)\,, \mathbf{m}_0\bigl[\sigma\rangle\mathbf{m}\,, \mathbf{m}\in F\ \mathrm{e}\  w=l(\sigma)\bigr\}

Composizione concorrente

Composizione concorrente tra RdP

La composizione concorrente tra due RdP etichettate N_{l_1}\,, N_{l_2} si ottiene fondendo le transizioni con la stessa etichetta.
Se N_l è la rete ottenuta facendo la composizione concorrente, allora:

\mathcal{L}\bigl(N_l\bigr)=\mathcal{L}\bigl(N_{l_1}\bigr) \| \mathcal{L}\bigl(N_{l_2}\bigr)
\mathcal{L}_m\bigl(N_l\bigr)=\mathcal{L}_m\bigl(N_{l_1}\bigr) \| \mathcal{L}_m\bigl(N_{l_2}\bigr)

Composizione concorrente – Algoritmo 1/3

Ingressi e Uscite

Ingressi: due reti etichettate N_{l_1}=\bigl(N_1\,,\mathbf{m}_{0_1}\,,l_1\,,F_1\bigr), N_{l_2}=\bigl(N_2\,,\mathbf{m}_{0_2}\,,l_2\,,F_2\bigr)
con N_1=\bigl(P_1\,,T_1\,,\mathbf{Pre}_1\,,\mathbf{Post}_1\bigr), N_2=\bigl(P_2\,,T_2\,,\mathbf{Pre}_2\,,\mathbf{Post}_2\bigr)

Uscita: rete composizione concorrente N_l=\bigl(N\,,\mathbf{m}_0\,,l\,,F\bigr), con N=\bigl(P\,,T\,,\mathbf{Pre}\,,\mathbf{Post}\bigr)

Composizione concorrente – Algoritmo 2/3

  1. P=P_1\	cup P_2
  2. l’insieme delle transizioni T si determina come segue:

a) se \bar{t}\in T_1 e l_1(\bar{t})\in E_1\setminus E_2, allora l(\bar{t})=l_1(\bar{t}) e \forall\ p'\in P_1\,, \mathbf{Pre}(p'\,,\bar{t})=\mathbf{Pre}_1(p'\,,\bar{t})\,, \mathbf{Post}(p'\,,\bar{t})=\mathbf{Post}_1(p'\,,\bar{t}) e \forall\ p''\in P_2\,, \mathbf{Pre}(p''\,,\bar{t})=0\,, \mathbf{Post}(p''\,,\bar{t})=0
b) se \bar{t}\in T_2 e l_2(\bar{t})\in E_2\setminus E_1, allora l(\bar{t})=l_2(\bar{t}) e \forall\ p''\in P_2\,, \mathbf{Pre}(p''\,,\bar{t})=\mathbf{Pre}_2(p''\,,\bar{t})\,, \mathbf{Post}(p''\,,\bar{t})=\mathbf{Post}_2(p''\,,\bar{t}) e \forall\ p'\in P_1\,, \mathbf{Pre}(p'\,,\bar{t})=0\,, \mathbf{Post}(p'\,,\bar{t})=0

Composizione concorrente – Algoritmo 3/3

c) Sia e un evento tale che e\in E_1\cap E_2. Se e etichetta n_1 transizioni in N_1 e n_2 transizioni in N_2, allora si introducono n_1\times n_2 transizioni \tilde{t}, ognuna associata ad una coppia

3. (t_1\,,t_2)\,, t_1 \inT_1\,, t_2\in T_2, e \forall\ p'\in P_1\,, \mathbf{Pre}(p'\,,\tilde{t})=\mathbf{Pre}_1(p'\,,t_1)\,, \mathbf{Post}(p'\,,\tilde{t})=\mathbf{Post}_1(p'\,,t_1)\,, e \forall\ p''\in P_2\,, \mathbf{Pre}(p''\,,\tilde{t})=\mathbf{Pre}_2(p''\,,t_2)\,, \mathbf{Post}(p''\,,\tilde{t})=\mathbf{Post}_2(p''\,,t_2)\,,
\mathbf{m}_0=\bigl[\mathbf{m}_{0_1}^T\ \mathbf{m}_{0_2}^T\bigr]^T

4.F=F_1\times F_2\Rightarrow se \mathbf{m}\in F allora \mathbf{m}=\bigl[\mathbf{m}_1^T\ \mathbf{m}_2^T\bigr]^T con \mathbf{m}_1\in F_1\,, \mathbf{m}_2\in F_2

I materiali di supporto della lezione

Capitolo 4, paragrafi 4.1 e 4.2 da Di Febbraro-Giua.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion