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