Home

Federica EU

1/25

Gianmaria De Tommasi » 15.Controllo supervisivo mediante posti monitor

Sommario della lezione

Vincoli di mutua esclusione generalizzata (GMEC);
Controllo supervisivo mediante posti monitor;
Utilizzo di posti monitor in presenza di transizioni non controllabili.

Vincoli di mutua esclusione generalizzata

I vincoli di mutua esclusione generalizzata (generalized mutual exclusion contraints, GMEC):

consentono di esprimere specifiche STATICHE (stati ammissibili);
sono utili per il controllo di processi composti da più sottosistemi che accedono in parallelo a un numero limitato di risorse.

Definizione di GMEC

Sia $\langle N\,,\mathbf{m}_0\rangle$ un sistema rete con $m$ posti. Un GMEC $\bigl(\mathbf{w}\,,k\bigr)$ con $\mathbf{w}\in\mathbb{Z}^m$ e $k\in\mathbf{Z}$ definisce l’insieme di marcature legali

$\mathcal{L}\bigl(\mathbf{w}\,,k\bigr)=\bigl\{\mathbf{m}\in\mathbb{N}^m\ |\ \mathbf{w}^T\mathbf{m}\leq k\bigr\}\,.$

Pertanto l’insieme delle marcature raggiungibili e legali è

$\mathcal{M}\bigl(N\,,\mathbf{m}_0\,,\mathbf{w}\,,k\bigr)=R\bigl(N\,,\mathbf{m}_0\bigr)\cap\mathcal{L}\bigl(\mathbf{w}\,,k\bigr)\,.$

GMEC multipli

Vincoli multipli

Nel caso si debbano imporre contemporaneamente $q$ vincoli di mutua esclusione generalizzata, si ha

$\mathbf{W}=\bigl(\mathbf{w}_1\ \mathbf{w}_2\ \ldots\ \mathbf{w}_q\bigr)$

$\mathbf{k} = \bigl(k_1\ k_2\ \ldots\ k_q\bigr)^T$

$\mathcal{L}\bigl(\mathbf{W}\,,\mathbf{k}\bigr)=\bigl\{M\in\mathbb{N}^m\ |\ \mathbf{W}^T\mathbf{m}\leq\mathbf{k}\bigr\}=\mathcal{L}\bigl(\mathbf{w}_1\,,k_1\bigr)\cap\mathcal{L}\bigl(\mathbf{w}_2\,,k_2\bigr)\cap\ldots\cap\mathcal{L}\bigl(\mathbf{w}_q\,,k_q\bigr)$

Proposizione 1

Dato un GMEC multiplo $\bigl(\mathbf{W}\,,\mathbf{k}\bigr)$ , l’insieme delle marcature ammissibili $\mathcal{L}\bigl(\mathbf{W}\,,\mathbf{k}\bigr)$ è CONVESSO, cioè dati $\mathbf{m}'\,,\mathbf{m}''\in\mathcal{L}\bigl(\mathbf{W}\,,\mathbf{k}\bigr)$ , allora anche

$\mathbf{m}=\alpha\mathbf{m}'+(1-\alpha)\mathbf{m}''\in\mathbb{N}^m$ con $\alpha\in\bigl[0\,,1\bigr]$

Appartiene a $\mathcal{L}\bigl(\mathbf{W}\,,\mathbf{k}\bigr)$

Proposizione 1 – Dimostrazione

$\mathbf{m}'\,,\mathbf{m}''\in\mathcal{L}\bigl(\mathbf{W}\,,\mathbf{k}\bigr)\Rightarrow \mathbf{W}^T\mathbf{m}'\leq\mathbf{k}\ \mathrm{e}\ \mathbf{W}^T\mathbf{m}''\leq\mathbf{k}$

Sia $\mathbf{m}=\alpha\mathbf{m}'+(1-\alpha)\mathbf{m}''$ , allora

$\mathbf{W}^T\mathbf{m}=\alpha\mathbf{W}^T\mathbf{m}'+(1-\alpha)\mathbf{W}^T\mathbf{m}''\leq\alpha\mathbf{k}+(1-\alpha)\mathbf{k}=\mathbf{k}\Rightarrow \mathbf{m}\in\mathcal{L}\bigl(\mathbf{W}\,,\mathbf{k}\bigr)\,.$

