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

Gianmaria De Tommasi » 9.Reti di Petri – Stima dell'insieme di raggiungibilità e classificazione


Sommario della lezione

  • Metodi algebrici per la stima dell’insieme di raggiungibilità
    • P-vettori
    • T-vettori
  • Classificazione delle reti di Petri

Stima dell’insieme di raggiungibilità

Osservazioni preliminari.

  1. Seppur teoricamente decidibile, il problema della raggiungibilità è molto oneroso dal punto di vista computazionale.
  2. Nel caso di reti limitate, per risolvere il problema della raggiungibilità si può pensare di utilizzare il grafo di raggiungibilità.
  3. Nel caso di reti non limitate, il grafo di copertura consente di formulare condizioni o solo necessarie o solo sufficienti per quanto riguarda il problema della raggiungibilità.

Nasce l’esigenza di poter effettuare delle stime dell’insieme R\bigl(N\,,\mathbf{m}_0\bigr).

Le stime dell’insieme R\bigl(N\,,\mathbf{m}_0\bigr) possono essere calcolate efficientemente utilizzando dei metodi algebrici basati sull’equazione di stato della rete.

Insieme delle marcature potenzialmente raggiungibili

Definizione.

Dato un sistema rete \langle N\,,\mathbf{m}_0\rangle, l‘insieme delle marcature potenzialmente raggiungibili è definito come:

PR\bigl(N\,,\mathbf{m}_0\bigr):=\bigl\{\mathbf{m}\in\mathbb{N}^m\ |\ \exists\ \mathbf{y}\in\mathbb{N}^n\ :\ \mathbf{m}=\mathbf{m}_0+\mathbf{C}\cdot \mathbf{y}\bigr\}

Si noti che vale

R\bigl(N\,,\mathbf{m}_0\bigr)\subseteq PR\bigl(N\,,\mathbf{m}_0\bigr)

Esempio

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

Utilizzando \mathbf{y}=\bigl[1\ 0\ 1\bigr]^T, è facile verificare che

\mathbf{m}=\bigl[1\ 0\ 0\bigr]\in PR\bigl(N\,,\mathbf{m}_0\bigr)

mentre

\mathbf{m}=\bigl[1\ 0\ 0\bigr]\notin R\bigl(N\,,\mathbf{m}_0\bigr)

Si noti che è presente un ciclo (transizione t_3).


P-vettori

Un vettore \mathbf{x}\in\mathbb{N}^m con \mathbf{x}\gneq 0 (\mathbf{x} deve avere almeno una componente non nulla) è detto:

  • P-Invariante se \mathbf{x}^T\cdot\mathbf{C}=\mathbf{0}^T
  • P-Vettore Crescente se \mathbf{x}^T\cdot\mathbf{C}\geq\mathbf{0}^T\
  • P-Vettore  Decrescente se \mathbf{x}^T\cdot\mathbf{C}\leq\mathbf{0}^T\

T-vettori

Un vettore \mathbf{y}\in\mathbb{N}^n con \mathbf{y}\gneq 0 (\mathbf{y} deve avere almeno una componente non nulla) è detto:

  • T-Invariante se \mathbf{C}\cdot\mathbf{y}^T=\mathbf{0}
  • T-Vettore Crescente se \mathbf{C}\cdot\mathbf{y}^T\geq\mathbf{0}
  • T-Vettore  Decrescente se \mathbf{C}\cdot\mathbf{y}^T\leq\mathbf{0}

Supporto

Supporto di un P(T)-vettore.

Se \mathbf{x} (\mathbf{y}) è un P (T) vettore, l’insieme dei posti (transizioni) per cui \mathbf{x}(i)>0 (\mathbf{y}(i)>0) si dice Supporto del P (T) vettore e si denota con il simbolo \|\mathbf{x}\| (\|\mathbf{y}\|)

P-vettori – Risultati

Proposizione.

