DAS-5202: Modelagem e Controle
de Sistemas Automatizados
Profs. Eduardo Camponogara & José Cury
Page1
Agenda
Informações Gerais
• Programa da disciplina
• Atendimento
• Avaliação
Introdução a Sistemas a Eventos Discretos (SEDs)
Page2
1. Sistema Contínuo
Breve histórico
• Interesse inicial por sistemas que evoluem
continuamente
– Como leis de movimento e de conservação de
energia
– Modelagem por meio de equações diferenciais e
de diferença
Page3
1. Pêndulo Invertido
Page4
1. Pêndulo Invertido
Page5
1. Sistemas a Eventos Discretos
• Tecnologia moderna despertou interesse por
sistemas a eventos discretos (SEDs)
– SED: sistema cujos estados mudam em pontos
discretos no tempo em resposta a ocorrência de
um evento
• Sistemas de Manufatura
• Redes de Computadores
• Circuitos Integrados
– Evento: qualquer ocorrência, acontecimento em
fenômeno aleatório
Page6
1. Contraste dos Sistemas
Estado
Estado
x(t)
x(t0)
Tempo
x4
x3
x2
x1
e1
e2
e3
e4
Tempo
Page7
1. Trajetória do Sistema Discreto
• Um conjunto de estados discretos pode ser
visitado
• Cada transição é resultado da ocorrência de um
evento. Ex:
– Mensagem recebida
– Tarefa finalizada
– Máquina falhou
– Processo ativado
• A noção do tempo—descrita pela variável
independente do tempo no sistema contínuo—é
substituída pela sequência de eventos no sistema
discreto
Page8
1. Nível de Detalhes
• A quantidade de informação depende da aplicação
– S1 = {e1, e2, …}
– S2 = {(e1,t1), (e2,t2), …}
• Com S1, não estamos preocupados com o tempo,
mas sim com questões “qualitativas” e “lógicas” do
sistema
– O sistema pode travar?
– O sistema atingirá os estados desejáveis
• Com S2, podemos tratar das questões
“quantitativas” relativas ao desempenho
– Desempenho e otimização de sistemas
Page9
1. Primeiros SEDs
• Os primeiros sistemas a eventos discretos
surgiram da prática de engenharia
– Sistemas de manufatura
– Sistemas computacionais
• Sistemas a eventos discretos define uma área
multidisciplinar com contribuições de campos tais
como:
–
–
–
–
Ciência da computação
Teoria de filas
Simulação
Controle
• A contribuição principal do controle se refere
ao aspecto dinâmico
Page10
1. Resto da Apresentação
• Vários modelos para SEDs reflete a diversidade
das aplicações
–
–
–
–
–
–
Cadeia de Markov
Teoria de filas
Processo Semi-Markoviano Generalizado
Autômatos
Álgebra Min-Max
Redes de Petri
Page11
2. Modelos Para SEDs
• Vários modelos foram propostos
• Modelos apresentam vantagens e desvantagens,
cada um é mais adequado para uma classe de
problemas
Page12
2.1 Um Sistema Exemplo
Um sistema constituído de duas máquinas e uma área
de estocagem intermediária
Saída de
peça
Entrada de
peça
Máquina M1
Área de
Estoque
Máquina M2
O tempo de processamento em cada máquina
pode ser determinístico ou estocástico
Page13
2.2 Cadeia de Markov
Teoria de probabilidades, caso discreto
– Eventos elementares
– Conjunto de possíveis resultados de um
experimento
– Espaço amostral S
– Conjunto de todos os eventos elementares
– Ex: experimento rolar um dado, S = {1, …, 6}
– Evento
– Qualquer subconjunto A de S
Page14
2.2 Cadeia de Markov
Teoria de probabilidades, caso discreto
– Distribuição de probabilidades Pr{} sobre um
espaço amostral S
– Pr{}: 2S  R, tal que
1) Pr{A}  0 para qualquer A  S
2) Pr{S} = 1
3) Pr{A  B} = Pr{A} + Pr{B} se A e B são
mutuamente exclusivos, i.e., A  B = 
Page15
2.2 Cadeia de Markov
Variável Randômica X
– Uma função do espaço de estados para os reais
X:SR
– Dado um x  R, define-se
X = x como {s  S : X(s) = x}
Exemplo (Rolar Dado):
X(s) = 1 se s é um número par,
X(s) = 0 caso contrário
Page16
2.2 Cadeia de Markov
Variável Randômica X
– Probabilidade da variável randômica
Pr{X=x} =  Pr{s}
{s  S: X(s) = x}
– Exemplo:
Pr{X=1} = Pr{2} + Pr{4} + Pr{6} = ½
Page17
2.2 Cadeia de Markov
Condições
– O “buffer” tem capacidade infinita
– O estado do sistema x  N é o número de peças
no “buffer”
– l taxa de produção da máquina M1, m taxa de
M2
Page18
2.2 Cadeia de Markov
Condições
– O “buffer” tem capacidade infinita
– O estado do sistema x  N é o número de peças no
“buffer”
– l taxa de produção da máquina M1, m taxa de M2
l
1-l
0
1
Page19
2.2 Cadeia de Markov
Condições
– O “buffer” tem capacidade infinita
– O estado do sistema x  N é o número de peças no
“buffer”
– l taxa de produção da máquina M1, m taxa de M2
l
1-l
0
l
1
m
2
m
Page20
2.2 Cadeia de Markov
Condições
– O “buffer” tem capacidade infinita
– O estado do sistema x  N é o número de peças no
“buffer”
– l taxa de produção da máquina M1, m taxa de M2
l
1-l
0
l
1
m
l
2
m
l
3
m
Page21
2.2 Cadeia de Markov
• Questões que podem ser respondidas com
cadeias de Markov
– Para o caso finito, podemos calcular a taxa de
permanência em cada estado
– Podemos calcular a frequência de cada transição
• Poderíamos ter transformado o modelo para o
caso de “buffer” com capacidade finita?
Page22
2.3 Processo Semi-Markoviano
Generalizado
• Abordagem para modelagem formal de programas
ou linguagens de simulação para SEDs
• A parte discreta do sistema (e.g., número de
clientes) é referenciada como estado
• A parte contínua (e.g., tempo restante de
processamento) é referenciada como linha de vida
Page23
2.3 Processo Semi-Markoviano
Generalizado
• Representação
– Para cada estado, temos uma lista de eventos
factíveis
– Para cada evento de uma lista, geramos uma
linha de vida de acordo com uma probabilidade
– Estes eventos competem e aquele com a menor
linha de vida será disparado
Page24
2.3 Processo Semi-Markoviano
Generalizado
• No exemplo, temos dois eventos:
– a: chegada de uma peça no “buffer”
– b: saída de uma peça do buffer
• A lista de eventos para cada estado n > 0 é {a,b},
para o estado n = 0 a lista é {a}
t0
1
b
a
Page25
2.3 Processo Semi-Markoviano
Generalizado
• No exemplo, temos dois eventos:
– a: chegada de uma peça no “buffer”
– b: saída de uma peça do buffer
t0
1
t1
0
b
a
a
Page26
2.3 Processo Semi-Markoviano
Generalizado
• No exemplo, temos dois eventos:
– a: chegada de uma peça no “buffer”
– b: saída de uma peça do buffer
t0
1
t1
0
t2
1
b
a
a
b
a
Page27
2.3 Processo Semi-Markoviano
Generalizado
• No exemplo, temos dois eventos:
– a: chegada de uma peça no “buffer”
– b: saída de uma peça do buffer
t0
1
t1
0
t2
1
t3
2
1
b
a
a
b
a
b
a
Page28
2.4 Autômatos e Máquinas de
Estados Finitos
• Por questões de simplificação, assumiremos que a
área de armazenamento tem capacidade unitária
• O “buffer” pode estar em um de dois estados:
– Vazio
– Cheio
• As máquinas podem estar em um de três estados:
– Ociosa
– Trabalhando em uma peça
– Quebrada
Page29
2.4 Autômatos e Máquinas de
Estados Finitos
Diagrama de Estados
Para as Máquinas
Ii(Ociosa)
si:ui
ri:vi
fi
bi
Wi(Ocupada)
Di(Quebrada)
Eventos: si, fi, ri, bi
Variáveis de controle: ui (habilita si)
e vi (habilita fi)
Page30
2.4 Autômatos e Máquinas de
Estados Finitos
Diagrama de Estados
Para as Máquinas
Diagrama de Estados
Para o “Buffer”
I(Cheio)
Ii(Ociosa)
si:ui
ri:vi
fi
s2
f1
bi
Wi(Ocupada)
Di(Quebrada)
Eventos: si, fi, ri, bi
Variáveis de controle: ui (habilita si)
e vi (habilita fi)
E(Vazio)
Page31
2.4 Autômatos e Máquinas de
Estados Finitos
• Restrições de Operação
– M1 só pode começar a trabalhar se o “buffer”
estiver vazio
– M2 só pode trabalhar se B está cheio
– M1 não pode trabalhar quando M2 está quebrada
– Se ambas as máquinas estão quebradas, então
M2 é reparada primeiro
Page32
2.4 Autômatos e Máquinas de
Estados Finitos
• Dos 18 estados possíveis (2x3x3), podemos
eliminar 6 estados se M1 está trabalhando ou
quebrada e B está cheio
(i.e., 2 estados para M1 e 3 estados para M2)
• Representação do estado
– (M1, B, M2)
– M1  {I, W, D}
– M2  {I, W, D}
– B  {I, E}
Page33
2.4 Autômatos e Máquinas de
Estados Finitos
IEI
DEI
IED
WEI
IFI
IEW
WEW
DEW
DED
WED
IFD
IFW
Page34
2.4 Autômatos e Máquinas de
Estados Finitos
IEI
IED
s1
DEI
WEI
IFI
IEW
WEW
DEW
DED
WED
IFD
IFW
Page35
2.4 Autômatos e Máquinas de
Estados Finitos
IEI
IED
s1
DEI
b1
WEI
f1
IFI
IEW
WEW
DEW
DED
WED
IFD
IFW
Page36
2.4 Autômatos e Máquinas de
Estados Finitos
IEI
r1
DEI
IED
s1
b1
WEI
f1
IFI
s2
IEW
WEW
DEW
DED
WED
IFD
IFW
Page37
2.4 Autômatos e Máquinas de
Estados Finitos
IEI
r1
DEI
f2
s1
b1
WEI
f1
IFI
s2
IED
b2
IEW
s1
WEW
DEW
DED
WED
IFD
IFW
Page38
2.4 Autômatos e Máquinas de
Estados Finitos
r2
IEI
r1
DEI
f2
s1
b1
IED
WEI
f1
IFI
s2
f2
DEW
DED
WED
b1
IFD
b2
b2
IEW
s1
WEW
f1
IFW
Page39
2.4 Autômatos e Máquinas de
Estados Finitos
r2
IEI
r1
r1
DEI
f2
DEW
b2
f2
s1
b1
DED
WEI
r2
r2
b1
b1
IED
WED
f1
IFI
s2
f2
f1
r2
IFD
f2
b2
b2
b2
IEW
s1
WEW
f1
IFW
Page40
2.4 Autômatos e Máquinas de
Estados Finitos
• Desejamos projetar um controlador que
manipule as variáveis u e v, de forma a
assegurar que apenas as transições do
diagrama sejam permitidas
• Se a informação completa do estado está
disponível, então é fácil implementar tal
controlador
Page41
2.4 Autômatos e Máquinas de
Estados Finitos
• Um problema surge quando o estado não
é observável, mas apenas os eventos
Page42
2.4 Autômatos e Máquinas de
Estados Finitos
• É possível implementar um controlador a
partir dos eventos produzidos pela
planta?
– Uma solução é criar um modelo do sistema
(como o anterior) que roda em paralelo e é
sincronizado com os eventos do sistema real
– Dessa maneira, podemos implementar um
controlador apropriado com base no estado
– A cópia do sistema e do controlador é chamada
de supervisor
Page43
2.4 Autômatos e Máquinas de
Estados Finitos
• Formalização do Problema
– Q é o conjunto de estados
– S é o conjunto de eventos
– Certa transições são habilitadas/desabilitadas
por variáveis de controle
– A sequência de eventos descreve a saída do
sistema, s = <e1, e2, …,en>
– A coleção de sequência de eventos L, que
caracteriza o comportamento desejável do
sistema
Page44
2.4 Autômatos e Máquinas de
Estados Finitos
• Problema de Controle Supervisório
– Determine se apenas sequências em L podem ser
produzidas, manipulando-se as variáveis de
controle e observando-se apenas os eventos
Page45
2.5 Álgebra Min-Max
• A proposta trata de sistemas determinísticos
• Seja a o tempo de processamento de M1 e b1, de
M2
• Seja xn o instante em que M1 finaliza a n-ésima
tarefa
• Seja yn o instante em que M2 finaliza a n-ésima
tarefa
• x0, y0 são os instantes iniciais
• Por conveniência, assumimos x0 = 0
Page46
2.5 Álgebra Min-Max
• Obtém-se então:
x1 = x0 + a
x2 = x1 + a
Y1 = Max{y0 + b, x1 + b}
(1)
(2)
Page47
2.5 Álgebra Min-Max
• Na álgebra min-max as duas operações são
definidas como
– Produto: a*b = a + b
– Adição: a#b = max{a,b}
• Portanto, as equações (1) e (2) são escritas como:
– x2 = x1*a
– y1 = x1*b # y0*b
• Através destas equações podemos escrever
equações dinâmicas que descrevem o
comportamento do sistema
Page48
2.6 Redes de Petri
• Redes de Petri são tipicamente utilizadas para
modelar sistemas com comportamento
concorrente:
– Sistemas computacionais distribuídos
– Sistemas de manufatura
Page49
• Em uma representação gráfica, a estrutura da
rede de Petri é definida por três conjuntos
– a) con junto de lugares, P
– b) conjunto de transições, T
– c) conjunto de arcos direcionados, A
• Um arco conecta um lugar a uma transição ou
uma transição a um lugar
Page50
2.6 Redes de Petri
B1
1-e-lx
t1
Q (no. de
peças no
“buffer”)
B2 (M2 ocupada)
1-e-mx
I (M2 ociosa)
t3 (inicia
proces.)
t3 (término)
Page51
2.6 Redes de Petri
B1
1-e-lx
t1
Q (no. de
peças no
“buffer”)
B2 (M2 ocupada)
1-e-mx
I (M2 ociosa)
t3 (inicia
proces.)
t3 (término)
Page52
2.6 Redes de Petri
B1
1-e-lx
t1
Q (no. de
peças no
“buffer”)
B2 (M2 ocupada)
1-e-mx
I (M2 ociosa)
t3 (inicia
proces.)
t3 (término)
Page53
2.6 Redes de Petri
• Definição formal da Rede de Petri
– PN = {P, T, A}, Rede de Petri
– P = {P1, P2, …, Pn}, lugares
– T = {t1, …, tm}, transições
– A = Ai  Ao
• Ai  P x T
• Ao  T x P
– M0  N|P|, marcação inicial
• Mo(p) é o número de fichas no lugar p
Page54
2.6 Redes de Petri
• Conceitos
– Marcação corresponde ao estado inicial
– Transição habilitada
– Disparo de transição
– Evolução do Sistema
– Evento (corresponde ao disparo de transição)
– Propriedades
– Redes de Petri modelam os relacionamentos
lógicos entre os componentes do sistema e
entre as sequências dos lugares
– Não modelam o instante de ocorrência
Page55
3 Fim
Obrigado!
Page56