Sistema : Conceito primitivo (intuitivo) Tentativas de definiçãorafael/ia851/introducao_sed_a.pdf · 2010-03-08 · Modelagem e Controle de Sistemas a Eventos Discretos 1 1. Introdução:

1Modelagem e Controle de Sistemas a Eventos Discretos

1. Introdução: Sistemas e Modelos

Sistema: Conceito primitivo (intuitivo)

Tentativas de definição:

•Agregação ou montagem de coisas, combinadas pelo homem ou pela natureza de modo a formar um todo unificado.

•Grupo de itens interdependente ou interagindo regularmente,formando um todo unificado.

•Combinação de componentes que agem em conjunto para desempenhar uma função que se torna impossível na ausên-cia de qualquer das partes.

Modelo:

Dispositivo que de alguma maneiradescreve o comportamento do sistema



Em geral definimos para o modelo: •Variáveis de entrada;•Variáveis de saída;

que espelham as interações do sistema com o Universo

sistema

entr

adas saíd

as

Espera-se do modelo estabelecer relações entre estas variáveis. Para certa classe de sistemas é conveniente o seguinte modelo:

modelo

variá

veis

de

entr

ada variáveis

de saíd

a

u(t) y(t)

y(t) = g(u(t))



Exemplo:

Os modelos de sistemas podem ser classificados sob vários cortes:

•Físicos ou Matemáticos•Estáticos ou Dinâmicos•Lineares ou Não-lineares•Variante ou Invariante no tempo•Analíticos ou Numéricos

O exemplo acima é um modelo matemático, estático, linear, invariante no tempo e analítico de um circuito elétrico.

R

ru(t)

+

