Aula-3-Autômatos

Prévia do material em texto

Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Modelagem e CLP – Autoˆmatos
Rafael Garlet de Oliveira
Instituto Federal Catarinense - IFC
Caˆmpus Luzerna
5 de marc¸o de 2014
Rafael Garlet de Oliveira 1 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Suma´rio
1 Autoˆmato Determinı´stico Finito
Definic¸a˜o
Exemplo
Linguagem de um Autoˆmato
Autoˆmatos x Linguagens Regulares
Composic¸a˜o de Autoˆmatos
Abordagens para modelagem
Eventos Controla´veis e Observa´veis
Autoˆmatos Acessı´veis e Co-acessı´veis
2 Resumo sobre Teoria de Controle Superviso´rio
Introduc¸a˜o
Controle superviso´rio
Metodologia para sı´ntese de supervisores o´timos
Rafael Garlet de Oliveira 2 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Introduc¸a˜o
Autoˆmato
Linguagem que permite representar o comportamento de
SEDs;
Uma forma de representar expresso˜es regulares, que por
sua vez geram as linguagens;
Representac¸a˜o gra´fica: os no´s representam estados e os
arcos, eventos;
Os no´s sa˜o os estados globais do sistema, ou seja, a
situac¸a˜o de todas as subpartes do SED.
Rafael Garlet de Oliveira 3 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Definic¸a˜o
Um Autoˆmato Determinı´stico de Estados Finitos (ADEF) e´
definido por:
G = (Q, Σ, f, q0, Qm)
Q: Conjunto finito e na˜o-vazio de estados;
Σ: Alfabeto com os eventos do sistema;
f: Q x Σ→ Q: Func¸a˜o de transic¸a˜o de estados;
q0 ∈ Q: Estado inicial;
Qm ⊆ Q: Conjunto de estados finais.
Rafael Garlet de Oliveira 4 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Exemplo
Representac¸a˜o do comportamento de uma ma´quina:
Estado 1: Ma´quina parada;
Estado 2: Ma´quina em
operac¸a˜o.
Evento a: inı´cio de uma
tarefa;
Evento b: te´rmino da
tarefa.
Q = {1, 2};
Σ = {a, b};
f(1, a) = 2, f(2, b) = 1;
q0: estado 1;
Qm = estado 1.
Figura: Autoˆmato representando a
operac¸a˜o da ma´quina.
Rafael Garlet de Oliveira 5 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Linguagem de um Autoˆmato
Os autoˆmatos permitem representar expresso˜es regulares.
A Linguagem Gerada por G e´:
L(G) := {s ∈ Σ∗/f (q0, s) e´ definida}
A Linguagem Marcada de G e´:
Lm(G) := {s ∈ L(G)/f (q0, s) ∈ Qm}
A linguagem L(G) representa todas as cadeias geradas no
autoˆmato a partir do estado inicial; a linguagem Lm(G)
representa todas as cadeias que, a partir do estado inicial,
atingem um estado marcado.
Rafael Garlet de Oliveira 6 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Exemplo
Seja Σ = {a,b};
Qual a Linguagem representada pelo seguinte autoˆmato?
Rafael Garlet de Oliveira 7 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Autoˆmatos x Linguagens Regulares
Teorema de Kleene
Uma linguagem e´ regular se e somente se for reconhecida por
um autoˆmato de estados finitos determinı´stico.
Autoˆmato↔ Expressa˜o Regular
Rafael Garlet de Oliveira 8 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Composic¸a˜o de Autoˆmatos
Composic¸a˜o Sı´ncrona
A Composic¸a˜o de Autoˆmatos e´ uma operac¸a˜o que sincroniza
eventos compartilhados, enquanto que os na˜o compartilhados
podem executar de uma forma assı´ncrona.
Utilizada em uma abordagem modular;
G1||G2 = G2||G1;
(G1||G2)||G3 = G1||(G2||G3);
A composic¸a˜o pode ser estendida para n autoˆmatos.
Rafael Garlet de Oliveira 9 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Abordagens para modelagem
Gerador: Pode ser entendido como um autoˆmato. Pode
gerar duas linguagens, a linguagem gerada L(G) e a
linguagem marcada Lm(G).
Abordagem global: Modelar o sistema como um todo, de
uma forma generalizada;
Abordagem local: Modelar cada subsistema
separadamente e formar o sistema global a partir da
composic¸a˜o.
Rafael Garlet de Oliveira 10 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Eventos Controla´veis e Observa´veis
Eventos Controla´veis
Podem ser habilitados, ou desabilitados, pelo controle
superviso´rio, ex: Atuadores.
Eventos Observa´veis
Eventos que podem ser medidos. Os na˜o observa´veis podem
ser entendidos como eventos internos de uma ma´quina.
Rafael Garlet de Oliveira 11 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Autoˆmatos Acessı´veis e Co-acessı´veis
Acessı´vel: Todos os estados Q podem ser alcanc¸ados a
partir de q0.
Na˜o Acessı´vel: Ha´ estados inacessı´veis a partir de q0.
E´ possı´vel reduzir um autoˆmato a sua componente
acessı´vel, removendo os estados na˜o acessı´veis.
Co-acessı´vel ou na˜o bloqueante: Todas as cadeias sa˜o
prefixo de cadeias marcadas.
L(G) = Lm(G)
Ou seja, a partir de qualquer estado pode-se chegar a um
estado final (marcado).
E´ possı´vel obter uma componente co-acessı´vel, eliminando
os estados alcanc¸ados por cadeias que na˜o podem ser
completadas em tarefas.
Trim: Acessı´vel e co-acessı´vel.
Rafael Garlet de Oliveira 12 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Exemplos
Figura: Autoˆmato acessı´vel com
bloqueio. Figura: Autoˆmato trim: acessı´vel e
co-acessı´vel.
Mostrar exemplos no IDES.
Rafael Garlet de Oliveira 13 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Exemplo
Estrutura de autoˆmato com deadlock e livelock. Para encontrar
a componente trim basta eliminar os estados na˜o acessı´veis e
na˜o co-acessı´veis.
Figura: Exemplo de deadlock e livelock.
Rafael Garlet de Oliveira 14 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Introduc¸a˜o
Composic¸a˜o dos subsistemas em uma planta pode gerar
eventos indeseja´veis.
E´ papel do supervisor fazer com que os subsistemas atuem
de forma coordenada.
Para isso, o supervisor desabilita estes eventos indeseja´veis.
Rafael Garlet de Oliveira 15 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Obtenc¸a˜o da Especificac¸a˜o
Deve restringir o comportamento do sistema para atingir
os objetivos do projeto;
Autoˆmato que leva em conta os eventos que devem ser
coordenados;
Pode ser modelado com a abordagem local.
Figura: Especificac¸a˜o para o acionamento ordenado de duas
ma´quinas.
Rafael Garlet de Oliveira 16 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Obtenc¸a˜o do supervisor
Supervisor e´ obtido pela composic¸a˜o sı´ncrona R=G||E,
eliminando-se estados com eventos na˜o-controla´veis
(maus-estados).
O comportamento R pode ser na˜o-controla´vel, devido aos
eventos na˜o controla´veis de G.
Enta˜o deve-se obter a ma´xima linguagem controla´vel,
supC, que representa a lo´gica o´tima de supervisa˜o.
supC representa o comportamento menos restritivo
possı´vel.
Rafael Garlet de Oliveira 17 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Algorı´tmo para o ca´lculo de supC
Dados G, E e R, calcular supervisor S:
1 Identificar maus estados em R,
caso na˜o existam fazer S = R;
2 Caso existam, atualizar R por eliminac¸a˜o de maus
estados;
3 Calcular a componante trim de R e voltar ao passo 1.
Mau estado: Estado em R cujo estado correspondente em G
possui algum evento na˜o-controla´vel que na˜o pertence a este
estado de R.
Rafael Garlet de Oliveira 18 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Metodologia para sı´ntese de supervisores o´timos
Passo a passo para obtenc¸a˜o de um supervisor:1 Obtenc¸a˜o do modelo da planta G;
2 Modelagem da especificac¸a˜o E;
3 Composic¸a˜o da planta G com as especificac¸o˜es E:
R = G||E;
4 Ca´lculo de S = supC(R).
Exemplos e atividades...
Rafael Garlet de Oliveira 19 / 20
Autoˆmato Determinı´stico Finito Resumo sobre Teoria de Controle Superviso´rio
Rafael Garlet de Oliveira
rafael.oliveira@luzerna.ifc.edu.br
Sala de Professores 1
Rafael Garlet de Oliveira 20 / 20
	Autômato Determinístico Finito
	Definição
	Exemplo
	Linguagem de um Autômato
	Autômatos x Linguagens Regulares
	Composição de Autômatos
	Abordagens para modelagem
	Eventos Controláveis e Observáveis
	Autômatos Acessíveis e Co-acessíveis
	Resumo sobre Teoria de Controle Supervisório
	Introdução
	Controle supervisório
	Metodologia para síntese de supervisores ótimos