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

  1. \mathbf{w}^T\mathbf{m}\leq k, cioè \mathbf{m} soddisfa il GMEC
  2. 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

  1. GMEC \bigl(\mathbf{w}\,,k\bigr) è realizzabile
  2. \mathbf{m}_0 è ammissibile
  3. \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}

  1. 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.
  2. 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)

I materiali di supporto della lezione

Capitolo 8, paragrafi 8.1, 8.2 e 8.3 da Di Febbraio Giua

  • 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