−)t(u

rR

R)t(y

+=



Modelos dinâmicos × Modelos estáticos

Um modelo é dinâmico se o valores das saídas dependem de valores passados das entradas

Modelos invariantes no tempo × Modelos variantes no tempo

y(t) = g(u(t)) ou y(t) = g(u(t),t)

Estado: é a informação necessária num instante de tempo para se prever a saída futura do sistema, caso os valores futuros das variáveis de entrada sejam conhecidos.

x = f(x,u,t)y = g(x,u,t)

⋅⋅⋅⋅

Para uma certa classe de sistemas, o estado pode ser representado por um vetor x(t) e o modelo fica:



Exemplo:

R

Cu(t)

+

−)t(v)t(u)t(y c−=

uRC

1v

RC

1v cc +−=&

Este é um exemplo de um modelo matemático, dinâmico, linear, invariante no tempo e analítico de um circuito elétrico.

Modelos lineares × Modelos não-lineares

Um modelo é linear se o princípio da superposição se aplica:

Um sistema modelado pelas funções f e g será linear sse as funções f e g forem lineares.

entrada saídau1 y1

u2 y2

αu1 + βu2 αy1 + βy2



Espaço de Estados

Nos exemplos anteriores o estado assume valores num sub-conjunto de Rn:espaço de estados

Em sistemas físicos o estado está associado ao armazenamento de energia.

Contudo o conceito de estado é mais geral: A informação que sintetiza o passado do sistema pode ser expressa de outras maneiras.

x ∈ Z x ∈ {0,1}x ∈ {a, b, c, d, e} x ∈ {0,1} × Nn • • •

Modelos com espaço de estado contínuo×

Modelos com espaço de estado discreto

Portanto pode-se classificar os modelos segundo:

Exemplos:



Exemplo: Sistema de estocagem

chegada de produtos

saída de produtos

u1(t) = num. deitens que entraram

u2(t) = num. de itens que saíram

x(t) = num. de itens em estoque

0)t(u)t(u)t(x)t(y 21 ≥−==

As variáveis envolvidas no exemplo anterior podem ser determinísticasou estocásticas, portanto pode-se ainda distinguir:

Modelos determinísticos × Modelos estocásticos

Esta distinção será explorada num próximo capítulo



Finalmente pode-se distinguir entre:

Modelos dirigidos pelo tempo×

Modelos dirigidos pela ocorrência de eventos

Um modelo com espaço de estados contínuo cujas trajetórias no espaço de estado sejam contínuas tem sua dinâmica naturalmente dirigida pelo tempo.

•conceito primitivo•sem duração•altera o estado

Usualmente, a formulação matemática deste tipo de modelo envolveequações diferenciais

obs.: num modelo dirigido pela ocorrência de eventos o estado só muda quando ocorre um evento

evento:



Um modelo com espaço de estados discreto pode apresentar:

•dinâmica dirigida pelo tempo eventos ocorrem sincronizados por um relógio.

•dinâmica dirigida pela ocorrência de eventos eventos ocorrem assíncrona e concorrentemente

A ausência de paradigmas para a modelagem dos Sistemas Dinâmicos aEventos Discretosfaz da simulaçãouma importante ferramenta para seu estudo

Não há paradigma formal para os modelos com espaço de estados discretocom dinâmica dirigida pela ocorrência de eventos

Os sistemas a que se referem estes modelos são chamados de SistemasDinâmicos a Eventos Discretos



modelos

estáticos dinâmicos

variantes no tempo invariantes no tempo

lineares não-lineares

estado contínuo

tempo discreto

dirigidos pelo tempo dirigidos por eventos

determinísticos estocásticos

tempo contínuo

estado discreto

Siste

mas

Din

âmico

s a

Even

tos D

iscre

tos



Características dos Sistemas Dinâmicos a Eventos Discretos: •Espaços de estado discretos

•Dinâmica dirigida pela ocorrência de eventos•Sincronismo•Concorrência

As seguintes associações são comuns na literatura:

•Dinâmica Contínua Natureza(existência de leis de conservação)

•Dinâmica Discreta Sistemas construídos pelo Homem(interface com seres humanos, explosão combinatorial)

Níveis de Abstração: •não-temporizado ou lógico•temporizado•temporizado estocástico



A cada nível se associa uma “linguagem”:

e1, e2, e3, ...(e1,t1), (e2,t2), (e3,t3), ...

(e1, p(t1)), (e2, p(t2)), (e3, p(t3)), ...

Formalismospara a modelagem de SED’s constituem representações destas linguagens, caracterizados por:

•destacar as informações estruturais sobre o sistema;

•permitir a manipulação do modelo visando análise (p.ex. verificação)e síntese (p.ex. de controladores).

São formalismos importantes:•autômatos•redes de Petri



Estes formalismos tem em comum representar linguagens pela estrutura de transição de estado (que eventos podem ocorrer num dado estado)

Diferem pela forma como representam os estados

Para o problema de simulação, vamos nos concentrar nos autômatos em suas versões:

♦determinística ♦ temporizada ♦ estocástica

Segundo Yu Chi Ho, são características desejáveis para os modelos para Sistemas a Eventos Discretos:

•Natureza descontínua dos estados;•Natureza contínua das medidas de desempenho;•Importância da formulação probabilística;•Necessidade de análise hierárquica;•Presença de dinâmica;•Realizabilidade do esforço computacional



Classificação dos modelos para SDED’s:

temporizados não temporizados

Lógicos Lógica Temporal; Máq. de Estados Finitos;Redes de Petri Redes de Petritemporizadas

Algébricos Álgebra Min-max Processos FinitamenteRecursivos;Processo de Comunica-ção sequencial

Desempenho Cadeias de Markov;Redes de Filas;GSMP;Simulação

estocásticos determinísticos



chegada de clientes partida de clientesfila servidor

Exemplos:

Sistema de fila simples:

Rede de filas:

Aplicações:CPU + periféricosManufaturaetc.



Nota histórica:

•A História da Engenharia sempre foi marcada pelo paradigma de sistemas contínuos

•Contudo, as equações diferenciais se mostraram insuficientes para a mode-lagem de certos problemas

•Tradicionalmente estes problemas foram tratados através de heurísticas e simulação

•A importância destes problemas aumentou nas últimas décadas

•Cenário hoje se caracteriza por um esforço para o desenvolvimento de ferramentas formais mais adequadas



Segundo Thomas Khun, a História da Ciência é marcada por criação, arti-culação e quebra de paradigmas, após as quais se verifica:•inexistência de consenso;•diversidade de abordagens

A possibilidades com a articulação de novos paradigmas incluem:•consenso;•áreas de pesquisa “irreconciliáveis”

O estudo dos Sistemas Dinâmicos a Eventos Discretos encontra-se na inters-secção de três áreas:•Pesquisa Operacional;•Teoria de Controle;•Teoria de Computação (IA, PLN)

P.O. Controle

Computação



Máquina 1 Máquina 2Buffer

SuprimentoInfinito de Peças Saída de Peças

Consideremos o exemplo simples a seguir:

a = tempo de serviço na máq. 1b = tempo de serviço na máq. 2a > b (o sistema é estável)xn = instante do n-ésimo final de serviço da máquina 1yn = instante do n-ésimo final de serviço da máquina 2x0 e y0 são instantes conhecidos (sem perda de generalidade, pode-se assumir que x0 = 0)



É fácil provar que a "soma" é comutativa e associativa e que o "produto"é distributivo em relação à "soma". Além disso, a soma satisfaz à propri-edade da idempotencia, ou seja, a ⊕ a = a.

x1 = x0 + ax2 = x1 + ay1 = max{y0 + b , x1 + b}

a ⊕ b = max{a,b}a ⊗ b = a + b

Tem-se:

A álgebra max-plus proporciona uma maneira simples de equacionar aevolução do sistema. Define-se:



Em termos matriciais:

⊗

−=

0

1

1

2

y

x

bb

Ha

y

x

onde H é escolhido tal que−H < x1 − y0

Chamando:

−=

= +

bb

HaMe

y

xz

n

1nn

temos:

0n

n02

1201 zMz;zMMzz;Mzz ==== L



Para o cálculo da matriz Mn definimos:

c = a − bJ = H + a

e concluímos que:

Kacc

J0aM ⊗=

−−−

⊗=

Portanto:

nnnn K)na(KaM ⊗=⊗=

−−⊕−−−

=)cJ()nc(c

J0K n

Pode-se mostrar que:



>−

−−−−

<−

−−−

=

Jc)1n(secJc

J0

Jc)1n(sencc

J0

K n

−−−−

==cJc

J0PK n

ou, equivalentemente:

Portanto, para n suficientemente grande:

Observa-se que P é independente de n, o que denota a entrada do sistema em regime permanente.



Fazendo as substituições adequadas, concluímos:

=⊗⊗⊗=

b

azPcomzP)na(z 00n

++

=

= +

bna

a)1n(

y

xz

n

1nn

e, finalmente:

que é a solução em regime previsível.

a a a a a

y0x1 x2 x3 x4 tempo

a

b b b b b

y1 y2 y3y4

x5

y5

x0



Conclusão: alguns fatos devem ser ressaltados:

• A matriz K é periódica (com período 1, mas em geral poderiaser d-periódica)

• Apenas a partir da análise da matriz M de um sistema maiscom-plexo, é possível inferir muitas propriedades do sistema;

• Esta metodologia é muito adequada para o estudo de sistemasonde há sincronismo mas não há concorrência (limitação severa)



Considere-se o exemplo da seção anterior com as seguintes modificações:

•Tamanho do buffer limitado a 1;•Máquina 1 com tempo de serviço exponencialλ;•Máquina 2 com tempo de serviço exponencialµ.

Buffer:Vazio (E)Cheio (F)

Estados admissíveis para cada sub-sistema:

Máqs. 1 e 2:Livre (I)Trabalhando (W)Quebrada (D)



As transições de estado são provocadas pelos seguintes eventos(com respectivos rótulos):•início de trabalho na máq. i : si

•final de trabalho na máq. i : fi

•reparação da máq. i : ri

•quebra da máq. i : bi

Os eventos si e ri podem ser inibidos respectivamente pelos sinais ui e vi.

Diagramas de transição de estado:

E

F

s2

f1

I i

DiWi

f i

si:ui ri:vi

bi

i = 1,2



Objetivos de Controle:

•M1 só pode ser iniciada se B está vazio;•M2 só pode ser iniciada se B está cheio;•M1 não pode ser iniciada quando M2 está quebrada;•Se ambas as máqs. estão quebradas, então M2 deve ser reparada antes.

Estas podem ser vistas como especificações em malha fechada

Estas regras eliminam 6 dos 18 estados possíveis do sistema

Em outras palavras, o controle deve garantir uma limitação no espaço de estados através da habilitação e inibição de ui e vi.



Em malha fechada (i.e. sob ação de controle) o sistema deveráevoluir segundo o diagrama de transição a seguir:



Supondo que o estado completo do sistema é observável, não é difí-cil definir o controlador

Para cada estado, basta decidir quais próximos estados devem ser evitados e inibir a transição correspondente

A tabela a seguir fornece um controlador por realimentação de estado

554321030100estado reduz.

--111--1----v2

0000-1000100u2

110---------v1

--0000101011u1

11109876543210controle/estado



Da tabela anterior, observa-se que para muitos estados a função decontrole é a mesma, sendo possível trabalhar com o conceito deestado reduzido.

Se os estados não são observáveis, mas a sequência de eventos é, a solução é criar uma cópia do sistema, que a partir da sequênciade eventos, produza a sequência de estados correta.

cópia + controle = supervisor

cópia reduzida + controle = supervisor quociente



Sistema Dinâmico

Observador

Estimador de Estado

Cópia do Sistema Dinâmico

Controladorpor Realimentação

de Estado

Controle Estado

x

Medidas

y

EstadoEstimado

Sistema Discreto

Gerador deEventos

Cópia do SistemaDiscreto

Controladorpor Realimentação

de Estado

Controle Estado

x

EventosObservados

EstadoExato

A figura mostra a analogia entre esta abordagem e o controleótimo estocástico LQG:

supervisorquociente



Associando a sequência de eventos à saída do sistema;

Definindo uma coleção de sequências de eventoscom sendo uma linguagem

O problema de controle supervisório é:

• Pode uma dada linguagemser implementada por uma escolha adequadade uma função de controle baseada na observação de uma seq. de eventos?

• Se sim, como?

• Se não, é sempre possível aproximar uma linguagem por outra, a saber aúnica mais abrangente linguagem controlável contida na primeira.

Documents

Sistema : Conceito primitivo (intuitivo) Tentativas de definiçãorafael/ia851/introducao_sed_a.pdf · 2010-03-08 · Modelagem e Controle de Sistemas a Eventos Discretos 1 1. Introdução: