Home

Federica EU

1/30

Installa flash player

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

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

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

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$

$\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

$P=P_1\ cup P_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$