Universidade Federal de Santa Catarina
Pós-graduação em Engenharia Elétrica
Departamento de Automação e Sistemas
Controle Supervisório Hierárquico para Sistemas
a Eventos Discretos: Uma Abordagem Baseada
na Agregação de Estados.
Doutorando: César R. Claure Torrico
Orientador: José Eduardo Ribeiro Cury
Florianópolis, Março de 2003
Sumário








Introdução
Controle hierárquico e agregação de estados
(Teorias de base)
Nova abordagem para controle supervisório
Controle hierárquico por agregação de estados
(Modelo proposto)
Redução do modelo agregado com estruturas de
controle estado dependente
Controle supervisório hierárquico modular por
agregação de estados
Exemplo de aplicação
Conclusões e perspectivas
Março de 2003
LCMI-UFSC
1 de 44
Introdução

Sistemas a Eventos Discretos (SEDs), são sistemas
dinâmicos a estado discreto dirigidos por eventos

Controle Supervisório de SEDs ( Ramadge e Wonham 87)
PLANTA
Eventos
desabilitados
Eventos
SUPERVISOR
Março de 2003
LCMI-UFSC
2 de 44
Motivação


Aumento da complexidade dos processos
Explosão de estados em sistemas de grande porte
(Ramadge e Wonham 87)
*
*
*

Controle modular
Exploração de simetria em síntese de supervisores
Controle hierárquico
Controle hierárquico
Modelo de Zhong 90, Wong 96, Pu 2000
Modelo de Caines 98
Condições de consistência hierárquica conservadoras
Geralmente o canal de informação entre os níveis de
hierarquia deve ser refinado várias vezes para alcançar
boas propriedades para controle hierárquico.
*
*

Controle Modular (Wonham 88)
Março de 2003
LCMI-UFSC
3 de 44
Motivação
Decomposição Vertical e Horizontal
Controlador 2a
Controlador 1a
Abstração 2
Abstração 1
Controlador 1b
Planta
Real
Controlador
Março de 2003
Controlador 2b
LCMI-UFSC
4 de 44
Objetivos

Propor um novo modelo de controle hierárquico
de SED por agregação de estados
*
*


Modelo abstrato obtido mais naturalmente
Condições de consistência hierárquica não
conservadoras
Integrar o novo modelo com a abordagem de
controle modular
Implementar uma ferramenta computacional para
modelagem
Março de 2003
LCMI-UFSC
5 de 44
Controle hierárquico (Zhong 90)

Hierarquia de dois níveis.
Infge
Cge
Conge
Gge
Nível Gerencial
Infog
Comgo
Infop
Cop
Gop
Nível Operacional
Conop
Março de 2003
LCMI-UFSC
6 de 44
Modelos de alto e baixo nível

Modelo de alto nível
Gge :

0

1

Modelo de baixo nível
Canal de informação
~
G op :
0
a

d
0
g
c
b
0
c

h

e
f
Março de 2003
LCMI-UFSC
7 de 44
Problema de controle supervisório hierárquico
Construção do modelo abstrato tal que:

Todo comportamento implementado pelo
supervisor no nível gerencial seja igual à imagem
do comportamento implementado através do nível
operacional (consistência hierárquica)
Março de 2003
LCMI-UFSC
8 de 44
Extensão ao modelo de Zhong90

(Wong 96) , estende-se o problema de
controle hierárquico:
Construir o modelo abstrato tal que:
* Além de consistência hierárquica, que todo
comportamento realizável no nível operacional
tenha imagem realizável no nível gerencial
(consistência hierárquica forte)

Inclui linguagens marcadas (Qm  Q)
*
Permite lidar com o bloqueio
Março de 2003
LCMI-UFSC
9 de 44
Controle hierárquico por agregação de
estados (Caines e Hubbard 98)

Modelo de alto nível
V01
U 02
X0
U

V14
X1
3
0
X2
V24
X4
V34
X3
Modelo de baixo nível
X1
X0
X2
X4
X3
Março de 2003
LCMI-UFSC
10 de 44
Problema de controle hierárquico (C-H 98)
Obter um modelo abstrato por agregação de estados tal
que:
 Para qualquer especificação por estado proibido
