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 » 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à

  1. Se il grafo di raggiungibilità ha un numero finito di nodi, allora: \mathbf{m} è un nodo del grafo
  2. 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}'
  3. 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

  1. La marcatura iniziale \mathbf{m}_0 è il nodo radice dell’albero di copertura. 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 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.

  1. 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à)
  2. 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à)
  3. 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)
  4. 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).

I materiali di supporto della lezione

Capitolo 4, paragrafo 4.3 (da pagina 164 a pagina 172) 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