Home

Federica EU

1/17

Gianmaria De Tommasi » 7.Reti di Petri – Grafo di raggiungibilità e grafo di copertura

Sommario della lezione

Grafo di raggiungibilità
Grafo di copertura

Rappresentazione grafica di $R(N\,,\mathbf{m}_0)$

Grafo di raggiungibilità & grafo di copertura

Il grafo di raggiungibilità è una rappresentazione grafica dell’insieme di raggiungibilità $R(N\,,\mathbf{m}_0)$ di una rete di Petri.
Nel grafo di raggiungibilità associato ad un sistema rete $\langle N\,,\mathbf{m}_0\rangle$ ogni vertice (nodo) corrisponde ad una marcatura raggiungibile da $\mathbf{m}_0$
Se $R(N\,,\mathbf{m}_0)$ ha cardinalità infinita il grafo di raggiungibilità dovrebbe avere un numero di nodi infinito!
Nel caso di reti di Petri il cui insieme di raggiungibilità abbia cardianlità infinita, si utilizza il grafo di copertura per rappresentare graficamente $R(N\,,\mathbf{m}_0)$ in maniera finita.
Nel grafo di copertura ogni vertice “copre” una marcatura raggiungibile

Grafo di raggiungibilità

Algoritmo per la costruzione del grafo di raggiungibilità

Ingresso: sistema rete $\langle N\,,\mathbf{m}_0\rangle$

Uscita: grafo di raggiungibilità

1. La marcatura iniziale $\mathbf{m}_0$ è il nodo radice del grafo di raggiungibilità. Il nodo radice non è inizialmente etichettato.

2. Si consideri un nodo non etichettato associato alla marcatura $\mathbf{m}$

a) $\forall\ t\in T$ tali che $\mathbf{m}\big[t\rangle$

- Si calcoli $\mathbf{m}'=\mathbf{m}+\mathbf{C}(\cdot,t)$
- Se non esiste un nodo associato a $\mathbf{m}'$ lo si aggiunga senza etichetta
- Si aggiunga un arco etichettato con $t$ tra $\mathbf{m}$ e $\mathbf{m}'$

b) Si etichetti il nodo associato a $\mathbf{m}$ come old

3. Se esistono nodi senza etichetta si ritorni al passo 2

4. Si rimuovano le etichette

Grafo di raggiungibilità – Esempio 1/3

Sistema rete $\langle N\,,\mathbf{m}_0\rangle$ con $\mathbf{m}_0=\bigl[1\ 1\ 0\bigr]^T$ (figura a lato).
Transizioni abilitate

$t_1\,,t_2 \,,t_3$

Grafo di raggiungibilità – Esempio 2/3

Sistema rete $\langle N\,,\mathbf{m}_0\rangle$ con $\mathbf{m}_0=\bigl[1\ 1\ 0\bigr]^T$ (figura a lato).

Grafo di raggiungibilità – Esempio 3/3

Sistema rete $\langle N\,,\mathbf{m}_0\rangle$ con $\mathbf{m}_0=\bigl[1\ 1\ 0\bigr]^T$ (figura a lato).

Grafo di raggiungibilità – Proprietà

Se il grafo di raggiungibilità ha un numero finito di nodi, allora: $\mathbf{m}$ è un nodo del grafo
La marcatura $\mathbf{m}'$ è raggiungibile da una marcatura $\mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr)\iff$ esistono nel grafo due nodi $\mathbf{m}$ e $\mathbf{m}'$ , ed esiste un cammino orientato che va da $\mathbf{m}$ ad $\mathbf{m}'$
La transizione $t$ è abilitata da una marcatura $\mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr)\iff$ esiste nel grafo un nodo $\mathbf{m}$ da cui esce un arco etichettato con $t$

Grafo di raggiungibilità – Proprietà (segue)

“Esplosione” dello spazio di stato

La rappresentazione dell’insieme di raggiungibilità $R\bigl(N\,,\mathbf{m}_0\bigr)$ mediante grafo di raggiungibilità fa perdere la proprietà di compattezza nella rappresentazione dello spazio di stato tipica delle reti di Petri

Di fatto il grafo di raggiungibilità non è nient’altro che un automa i cui stati sono le marcature raggiungibili da $\mathbf{m}_0$

Il numero di nodi del grafo di raggiungibilità aumenta velocemente al aumentare del numero di gettoni nella marcatura iniziale $\mathbf{m}_0$

Per esempio si disegni il grafo di raggiungibilità per la rete d’esempio con $\mathbf{m}'_0=\bigl[2\ 2\ 0\bigr]^T$ e $\mathbf{m}''_0=\bigl[3\ 3\ 0\bigr]^T$

Reti con spazio di stato a cardinalità infinita

Reti di Petri con insieme di raggiungibilità a cardinalità infinita

Se $R\bigl(N\,,\mathbf{m}_0\bigr)$ ha cardinalità infinita l’algoritmo per la costruzione del grafo di raggiungibilità non termina mai!

In questo caso ci sono delle transizioni il cui scatto porta ad incrementare sempre almeno una componente del vettore delle marcature $\mathbf{m}$ .

Per poter rappresentare insieme di raggiungibilità a cardianlità infinita con un grafo con un numero finito di nodi si introduce il simbolo $\omega$

Albero di copertura & Grafo di copertura

Albero di copertura

L’algoritmo per la costruzione del grafo di copertura è basato sulla un altro grafo chiamato albero di copertura.

La costruzione dell’albero di copertua è simile quella del grafo di raggiungibilità.

Albero di copertura

Ingresso: sistema rete $\langle N\,,\mathbf{m}_0\rangle$

Uscita: albero di copertura