realizável, a arquitetura possua consistência
hierárquica forte (Controlabilidade IBC não
bloqueante)
Março de 2003
LCMI-UFSC
11 de 44
Discussão(Controle Hierárquico)

(Zhong 90), limitada a linguagens prefixo
fechadas
*

Consistência hierárquica
(Wong 96), extensão da abordagem de Zhong
*
Consistência hierárquica forte
*
*
Linguagens marcadas
*

Mapa repórter observador
Consistência de marcação
(Caines 98), agregação de estados
*
*
Consistência hierárquica forte (IBC-não bloqueante)
Limitada a especificações de estado proibido
Março de 2003
LCMI-UFSC
12 de 44
Discussão(Controle Hierárquico)

Alfabeto do alto nível diferente do de baixo nível

Abordagens condicionadas à estrutura tradicional
de controle cujos eventos são particionados em
controláveis e não controláveis.

A obtenção do modelo abstrato pode ser
melhorada com a introdução de estruturas de
controle mais elaboradas.
Março de 2003
LCMI-UFSC
13 de 44
Novo modelo para controle supervisório


Modelo proposto por Cury, Torrico e Cunha (ECC 2001)
Um SED é representado como um par D = (L,):
*
*

L  * é uma linguagem prefixo fechada
 é uma estrutura de controle que associa a cada s  L um
conjunto de padrões de controle (s)={(,)  2 {M,N}}
Um padrão de controle (,)(s) significa:
*
, é um conjunto de eventos habilitados após s
*
 {M,N} é uma etiqueta de marcação
Março de 2003
LCMI-UFSC
14 de 44
Requisitos para 

Impõe-se que (s) deve satisfazer os seguintes
requisitos: sL,
1.
2.

