Reti di Petri temporizzate

Le reti di Petri temporizzate (RPT) sono un'estensione delle reti P/T in cui è introdotta la variabile tempo. Sono anche conosciute come Timed Petri Net (TPN).

Nelle reti di Petri temporizzate il funzionamento dei posti e delle transizioni è vincolato anche allo scorrere del tempo.

In particolar modo dei tempi di ritardo.

Nota. Essendo un'estensione delle reti di Petri, le TPN ereditano gran parte delle proprietà delle reti P/T non temporizzate. Quindi, molte regole sono le stesse.

Come funziona una rete di Petri temporizzata

La rete è associata a una struttura di temporizzazione che specifica in quali istanti di tempo si possono verificare gli eventi e le regole di scatto.

Esistono diverse tipologie di strutture di temporizzazione. Le principali sono la temporizzazione sui posti e la temporizzazione sulle transizioni.

Temporizzazione sui posti

In una struttura di temporizzazione basata sui posti, le marche che entrano in un posto abilitano le transizioni collegate dopo un lasso di tempo. Quindi, non sono subito disponibili.

Nota. La temporizzazione sui posti è equivalente a quella sulle transizioni. E' la strada meno seguita nella letteratura dei sistemi a eventi discreti. In genere, si preferisce la struttura a temporizzazione sulle transizioni.

Temporizzazione sulle transizioni

In una struttura di temporizzazione basata sulle transizioni lo scatto è sottoposto a un tempo di ritardo.

Quando la transizione viene abilitata nell'istante t₁, comincia un tempo di attesa d₁.

Lo scatto effettivo avviene nell'istante t₁+d₁.

Esempio

Questa rete temporizzata ha una sola transizione a cui ho associato un ritardo di 2 secondi.

Nell'istante t=0 la transizione t₁ viene abilitata dalla marca nel posto p₁.

Lo scatto non è però immediato, avviene dopo due secondi nell'istante t=2.

A cosa serve il ritardo? Questo lasso di attesa è utile per far svolgere una determinata attività. Quindi, il ritardo d₁ deve sempre essere pari o superiore alla durata dell'attività. Ad esempio, un cancello automatico si apre, poi si chiude automaticamente dopo un lasso di tempo sufficiente al passaggio dell'automobile.

Esistono due metodi alternativi di temporizzazione.

• Scatto atomico
• Scatto in tre fasi

Lo scatto atomico

Ogni transizione è associata a un tempo di ritardo tra abilitazione e scatto.

Lo scatto avviene dopo un lasso di tempo. Soltanto al momento dello scatto le marche sono prelevate dal posto di origine e spostate in quello di destinazione.

Le marche sono prelevate ex-post ossia al termine del tempo di attesa (ritardo).

Quindi, durante il tempo di attesa restano disponibili per altre transizioni della rete.

Nota. Sempre che le marche siano ancora presenti nel posto ossia se la transizione è ancora abilitata. Altre transizioni potrebbero aver usato le marche nel posto durante il lasso di ritardo. In caso di conflitto, quando due transizioni abilitate impegnano la stessa marca in un posto, lo scatto avviene soltanto nella transizione con ritardo minore. L'altra transizione viene disabilitata. Inoltre, ogni transizione può avere tempi di ritardo diversi. Quindi, una transizione abilitata prima potrebbe essere disabilitata da un'altra transizione abilitata successivamente, se quest'ultima ha un lasso di ritardo sufficientemente più piccolo.

Lo scatto in tre fasi

Lo scatto è suddiviso in tre fasi.

1. Nella prima fase la marche sono prelevate dal posto di origine. Quindi, non sono più disponibili.
2. Nella seconda fase il processo resta in attesa per un lasso di tempo di ritardo associato alla transizione.
3. Nella terza fase le marche sono depositate nel posto di destinazione.

Nello scatto a tre fasi le marche sono immediatamente prelevate dal posto di origine.

Quindi, sono vincolate ex-ante e non possono essere usate da altre transizioni durante il tempo di attesa.

Nota. Le transizioni temporizzate sono indicate in modo diverso. Ad esempio, possono essere rappresentate con un rettangolo nero più spesso rispetto alle altre oppure un colore diverso.

Il problema delle marche scomparse

Durante il ritardo le marche scompaiono dalla rete.

Questo può comportare problemi di calcolo durante l'analisi vettoriale della rete.

Per risolvere il problema ci sono due soluzioni

1. Posso modificare la struttura della rete durante ogni tempo di attesa, sostituendo la transizione in attesa con una sottostruttura temporanea composta da due transizioni, un posto e la marca (o le marche). Poi rimuoverla al momento dello scatto effettivo.
   

   Nota. La prima transizione della struttura temporanea è immediata (ritardo pari a zero) per impegnare immediatamente il token. Questa soluzione risolve il problema delle marche scomparse ma complica notevolamente la gestione della rete. Non è la strada migliore.

2. Posso vincolare la marca lasciandola nel posto di origine. Il prelievo avviene al momento dello scatto. Durante il tempo di attesa (ritardo) la marca non può essere usata da altre transizioni della rete.
   

   Nota. E' la strada migliore per risolvere il problema perché la struttura della rete non cambia. La rete ha lo stesso numero di posti, transizioni e marche in ogni momento. Devo semplicemente aggiungere una variabile per ogni marca in cui scrivere eventualmente quale transizione ha già impegnato la marca. Se le marche non sono molte, è la soluzione preferibile.

Le transizioni deterministiche e stocastiche

Per associare il tempo di ritardo a ogni transizione posso seguire un approccio deterministico o stocastico.

• Transizioni immediate
  Le transizioni immediate hanno un tempo di attesa nullo d_i=0 e coincidono con le reti P/T non temporizzate.

  Esempio. Ecco un esempio pratico di transizioni immediate. Ogni transizione ha un tempo nullo di attesa tra abilitazione e scatto.
  

• Transizioni deterministiche
  Le transizioni deterministiche hanno un tempo di ritardo prefissato e noto a priori. Possono essere costanti oppure variabili dipendenti da una funzione di calcolo.

  Esempio. In una rete le transizioni deterministiche sono rappresentate con un rettangolo nero (o con un colore apposito) e sono associate a un tempo di ritardo. Ad esempio, in questa rete la transizione t₁ ha un tempo di ritardo di d₁=0.5 secondi, la transizione t₂ di d₂=2.5 secondi e la transizione t₃ di d₃=0.7 secondi.
  

• Transizioni stocastiche
  Le transizioni stocastiche hanno un tempo di tardo associato a una variabile aleatoria in funzione di una distribuzione di probabilità.
  • Le transizioni stocastiche esponenziali usano la distribuzione esponenziale dove il tempo medio di ritardo è l'inverso della frequenza di scatto λ_i della transizione t_i, $$ d_i = \frac{1}{λ_i} $$ perché la distribuzione della probabilità dipende dalla frequenza di scatto. $$ f_i(x) = λ_i e^{-λ_ix} $$

    Esempio. In una rete P/T le transizioni stocastiche sono rappresentate con un rettangolo bianco o con un colore diverso. Inoltre, in ogni transizione è indicato il parametro λ_i che determina la distribuzione di probabilità del ritardo della transizione.
    

  • Le transizioni stocastiche estese usano altre distribuzioni di probabilità, diverse da quella esponenziale.
  • Le transizioni stocastiche in funzione della marcatura hanno una distribuzione della probabilità che varia in base alla marcatura corrente della rete.

La memoria delle transizioni

Oltre alla distribuzione di probabilità (deterministica o stocastica), nelle reti temporizzate è molto importante anche la tipologia della memoria nelle transizioni.

Ogni transizione deve avere una memoria in cui registrare il ritardo.

Ci sono due soluzioni possibili

• Memoria globale o totale (permanente)
  Ogni transizione è associata a una variabile. Il ritardo viene conservato anche se la transizione non scatta.
• Memoria di abilitazione (temporanea)
  Ogni transizione abilitata è associata a una variabile temporanea. Quando la transizione viene disabilitata, l'informazione sul ritardo viene eliminata. Quindi, il ritardo si azzera (resetta).

Un esempio pratico

In questa rete il posto p₀ abilita due transizioni con tempi di ritardo diversi.

La transizione t₁ ha un ritardo d₁=0.5 mentre t₂ ha un ritardo d₂=0.7

Poiché la transizione t₁ ha un tempo di attesa inferiore di t₂, la transizione t₁ è sicuramente la prima a scattare dopo 0.5 secondi.

Con lo scatto di t₁ la marca passa dal posto p₀ al posto p₁ e le transizioni t₁ e t₂ sono disabilitate.

Nota. Il conteggio del ritardo nella transizione t₂ si ferma dopo 0.5 secondi quando scatta la transizione t₁. Per questa ragione il ritardo d₂ è 0.2 ossia d₂=0.7-0.5=0.2. Viceversa, il ritardo della transizione d₁=0 perché la transizione t₁ è scattata dopo 0.5 secondi. Quando una transizione scatta il ritardo torna al suo valore pieno d₁=0.5

La transizione t₃ ha un ritardo di un secondo d₃=1.0

Pertanto, dopo un secondo il posto p₀ riceve di nuovo la marca e riabilita le transizioni t₁ e t₂.

A questo punto, l'evoluzione futura della rete cambia a seconda del tipo di memoria adottato (totale o di abilitazione).

Il caso della memoria totale

Nel caso della memoria totale, la rete conserva il ritardo delle transizioni d₁=0.5 (t₁ è scattata) e d₂=0.2.

La transizione t₂ non è scattata e il countdown si è fermato a 0.2 dalla fine.

Pertanto, quando il posto p₀ riabilita le transizioni t₁ e t₂, sarà la transizione t₂ a scattare dopo 0.2 secondi.

In questo caso la marca si sposta dal posto p₀ al posto p₂.

Nota. Dopo lo scatto il ritardo della transizione t₂ (scattata) viene resettato da zero a d₂=0.7. Viceversa, il ritardo della transizione t₁ (non scattata) si ferma a d₁=0.5-0.2=0.3.

Il caso della memoria di abilitazione

Nel caso della memoria di abilitazione, dopo lo scatto della transizione t₁ entrambi i ritardi sono resettati a d₁=0.5 e d₂=0.7.

Quando il posto p₁ torna ad abilitare le transizioni t₁ e t₂, sarà di nuovo la transizione t₁ a scattare dopo 0.5 secondi.

La transizione t₂, invece, non scatterà mai.

E così via.