Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento 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 » 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