DAS5202 - Modelagem e Controle de Sistemas Automatizados

8/18/2019 DAS5202 - Modelagem e Controle de Sistemas Automatizados

1/102

1

DAS 5202DAS 5202 – – Modelagem eModelagem e

Controle de SistemasControle de Sistemas

AutomatizadosAutomatizados

Jean-Marie Farines

José Eduardo Ribeiro Cury

Max Hering de Queiroz

22

OrganizaçãoOrganização

• Parte 1 (SED): Sistemas a Eventos Discretos(SEDs):conceituação, classificação, propriedades, exemplos;

• Parte 2 (Redes de Petri e verificação): Redes de Petri:definições, propriedades, análise, implementação,

modelagem; verificação de propriedades;• Parte 3 (Autômatos e controle supervisório): Modelos

Autômatos de Estados Finitos: conceituação básica,operações, controle supervisório de SEDs baseado emautômatos;

• Parte 4 (Trabalho): Trabalho a ser desenvolvido porequipes e apresentado oralmente pelas equipes, em aula,cada equipe tendo 20 minutos para sua apresentação.


2/102

2

33

Controle & AutomaçãoControle & Automação

SistemaSistemaentradas saídas

Controlereferência

perturbação

realimentação

44

Problemas de EngenhariaProblemas de Engenharia

• Modelagem e Análise

• Projeto e Síntese

• Controle

• Avaliação de Desempenho

• Otimização


3/102

3

55

ModelosModelos

• Sistemas Dinâmicos de Variáveis Contínuas

• Sistemas Dinâmicos a Eventos Discretos

• Sistemas Híbridos

66

ModelosModelos

tempo

estado

d x/d t = f ( x,u,t )

γ

γ

x1

x2

x3

x4

t 1 t 2 t 3 t 4 t 5 t 6

x0


4/102

4

77

Sistemas Dinâmicos de Variáveis ContínuasSistemas Dinâmicos de Variáveis Contínuas

• variáveis contínuas:

– temperatura, vazão, pressão, nível, velocidade,

etc

• dirigido pelo tempo:

– estado evolui continuamente

• modelos matemáticos:

– equações diferenciais/a diferenças

88


5/102


6/102

6

1111

1212

Sistemas HíbridosSistemas Híbridos

• Dinâmica Contínua

• Dinâmica Discreta


7/102

7

Exemplos deExemplos de SEDsSEDs

1414

Sistema de Filas

• Origem no seguinte fato: o uso de certos recursos

exige espera.

• Os três elementos básicos de um sistema de filassão:

– 1. As entidades que devem esperar pelo uso de recursos

(clientes);

– 2. Os recursos pelos quais se espera. Fornecem serviço

aos clientes (servidores);

– 3. O espaço onde a espera se faz (fila).


8/102

8

1515

Diagrama representativo de uma fila

1616

Eventos e estados


9/102

9

1717

Sistemas de Redes de FilasSistemas de Redes de Filas

1818

Sistemas de manufaturaSistemas de manufatura

• Sistemas descritos por modelos de filas.

– clientes: peças ou itens; ”pallets”;

– servidores: máquinas; dispositivos de manuseioe transporte (robôs, esteiras, ...);

– filas: armazéns; ”buffers”.


10/102

10

1919

Linha de transferênciaLinha de transferência

2020

Sistema de TráfegoSistema de Tráfego


11/102

11

2121

Eventos e EstadosEventos e Estados

2222

Modelos para SEDModelos para SED

• Modelos lógicos

– Orientados para a análise do comportamento

lógico (sequencial) do sistema• Modelos de Avaliação de Desempenho

– Orientados para a análise de performance

(quantitativa) do sistema


12/102

12

2323

Questões de análiseQuestões de análise

• Modelos lógicos – Estado proibido ou desejado

• Pode um certo estado ser alcançado?

– Vivacidade do sistema• O sistema está livre de bloqueio?

• Modelos de Avaliação de Desempenho

– Índices de desempenho• Qual o lead-time, estoque médio de “buffers”, taxa de

produção, taxa de ocupação de equipamentos, eficiência, etc ?

2424

AbordagensAbordagens

• Modelos lógicos – Redes de Petri

– Autômatos (Teoria de Controle Supervisório)

– Lógica Temporal

• Modelos de Avaliação de Desempenho – Modelos Analíticos

• Cadeias de Markov, Redes de Filas, etc

– Modelos p/ Simulação• Arena, Automod, etc


13/102

13

2525

Redes deRedes de PetriPetri

• Lugar, Transição e Ficha

• Regra de habilitação

• Regra de disparo

t

2626

ExemploExemplo

...

Par ts

Mach ine 1Buf fe r

R o b o t

Mach ine 2

Fina l P roduc ts

M1 M2B

R

I

t1 t2 t3 t4

t5

t6 t7

M1 M2B

R

I

t1 t2 t3 t4

t5

t6 t7

M1 M2B

R

I

t1 t2 t3 t4

t5

t6 t7

M1 M2B

R

I

t1 t2 t3 t4

t5

t6 t7

M1 M2B

R

I

t1 t2 t3 t4

t5

t6 t7

M1 M2B

R

I

t1 t2 t3 t4

t5

t6 t7

M1 M2B

R

I

t1 t2 t3 t4

t5

t6 t7

M1 M2B

R

I

t1 t2 t3 t4

t5

t6 t7

M1 M2B

R

I

t1 t2 t3 t4

t5

t6 t7


14/102

14

2727

Exemplo: Redes de FilasExemplo: Redes de Filas

λ μ

λ μ

A

B

μ

μ

λ

λ

2μ

λ

λ C


15/102

1

Modelagem e Controle de Sistemas AutomatizadosModelagem e Controle de Sistemas Automatizados

DAS5202 - ECA - UFSC

Aula 2

Linguagens

2DAS5202 - ECA - UFSC

Alfabetos

Um alfabeto é um conjunto finito enão-vazio de símbolos (eventos).

Exemplos: Σ = {0, 1}

Σ = {a, b, ..., z }

Σ = {α, β, ..., ω}

caracteres ASCII


16/102

2


Cadeias Uma cadeia (ou palavra) é uma seqüência finita

de símbolos de um alfabeto.