Proposizione 2

Se un sistema rete $\langle N\,,\mathbf{m}_0\rangle$ è 1-limitato (SAFE), allora qualsiasi specifica statica può essere espressa mediante un GMEC multiplo.

Posto monitor

Si consideri il sistema rete $\langle N\,,\mathbf{m}_0\rangle$ con matrice di incidenza $\mathbf{C}$ e un GMEC $\bigl(\mathbf{w}\,,k\bigr)$ .

Si definisce posto monitor corrispondente a $\bigl(\mathbf{w}\,,k\bigr)$ il nuovo posto $p_s$ i cui archi entranti e uscenti sono definiti dalla riga della matrice d’incidenza

$\mathbf{c}_s=-\mathbf{w}^T\mathbf{C}\,,$

e la cui marcatura iniziale è $\mathbf{m}_0\bigl(p_s\bigr)=k-\mathbf{w}^T\mathbf{m}_0$ .

Rete a ciclo chiuso

Dato un sistema rete $\langle N\,,\mathbf{m}_0\rangle$ con matrice di incidenza $\mathbf{C}$ , un GMEC $\bigl(\mathbf{w}\,,k\bigr)$ con il relativo posto monitor $p_s$ , la rete a ciclo chiuso avrà come matrice d’incidenza:

$\mathbf{C}_{cc}=\left(\begin{array}{l}\mathbf{C}\\ \mathbf{c}_s\end{array}\right)\,,$

e come marcatura iniziale:

$\mathbf{m}_{cc_0}=\left(\begin{array}{c}\mathbf{m}_0\\ \mathbf{m}_0(p_s)\end{array}\right)\,.$

Proposizione 3

Si consideri un sistema rete $\langle N\,,\mathbf{m}_0\rangle$ con matrice d’incidenza $\mathbf{C}$ e un GMEC $\bigl(\mathbf{w}\,,k\bigr)$ .

Sia $\langle N_{cc}\,,\mathbf{m}_{cc_0}\rangle$ è il sistema a ciclo chiuso ottenuto aggiungendo al sistema $\langle N\,,\mathbf{m}_0\rangle$ il posto monitor corrispondente al GMEC $\bigl(\mathbf{w}\,,k\bigr)$ . Sia, inoltre, $\mathbf{m}_{cc}=\bigl(\mathbf{m}\ \mathbf{m}(p_s)\bigr)^T\in R\bigl(N_{cc}\,,\mathbf{m}_{cc_0}\bigr)$ una generica marcatura raggiungibile del sistema a ciclo chiuso, allora:

