Home

Federica EU

1/21

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:

rimuovere tutti gli stati proibiti e gli archi ad essi collegati (entranti ed uscenti) dall’automa del processo $G$
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.

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$

$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

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)