ε: cadeia vazia

|s|: comprimento da cadeia s

Concatenação de u (αββ) e v (γβ) é dada por uv

(αββγβ)

εs = sε = s: identidade da concatenação

u é um prefixo de s (u


17/102

3


Fechamento de Kleene

Σ*: conjunto de todas as cadeiassobre um alfabeto Σ.

Ex.: {0,1}* = {ε,0,1,00,01,10,11,000,...}

Σ* = Σ0 ∪ Σ1 ∪ Σ2 ∪ ...

Σ+ = Σ1 ∪ Σ2 ∪ Σ3 ∪ ...

Σ* = Σ+ ∪ {ε}


Linguagens

Uma linguagem L sobre Σ é umsubconjunto de Σ*. (L ⊆ Σ*)

Ex.: Σ*, ∅, {ε}

Português

C

Para Σ = {α, β, γ}:• L1 = {ε, α, αββ}

• L2 = {todas as possíveis cadeias finitas iniciadaspelo símbolo α}


18/102

4


Operações sobre linguagens

Sejam A, B ⊆ Σ*

Concatenação:

AB := {s: s = uv , u ∈ A, v ∈ B}

Prefixo-Fechamento:

A := {s: ∃t ∈ Σ*, st ∈ A}

Fechamento de Kleene: A* = ∪n=0,∞A

n, onde

A0 = {ε} e An = An-1A

Operações usuais sobre conjuntos


Exemplo


19/102

5


Representação de SEDs porLinguagens


Propriedades de L e Lm


20/102

6


Exemplos

Esteira da linha de produção decervejas

Robô inserido num sistema demanufatura


Robô


21/102


22/102

1

1


DAS5202 - UFSC

Aula 3

Expressões Regulares

DAS5202 - UFSC 2

Convenção

Se u e v são cadeias de eventos:

u = {u}

(u + v) = {u, v} = {u} ∪ {v}

u* = {ε, u, uu, uuu, ...} uv = {uv}


23/102

2

DAS5202 - UFSC 3

Expressão Regular

Definição Recursiva:

1. São expressões regulares:

a) ∅: conjunto vazio,

b) ε: linguagem {ε},

c) σ: linguagem {σ}, ∀σ∈Σ;

2. Se r e s são expressões regulares, então

rs, r *, s*, (r + s) são expressões regulares;

3. Toda expressão regular é obtida pela

aplicação das regras 1 e 2 um número finito

de vezes.

DAS5202 - UFSC 4

Exemplos

Σ = {α, β, γ}

(α + β)γ* = {α,β,αγ,βγ,αγγ,βγγ,αγγγ,βγγγ,...}

(αβ)* + γ = {ε,γ,αβ,αβαβ,αβαβαβ,...}


24/102

3

DAS5202 - UFSC 5

Ordem de precedência

1. Fechamento de Kleene

2. Concatenação

3. União

Ex.:

α + βγ* = (α + (β(γ)*))

DAS5202 - UFSC 6

Exemplo


25/102

4

DAS5202 - UFSC 7

Exemplo

Σ = {α, β}

α: acesso de uma tarefa a um recurso

β: acesso de outra tarefa ao mesmo recurso

A = (αβ)*

B = (α + β)*

C = (αβ)* + (βα)*

Encontre uma expressão regular que indiqueque a diferença entre os números de acessosdas duas tarefas não seja superior a 1,mesmo para cadeias incompletas.

DAS5202 - UFSC 8

Exemplo


26/102

5

DAS5202 - UFSC 9

Linguagem regular

Definição:

Qualquer linguagem que possa ser descrita

como uma expressão regular é uma

linguagem regular .

DAS5202 - UFSC 10

Questões

Se L é uma linguagem finita, então L é

regular?

Para qualquer alfabeto Σ, Σ* é uma

linguagem regular? Qualquer linguagem é uma linguagem

regular?


27/102

1

Modelagem e Controle de SistemasModelagem e Controle de Sistemas


DAS5202 - UFSC

Aula 4

Autômatos

DAS5202 - UFSC 2

Autômatos Determinísticos de Estados

Finitos (ADEF)

Um ADEF é uma quíntuplaG = (X, Σ, f , x0, Xm)

X = conjunto não-vazio e finito de estados;

Σ = alfabeto;

f : X × Σ → X = função de transição (possivelmente parcial)de estados, definida apenas para alguns elementos deX × Σ (notação: f (q, σ)! ) ;

x0 ∈ X = estado inicial;

Xm ⊆ X = conjunto de estados marcados ou finais.

Função de eventos factíveis ΣG: X → 2Σ:

ΣG(x) = {σ: σ ∈ Σ e f (x, σ)! }


28/102

2

DAS5202 - UFSC 3

Exemplo

G = (X, Σ, f , x0, Xm)

X = {x, y, z}

Σ = {α, β, γ}

f (x,α) = x, f (x,γ) = z,f (y,α) = x, f (y,β) = y,f (z,β) = z, f (z,α) = f (z,γ) = y,

x0 = x Xm = {x, z}

ΣG(x) = {α,γ}, ΣG(y) = {α,β}, ΣG(z) = {α,β,γ}

DAS5202 - UFSC 4

Diagrama de Transição de Estado

São grafos direcionados onde os nós representam os estados e os

ramos representam os eventos

Exemplo:

x

z

yα

α,γ

γ

β

βα

G = (X, Σ, f , x0, Xm) X = {x, y, z}

Σ = {α, β, γ}

f (x,α) = x, f (x,γ) = z,f (y,α) = x, f (y,β) = y,f (z,β) = z, f (z,α) = f (z,γ) = y,

x0 = x

Xm = {x, z}

ΣG(x) = {α,γ}, ΣG(y) = {α,β},ΣG(z) = {α,β,γ}


29/102

3

DAS5202 - UFSC 5

Extensão da função de transição para cadeias

f ^: X × Σ* → X

f ^(x,ε) = x,

f ^(x,sσ) = f (f

^(x,s),σ)

Exemplo:

f ^(x, γβα) = f (f

^(x, γβ),α) = f (f (f

^(x, γ),β),α)

= f (f (f (f ^(x,ε), γ),β),α) = f (f (f (x, γ),β),α)