$\mathbf{w}^T\mathbf{m}\leq k$ , cioè $\mathbf{m}$ soddisfa il GMEC
Data una qualsiasi transizione $t$ , se $\mathbf{m}\bigl[t\rangle\mathbf{m}'$ e $\mathbf{m}(p_s)<\mathbf{Pre}(p_s\,,t)$ vale $\mathbf{w}^T\mathbf{m}'>k$ , cioè se il posto monitor disabilita $t$ vuol dire che il suo scatto porterebbe ad una marcatura proibita.

Condizione di ammissibilità di un GMEC

Le seguenti tre affermazioni sono equivalenti

GMEC $\bigl(\mathbf{w}\,,k\bigr)$ è realizzabile
$\mathbf{m}_0$ è ammissibile
$\mathbf{m}_0(p_s)=k-\mathbf{w}^T\mathbf{m}_0\geq 0$

Reti con transizioni non controllabili

In generale alcune transizioni saranno associate ad eventi controllabili e altre ad eventi non controllabili, cioè $T=T_c\cup T_{nc}$ con $T_c\cap T_{nc}=\emptyset$ .

Posto monitor ammissibile

Un posto monitor associato al GMEC $\bigl(\mathbf{w}\,,k\bigr)$ è detto AMMISSIBILE se $\forall\ \mathbf{m}_cc$ raggiungibile a ciclo chiuso $\mathbf{m}_cc=\bigl[\mathbf{m}\ \mathbf{m}(p_s)\bigr]^T$ e $\forall\ t\in T_{nc}$ vale

$\mathbf{m}\bigl[t\rangle\Rightarrow \mathbf{m}(p_s)\geq\mathbf{Pre}(p_s\,,t)\,,$

cioè se $t\in T_{nc}$ è abilitata a ciclo aperto lo è anche a ciclo chiuso.

Posto monitor controllabile

Un posto monitor associato al GMEC $\bigl(\mathbf{w}\,,k\bigr)$ è detto STRUTTURALMENTE CONTROLLABILE (o CONTROLLABILE) se $\forall\ t\in T_{nc}$ vale $\mathbf{Pre}~(p_s\,,t)=0$ , cioè se $p_s$ non ha archi verso transizioni non controllabili.

Osservazione

Il posto monitor $p_s$ è CONTROLLABILE $\Rightarrow$ $p_s$ è AMMISSIBILE.

Proposizione 4

Dati un sistema rete $\langle N\,,\mathbf{m}_0\rangle$ e un GMEC $\bigl(\mathbf{w}\,,k\bigr)$ , $p_s$ è CONTROLLABILE se e solo se

$\mathbf{c}_{s_{nc}}\triangleq -\mathbf{w}^T\mathbf{C}_{nc}\geq0\,.$

Marcature non-controllabili e controllabili

Si consideri un sistema rete $\langle N\,,\mathbf{m}_0\rangle$ con $T=T_c\cap T_{nc}$ . Sia $\bigl(\mathbf{w}\,,k\bigr)$ un GMEC che si desidera imporre. L’insieme delle marcature raggiungibili e legali:
$\mathcal{M}\bigl(N\,,\mathbf{m}_0\,,\mathbf{w}\,,k\bigr)$
può essere partizionato come segue:

$\mathcal{M}_{nc}\bigl(N\,,\mathbf{m}_0\,,\mathbf{w}\,,k\bigr)=\Bigl\{\mathbf{m}\in R\bigl(N\,,\mathbf{m}_0\bigr)\ |\ \exists\ \sigma\in T^\ast_{nc}\ \mathbf{m}\bigl[\sigma\rangle\mathbf{m}'\ \mathrm{e}\ \mathbf{m}'\notin\mathcal{L}\bigl(\mathbf{w}\,,k\bigr)\Bigr\}$ INSIEME DELLE MARCATURE NON-CONTROLLABILI
$\mathcal{M}_c\bigl(N\,,\mathbf{m}_0\,,\mathbf{w}\,,k\bigr)=\mathcal{M}\bigl(N\,,\mathbf{m}_0\,,\mathbf{w}\,,k\bigr)\setminus\mathcal{M}_{nc}\bigl(N\,,\mathbf{m}_0\,,\mathbf{w}\,,k\bigr)$ INSIEME DELLE MARCATURE CONTROLLABILI

Esempio

Si consideri il GMEC definito da
$w=\bigl(0\ 0\ 1\bigr)^T$ e $k=1\Rightarrow \mathbf{m}(p_3)\leq 1$

Se $T_{nc}=\bigl\{t_2\,,t_3\bigr\}$ , allora dato che $-\mathbf{w}^T\mathbf{C}_{nc}\ngeq0\Rightarrow p_s$ non è controllabile e $\mathbf{m}=\bigl(1\ 1\ 0\bigr)^T$ è LEGALE ma NON-CONTROLLABILE

Problema del controllo in presenza di transizioni non controllabili

Dato un GMEC $\bigl(\mathbf{m}\,,k\bigr)$ NON CONTROLLABILE, esiste un GMEC CONTROLLABILE $\bigl(\widetilde{\mathbf{w}}\,,\widetilde{k}\bigr)$ tale che

$\mathcal{M}\bigl(N\,,\mathbf{m}_0\,,\widetilde{\mathbf{m}}\,,\widetilde{k}\bigr)=\mathcal{M}_c\bigl(N\,,\mathbf{m}_0\,, \mathbf{m}\,,k\bigr)\subset\mathcal{M}\bigl(N\,,\mathbf{m}_0\,, \mathbf{m}\,,k\bigr)$ ?

Esempio

Con riferimento all’esempio precedente, per risolvere il problema del controllo mediante posti monitor in presenza di transizioni non controllabili, basterebbe considerare

$\widetilde{\mathbf{w}}=\bigl(0\ 1\ 1\bigr)^T$ e $\widetilde{k}=1\Rightarrow\mathbf{m}(p_2)+\mathbf{m}(p_3)\leq1$

Proposizione 5

Dato un GMEC $\bigl(\mathbf{w}\,,k\bigr)$ con $\mathbf{w}\in\mathbb{Z}^m$ e $k\in\mathbb{Z}$ , si scelgano arbitrariamente uno scalare intero positivo $r\in\mathbb{N}$ e un vettore $z\in\mathbb{N}^m$ , e si consideri il GMEC $\bigl(\widetilde{\mathbf{w}}\,,\widetilde{k}\bigr)$ dato da:

$\widetilde{\mathbf{w}}=(r\mathbf{w}+\mathbf{z})$ e $\widetilde{k}=r(k+1)-1$

allora vale

$\mathcal{L}\bigl(\widetilde{\mathbf{w}}\,,\widetilde{k}\bigr)\subseteq\mathcal{L}\bigl(\mathbf{w}\,,k\bigr)\,.$

Algoritmo 1/3

Algoritmo per il calcolo di $\widetilde{\mathbf{w}}$ e $\widetilde{k}$

Costruire la tabella iniziale
$A:=\left|\begin{array}{ccc}\mathbf{C}_{nc} & \mathbf{I}_{m\times m} & 0\\ \mathbf{v}^T & \mathbf{z}^T & r\end{array}\right|=\left|\begin{array}{ccc}\mathbf{C}_{nc} & \mathbf{I}_{m\times m} & 0\\ \mathbf{w}^T\mathbf{C}_{nc} & 00\ldots 0 & 1\end{array}\right|$
se $\bigl(\mathbf{w}\,,k\bigr)$ è NON CONTROLLABILE, allora $\mathbf{w}^T\mathbf{C}_{nc}\nleq0$ .
Si consideri l’insieme degli indici di colonna degli elementi positivi del vettore $\mathbf{v}$ , cioè $\mathcal{J}=\bigl\{j\ |\ \mathbf{v}(j)>0\bigr\}$ . Se $\mathcal{J}=\emptyset$ vai al passo 6.

Algoritmo 2/3

3. Se $\mathcal{J}\neq\emptyset$ sia $\bar{j}\in\mathcal{J}$ e si annulli l’elemento $\mathbf{v}(\bar{j})$ con le seguenti operazioni:

a) sia $\mathcal{I}=\bigl\{i\ |\ \mathbf{C}_{nc}(i\,,j)<0\bigr\}$ , se $\mathcal{I}=\emptyset$ allora vai al passo 5

b) si scelga $\bar{i}\in\mathcal{I}$ e sia $d=\mathrm{mcm}\Bigl(-\mathbf{C}_{nc}\bigl(\bar{i}\,,\bar{j}\bigr)\,,\mathbf{v}(\bar{j})\Bigr)$

c) sia
$A\bigl(m+1\,,\cdot\bigr)=\frac{d}{\mathbf{v}(\bar{j})}A\bigl(m+1\,,\cdot\bigr)+\frac{d}{\mathbf{C}_{nc}\bigl(\bar{i}\,,\bar{j}\bigr)}A\bigl(\bar{i}\,,\cdot\bigr)\,.$
Per costruzione si ha $A\bigl(m+1\,,\bar{j}\bigr)=\mathbf{v}(\bar{j})=0$ .

Algoritmo 3/3

4. Vai al passo 2.
5. L’algoritmo termina senza trovare una soluzione
6. L’algoritmo termina e resituisce come ultima riga
$\bigl|\mathbf{v}^T\ \mathbf{z}^T\ r\bigr|\,,$
con $\mathbf{v}\leq 0$ . Allora

$\widetilde{\mathbf{w}}=(r\mathbf{w}+\mathbf{z})$
e
$\widetilde{k}=r(k+1)-1$

Osservazioni

L’algoritmo proposto termina solo se sono assenti cicli di transizioni non controllabili
L’algoritmo proposto potrebbe non terminare con succcesso (e quindi non trovare una soluzione)