Home

Federica EU

1/20

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.

Seppur teoricamente decidibile, il problema della raggiungibilità è molto oneroso dal punto di vista computazionale.
Nel caso di reti limitate, per risolvere il problema della raggiungibilità si può pensare di utilizzare il grafo di raggiungibilità.
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