= f (f (z,β),α) = f (z,α) = y

DAS5202 - UFSC 6

Linguagens de um autômato

Linguagem Gerada:

L(G) = {s: s ∈ Σ* e f ^(x0, s)!}

Linguagem Marcada:

Lm(G) = {s: s ∈ L(G) e f ^(x0, s) ∈ Xm}


30/102

4

DAS5202 - UFSC 7

Exemplo

Máquina com três estados

Lm(G) = (sf + sbr)*

representa os ciclos de trabalho realizados pelo sistema

L(G) = (sf + sbr)*(ε + s + sb)

representa o conjunto de todas as seqüências fisicamente

possíveis de ocorrer no sistema

Is

W

br

D

f

DAS5202 - UFSC 8

Exemplo Seja Σ = {α, β, γ}. Uma tarefa é definida como

qualquer cadeia que inicie uma seqüência de 3eventos, iniciada por α, seguida por β ou γ eentão α.

Expressão Regular: α(β+γ)α(α+β+γ)* Autômato:

α

γ

βα,β,γ

0 1

2

3

4

α

α


31/102

5

DAS5202 - UFSC 9

Exercício

Construa um autômato G tal que L(G) e Lm(G)

correspondam aos comportamentos gerado e

marcado do robô abaixo:

DAS5202 - UFSC 1 0

Questões

Toda linguagem regular pode serreconhecida por um autômatodeterminístico de estados finitos?

Toda linguagem reconhecida por umautômato determinístico de estados finitosé regular?


32/102

6

DAS5202 - UFSC 1 1

Teorema de Kleene (1956)

Se L é regular, existe um autômato G

com um número finito de estados tal que

Lm(G) = L. Se G tem um número finito de

estados, então Lm(G) é regular.

DAS5202 - UFSC 1 2

Exemplo

L(G) = [b*aa*b]*(ε + b*aa*)

Lm(G) = [b*aa*b]*b*aa*


33/102

7

DAS5202 - UFSC 1 3

Exemplo: fila infinita

Sistema de fila

X = {0, 1, 2, ...}

Σ = {a, d}

f (x, a) = x + 1 para todo x ≥ 0

f (x, d) = x - 1 se x > 0

x0 = 0

Xm = {0}

a d

0a

1

d

a2

d

a3

d

a...

d

DAS5202 - UFSC 1 4

Exercício

Lm(G) = (a+b)*ab

L(G) = (a+b)*


34/102

1



DAS5202 - UFSC

Aula 5

Determinização e

Minimização de Autômatos

DAS5202 - UFSC 2

Autômato Não-Determinístico de Estados Finitos

Um ANDEF é uma quíntuplaG = ( X , Σ, f , x 0, X m) X = conjunto não-vazio e finito de

estados;

Σ = alfabeto; f : X × Σ → 2 X = função de transição de

estados;

x 0 ∈ X = estado inicial;

Xm ⊆ X = conjunto de estados marcadosou finais.


35/102

2

DAS5202 - UFSC 3

Exemplo G = ( X , Σ, f , x 0, X m)

X = {0, 1}

Σ = {α, β}

f (0,α) = {0,1}, f (0,β) = ∅,f (1,α) = ∅, f (1,β) = {0},

x 0 = 0

X m = {0}

0 1

α

β

α

DAS5202 - UFSC 4

Extensão da função de transição para cadeias

f ^: X × Σ* → 2 X

f ^( x ,ε) = { x },

f ^( x ,sσ) = { z : z ∈ f (y,σ), y ∈ f

^( x ,s)} = Uy ∈f ̂ ( x ,s)f (y ,σ)

Exemplo:

f ^(0,ααβ) = { z : z ∈ f(y,β), y ∈ f

^(0,αα)}

= { z : z ∈ f(y,β), y ∈ f ( x ,α) , x ∈ f (0,α )}

= { z : z ∈ f(y,β), y ∈ f ( x ,α) , x ∈{0,1}}

= { z : z ∈ f(y,β), y ∈ {0,1}}

= { z : z ∈ {0}} = {0}


36/102

3

DAS5202 - UFSC 5

Equivalência entre ADEF e ANDEF

Questão: É possível que um ANDEF reconheçalinguagens que não são reconhecíveis por algumADEF?

Teorema: Uma linguagem é reconhecida por umautômato não-determinístico de estados finitos see somente se for reconhecida por um autômatodeterminístico de estados finitos.

Corolário: A todo autômato não-determinísticocorresponde um autômato determinísticoequivalente, ou seja, que reconhece a mesmalinguagem.

DAS5202 - UFSC 6

ANDEF → ADEF

Seja um ANDEF N = ( X N, Σ, f N, x 0, X mN). Defina o ADEF D = ( X D, Σ, f D, { x 0}, X mD),

sendo que:

X D = 2 X N

; X mD = {S: S ∈ X D, S ∩ X mN ≠ ∅};

f D(S,σ) = U x ∈S f N( x ,σ). Com isso:

Lm(N) = Lm(D) Para que L(N) = L(D), remover o estado ∅.


37/102

4

DAS5202 - UFSC 7

{1}

∅

{0}

{0,1}

Exemplo

{0}

α

β

α,β

{0,1}

α

β

β

α

{0}

α

β

α,β

{0,1}

∅

β

α

DAS5202 - UFSC 8

Mais Exemplos

a

d

0

0

0,1

e

b 0

1

1

1c

0


38/102

5

DAS5202 - UFSC 9

Exercício

a

0,1

c1

b0,1

d0,1

DAS5202 - UFSC 10

Equivalência de autômatos

Dois autômatos A e B são equivalentes see somente se L(A) = L(B) e Lm(A) =Lm(B).

Exemplo:

x y

0

0,1

0

1

z w

1 0,1

A:

x yzw0,1

0,1

B:


39/102

6

DAS5202 - UFSC 11

Estados Equivalentes

Seja G = ( X , Σ, f , x 0, X m) um AFD e S ⊆ X .Diz-se que o conjunto S é constituído deestados equivalentes em relação a X m se,para quaisquer x , y ∈ S, x ≠ y , e qualquercadeia s: f

^( x , s) ∈ X m ⇔ f

^(y , s) ∈ X m