La marcatura iniziale $\mathbf{m}_0$ è il nodo radice dell’albero di copertura. Il nodo radice non è inizialmente etichettato.
Si consideri un nodo non etichettato associato alla marcatura $\mathbf{m}$

a) $\forall\ t\in T$ tali che $\mathbf{m}\big[t\rangle$

Si calcoli $\mathbf{m}'=\mathbf{m}+\mathbf{C}(\cdot,t)$

Se esiste un nodo associato a $\bar{\mathbf{m}}$ sul cammino che parte da $\mathbf{m}_0$ e finisce a $\mathbf{m}'$ , tale che $\mathbf{m}'\gneq\bar{\mathbf{m}}$ , allora

sia $\bar{\mathbf{m}}'$ il vettore che si ottiene da $\mathbf{m}'$ sostituendo tutte le componenti crescenti con $\omega$

Altrimenti $\bar{\mathbf{m}}'=\mathbf{m}'$

Albero di copertura (segue)

Si aggiunga $\bar{\mathbf{m}}'$ all’albero

Si aggiunga un arco etichettato con $t$ tra $\mathbf{m}$ e $\bar{\mathbf{m}}'$

Se esiste già un nodo associato a $\bar{\mathbf{m}}'$ nell’albero, etichettare il nodo come copy

Etichettare $\mathbf{m}$ come old

3. Se esistono nodi senza etichetta si ritorni al passo 2.

Grafo di copertura

Algoritmo per la costruzione del grafo di copertura

Ingresso: albero di copertura associato al sistema rete $\langle N\,,\mathbf{m}_0\rangle$ .

Uscita: grafo di copertura.

1. Se l’albero di copertura non contiene nodi etichettati come copy vai al passo 4.
2. Si consideri un nodo associato alla marcatura $\mathbf{m}$ etichettato come copy. Per costruzione tale nodo non ha archi uscenti e in ingresso ha un solo arco associato a $t$ proveniente da un nodo $\mathbf{m}'$ Inoltre esiste sicuramente nell’albero un nodo associato alla marcatura $\mathbf{m}$ ma etichettato come old. Allora:

Si rimuova l’arco entrante $t$ al nodo associato a $\mathbf{m}$ ed etichettato come copy

Si aggiunga un arco $t$ al nodo associato a $\mathbf{m}$ ed etichettato come old

Si rimuova il nodo associato a $\mathbf{m}$ ed etichettato come copy

3. Se esistono ancora nodi etichettato come copy si ritorni al passo 2
4. Eliminare le etichette.

Albero di copertura – Esempio

Sistema rete $\langle N\,,\mathbf{m}_0\rangle$ con $\mathbf{m}_0=\bigl[1\ 0\ 0\bigr]^T$ (figura a lato).

Grafo di copertura – Esempio

Sistema rete $\langle N\,,\mathbf{m}_0\rangle$ con $\mathbf{m}_0=\bigl[1\ 0\ 0\bigr]^T$ (figura a lato).

$\omega$ -copertura

Una marcatura $\mathbf{m}$ si dice $\omega$ -coperta da un’altra marcatura $\mathbf{m}_\omega$ se

$\mathbf{m}_\omega(p)=\mathbf{m}(p)\ \forall\ p\ |\ \mathbf{m}_\omega(p)\neq\omega$

La notazione $\mathbf{m}_\omega\geq_\omega\mathbf{m}$ indica che la marcatura $\mathbf{m}_\omega$ $\omega$ -copre la marcatura $\mathbf{m}$ .

Grafo di copertura – Proprietà

Si consideri un sistema rete $\langle N\,,\mathbf{m}_0\rangle$ e il grafo di copertura associato.

La marcatura $\mathbf{m}$ è raggiungibile da $\mathbf{m}_0 \Rightarrow$ esiste nel grafo un nodo associato a $\mathbf{m}_\omega\geq_\omega\mathbf{m}$ (condizione necessaria per la raggiungibilità)
La marcatura $\mathbf{m}$ è raggiungibile da $\mathbf{m}_0 \Leftarrow$ $\mathbf{m}\in\mathbb{N}^m$ è un nodo del grafo (condizione sufficiente per la raggiungibilità)
Sia $\mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr)$ , la sequenza $\sigma=t_{j_1}t_{j_2}\ldots$ appartiene a $L\bigl(N\,,\mathbf{m}_0\bigr)$ e può essere generata con la traiettoria $\mathbf{m}\bigl[t_{j_1}\rangle\mathbf{m}'\bigl[t_{j_2}\rangle\mathbf{m}''\dots\Rightarrow$ esiste nel grafo di copertura un cammino orientato $\gamma=\mathbf{m}_\omega t_{j_1}\mathbf{m}'_\omega t_{j_2}\mathbf{m}''_\omega\ldots$ con $\mathbf{m}_\omega\geq_\omega\mathbf{m}\,, \mathbf{m}'_\omega\geq_\omega\mathbf{m}'\,, \mathbf{m}''_\omega\geq_\omega\mathbf{m}''$ (condizione necessaria)
Sia $\mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr)$ , la sequenza $\sigma=t_{j_1}t_{j_2}\ldots$ appartiene a $L\bigl(N\,,\mathbf{m}_0\bigr)$ e può essere generata con la traiettoria $\mathbf{m}\bigl[t_{j_1}\rangle\mathbf{m}'\bigl[t_{j_2}\rangle\mathbf{m}''\dots\Leftarrow$ esiste nel grafo di copertura un cammino orientato $\gamma=\mathbf{m}_\omega t_{j_1}\mathbf{m}'_\omega t_{j_2}\mathbf{m}''_\omega\ldots$ con $\mathbf{m}\,,\mathbf{m}'\,,\mathbf{m}''\,,\ldots\in\mathbb{N}^m$ (condizione sufficiente).