Vai alla Home Page About me Courseware Federica Virtual Campus 3D 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 » 13.Controllo di Supervisione - Parte Seconda


Sommario della lezione

  • Linguaggi ammissibili e richiesti a ciclo chiuso;
  • Traduzione di specifiche dinamiche mediante automi a stati finiti;
  • Teorema di Controllabilità.

Linguaggio ammissibile

Specifiche dinamiche – Linguaggio ammissibile

Una specifica dinamica può essere espressa attraverso due linguaggi:
il linguaggio ammissibile (o legale) L_a\subset\mathcal{L}\bigl(G\bigr);
il linguaggio marcato ammissibile L_{am}\subset\mathcal{L}_m\bigl(G\bigr).

Per il sistema a ciclo chiuso varrà:
\mathcal{L}\bigl(S/G\bigr)\subseteq L_a\subset\mathcal{L}\bigl(G\bigr)
\mathcal{L}_m\bigl(S/G\bigr)\subseteq L_{am}\subset\mathcal{L}_m\bigl(G\bigr)

Linguaggio richiesto

Specifiche dinamiche – Linguaggio richiesto

A volte è necessario fissare dei requisiti minimi per il funzionamento del sistema a ciclo chiuso. In questo caso è utile definire due ulteriori linguaggi:
il linguaggio richiesto L_r\subset\mathcal{L}\bigl(G\bigr);
il linguaggio richiesto marcato L_{rm}\subset\mathcal{L}_m\ bigl(G\bigr)

In questo caso vale:
L_r\subseteq\mathcal{L}\bigl(S/G\bigr)\subseteq L_a\subset\mathcal{L}\bigl(G\bigr)
L_{rm}\subseteq\mathcal{L}_m\bigl(S/G\bigr)\subseteq L_{am}\subset\mathcal{L}_m\bigl(G\bigr)

Linguaggi ammissibili e richiesti

Osservazione

Nel seguito considereremo:
il linguaggio ammissibile chiuso rispetto ai prefissi \Rightarrow L_a = \overline{L}_a;

il linguaggio richiesto L_r non necessariamente chiuso rispetto ai prefissi.

Nel caso in cui si utilizzino gli automi a stati finiti come strumento di modellistica L_a\,,L_{am}\,,L_r e L_{rm} sono linguaggi regolari.

Riconoscitore di una specifica dinamica

Data una specifica dinamica K, se una automa H marca K, allora si dice che H è un RICONOSCITORE di K.

In generale il processo di modellazione delle specifiche non è banale e richiede esperienza.

Sviluppo di un supervisore


Traduzione di specifiche in automi 1/7

Stati proibiti

In questo caso, per ottenere l’automa H_a che descrive il comportamento a ciclo chiuso:

  1. rimuovere tutti gli stati proibiti e gli archi ad essi collegati (entranti ed uscenti) dall’automa del processo G
  2. effettuare la parte accessibile Ac(\cdot)

In questo caso il linguaggio ammissibile è L_a=\mathcal{L}\bigl(H_a\bigr).

Nell’ipotesi di voler considerare anche la condizione di non bloccaggio, al passo 2. bisogna effettuare l’operazione di rifinitura Trim(\cdot) al posto di Ac(\cdot)

Traduzione di specifiche in automi 2/7

Stati proibiti – Esempio

Figura a): Modello dell’impianto non controllato G. Lo stato X1 è uno stato proibito.
Figura b): Modello del sistema supervisionato H_a. In questo caso non si è tenuto conto della specifica sul bloccaggio perché \overline{\mathcal{L}_m\bigl(H_a\bigr)}\neq\mathcal{L}\bigl(H_a\bigr)
Figura c): Modello del sistema supervisionato H_a. In questo caso si è tenuto conto anche della specifca di non-bloccaggio.

Fig. a
Fig. c
Fig. b

Traduzione di specifiche in automi 3/7

Eventi alternati

Se si vuole imporre l’alternanza tra due eventi a e b, allora è sufficiente costruire l’automa

L’automa H_a che specifica il comportamento del sistema supervisionato si ottiene come

H_a=H_{spec}\| G


Traduzione di specifiche in automi 4/7

Parole proibite 1/2

Si consideri la seguente stringa proibita
\sigma_f = \sigma_1\sigma_2\ldots\sigma_n\in E^\ast

Per costruire l’automa della specifica H_{spec} si può procedere come segue:
X=\bigl\{\varepsilon\,,\sigma_1\,,\sigma_1\sigma_2\,,\ldots\,,\sigma_1\sigma_2\ldots\sigma_{n-1}\bigr\}=X_m
f\bigl(\sigma_1\ldots\sigma_i\,,\sigma_{i+1}\bigr)=\sigma_1\ldots\sigma_{i+1} per i=0\,,\ldots\,,n-2
Per ogni stato diverso da \sigma_1\ldots\sigma_{n-1} completare f\bigl(\sigma_1\ldots\sigma_i\,,\gamma\bigr)= il suffisso più lungo di \sigma_1\ldots\sigma_i\gamma\,,\forall\ \gamma\in E

Traduzione di specifiche in automi 5/7