f ̂ ( x , s)! ⇔ f ̂ (y , s)!

DAS5202 - UFSC 12

Exemplo

Um autômato deve detectar a seqüênciade dígitos 1,2,3

x 0

1

x 121

x 1

2

x 12331

1

x n1

2,3

2,3 2,331 2


40/102

7

DAS5202 - UFSC 13

Algoritmo para Identificação de

Estados Equivalentes1. Excluir ( x , y ) para todo x ∈ X m e y ∉ X m2. Para todo par ( x , y ) não excluído em 1:

a) Se o par (f ( x , σ), f (y , σ)) está excluído para algum σ∈Σou não está definido para uma só das componentes,então:

i. Excluir ( x , y );

ii. Excluir todos os pares (w , z ) na lista de ( x , y );

iii. Repetir para cada (w , z ) até que nenhuma exclusão sejapossível.

b) Se (f ( x , σ), f (y , σ)) não está excluído para nenhum σ∈Σentão:

i. Se f ( x , σ) ≠ f (y , σ), então acrescentar ( x , y ) à lista de(f ( x , σ), f (y , σ)) .

DAS5202 - UFSC 14

Exemplo

x 12 x n1 x 1

x 123

x 12

x n1

x 0

x 1

x 0

1

x 121

x 1

2

x 12331

1

x n1

2,3

2,3 2,331 2

X X X X

X(x0, x1)(xn1, x1)X

X

X

X


41/102

8

DAS5202 - UFSC 15

Minimização de AFD

1. Eliminar qualquer estado que não possaser alcançado a partir do estado inicial.

2. Particionar os estados restantes emblocos, de modo que:

todos os estados num mesmo bloco sejamequivalentes

e nenhum par de estados de blocos distintosseja equivalente.

DAS5202 - UFSC 16

Exemplo

Um autômato deve detectar a seqüênciade dígitos 1,2,3

x 0

1

x 12

1 x 1

2

x 123

31

1

x n1

2,3

2,3 2,331 2


42/102


43/102

10

DAS5202 - UFSC 19

Exemplo

G

X

F

X

X

E

X

X

X

XXXG

XXE

XXXF

CBA

H

C

B

XX

XX

X

DAS5202 - UFSC 20

Exemplo

AE

0

C0

BH

0

1

1

F

1

0

G

0

1

1


44/102

1



DAS5202 - UFSC

A u l a 6

Bloqueio e

Composição de autômatos

DAS5202 - UFSC 2

B l o q u e i o

Deadlock: estado x tal que

• ΣG(x) = ∅ e• x ∉ Xm

Livelock: conjunto de estados que

• formam componente fortemente conexa (estadossão todos acessíveis entre si)• não há transição que saia do conjunto• não são marcados

Um autômato é não-bloqueante se

• Lm(G) = L(G) Se um autômato for bloqueante, então pode ocorrer

deadlock e/ou livelock.


45/102

2

DAS5202 - UFSC 3

E x e m p l o

Estado 5 é um deadlock Estados 3 e 4 estão envolvidos num livelock

αα ∈ L(G), mas αα ∉ Lm(G)

0 5

α1

γ

2

βγ

α

4

γ

3

α

β

DAS5202 - UFSC 4

A c e s s i b i l i d a d e

Um estado x ∈ X é chamado deacessível se ∃s ∈ Σ* tal que f (x0, s) = x.

Componente Acessível de um autômato: Ac(G) = (Xac

, Σ, f ac

, x0, Xmac)• X

ac= {x∈X: ∃s ∈ Σ* , f (x0, s) = x}

• xmac

= Xac

∩ Xm

• f ac

= f |Xac×Σ→Xac

Um autômato é acessível se Ac(G) = G


46/102

3

DAS5202 - UFSC 5

C o a c e s s i b i l i d a d e

Um estado x ∈ X é coacessível se

∃s ∈ Σ* tal que f (x, s) ∈ Xm

.

Um autômato é coacessível se todos os

estados forem coacessíveis.

Um autômato é trim (aparado) se for

acessível e coacessível. Um autômato é não-bloqueante sse

Ac(G) for coacessível.

DAS5202 - UFSC 6

E x e m p l o

Estado 5: não acessível

Estado 4: não coacessível

0 5

α1

γ

2

βγ

α

4

γ

3 β


47/102

4

DAS5202 - UFSC 7

E x e m p l o

Componente acessível

0

α1

2

βγ

α

4

γ

3β

DAS5202 - UFSC 8

E x e m p l o

autômato Trim

0

α1

2

βγ

α

3


48/102

5

DAS5202 - UFSC 9

P r o b l e m a

Cozinheiro C1: pega o garfo (g1), pega a faca (f 1) e

devolve ambos talheres (d1) após a operação.

Cozinheiro C2: pega a faca (f 2), pega o garfo (g2)e

devolve ambos talheres (d2) após a operação. Controle: cada recurso não pode ser pego por ambos

usuários ao mesmo tempo

C1 C2

g1, f 1

d1

f 2, g2

d2

DAS5202 - UFSC 10

Q u e s t õe s

1. Existe bloqueio?

2. Modelar por um autômato o

comportamento do sistema.3. Como evitar o bloqueio?

4. Qual o modelo resultante?


49/102

6

DAS5202 - UFSC 11

So l ução

00

g10210

11 12 22f 1

d1

g2

f 2

g1f 2

d2

DAS5202 - UFSC 12

So l ução

00

g10210

11 22f 1

d1

g2

f 2d2


50/102


51/102

8

DAS5202 - UFSC 15

O b s e r v a çõe s

G = G1 || G2 é obtido fazendo-se a evolução em paralelodos autômatos G1 e G2, na qual um evento comum aosdois autômatos só é executado se ambos o executaremsimultaneamente.

Alfabetos idênticos ⇒ interseção.

Alfabetos disjuntos ⇒ composição assíncrona.

Propriedades:

• G1 || G1 ≡ G1• G1 || G2 ≡ G2 || G1• (G1 || G2) || G3 ≡ G1 || (G2 || G3)

DAS5202 - UFSC 16

P r o b l e m a

Cozinheiro C1: pega o garfo (g1), pega a faca (f 1) edevolve ambos talheres (d1) após a operação.