(1,N), (2,N)  (s)  (12,N)  (s)
(1,M), (2,#)  (s)  (12,M)  (s), # = M,N
Generalização dos modelos usuais:
*
R-W (,)(s) , u   e #=M se s  Lm e
#=N se s  (L-Lm)
Março de 2003
LCMI-UFSC
15 de 44
Controle supervisório
Supervisor

Mapeamento f : L  2{M,N}, que para s L seleciona o
padrão de controle (,#)  (s)
Comportamentos
*
*
L(f/D), linguagem formada pelas palavras de L que
sobrevivem à supervisão de f
Lm(f/D), linguagem formada pelas palavras em L(f/D) em
que o supervisor selecionou um atributo de marcação M
Supervisor
*
em malha fechada
não bloqueante
( Lm ( f / D))  L( f / D) .
Março de 2003
LCMI-UFSC
16 de 44
-compatibilidade e existência de supervisores
-compatibilidade:
Dado D=(L, ), a linguagem KL é -compatível se
K= ou se
(s K)
((,M)(s)) : L(s) = K(s)
* (s pre(K)-K) ((,N)(s)) : L(s) = K(s)
*
Existência de supervisores:
Dado D=(L, ) e a linguagem KL, existe um
supervisor não bloqueante f para D tal que Lm(f/D) = K
se e somente se K for -compatível.
Dado K  L, o conjunto das linguagens -compatíveis
contidas em K, CM(K), é não vazio, fechado para a
união e possui um elemento supremo supCM(K), a
máxima linguagem -compatível.
Março de 2003
LCMI-UFSC
17 de 44
Controle hierárquico por agregação de estados

Hierarquia de dois níveis.
A
fA
Nível Agregado
GA
ConA
A
Com

Nível Operacional
f
G
Con
Problema
de Controle Hierárquico: Dada uma
planta G e um alfabeto A construir GA sobre A
tal que a estrutura hierárquica possua consistência
hierárquica forte
Março de 2003
LCMI-UFSC
18 de 44
Obtenção do modelo agregado
g
G:
b
0
1
a
e
4
g
GA:
g
b
X0
g
X1
...
d e
a
3
2
e
5
Problemas
d
6
X2
a
g
A={a,b,g}
a
g...
decorrentes da agregação de estados
* Não
determinismo;
* Ausência de consistência hierárquica.
Março de 2003
LCMI-UFSC
19 de 44
Descrição dos blocos da partição
Sub-autômatos,
H1:
1
Hij, de um bloco Xi.
g
e
4
1
g’
d e
g
H1,1:
H1,4:
e
4
d e
g’
3
3
H1,3:
Autômato
aumentado, H+ij , de um sub-autômato Hij,
g
1
x+
e
4
g'
d e
H+
Março de 2003
1,3
:
3
LCMI-UFSC
20 de 44
Estruturas de controle para o nível agregado
entre Hij, e H+ij .
Sub-autômatos
a
e
d
g
h
f
e
d
b
c
g
a
b
h
f
c
Constróem-se
estruturas de controle para cada bloco, Xi
e cada entrada no bloco xj.
ij = {({a};N), ({b};N), ({b};M), ({a,b};M), ... {a,b,c};M) }
Março de 2003
LCMI-UFSC
21 de 44
Autômato agregado- com estruturas de controle
Autômato
*
com  estado dependente (Gs).
Refina-se cada bloco para cada estado de entrada que tenha
estruturas de controle diferente.

i,1
X
 i




1
2
3

Autômato
i,1  i,2 = i,3

i,2=i,3







com  (s, e, ps)-dependente (Ge).
*Adota-se
esta forma de representação a fim de manter a estrutura
de transição inicial do autômato agregado.

X2
X4
3
X1
Março de 2003

2
LCMI-UFSC



(X4, , X2)=4,3
(X4, , X1)=4,2
22 de 44
Solução para os problemas da agregação
Não
*
determinismo.
Consideram-se duas situações:
c
c”
X0
X1
X0
c
c’
a
a”
X1
a
a’
X2
*Eliminação
Ausência
de não determinismo por renomeação de eventos
de consistência hierárquica.
*Constatou-se
que a estrutura hierárquica tal como construída
garante a consistência hierárquica forte.
Março de 2003
LCMI-UFSC
23 de 44
Tradução do controle do alto para o baixo nível
GA:
X0
X4 (4,#4)
X2
fA(S)=(0,#0)
(3,#3)
X3
X1
(1,#1)
X5
X1
G:
X3
f
f3
X0
f0
f1
f4
f0
f1
f3
f4
X4
X2
X5
Março de 2003
LCMI-UFSC
24 de 44
Resultados Principais
Teorema:
*
(Consistência Hierárquica Forte).
Dada uma linguagem KA realizável pelo supervisor
do nível agregado, isto é, Lm(fA/GA)=KA, e a
correspondente realização no baixo nível,
Lm(f/G)=K, pode se afirmar que (K) = KA (C.H.) e
toda linguagem
K  Lm(G) controlável e Lmfechada, tem imagem -compatível no nível
agregado.
Março de 2003
LCMI-UFSC
25 de 44
Discussão sobre o novo modelo de controle
hierárquico
Modelo de alto nível construído a partir de uma
planta G e um conjunto de eventos relevantes
para especificação.
A forma de construção do modelo já garante
consistência hierárquica forte.
Este modelo apresenta um custo computacional
exponencial em relação ao número de eventos
relevantes.
Trabalho relacionado (Cunha 2001)
*
Condições mais relaxadas de consistência hierárquica
Março de 2003
LCMI-UFSC
26 de 44
Redução do modelo GsA
reduções de renomeações e estados de GsA
A renomeação de eventos leva a um crescimento
exponencial do número de padrões de controle
Problema de renomeação:
Propõem-se
X0
1
0
2
a
a’
3
a
a”
0,0 ={({a’},N),
({a”},N),
0,0 = {({a},N)}
({a’, a”},N)}
Março de 2003
X1
5
X2
b
6
4
1,3 = {(Ø,M),
1,4 = {({b},M)}
({b},M)}
1,4 = {({b},M)}
LCMI-UFSC
27 de 44
Equivalência de estados e redução de GsA
Critério
de Equivalência
Dois estados de GA são equivalentes se:
 Pertencem
à mesma classe de equivalência de Nerode
 Possuem o mesmo conjunto de padrões de controle
Redução
estática:
 Consiste
em renomear todos os não determinismos para
depois proceder com a redução.
Redução
dinâmica:
 A renomeação
e redução são feitas na medida em que são
calculadas as estruturas de controle
Apresentam-se
Março de 2003
algoritmos para a redução.
LCMI-UFSC
28 de 44
Discussão (Redução de GsA)
O
Modelo agregado reduzido mantém a propriedade de
consistência hierárquica forte.
A simplificação de renomeações diminui.
exponencialmente o número de padrões de controle.
A renomeação dinâmica converge mais rapidamente
que a estática.
O autômato reduzido não necessariamente será o
mínimo.
Março de 2003
LCMI-UFSC
29 de 44
Controle Hierárquico Modular
Controle
Modular (Wonham 88):
E. Desabilitados
Superv 2
E. Desabilitados
Planta
Eventos
Restrita
Eventos
para supervisores não conflitantes
Linguagens
Março de 2003
Superv 1
modulares: K1 K2 = K1  K2.
LCMI-UFSC
30 de 44
Arquitetura do Controle Hierárquico Modular
Duas
ou mais especificações modulares no nível
gerencial.
f1
A
Infge1
Conge1
Infge2
GA
Conge2
f2A
Nível Gerencial
Infog
G
Infop
com1
Conop
f

Março de 2003
Nível Operacional
com2
com
LCMI-UFSC
31 de 44
Problema de controle hierárquico modular

Modularidade Hierárquica:
*
Propriedade verificada quando para dois supervisores do alto
nível f1A e f2A, tais que,
Lm(fiA/GA) = supCM(EiA,L(GA)), i = 1,2,
tem-se
(Lm(f/G))=supCM(E1A  E2A, L(GA)) com f não bloqueante.
Problema:
*
Obter condições necessárias e suficientes para modularidade
hierárquica.
Março de 2003
LCMI-UFSC
32 de 44
Operador de Conjunção
f1A
Processa
comandos com1 e com2
vindos de f1A e f2A respectivamente e
traduz num único comando com.

Infge1
do Operador de
Conjunção: Xi de GA.
Se: com1 = (1,N)  i
com2 = (2,#)  i para #=M,N
Se: com1 = (1,M)  i
com2 = (2,M)  i
Março de 2003
GA
Conge1
Infog
Conge2
f2A
G
Infop
com1
Funcionamento
Infge2
Conop
f

com
com2
com = ([12],N), se
([12],N)  i , senão
com indefinido!
com = ([12],M), se
([12],M)  i , senão
com indefinido!
LCMI-UFSC
33 de 44
Fechamento para conjunção das estruturas de
controle de GA
 As estruturas de controle de GA são fechadas
para conjunção quando com é definido para
todo par com1 e com2.
Exemplo: Estrutura não fechada para conjunção
i ={({b},N), ({a,b},M), ({b,c},M), ({a,b,c},M)}
({a,b},M), ({b,c},M)  i
Março de 2003
entretanto ({b},M)  i
LCMI-UFSC
34 de 44
Supervisor equivalente de alto nível
O
fechamento para conjunção garante a existência de
um supervisor equivalente de alto nível :
f1 A
com1
f2A

com2
feA
fechamento para
conjunção
com
com
f
Março de 2003
f
LCMI-UFSC
35 de 44
Resultados principais
Proposição 1: A -compatibilidade de Lm(f1A/GA) 
Lm(f2A/GA) é condição necessária e suficiente para que a
modularidade hierárquica seja verificada para dois
supervisores f1A e f2A tais que
Lm(f1A/GA)  Lm(f2A/GA) = Lm(f1A/GA)  Lm(f2A/GA)
Proposição
2: Para qualquer par de supervisores f1A e f2A
tais que
Lm(f1A/GA)  Lm(f2A/GA) = Lm(f1A/GA)  Lm(f2A/GA)
o fechamento para conjunção das estruturas de controle
implica que Lm(f1A/GA)  Lm(f2A/GA) é -compatível
Março de 2003
LCMI-UFSC
36 de 44
Resultados principais
Corolario:
O fechamento para conjunção das estruturas
de controle do alto nível é condição suficiente para que a
modularidade hierárquica seja verificada para qualquer
par de supervisores f1A e f2A tais que
Lm(f1A/GA)  Lm(f2A/GA) = Lm(f1A/GA)  Lm(f2A/GA)
Março de 2003
LCMI-UFSC
37 de 44
Exemplo: Mesa Giratória
Buffer de saída
Peças Boas
Robô
Buffer de saída
Peças Ruins
P3
Entrada
P1
P2
Esteira
Máquina(Furadeira + Teste)
Mesa
0
0
Março de 2003
Esteira
Máquina
1
1
Robô
2
2b 2r
LCMI-UFSC
3b
3b
3r
3r
38 de 44
Continuação do exemplo
Especificações de baixo nível:
Especif a) (Mesa não girar à toa)
1 , 2b , 2r
1 , 2b , 2r
0
Especif b) (Exclusão mutua)
0 ,1
 0 , 1
Mesa-esteira
Março de 2003
0 ,2
0 , 2b , 2r
Mesa-maquina
LCMI-UFSC
0 ,3b ,3r
0 , 3b, 3r
Mesa- robô
39 de 44
Continuação do exemplo
Especif c) (Coerência)
0
1
2
0
1
0
2
2b
2r
0
3b ,3r
2b
2r
3b ,3r
Modelo de baixo nível: Adota-se como modelo de baixo
nível a solução para as especificações de baixo nível
(51 Estados ; 122 transições ; 11 símbolos)
Modelo agregado:
Interesse no nível agregado  Classificação de peças boas e ruins
Eventos relevantes  1, 1, 2b, 2r, 3b, 3r
Estados
Transições
Símbolos
Padrões de cont.
Modelo Agregado
29
136
27
624
Modelo Agreg-Red
24
79
21
509
Março de 2003
LCMI-UFSC
40 de 44
Continuação do exemplo
*Especificações
do nível agregado
(Classificação de peças em boas e ruins)
0 ,3b ,3r
0 ,3b ,3r
3b ,3r
2b
2r
0
0
3r
3b
Supervisores
Sup 1
3b ,3r
Estados
38
Sup 2
Transições
105
38
105
Sup 1 e Sup 2  Não conflitantes
Março de 2003
LCMI-UFSC
41 de 44
Conclusões
Principais
contribuições:
 Novo
modelo formal para controle supervisório de SEDs
(Cury, Torrico, da Cunha).
 Controle supervisório hierárquico por agregação de estados
(Torrico, Cury).
 Redução de modelos agregados (Torrico, Cury).
 Controle hierárquico modular por agregação de estados
(Torrico, Cury).
 Extensão da ferramenta computacional Grail (Torrico).
Estas
abordagens mostram-se apropriadas para
modelagem e controle num alto nível de abstração.
Março de 2003
LCMI-UFSC
42 de 44
Conclusões
A forma
de construção da arquitetura hierárquica,
apresenta as boas propriedades para controle hierárquico.
Uma limitação do controle hierárquico aqui apresentado
está na obtenção do modelo agregado.
Esta metodologia justifica-se em aplicações onde o
modelo agregado obtido é utilizado para resolver
múltiplos problemas de controle.
O controle hierárquico modular permite ainda maiores
ganhos na resolução de múltiplos problemas de controle
 Flexibilidade
 Ganho
Março de 2003
computacional da abordagem modular clássica
LCMI-UFSC
43 de 44
Perspectivas para trabalhos futuros
Otimizar
o cômputo das estruturas de controle usando
o fato de que  é fechada para união.
Buscar alternativas para solução do problema de não
determinismo do nível agregado de tal forma a evitar o
crescimento exponencial do número de padrões de
controle.
Explorar métodos para minimização do autômato
agregado. Nesta tese apresentam-se apenas métodos de
redução.
Para sistemas compostos com estruturas de controle
avançadas, explorar a abordagem modular local
proposta em (Queiroz 2000).
Março de 2003
LCMI-UFSC
44 de 44
Continuação do exemplo
*Especificações
do nível agregado
(Classificação de peças em boas e Ruins)
0 ,3b ,3r
0 ,3b ,3r
3b ,3r
2b
2r
0
0
3r
3b
Supervisor 1
3b ,3r
Estados
38
Transições
105
Supervisor 2
38
105
Superv. Monolítico
20
33
Março de 2003
LCMI-UFSC
46 de 44