Parole proibite 2/2
4. Per lo stato \sigma_1\ldots\sigma_{n-1} e \forall\ \gamma\in E\setminus\bigl\{\sigma_n\bigr\} completare f\bigl(\sigma_1\ldots\sigma_{n-1}\,,\gamma\bigr)= il suffisso più lungo di \sigma_1\ldots\sigma_{n-1}
5. x_0=\varepsilon

Seguendo la procedura proposta si otterrà un automa H_{spec} per il quale vale

\mathcal{L}\bigl(H_{spec}\bigr)=\mathcal{L}_m\bigl(H_{spec}\bigr)=E^\ast\setminus E^\ast\bigl\{s_f\bigr\}E^\ast

e

H_a=H_{spec}\times G

Traduzione di specifiche in automi 6/7

Parole proibite – Esempio

Si consideri E=\bigl\{a\,,b\,,c\,,d\bigr\} e s_f=abcd, allora l’automa H_{spec} di specifica è


Traduzione di specifiche in automi 7/7

Osservazioni

  • Se E_{no}=E_{nc}=\emptyset, allora l’automa H_a rappresenta la legge di controllo S(\cdot).
  • Con l’automa H_a, infatti, è possibile seguire l’evoluzione dell’impianto a ciclo chiuso e di decidere quali eventi abilitare e quali disabilitare.
  • Se E_{nc}\neq\emptyset e/o E_{no}\neq\emptyset la legge di controllo non si ottiene facilmente dall’automa H_a

Teorema di Controllabilità

Si consideri un SED G=\bigl(X\,,E\,,f\,,\Gamma\,,x_0\bigr) con E_{nc}\subseteq E insieme degli eventi non controllabili.
Sia K\subseteq \mathcal{L}\bigl(G\bigr) e K\neq\emptyset.

Esiste un supervisore S(\cdot) tale che \mathcal{L}\bigl(S/G\bigr)=\overline {K}

SE E SOLO SE

\overline{K}E_{nc}\cap\mathcal{L}\bigl(G\bigr)\subseteq\overline{K} (CONDIZIONE DI CONTROLLABILITÀ)

Controllabilità

Siano K e M=\overline{M} due linguaggi definiti sull’insieme di eventi E.
Sia E_{nc}\subseteq E.
Il linguaggio K si dice CONTROLLABILE dato M e E_{nc} se

\overline{K}E_{nc}\cap M\subseteq\overline{K}

Tale condizione è equivalente alla seguente:

Se s\in \overline{K}, per ogni e\in E_{nc} e se\in M deve valere se\in \overline{K}.

Test di controllabilità per linguaggi regolari

Test di controllabilità per linguaggi regolari

Nel caso di linguaggi REGOLARI è possibile verificare la controllabilità di un linguaggio K mediante un automa a stati finiti.

Il test da effettuare è il seguente:

  • Sia H un automa che genera il linguaggio \overline{K}
    Sia G un automa che genera il linguaggio M
    Si costruisca l’automa H\times G
    Se esistono eventi NON CONTROLLABILI che appartengono a \Gamma_G(\cdot) e non a \Gamma_{H\times G} allora K NON È CONTROLLABILE

Esempio 1/5

Si considerino due transazioni in una database

T_1=a_1b_1 e T_2=a_2b_2

Il seguente automa G rappresenta tutti i possibili schedule delle due transazioni


Esempio 2/5

Si supponga che gli schedule ammissibili debbano soddisfare la seguente condizione

a_1 precede a_2\iff b_1 precede b_2

Il linguaggio ammissibile a ciclo chiuso è generato dall’automa H_a


Esempio 3/5

Se M=\mathcal{L}\bigl(G\bigr) e K=\mathcal{L}_m\bigl(H_a\bigr) si può facilmente verificare che H_a\times G=H_a (rinominando opportunamente gli stati)


Esempio 4/5

Per l’automa G, inX4 si ha

\Gamma_G\bigl(X4\bigr)=\bigl\{b_1\,,b_2\bigr\}

Per l’automa H_a\times G, in \bigl(X4\,,Y4\bigr) e \bigl(X4\,,Y9\bigr) si ha

\Gamma_{H_a\times G}\Bigl(\bigl(X4\,,Y4\bigr)\Bigr)=\bigl\{b_2\bigr\}

\Gamma_{H_a\times G}\Bigl(\bigl(X4\,,Y9\bigr)\Bigr)=\bigl\{b_1\bigr\}


Esempio 5/5

Esempio 5/5

Dato che

\Gamma_G\bigl(X4\bigr)=\bigl\{b_1\,,b_2\bigr\}

e

\Gamma_{H_a\times G}\Bigl(\bigl(X4\,,Y4\bigr)\Bigr)=\bigl\{b_2\bigr\}

\Gamma_{H_a\times G}\Bigl(\bigl(X4\,,Y9\bigr)\Bigr)=\bigl\{b_1\bigr\}

Se E_{nc} contiene b_1 e/o b_2 allora K NON È CONTROLLABILE.

I materiali di supporto della lezione

Capitolo 3, paragrafi 3.3 e 3.4 (fino a 3.4.1 incluso), da Cassandras-LaFortune.

  • 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