Cozinheiro C2: pega a faca (f 2), pega o garfo (g2)edevolve ambos talheres (d2) após a operação.

Controle: cada recurso não pode ser pego por ambosusuários ao mesmo tempo

C1 C2

g1, f 1

d1

f 2, g2

d2


52/102

9

DAS5202 - UFSC 17

Mod e l o s L o c a i s

R F C

g2f 2

d2

G2

R G Cg1 f 1

d1

G10 1

f 1, f 2

d1, d2

Gf

0 1

g1, g2

d1, d2

Gg

DAS5202 - UFSC 18

Pr o d u t o S ín c r o n o G g || G f

0 1

f 1, f 2

d1, d2

Gf

0 1

g1, g2

d1, d2

Gg 00

01

g1, g2

d1, d210

11

f 1, f 2

g1, g2f 1, f 2


53/102


54/102

11

DAS5202 - UFSC 21

RR

00

g1 RF01

GR

10

CR

11

GF

11

RC

11

f 1

d1

g2

f 2

g1f 2

d2

So l ução

DAS5202 - UFSC 22

L óg i c a d e c o n t r o l e

RR

00

g1 RF01

GR

10

CR

11

RC

11

f 1

d1

g2

f 2

g1f 2

d2

f 2 g1


55/102


56/102

2

DAS5202 - UFSC 3

Abordagem Global X Abordagem Local

• Abordagem global: procura-se por umADEF que represente todas as seqüências possíveis de eventos que ele pode gerar etarefas que pode completar.

• Tarefa de grande complexidade para sistemas demaior porte;

• Inclusão ou retirada de equipamentos, oumodificação em sua lógica de controle, requer areconstrução do modelo como um todo.

DAS5202 - UFSC 4

Abordagem Global X Abordagem Local

• Abordagem local: parte do princípio de que se pode

construir modelos locais para cada sub-sistema e

restrição de coordenação, e que se pode compor os

mesmos para obter um modelo do sistema global.• Maior facilidade na obtenção de modelos de sistemas de

grande porte;

• Alterações num subsistema ou em alguma restrição

somente exigirão uma mudança no modelo especıfico

correspondente.


57/102

3

DAS5202 - UFSC 5

Modelagem da Planta

1. Identificar o conjunto de sub-sistemas ou

equipamentos envolvidos no sistema a

controlar;

2. Construir o modelo básico ADEF Gi, de cada

equipamento i envolvido no sistema;

3. Obter o modelo da planta G a ser controlada,através da composição síncrona de todos os

ADEF Gi.

DAS5202 - UFSC 6

Exemplo: Sistema de Manufatura

Suponha um sistema constituído por duas

máquinas e um buffer

Onde:

{a1,a2}⇒ indicam início de operação

{b1,b2}⇒ indicam fim de operação e depósito de peça

no buffer (b1)

M2M1 Ba1 b1 a2 b2


58/102

4

DAS5202 - UFSC 7


Máquina M1:

Máquina M2:

M2M1 Ba1 b1 a2 b2

I W

a1

b1

G1:

a2

b2

G2:

I W

DAS5202 - UFSC 8


G1 || G2 :

M2M1 Ba1 b1 a2 b2

II WI

a1

b1

G:

WW

a1

b1

IW

a2

b2

a2

b2

I W

a1

b1

G1:

a2

b2

G2:

I W


59/102

5

DAS5202 - UFSC 9

Modelagem da Especificação1. Construir autômatos E j para cada restrição de coordenação j,

do sistema a ser controlado; Em geral, cada restrição diz respeito a um sub-conjunto dos sub-

sistemas;

Podem ser muitas vezes descritas por um conjunto pequeno deeventos do sistema;

Não necessitam considerar o comportamento global de cadaequipamento (vide caso justiça no acesso a recurso).

2. Realizar a composição dos autômatos construídos no passo

1; compor o autômato resultante com o autômato da plantaG, gerando o autômato R; Composição das restrições de coordenação, feita no passo 2, leva a

uma restrição global de coordenação;

Composição com G leva à sua reescrita levando em conta ocomportamento da planta ( Lm(R) ⊆ Lm(G))

DAS5202 - UFSC 10

Modelagem da Especificação

3. Atualizar R pela eliminação, caso houver, deestados considerados proibidos;

Considera p.e. restrições de segurança (p.e. estadosindicando colisão, situação de perigo, ...);

Após este passo Lm(R) = E .

4. Atualizar R pelo cálculo de sua componentecoacessível, ou não-bloqueante.

Reflete a idéia de que não se deseja que a especificaçãoinclua situações de bloqueio;

Após este passo Lm(R) = E ⊆ Lm(G) e L(R) = Lm(G).


60/102

6

DAS5202 - UFSC 11


Restrição de coordenação:

Evitar overflow e underflow

M2M1 Ba1 b1 a2 b2

a2

b1

0b1

a2

1

E:

DAS5202 - UFSC 12


E || G :

M2M1 Ba1 b1 a2 b2

a2

b1

a2

b1

II0 WI0

a1

R:

IW0

b2

b1

WI1

a1

a2

WW0

a1

IW1

b1

WW1

a1

b2

b2

b2a

2

II1


61/102

7

DAS5202 - UFSC 13

II0 WI0

a1

R:

IW0

b2

b1

WI1

a1

a2

WW0

a1

IW1

b1

WW1

a1

b2

b2

b2a

2

II1


Restrição de segurança:

Proibir operar as duas máquinas simultaneamente

M2M1 Ba1 b1 a2 b2

DAS5202 - UFSC 14


Eliminação de estados proibidos

M2M1 Ba1 b1 a2 b2

II0 WI0

a1

R:

IW0

b2

b1

WI1

a1

a2

IW1

b2

II1


62/102

8

DAS5202 - UFSC 15


Especificação não-bloqueante

M2M1 Ba1 b1 a2 b2

a2

a1

a2

a1

II0 WI0

a1

R:

IW0

b2

b1

a2

II1


63/102

1



DAS5202 - UFSC

Aula 8

Teoria de Controle Supervisório

DAS5202 - UFSC 2

Supervisor

supervisor S interage com a planta G, numa estrutura de malha fechada S observa os eventos ocorridos em G; e define que eventos são permitidos de ocorrerem a seguir (controle de natureza

permissiva )