Si consideri un sistema rete \langle N\,,\mathbf{m}_0\rangle e siano:

  • \mathbf{x}_I un P-invariante
  • \mathbf{x}_C un P-vettore crescente
  • \mathbf{x}_D un P-vettore decrescente

Per ogni sequenza \sigma=t^1t^2\ldots t^k\ldots\in L\bigl(N\,,\mathbf{m}_0\bigr) se
\mathbf{m}_0\bigl[t^1\rangle\mathbf{m}_1\ldots\mathbf{m}_{k-1}\bigl[t^k\rangle\mathbf{m}_k\ldots
allora vale:

  • \mathbf{x}_I^T\mathbf{m}_k=\mathbf{x}_I^T\mathbf{m}_0\ forall\ k
  • \mathbf{x}_C^T\mathbf{m}_{k+1}\geq\mathbf{x}_C^T\mathbf{m}_k\ forall\ k
  • \mathbf{x}_D^T\mathbf{m}_{k+1}\leq\mathbf{x}_D^T\mathbf{m}_k\ forall\ k

T-vettori – Risultati

Proposizione.

Si consideri un sistema rete \langle N\,,\mathbf{m}_0\rangle e sia \sigma una sequenza tale che \mathbf{m}_0\bigl[\sigma\rangle e \mathbf{m}_0\bigl[\sigma\rangle\mathbf{m}.  Si ha che:

  • \sigma è un T-invariante \iff\ \mathbf{m}=\mahtbf{m}_0, cioè \sigma è stazionaria
  • \sigma è un T-vettore crescente \iff\ \mathbf{m}\geq\mahtbf{m}_0
  • \sigma è un T-vettore decrescente \iff\ \mathbf{m}\leq\mahtbf{m}_0

Insieme X-invariante

Definizione.

Si consideri un sistema rete \langle N\,,\mathbf{m}_0\rangle e sia

\mathbf{X}=\bigl[\mathbf{x}_1\ \mathbf{x}_2\ \ldots\ \mathbf{x}_k\bigr]

una matrice m\times k la cui colonna i-ma \mathbf{x}_i è un P-invariante.

Per definizione, l’Insieme X-Invariante è

I_{\mathbf{X}}\bigl(N\,,\mathbf{m}_0\bigr):=\bigl\{\mathbf{m}\in\mathbb{N}^m\ |\ \mathbf{X}^T\cdot\mathbf{m}=\mathbf{X}^T\cdot\mathbf{m}_0\bigr\}

Stima dell’insieme di raggiungibilità

Proposizione.

Si consideri un sistema rete \langle N\,,\mathbf{m}_0\rangle, allora vale

R\bigl(N\,,\mathbf{m}_0\bigr)\subseteq PR\bigl(N\,,\mathbf{m}_0\bigr)\subseteq I_{\mathbf{X}}\bigl(N\,,\mathbf{m}_0\bigr)

Dimostrazione
Sia \mathbf{m}\in PR\bigl(N\,,\mathbf{m}_0\bigr)\Rightarrow \mathbf{m}=\mathbf{m}_0+\mathbf{C}\cdot\mathbf{y}\Rightarrow \mathbf{X}^T\mathbf{m}=\mathbf{X}^T\mathbf{m}_0+\mathbf{X}^T\cdot\mathbf{C}\cdot\mathbf{y}=\mathbf{X}^T\mathbf{m}_0

Classificazione delle reti di Petri

Reti ordinarie, pure e ristrette.

  • Una rete di Petri si dice Ordinaria se i suoi archi hanno tutti peso unitario
  • Una rete di Petri si dice Pura se la rete non contiene cappi, cioè se \forall\ p\ \mathrm{e}\ t\ \mathrm{vale}\ \mathbf{Pre}\bigl(p\,,t\bigr)\mathbf{Post}\bigl(p\,,t\bigr)=0
  • Una rete di Petri pura e oridnaria si dice Ristretta.

Classificazione delle reti di Petri  (segue)

Reti ristrette.

Se ci si limita all’utilizzo delle reti di Petri Ristrette non si limita il potere espressivo delle reti.

Ovviamente utilizzando reti di Petri ristrette Il potere espressivo delle reti ristrette si otterrà una rappresentazione meno compatta.

Classificazione delle reti di Petri (segue)

Reti acicliche.

Una rete di Petri si dice Aciclica se non contiene cicli orientati.

Per una rete aciclica non esistono soluzioni spurie dell’equazione di stato, vale a dire

R\bigl(N\,,\mathbf{m}_0\bigr)=PR\bigl(N\,,\mathbf{m}_0\bigr)

Sottoclassi di reti ordinarie -Macchine di Stato

Una Macchina di Stato è una rete di Petri ordinaria per la quale vale

\sum_{p\in P}\mathbf{Pre}\bigl(p\,,t\bigr)=\sum_{p\in P}\mathbf{Post}\bigl(p\,,t\bigr) =1\,,\quad\forall\ t\in T

Ogni transizione ha un solo arco entrante ed un solo arco uscente.

  • È possibile rappresentare le scelte.
  • È possibile rappresentare un forma limitata di parallelismo sfruttando marcature maggiori di 1.

Sottoclassi di reti ordinarie- Proprietà delle Macchine di Stato

  • Una Macchina di Stato è sempre strattamente conservativa \Rightarrow è limitata \Rightarrow\ R\bigl(N\,,\mathbf{m}_0\bigr) ha cardinalità finita
  • Una Macchina di Stato marcata \langle N\,,\mathbf{m}_0\rangle è viva se N è fortemente connesso e \mathbf{m}_0 ha almeno un elemento diverso da zero
  • R\bigl(N\,,\mathbf{m}_0\bigr)=PR\bigl(N\,,\mathbf{m}_0\bigr)

Sottoclassi di reti ordinarie- Grafi Marcati

Un Grafo Marcato è una rete di Petri ordinaria per la quale vale

\sum_{t\in T}\mathbf{Pre}\bigl(p\,,t\bigr)=\sum_{t\in T}\mathbf{Post}\bigl(p\,,t\bigr) =1\,,\quad\forall\ p\in P

Ogni posto ha un solo arco entrante ed un solo arco uscente.

  • Non è possibile rappresentare le scelte.
  • È possibile rappresentare il parallelismo e la sincronizzazione.

Sottoclassi di reti ordinarie-Proprietà dei Grafi Marcati

  • Ogni ciclo orientato di un Grafo Marcato è un P-invariante.
  • Il vettore \mathbf{1} è un T-invariante.
  • Un Grafo Marcato \langle N\,,\mathbf{m}_0\rangle è vivo \iff in \mathbf{m}_0 c’è una componente diversa da zero in ogni ciclo orientato.

Sottoclassi di reti ordinarie- Dualità tra Macchine di Stato e Grafi Marcati

Se  N=\bigl(P\,,T\,,\mathbf{Pre}\,,\mathbf{Post}\bigr) è una Macchina di Stato, allora N'=\bigl(T\,,P\,,\mathbf{Pre}^T\,,\mathbf{Post}^T\bigr) è un Grafo Marcato.

Sottoclassi di reti ordinarie – Reti a Scelta Libera

Una rete di Petri ordinaria è una RETE A SCELTA LIBERA se
\forall\ p\in P se  \mathbf{Pre}\bigl(p\,,t\bigr)=1 (se esiste un arco da  p a t), allora

\biggl[\forall\ t'\neq t\,,\mathbf{Pre}\bigl(p\,,t'\bigr)=0 \biggr]\bigvee\biggl[\forall\ p'\neq p\,,\mathbf{Pre}\bigl(p'\,,t\bigr)=0\biggr]

Se c’è una arco in uscita da p verso t, questo arco o è l’unico arco in uscita a p, oppure è l’unico arco in ingresso a t.

  • Non consente scelta e sincronizzazione contemporaneamente.

I materiali di supporto della lezione

Capitolo 4, paragrafi 4.4, 4.5 e 4.6 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