conjunto de eventos habilitados pelo supervisor define uma entrada decontrole;

entrada de controle é atualizada a cada nova ocorrência de eventoobservada em G;

conjunto de eventos é particionado num conjunto de eventos desabilitáveis,ou controláveis, e um conjunto de eventos cuja natureza não permite adesabilitação.

Planta Supervisor Evento

Habilitações


64/102


65/102


66/102

4

DAS5202 - UFSC 7

Controlabilidade

DAS5202 - UFSC 8


M2M1 Ba1 b1 a2 b2

a2

b1

a2

b1

II0 WI0

a1

R:

IW0

b2

b1

WI1

a1

a2

WW0

a1

IW1

b1

WW1

a1

b2

b2

b2a

2

II1


67/102

5

DAS5202 - UFSC 9


M2

M1 B

a1 b1 a2 b2

a2

a1

a2

a1

II0 WI0

a1

R:

IW0

b2

b1

a2

II1

DAS5202 - UFSC 10

Controlabilidade


68/102

6

DAS5202 - UFSC 11

Solução do PCS

C (E ): conjunto de linguagens controláveis contidas em E .

possui um elemento supremo supC (E ).

Teorema O problema de controle supervisório possui solução se e somente se supC (E ) ⊇ A

supC (E ) representa o comportamento menosrestritivo possível de se implementar por supervisão.

O supervisor ótimo S é tal que L m (S/ G) = supC (E ):

DAS5202 - UFSC 12

Síntese do supervisor não-bloqueante ótimo


69/102

7

DAS5202 - UFSC 13

Algoritmo para supC(E)

DAS5202 - UFSC 14

Maus Estados


70/102


71/102


72/102


73/102

2

DAS5202 - UFSC 3

Modelagem da Planta

DAS5202 - UFSC 4

Modelagem da Restrição


74/102


75/102

4

DAS5202 - UFSC 7

Modelagem da Planta

G1: a1

b1

G2: a2

b2

G3: a3

b3,c3

b1

a1

a1

a1

a1

a2

a2

a2

a2

a3a3

a3

a3

b1

b1

b1

b2

b2

b2

b2 b3,c3

G:

b3,c3

b3,c3

b3,c3

DAS5202 - UFSC 8

Modelagem das Restrições

E1:

a2

b1, c3 b2E2:

a3

E: b1, c3

a2

a2

b2 a3 b2 a3 b1, c3


76/102


77/102

6

DAS5202 - UFSC 11

Pequena fábrica com quebra

Suponha um sistema constituído por duasmáquinas e um armazém unitário

Incluindo: {λ1, λ2} ⇒ indicam quebra das máquinas

{μ1, μ2} ⇒ indicam reparo das máquinas

Restrições de coordenação: Impedir overflow e underflow do armazém

A prioridade de reparo é da máquina M2, ou seja, casoM1 e M2 estejam ambas quebradas, M2 deve serreparada primeiro.

M2M1 Bα1 β 1 α2 β2

DAS5202 - UFSC 12

Planta


78/102

7

DAS5202 - UFSC 13

Restrições

DAS5202 - UFSC 14

SupC(E)


79/102


80/102

2

DAS5202 - UFSC 3

Grail

Desenvolvido sob o paradigma de

orientação a objetos e implementado em

C++

Pacote disponível no DAS: Grail para

Controle Supervisório

Permite duas visões: Usuário ou programador

DAS5202 - UFSC 4

Instalação do Grail

Instalação (arquivos disponíveis):

Grail para controle supervisório em

http://www.das.ufsc.br/~cury/grail.html

Arquivo de instalação

Manual de utilização

Guia de instalação

Módulos para extensões de controle de SEDs

Instalar a ferramenta Graphviz, encontrada em

http://www.research.att.com/sw/tool/graphviz


81/102

3

DAS5202 - UFSC 5

Funcionamento do Grail A representação de uma máquina de estados finitos se dá

através de um conjunto de instruções armazenada em umarquivo ASCII

Exemplo:

Aceita múltiplos estados finais e iniciais É independente do tipo de alfabeto utilizado

)(|2

21

10

0|)(

FINAL

b

a

START

−

−

0 1 2a b

DAS5202 - UFSC 6

Filtros do Grail para autômatos (FM)


82/102

4

DAS5202 - UFSC 7

Funcionamento do Grail

Os filtros podem ser utilizados a partir de: um prompt de comando, onde o usuário pode

executar os filtros em arquivos de entrada

Exemplo: % fmsync m1.grail m2.grail > planta.grail

% fmsync m1.grail m2.grail | fmsync m3.grail > G.grail

um .bat criado com a seqüência de operações aser realizada

DAS5202 - UFSC 8

Controle Supervisório no Grail

No Grail, a planta é representada por uma FM onde as

etiquetas de transição são os eventos.

As linguagens das especificações também são

representadas por FM. Os conjunto de eventos não controláveis deve ser fornecido

em uma FM com um só estado com transições em selfloop

com os eventos não-controláveis.

Os supervisores são representados por FM e as ações de

controle são indicadas em outra FM com auto-laços dos

eventos desabilitados em cada estado.


83/102

5

DAS5202 - UFSC 9

Algumas funções básicas

fmstats: fornece informações sobre a FM % fmstats fm.grail

isdeterm: testa se FM é determinística

isomorph: testa se duas FM são isomórficas

fmalpha: obtém o alfabeto de uma FM

fmtodot: converte uma FM para o formato

reconhecido pelo Graphviz % fmtodot fm > fm.do

% dotty fm.do

DAS5202 - UFSC 10

Funções para Controle Supervisório

fmsync: faz o produto síncrono de duas FMs

fmremove: elimina estados de uma FM

fmtrim: encontra a componente trim de uma FM

fmcondat: informa dados de controle emsupervisão (eventos desabilitados) % fmcondat g.grail s.grail

fmsupc: encontra a máxima linguagemcontrolável % fmsupc g.grail r.grail sigmau.gdat


84/102


85/102


86/102


87/102

9

DAS5202 - UFSC 17

Exemplo: Sistema de Manufatura Determinação do supervisor minimamente restritivo

fmsupc g.grail rtrim.grail sigmau.gdat > s.grail

Teste de controlabilidade

fmcondat g.grail rtrim.grail sigmau.gdat > rtrim.gdat

(FINAL)|-2

(FINAL)|-0

5a15

2a12

1a21

0a20

DAS5202 - UFSC 18

Exemplo: Sistema de Manufatura Visualização do resultado através da ferramenta Graphviz

fmtodot s.grail > s.do

dotty s.do

(FINAL)|-2

(FINAL)|-0

5a15

2a12

1a21

0a20


88/102

10

DAS5202 - UFSC 19

Redução de supervisores

fmsupred g.grail s.grail > sred.grail

DAS5202 - UFSC 20

TCT

Ferramenta alternativa ao Grail (restrições quanto

a obtenção do supervisor reduzido)

Existem funções que convertem do formato do

grail para TCT (pacote minsup do Max) Desenvolvido na University of Toronto pela

equipe do Prof. Wonham

Documentação disponível no arquivo tctinfo.txt e

nas notas de aula do Prof. Wonham


89/102

11

DAS5202 - UFSC 21

Características

Interface com o usuário (sem script).

Salva os autômatos em arquivos binários:criados e editados dentro do TCT.

Eventos controláveis são representadospor números ímpares e não-controláveispor pares.

Manipula autômatos com até 1.000.000 deestados.

DAS5202 - UFSC 22

TCT

Instalação:

Baixar o TCT (CTCT,XPTCT...) presente em

http://www.control.utoronto.ca/people/profs/wonh

am/wonham.html

Descompactar o xptct86.zip para o diretório

desejado

Inserir o caminho [tct_dir] no path do sistema

Instalar a ferramenta Graphviz, encontrada em

http://www.research.att.com/sw/tool/graphviz


90/102

12

DAS5202 - UFSC 23

TCT

DAS5202 - UFSC 24

TCT

Geradores são representados por uma quíntupla

[Size, Init, Mark, Voc, Tran]

Size: número de estados (0… size-1)

Init: estado inicial (estado 0)

Mark: estados marcados

Voc: estados vocais

Tran: transições [I E J] evento E saindo de I e indo para J

(números não negativos, ímpar se controlável e par se

não-controlável)


91/102

13

DAS5202 - UFSC 25

Principais funções do TCT

Create ⇒ cria uma nova FM

Trim ⇒ encontra a componente trim de uma FM

Sync ⇒ realiza o produto síncrono de duas FMs

Supcon ⇒ encontra a máxima linguagem

Condat ⇒ informa dados de controle em

supervisão (eventos desabilitados)

Supreduce ⇒ encontra um supervisor reduzido

DAS5202 - UFSC 26

Exemplo

TUM2 B2c d e g

M1

f

aB1

b

a

bI W

M1

c

dI W

M2

e

f,gI W

TU

b,f

c

E1

d

e

E2Σu={b,d,g,f }


92/102

1


DAS5202 - UFSC

Aula 11

Controle Modular e Implementação

DAS5202 - UFSC 2

Célula de Manufatura

Buffer de entrada

Buffer de saída

ESTEIRA (M1)

FURADEIRA (M2)

TESTE (M3)

MANIPULADOR (M4)

MESA

CIRCULAR

(M0)

P1

P2

P3

P4

CLPSaídas

Entradas


93/102

2

DAS5202 - UFSC 3

O Problema de Controle

Planta livre: funcionamento independente dos 5 equipamentos.

Problemas: operar a esteira, a furadeira, o teste ou o robô enquanto a mesa

girar;

sobrepor peças na posição P1;

girar a mesa sem que as peças em P2, P3 e P4 tenham sidofuradas, testadas ou retiradas, respectivamente;

furar, testar ou acionar o robô sem peças em P2, P3 e P4, resp.;

furar ou testar duas vezes a mesma peça;

girar a mesa sem nenhuma peça.

Lógica de Controle: operar de 0 a 4 peças;

evitar os problemas;

não bloqueante;

minimamente restritiva.

ESTEIRA(M1)

FURADEIRA (M2)

TESTE(M3)

ROBÔ (M4)

MESA(M0)

P1

P2

P3

P4

DAS5202 - UFSC 4

Metodologia

obtenção de um modelo para a planta a ser

controlada;

obtenção de um modelo de representação

das especificações; síntese de uma lógica de controle não-

bloqueante e ótima.


94/102

3

DAS5202 - UFSC 5

βi

α i

Gi, i = 0, ..., 4:

Gerador para Mi , i = 0,...,4.

ESTEIRA(M1)

FURADEIRA(M2)

TESTE(M3)

ROBÔ (M4)

MESA(M0)

P1

P2

P3

P4

Modelagem da Planta

Planta global: G = ||i=0,...,4Gi (32 estados e 160 transições),

DAS5202 - UFSC 6

Modelagem das Especificações

E gen,a:

β1, β2, β3

α0β1, β2, β3

E gen,bi , i = 1,...,4:

α0, αi

β0, βi

E gen,ci , i = 1,2,3:

αi+1

βi βiα0 α0

αi+1

Especificação genérica:

Egen = ||x ∈ {a, b1, b2, b3, b4, c1, c2, c3}Egen,x(296 estados e 745 transições)

Especificação global:

Kglobal = Egen || Lm(G)(151 estados e 350 transições)

ESTEIRA(M1)

FURADEIRA(M2)

TESTE(M3)

ROBÔ (M4)

MESA(M0)

P1

P2

P3

P4


95/102

4

DAS5202 - UFSC 7

Controle Supervisório

Supervisor:

representado por um gerador S tal que S/G = S || G.

Objetivo:

obter S não-bloqueante tal que Lm(S/G) = Kglobal.

Condição necessária e suficiente: controlabilidade de Kglobal e.r.a G (Ramadge e Wonham, 1987).

Solução minimamente restritiva: SupC(Kglobal,G).

Planta Supervisor Evento

Habilitações

DAS5202 - UFSC 8

Síntese Monolítica para a C.M.

Supervisor:

gerador aparado (trim) de 151 estados e 350 transições;

requer muita memória e capacidade de processamento doCLP;

lógica de controle incompreensível;

dificuldade para:

programação;

depuração;

modificação.

Alternativas:

redução de supervisor;

arquitetura: controle modular local (Queiroz e Cury, 2000).


96/102

5

DAS5202 - UFSC 9

Redução de Supervisores

α1

α1

γ1 γ1 γ1 γ1

α1

β1 β1 β1β1

β5,β6

β5,β6

β5,β6

γ1 γ1γ1γ1τ1

τ1

τ1 τ1

τ1

τ1

S X1:

0 1 2 3

4 5 6 7

8 9 10 11

X1

X2

S red,1:

α1

γ1

α1

β1

γ1 X1 X2

DAS5202 - UFSC 10

Supervisor Monolítico Reduzido :


97/102

6

DAS5202 - UFSC 11

Abordagem Modular Local

S1

S2S3

S3S

2S1

M1M2

M3 M4

Desvantagem:

pode haver conflito⇒ Bloqueio.

Condição: modularidade local (Queiroz e Cury, 2000).

Se falhar:

resolução de conflito (coordenador).

DAS5202 - UFSC 12

Controle Modular Local - Modelagem

G = G2 || G3 || G4

G 2

6 5

E a

8 7

E b

3 4

G’ 2

3 5

G” 2 G 3

6 7 8 9

G 4

1 2

G1

G A = G2 || G3 ; G B = G3 || G4

E A(B) = E a(b) || Lm(G A(B))

K A(B) = E a(b) || Lm(G)


98/102

7

DAS5202 - UFSC 13

Controle Modular Local - Síntese

Definição (Queiroz e Cury, 2000):

Teorema (Queiroz e Cury, 2000):

Se {SupC ( E Xi, Lm(G Xi)), i ∈ I } é localmente modular, então

SupC (∩i∈ I K Xi, Lm(G)) = ||i∈ I SupC ( E Xi, Lm(G Xi)).

Modularidade local garante : otimidade

Sejam E Xi ⊆ Σ Xi*, i ∈ I . O conjunto { E Xi , i ∈ I } é

localmente modular se ||i∈ I E Xi = ||i∈ I E Xi

DAS5202 - UFSC 14

Metodologia

1. Modelar cada subsistema;

2. calcular a mais refinada RSP;

3. modelar cada especificação isoladamente;

4. obter a planta local para cada especificação;

5. calcular as especificações locais;

6. calcular as máximas linguagens controláveis;

7. verificar a modularidade local;

8. se não forem modulares, resolver o conflito ;

9. se forem modulares, implementar os supervisores.


99/102

8

DAS5202 - UFSC 15

Síntese Modular Local

4243284ci, i = 1,2,3

23342bi, i = 1,...,4

23232162a

Sred,xSloc,xEloc,xGloc,xEgen,xx

Teste de modularidade local:

S = ||xSloc,x (151 estados) é um autômato trim!

6215115132296Monolítico:

SredSmonKglobalGEgen

DAS5202 - UFSC 16

Supervisores Reduzidos

S red,a :

β1, β2, β3

α0

β1, β2, β3α0

S red,bi , i = 1,...,4:

α0, αi

β0, βi

α0,αi

S red,ci , i = 1,2,3:

αi+1

βi βi

α0,αi

α0

αi+1

αi α0,αiα0αi,αi+1αi+1


100/102

9

DAS5202 - UFSC 17

Estrutura Genérica de Implementação

Seqüências Operacionais

Supervisores Modulares

desabilitações eventos

Sistema-Produto

comandos respostas

Sistema Real

saídas do S.C. entradas do S.C.

S i s t e m a d e C o n t r o l e

P

l a n t a I

n t e r f a c e

DAS5202 - UFSC 18

Aplicação à Célula de Manufatura

S red,x, x { a, b1, b2, b3, b4, c1, c2, c3}

sinais de saída sinais de entrada

C L P

comandos respostas

mesa esteira furad. teste robô


G1 G2: G3: G4:G0:


101/102

10

DAS5202 - UFSC 19

Implementação em Diagrama Ladder

Supervisor Sred,c1 :

s0 1 s1

|--][-+-][--+--(S)-|

| | s0 |

| +--(R)-|

| s1 0 s2 |

|--][-+-][--+--(S)-|

| | s1 |

| +--(R)-|

| s2 2 s0 |

|--][-+-][--+--(S)-|

| | s2 |

| +--(R)-|

...

Máquina de estado

| s2 d-

0 |

|--][-+-----+--( )-|

| s3 | |

|--][-| |

| s1 d-

1 |

|--][-+-----+--( )-|

| s3 | |

|--][-| |

| s0 d-

2 |

|--][-+-----+--( )-|

| s1 |

|--][-|

Desabilitações


d-α0, d-α1, d-α2 α0, α2, β1

Sistema-Produto

iníc io de operação f inal de operação



α2

β1 β1

α0,α

1

α0

α2

α1 α0,α1α0α1,α2α2

s0

s1 s2

s3

DAS5202 - UFSC 20

g0 d-

1 e-ini

|--][-+-]/[-+--( )-|

| | 1 || +--( )-|

| | g1 |

| +--(S)-|

| | g0 |

| +--(R)-|

| | sup |

| +---->>|

Transição controlável

| g1 e-fim 1 |

|--][-+-][--+--( )-|

| | e3 || +--(R)-|

| | g1 |

| +--(S)-|

| | g0 |

| +--(R)-|

| | sup |

| +---->>|

Transição não-controlável

Planta G1 (Esteira): β1

α1

g0 g1


d-α0 α1, β1

Sistema-Produto

e-ini e-fim





102/102

DAS5202 - UFSC 21

e-ini e1

|--][-+-----+--(S)-|

| e1 O0.1 |

|--][-+-----+--(S)-|

| | e2 |

| +--(S)-|

| | e1 |

| +--(R)-|

| e2 I0.1 O0.1 |

|--][-+-][--+--(R)-|

| | e3 |

| +--(S)-|

| | e2 |

| +--(R)-|

| e3 e-fim |

|--][-+-----+--( )-|

Seqüência Operacional da Esteira:



Sistema-Produto

e-ini e-fim


O0.1 I0.1


Ferramenta CGLI

Documents

DAS5202 - Modelagem e Controle de Sistemas Automatizados