Modelagem e Controle de Sistemas a Eventos Discretos

5/11/2018 Modelagem e Controle de Sistemas a Eventos Discretos - slidepdf.com

http://slidepdf.com/reader/full/modelagem-e-controle-de-sistemas-a-eventos-discretos 1/21

MODELAGEM E CONTROLE DE

SISTEMAS A EVENTOS DISCRETOS

Rafael Santos MendesDCA/FEE/UNICAMP

C.P. 610113.081-970 Campinas SP

1. Introdução

Os objetivos deste artigo são a apresentação e discussão introdutórias sobre ossistemas, modelos e técnicas de controle usualmente encontrados em problemas

de automação da manufatura. Trata-se da abordagem ao problema que consideraos sistemas de automação como sistemas a eventos discretos e busca estabelecerquadros formais adequados para a sua análise e para a síntese de sistemas dedecisão associados. O quadro teórico delineado neste trabalho não se aplicaexclusivamente aos problemas de automação de manufatura, mas a toda umaclasse de sistemas dinâmicos, conforme será caracterizado ao longo do texto.Devido ao emaranhado conceitual, que envolve as discussões sobre sistemasdinâmicos em geral e abordagens alternativas em particular, julgou-seconveniente um esforço de conceituação, o mais amplo possível, de modo a

caracterizar apropriadamente o que venha a ser um sistema a eventos discretos.Por outro lado o texto se limita a apresentar de maneira introdutória dois dosmodelos para o problema encontrados na literatura, não havendo a intenção de seesgotar nenhum deles. De fato o número de artigos e trabalhos realizados sobreestes e outros modelos é excepcionalmente grande, apesar de seu adventorecente, e uma análise compreensiva e razoavelmente profunda de algum delesestaria fora do escopo deste trabalho.

Do ponto de vista dos Sistemas de Manufatura Integrados por Computador (CIM)

é importante ressaltar que constituem sistemas complexos e que algumas de suaspartes são sistemas a eventos discretos. Ora, o fato de não se conhecer até omomento uma descrição formal definitiva para estes sistemas permite concluir queos resultados das pesquisas em sistemas a eventos discretos terão granderepercussão no estudo e implementação de sistemas CIM. Obviamente estedesenvolvimento não é uma condição sine qua non para o avanço de sistemasCIM, existindo abordagens alternativas para o problema tais como o uso daInteligência Artificial, Simulação e outros.

A História da Engenharia sempre foi marcada pelo paradigma de sistemascontínuos (a serem devidamente caracterizados na seção seguinte). Estes modelos



formais, oriundos do estudo da Física, permeiam quase totalmente a formação dosengenheiros, havendo raras incursões sistemáticas a outras classes de dinâmicadurante os cursos de graduação, principalmente por não haver para estes, como severá, quadros teóricos largamente aceitos pelos pesquisadores. Contudo as

equações diferenciais se mostraram inadequadas para alguns problemas.Particularmente, os sistemas cuja dinâmica qualificar-se-á posteriormente comodiscreta, e que aparecem fartamente na engenharia, resistem a qualquermodelagem pela via das equações diferenciais (ou a diferenças). Entretanto, suaexistência e relevância cada vez maior levaram ao desenvolvimento de técnicas deanálise, mesmo na ausência de um quadro teórico satisfatório. Assim,tradicionalmente estes sistemas foram tratados através de heurísticas e simulação.Recentemente com a sofisticação das plantas industriais, das redes decomunicação e dos sistemas computacionais, estes problemas adquiriram

importância ainda maior, conduzindo a um grande esforço teórico para odesenvolvimento de ferramentas formais mais adequadas. Este estudo encontra-sena confluência de tres áreas: a Pesquisa Operacional, a Teoria de Controle e aTeoria de Computação (IA, PLN) (Ho, 1989). Como consequência destapluraridade de origens e do pouco tempo de existência, tem-se um quadro atualbem distante de uma desejável situação de unificação. Observa-se um grandenúmero de abordagens, algumas delas com ferramentais e linguagens bemdiferenciados. Esta multiplicidade, embora dispersiva, denota uma área depesquisa vigorosa que se propõe a responder questões intelectualmente excitantes

e de grande importância prática.

Boa parte do material deste texto (em particular as seções 4 e 5) foi extraída dealguns artigos tutoriais cuja leitura direta é recomendada. Em particular sãointeressantes os artigos de Ho (1989), Cao e Ho (1990), Cohen et al (1989) e olivro de Cassandras (1993). Na seção 2 deste artigo procura-se estabelecer deforma sólida alguns conceitos que, embora usuais em muitas teorias, podem darmargem a dúvidas. Passa-se então na seção 3 a uma classificação, enumeração ediscussão dos tipos de modelos hoje existentes para a descrição dos sistemas a

eventos discretos. Na seção 4 faz-se uma tentativa, seguindo Cao e Ho (1990), dese introduzir uma abordagem algébrica, a saber aquela baseada na álgebra Max-Plus. Um exemplo simples é apresentado, desenvolvendo-se para ele um modelo eanalisando-se alguns de seus aspectos. Finalmente, na seção 5, ainda segundo Caoe Ho (1990), introduz-se um modelo lógico seguindo o mesmo príncipio da seçãoanterior. O modelo escolhido é aquele conhecido como Controle Supervisório ouabordagem Ramadge-Wonham numa referência a seus iniciadores.



2. Conceitos Gerais

Neste trabalho, pretende-se apresentar, de uma maneira genérica, conceitos ediscussões relativos ao problema de modelagem e controle de Sistemas a Eventos

Discretos. Devido ao caráter interdisciplinar desta matéria, e considerando querecentemente estas discussões assumiram uma nova dimensão, é interessante quese revisite alguns conceitos básicos, de modo a resituá-los no novo contexto. Estarevisão é feita nesta seção.

Sistema:

O conceito de sistema é um conceito primitivo (intuitivo) que permeia todadiscussão científica, estando fora do escopo deste trabalho uma discussão mais

profunda sobre o tema. Contudo, por completude, cabe relacionar as seguintestentativas de definição (Cassandras, 1993):

"Agregação ou montagem de coisas, combinadas pelo homem ou pela natureza demodo a formar um todo unificado"

"Grupo de itens interdependentes ou interagindo regularmente formando um todounificado"

"Combinação de componentes que agem em conjunto para desempenhar umafunção que se torna impossível na ausência de qualquer das partes"

Sistema Dinâmico:

Sistema que evolui ao longo do tempo, sendo que em geral seu comportamentodepende do passado. Em oposição, encontram-se os sistemas estáticos, cujocomportamento depende exclusivamente de sua situação no instante considerado.

Modelo:O estudo de um sistema, qualquer que seja, se dá pela constituição de um modelo,definido como um dispositivo que de alguma maneira descreve o comportamentode um sistema. Em geral definimos para o modelo varáveis de entrada e variáveisde saída, esperando-se dele estabelecer relações entre estas variáveis

Do ponto de vista da engenharia, é interessante classificar os modelos da seguinteforma (Soares, 1990):

Físicos ou MatemáticosEstáticos ou Dinâmicos



Lineares ou não-linearesAnalíticos ou Numéricos

Por modelo físico entende-se a construção de um outro sistema, de fácil

manipulação, cujo comportamento é análogo ao do sistema em estudo. Casostípicos são as maquetes e os computadores analógicos. O modelo matemáticoestabelece equações relacionando as grandezas do sistema, de modo a permitirprevisões de comportamento em situações diversas. Como exemplo absolutamentefamiliar aos engenheiros pode-se citar as equações diferenciais como modelo parasistemas dinâmicos. A distinção entre modelo estático ou dinâmico é análoga àestabelecida anteriormente para sistemas. Nos modelos estáticos, as variáveis desaída dependem exclusivamente das variáveis de entrada, ao passo que nosmodelos dinâmicos há também a dependência dos valores passados das variáveis

do sistema. A distinção entre modelos lineares e não-lineares é feita através daidéia de superposição. Se a superposição de duas entradas leva o modelo aapresentar uma saída que é também uma superposição das saídas correspondentesàs entradas aplicadas separadamente, então o modelo é linear. Caso contrário omodelo é não-linear. Finalmente, pode-se distinguir entre modelos numéricos, quesão capazes de reproduzir o comportamento dos sistemas através de modelossimples, e.g. simuladores implementados em computadores digitais, e modelosanalíticos, que representam de maneira abstrata e sintética (em geral através deequações) as relações entre as variáveis do sistema.

No estudo de sistemas a eventos discretos são importantes os modelosmatemáticos e dinâmicos capazes de descrever sistemas lineares ou não. Emboranesta área o conhecimento disponível até o momento seja privilegiadamentenumérico, há um grande esforço da comunidade científica no sentido de sedesenvolver modelos analíticos. Nas seções 4 e 5 deste trabalho são esboçadosexemplos de modelos analíticos atualmente em estudo sendo representativos dasabordagens consideradas atualmente.

Estado:O conceito de estado é fundamental para o estudo de sistemas dinâmicos. De umamaneira genérica, constitui a informação necessária para se conhecer o valorfuturo das variáveis do modelo, desde que se conheçam as entradas. Estadefinição, embora qualitativa, é a mais conveniente para o estado. Outrasdefinições de natureza mais quantitativa mostram-se excessivamente restritivas ouaplicáveis a sistemas muito particulares. Um exemplo de tal particularização é atentativa de definir estado como sendo associado aos acumuladores de energia dosistema. Esta definição, embora conveniente para a descrição de sistemas

mecânicos, elétricos e outros de natureza contínua, não é adequada para ossistemas abordados neste trabalho. Conforme ver-se-á posteriormente, a



informação correspondente ao estado num sistema a eventos discretos pode ser denatureza muito variada podendo se constituir por exemplo simultaneamente denúmeros inteiros, números reais e variáveis booleanas, não tendo de maneira geralnenhuma relação com o conceito de energia.

Para ilustrar o conceito de estado num sistema contínuo, pode-se citar o caso deum circuito elétrico simples constituído de uma fonte de tensão, um resistor e umcapacitor ligados em série (circuito RC). Neste circuito o estado está obviamenteassociado à tensão no capacitor, que por sua vez está diretamente ligada à energiaacumulada no seu campo elétrico. Note-se que para se conhecer o comportamentodo circuito em qualquer instante, basta conhecer a evolução da fonte de tensão e ovalor da tensão no capacitor em algum instante.

Dentro do contexto da teoria de controle, é comum que se represente um sistemaatravés do esquema da figura 1. Esta representação contém os principaiselementos de representação de um sistema dinâmico, a saber, as variáveis deentrada, de saída e de estado, além da equação que descreve a evolução dinâmicado estado. Note-se que a representação ilustrada é conveniente para um sistemaque mais tarde será definido como sistema a dinâmica contínua. Num contextomais genérico, a representação do estado e suas relações dinâmicas podem não seradequadamente modeladas por uma equação diferencial (ou mesmo a diferenças) eeste fato determina uma ruptura entre os modelos utilizados para a descrição dos

sistemas contínuos e discretos.

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

Figura 1 - Representação de um Sistema Dinâmico

Controle:Outro conceito importante no contexto deste trabalho é o de controle.Genéricamente, trata-se da decisão sobre as variáveis de entrada de um sistema demodo que as variáveis de saída e/ou estado realizem determinado comportamento.A definição das estratégias de decisão, de critérios para avaliação de desempenho,e o estudo das técnicas de síntese dos esquemas de decisão constituem o objeto daTeoria de Controle. Para os sistemas que interessam ao contexto deste trabalho,

este é um problema sem resultados definitivos. A ausência de um paradigma demodelo constitui uma barreira para este avanço.



Pode-se classificar as estratégias de controle em dois grandes grupos; controle emmalha aberta e controle em malha fechada. O que as diferencia é o fato de seutilizar ou não a informação das variáveis de estado e/ou de saída no cálculo da

variável de entrada. As figuras 2 e 3 ilustram estas estratégias.

u(t)

dx = f(x,u,t)dt

Sistema

y = g(x,u,t)

u(t)= h(r,t)

r(t)

Controle

Figura 2 - Controle em Malha Aberta

u(t)

dx = f(x,u,t)dt

Sistema

y = g(x,u,t)

u(t)= h(r,x,t)

r(t)

Controle

Figura 3 - Controle em Malha Fechada

Dinâmica ContínuaTodos os exemplos citados anteriormente são típicamente sistemas com dinâmicacontínua. São caracterizados por apresentarem variáveis de estado contínuas,serem dirigidos pelo tempo (ou seja, o passar do tempo determina a evolução dadinâmica do sistema) e terem sua dinâmica descritível por relações algébricasentre suas variáveis e respectivas derivadas sendo portanto passíveis de descriçãopor Equações Diferenciais ou Equações a Diferenças (quando o tempo fordiscretizado). Desde sua invenção o Cálculo Diferencial tornou-se um dos maisbem sucedidos exemplos de paradigma na história da Ciência. De fato,virtualmente todos os modelos dinâmicos conhecidos e manipulados pela grandemaioria dos engenheiros são fundamentados nestes modelos e sua eficiência paraum grande número de problemas é incontestável. Contudo, existem sistemas que

não se enquadram neste contexto teórico, constituindo o que se convencionou



chamar de sistemas discretos ou sistemas dinâmicos a eventos discretos. São eleso objeto deste estudo.

Dinâmica Discreta (ou Sistemas a Eventos Discretos)

Em oposição aos sistemas contínuos pode-se considerar os Sistemas a DinâmicaDiscreta ou Sistemas a Eventos Discretos ou ainda Sistemas Discretos. Sãocaracterizados por apresentarem variáveis de estado discretas, serem dirigidos a Eventos e não serem descritíveis por equações diferenciais (ou a diferenças) (Ho,1989; Cassandras, 1993). A rigor, a primeira condição relacionada acima nãocaracteriza propriamente um sistema discreto, visto que sua inobservância nãoimpede que um sistema apresente dinâmica discreta. Contudo na maioria doscasos estudados na Engenharia esta característica está presente. O segundo ponto

é talvez o mais importante da caracterização dos sistemas discretos. Sua dinâmicaé dirigida a eventos, ou seja, o que determina a evolução do sistema é a ocorrênciade eventos e não simplesmente o passar do tempo. É óbvio que, embora o tempocontinue sendo um parâmetro importante na caracterização da dinâmica dosistema, ele agora não é tão determinante, havendo inclusive, como veremos aseguir, modelos para sistemas discretizados não temporizados.

Um exemplo simples é o sistema de estocagem representado na figura 4. Nestecaso, observe-se que o estado do sistema, dado pelo número de itens estocados,

varia discretamente e só é alterado quando há a ocorrência de um dos dois tiposde eventos possíveis neste sistema: chegada ou saída de um item.

u1(t)

u2(t)

x(t)Chegada de

produtos

Saída deprodutos

876543210

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 t

x(t)

Figura 4 - Sistema de Estocagem



Este exemplo permite compreender o fato de os sistemas discretos serem dirigidosa eventos. Contudo, há outros aspectos que, embora não estejam presentes neste

sistema, também fazem parte de uma descrição mais ampla dos sistemas discretos.Considere-se a representação, dada na figura 5, de uma fila simples. Estarepresentação, consagrada nos textos de Teoria de Filas, é também convenientepara o sistema de estocagem da figura 4 se se considerar os parâmetros adequadose pode ser utilizada para um grande número de sistemas discretos. Basicamente,uma fila simples é formada por um conjunto de servidores e clientes, sendocaracterizada por quatro parâmetros (Soares, 1990):• disciplina de chegada dos clientes• disciplina de serviço do servidor

• número de servidores presentes• capacidade de armazenamento da fila.

Fila Servidor

Saída deClientes

Chegada deClientes

Figura 5 - Sistema de Fila Simples

Considere-se agora a conexão de algumas filas simples, constituindo a rede defilas representada na figura 6. Pode-se observar que alguns aspectos ausentes nossistemas das figuras 4 e 5 aparecem neste sistema. É possível através desteexemplo, ilustrar o conceito de concorrência, se se imaginar que as duas filasassociadas ao servidor 1 concorrem para utilizá-lo. Pode-se também compreendero conceito de sincronismo, supondo-se que um servidor necessita de mais de umcliente oriundos de outros servidores para realizar seu processamento (Baccelli et

al., 1992). Um caso típico é encontrado em sistemas de manufatura, ondefrequentemente a montagem de uma peça depende do processamento prévio deduas ou mais de suas partes constituintes.



1

2

3

4

5

Figura 6 - Rede de Filas

Podemos finalmente relacionar algumas características que, de maneira essencialou acessória, encontram-se presentes nos sistemas discretos:• estado discreto• sincronismo• concorrência• dinâmica dirigida a eventos

É importante ressaltar que parte dos sistemas de interesse em Engenhariaapresenta os elementos acima descritos e desafortunadamente não podem serdescritos pelos métodos tradicionais utilizando equações diferenciais. Torna-seassim de fundamental importância a construção de ferramentas teóricas para suaanálise e para a síntese de procedimentos de decisão relativos ao seu controle.

Evento:Na análise dos sistemas a dinâmica discreta é de fundamental importância oconceito de evento. Embora sua conceituação tenha sido implicitamente abordadanas discussões precedentes, é conveniente explicitá-la. Um evento é por definiçãoum acontecimento sem duração temporal que altera o estado do sistema. Pode serprogramado por outro evento ou aleatoriamente, e, num mesmo sistema, é possívelhaver vários tipos de evento. Esta multiplicidade de tipos e causas de eventos éque, em geral, leva um sistema discreto a apresentar grande complexidade. Numsistema com dinâmica discreta o estado só se altera pela ocorrência de um evento.

Pode-se agora, seguindo Cassandras (1993), propor a classificação dos modelosde sistemas um pouco mais completa delineada na figura 7.



SISTEMAS

ESTÁTICOS DINÂMICOS

INV. NO TEMPO VAR. NO TEMPO

LINEARES Ñ-LINEARES

ESTADO CONT. ESTADO DISCR.

DIRIG. TEMPO DIRIG. EVENTO

DETERMIN. ESTOCÁST.

TEMPO DISCR. TEMPO CONT.

Sistemas Dinâmicos aEventos Discretos

Figura 7 - Classificação dos Modelos de Sistemas

É importante mais uma vez ressaltar o grande número de áreas da Engenhariacujos objetos de estudo podem ser classificados com sistemas a eventos discretos.

Sem a pretensão de exaurir a lista de aplicações, são apresentados nas figuras 8 e9 exemplos de sistemas de grande importância atual que podem se incluir entreelas.

D1

D2

CPU

Chegada de Jobs

Saída de Jobs

Figura 8 - Exemplo: Um modelo de Filas para um Sistema de Computação

1

Chegada de Peças

2

Saída de Peças

Figura 9 - -Exemplo: Um Sistema de Manufatura



Em relação às comparações entre sistemas a dinâmica contínua e discreta, éinteressante citar a distinção proposta por Ho (1989) na qual os sistemas adinâmica contínua são associados à Natureza, onde existem leis de conservação, eos sistemas a dinâmica discreta aos sistemas construídos pelo Homem,

caracterizados pela ausência de leis de conservação, interface com seres humanose explosão combinatorial. Resta portanto a excitante e intrigante questão sobre apossibilidade de se obter um dia um quadro teórico unificador para a descriçãodos sistemas dinâmicos.

3. Modelos

Conforme discutido na introdução deste trabalho, a décadas os sistemas discretos

são conhecidos dos engenheiros e seu estudo, embora restrito a alguns aspectos, éigualmente antigo. Assim, os problemas práticos tem sido manipulados através douso intensivo de simulação, das técnicas da Pesquisa Operacional e, maisrecentemente, através de técnicas da Inteligência Artificial. Desde a década de 80,tem-se observado um esforço da comunidade científica no sentido de estabeleceruma teoria mais consistente para estes sistemas. Esta teoria deve permitir a análisedos sistemas, tais como previsibilidade dos comportamentos dinâmicos, permitir odesenvolvimento de técnicas de síntese de controladores e ainda lidaradequadamente com a complexidade dos sistemas encontrados na prática. Ho

(1989) propõe um conjunto de características para os modelos a seremdesenvolvidos, em função dos aspectos práticos que eles devem atender:• 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

Até o presente, entretanto, nenhum modelo proposto na literatura reúne todas estascaracterísticas. O que há é um grande número de linhas teóricas concorrentes cadauma delas descrevendo adequadamente alguns aspectos (e sendo portanto útil emalgumas aplicações), mas sendo insuficiente em relação a outros. Näo háparadigma. Esta é uma situação similar àquela classificada por Kuhn (1962) comorevolucionária no desenvolvimento de uma teoria científica, dela podendo adviruma situação caracterizada pela síntese das correntes competidoras ou umasituação de ruptura de áreas de conhecimento. Em qualquer caso entrar-se-ia noque Kuhn chama de período regular caracterizado pela existência de umparadigma e no qual a principal função dos pesquisadores é articulá-lo.



De uma maneira geral, os modelos existentes podem ser classificados segundoalgumas características, descritas a seguir

Temporizados:

Levam em conta o tempo de permanência nos estados.

Não-temporizados:Interessam-se apenas pela sequência de estados.

Lógicos:Analisam o comportamento lógico do sistema, respondendo a questõesqualitativas. Em geral se preocupam com a estrutura lógica da evolução dinâmicado sistema. Podem ou não utilizar como ferramenta formal alguma sistema lógico

(em geral não-clássico) havendo alguns modelos baseados em lógica temporal.

Algébricos:Descrição através de equações algébricas, ou seja, buscam a obtenção de modelospara os sistemas discretos com as propriedade de síntese características dosmodelos algébricos.

Análise de Desempenho:Tentam responder questões relacionadas ao desempenho (em geral temporizados).

A maioria dos modelos mais antigos para sistema discretos, ou seja, aquelesbaseados em simulação e em Teoria de Filas podem ser classificados destamaneira.

A tabela 1 a seguir, proposta por Ho (1989), apresenta um resumo dos modelosexistentes e os classifica segundo os critérios acima:

Temporizados Não Temporizados

Lógicos Lógica TemporalRêdes de Petri Temporizadas Máquinas de Estados FinitosRêdes de Petri

AlgébricosÁlgebra Min-Max Processos Finitamente Rcursivos

Processos de Comunicação Sequencial

DesempenhoCadeias de Markov

Rêdes de FilasGSMPSimulação

Tabela 1 - Alguns Modelos Existentes para Sistemas Discretos



Nas próximas duas seções serão introduzidas, através de um mesmo exemplosimples, duas das mais promissoras abordagens citadas acima. São elas a

abordagem baseada na álgebra max-plus (cuja caracterização será esboçada napróxima seção) e aquela denominada controle supervisório (delineada na seção 5).Ambos os exemplos foram propostos originalmente por Cao e Ho (1990), sendoextremamente didáticos. Apesar de haver um número razoável de outrasabordagens também merecedoras de atenção, considerou-se que estas duasexemplificam adequadamente os tratamentos dados ao problema.

4. Modelo Algébrico

O modelo apresentado nesta seção, originou-se dos trabalhos de Cuninghame-Green (1979), e foi fortemente desenvolvido por Cohen e seu grupo (Cohen et al,1989). A apresentação feita a seguir utiliza uma instanciação (a álgebra max-plus)de uma estrutura algébrica mais geral denominada Dióide. Em Baccelli et al.(1992), há uma apresentação compreensiva da questão, bem como aplicações, nomesmo problema, de outras instâncias da estrutura citada.

Consideremos o exemplo simples de uma célula de manufatura com duas

máquinas e um buffer intermediário representado na figura 10 a seguir:

Máquina 1 Máquina 2Buffer

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

Figura 10 - Célula com duas Máquinas

Sejam os seguintes parâmetros associados ao sistema:a = tempo de serviço na máq. 1b = tempo de serviço na máq. 2xn = 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 quex0 = 0)



Obviamente, se a > b o sistema é estável, no sentido em que o número de peças nobuffer não cresce indefinidamente.

Tem-se:

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

A álgebra max-plus proporciona uma maneira simples de equacionar a evoluçãodo sistema. Define-se:

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

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

Considerando que a expressão matricial a seguir é escrita segundo estas novasdefinições de soma e produto, temos:

x2

y1=

a -H

b b

x1

y0

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

Chamando:

zn =

xn+1

yne M =

a -H

b b

tem-se:

z1 = Mz0 ; z2 = Mz1 = M

2

z0

portanto:

zn = Mn

z0

Para o cálculo da matriz Mn, define-se:

c = a - bJ = H + a

e conclui-se que:



M = a ⊗

0 -J

-c -c= a ⊗ K

Portanto:

Mn = an ⊗ Kn = (na) ⊗ Kn

Pode-se mostrar que:

Kn

=

0 -J

-c -nc⊕-J-c

ou equivalentemente:

0 -J

-c -ncse (n-1)c < J

Kn

=

0 -J

-c -J-cse (n-1)c > J

Portanto, para n suficientemente grande:

Kn = P =

0 -J

-c -J-c

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

Substituindo os valores adequados, concluímos que:

zn = (na) ⊗ P z0

P z0 =

a

be, finalmente:

zn =

xn+1

yn=

(n+1)a

na+b

que é a solução (previsível intuitivamente) em regime permanente.

Em conclusão, alguns fatos devem ser ressaltados:



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

• Apenas a partir da análise da matriz M de um sistema mais complexo, épossível inferir muitas propriedades do sistema. Pode-se por exemplo definir umauto-valor para esta matriz, obviamente com significado diferente daqueleutilizado em álgebra linear. Neste caso, o auto-valor da matriz está relacionadocom o período do sistema.

• Esta metodologia é muita adequada para o estudo de sistemas onde hásincronismo mas não há concorrência. Esta limitação é severa, no que diz respeitoàs aplicações e constitui, sem dúvida, a principal limitação desta abordagem.

• É importante ressaltar por outro lado os desdobramentos desta teoria porexemplo no que diz respeito aos aspectos estocásticos dos sistemas a eventosdiscretos. A esse respeito pode-se consultar o trabalho de Olsder et al. (1990).

5. Controle Supervisório

A abordagem conhecida como controle supervisório foi originalmente proposta

por Ramadge e Wonham (1989) e por este motivo também é conhecida comoabordagem R-W. Constitui-se uma das poucas abordagens em que existempropostas de técnicas de síntese de controladores e é baseada em teoria deautomâtos e linguagens. Uma visão ampla da teoria envolvida é dada porCassandras (1993).

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, µ

O sistema proposto é composto por tres sub-sistemas (duas máquinas e o buffer) eos estados admissíveis para cada sub-sistema são:• Máqs. 1 e 2:

Livre (I)Trabalhando(W)Quebrada(D)



• Buffer:Vazio (E)Cheio (F)

A extensão do espaço de estados do sistema é finita e é dada por todas ascombinações possíveis de estados dos tres sub-sistemas.

As transições de estado são provocadas pelos seguintes eventos (com respectivosrótulos):• início de trabalho na máq. i : si• final de trabalho na máq. i : f i• reparação da máq. i : ri• quebra da máq. i : bi

Vai-se supor que os eventos si e ri podem ser inibidos respectivamente pelossinais ui e vi que serão considerados como sendo as variáveis de controle dosistema.

Na figura 11 é apresentado o diagrama de transição de estados do sistemaproposto:

Ii

Di

si:ui

f i

ri:vi s2

f 1

F

Figura 11 - Diagrama de Transição de Estados

Supõe-se finalmente, que os objetivos de controle são dados pelas especificaçõesa seguir:• M1 só é autorizada a iniciar o trabalho se B está vazio• M2 só pode iniciar se B está cheia• M1 não pode iniciar quando M2 está quebrada• Se ambas as máqs. estão quebradas então M2 deve ser reparada antes



Estas regras eliminam 6 dos 18 estados possíveis do sistema e equivalem aespecificações em malha fechada na teoria de controle. Em outras palavras, ocontrole deve garantir uma limitação no espaço de estados (habilitando ouinibindo as quatro variáveis ui e vi)

Em malha fechada, (sob a ação do controle) o sistema deverá evoluir segundo odiagrama de transição a seguir:

0 4

101 2

3

11 9 8

7

6

5

r2

f2

s1r1

b1

f1

f2r2

s2

r2f2

b2

s1

f1

b2

b1

b2

f1b1

b2

r2f2

Estado 0 1 2 3 4 5 6 7 8 9 10 11M1 I W I I I W I I W D D DB E E F E E E F F E E E E

M2 I I I W D W W D D D I W

Figura 12 - Digrama para o Sistema em Malha Fechada

Supondo que o estado completo do sistema é observável, não é difícil definir a leide controle. Para cada estado, basta decidir quais próximos estados devem serevitados e inibir a transição correspondente. Para este sistema simples esteprocedimento pode ser feito diretamente e a tabela 2 a seguir dá um controladorpor realimentação de estado:



Controle/estado 0 1 2 3 4 5 6 7 8 9 10 11u1 1 1 0 1 0 1 0 0 0 0 - -

v1 - - - - - - - - - 0 1 1

u2 0 0 1 0 0 0 1 - 0 0 0 0

v2 - - - - 1 - - 1 1 1 - -

Estado Reduz. 0 0 1 0 3 0 1 2 3 4 5 5Legenda: 1 = habilitado; 0 = desabilitado; - = irrelevante

Tabela 2 - Definição do Controlador

Da tabela anterior, observa-se que para muitos estados a função de controle é amesma, sendo possível trabalhar com o conceito de estado reduzido.

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

O controle então é exercido da seguinte maneira. Os eventos observados são lidospela "cópia" do sistema que gera então uma sequência de estados. Esta "cópia"pode ou não ser a do sistema reduzido. Em seguida esta sequência de estados(reduzidos ou não) é enviada ao controlador que gera os sinais de controleadequados. É usual a adoção da seguinte nomenclatura:

cópia + controle = supervisor

cópia reduzida + controle = supervisor quociente

Pode-se observar a gra;nde analogia que existe entre os conceitos aqui propostos eaqueles da teoria de controle tradicional. A chamada "cópia" do sistema cumpreclaramente o papel que os observadores de estado cumprem no quadro clássico eo que se chamou aqui de controlador reproduz a função da realimentação deestado. A figura 13 mostra a analogia entre esta abordagem e o controle ótimoestocástico LQG:



SistemaDinâmico

Observador

Estimador deEstado

Cópia do SistemaDinâmico

Controladorpor Realimentação

de Estado

Controle Estado

x

Medidas

y

EstadoEstimado

SistemaDiscreto

Gerador deEventos

Cópia do SistemaDiscreto

Controladorpor Realimentação

de Estado

Controle Estado

x

EventosObservados

EstadoExato

Figura 13 - Analogia com o Controle LQG

Embora este exemplo seja de grande simplicidade, ele permite vislumbrar aproblemática central do controle supervisório. Associando-se uma sequência deeventos à saída do sistema e definindo uma coleção de sequência de eventos comosendo uma linguagem, pergunta-se:

• Pode uma dada linguagem ser implementada por uma escolha adequada deuma função de controle baseada na observação de uma sequência de eventos desaída ?

• 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



6. Referências Bibliográficas

F. Baccelli, Cohen, G., Olsder, G.J., Quadrat, J.P. (1992) - "Synchronization andLinearity - An Algebra for Discrete Event Systems" - John Wiley and Sons Eds.

X.-R. Cao, Ho, Y.-C. (1990) - Models of Discrete Event Dynamic Systems -IEEE Control Systems Magazine, junho, pg. 69.

C. Cassandras, (1993) - "Discrete Event Systems - Modeling and PerformanceAnalysis" - Aksen Associates.

G. Cohen, Moller, P., Quadrat, J.P., Viot, M. (1989) - Algebraic Tools for thePerformance Evaluation of Discrete Event Systems - Proceedings of IEEE, vol.

77, n°1, pg.39.

R.A. Cuninghame-Green. (1979) - "Minimax Algebra" - Lecture Notes inEconomics and Mathematical Systems, n° 166, Springer-Verlag.

Y.-C. Ho, (1989) - Dynamics of Discrete Event Systems - Proceedings of IEEE,vol. 77, n°1, pg.3.

G.J. Olsder, Resing, J.A.C., De Vries, R.E., Keane, M.S. e Hooghiemstra, G.(1990) - Discrete Event Systems with Stochastic Processing Times - IEEE-Transactions on AC, vol.35, n°3, pg.299.

L.F.G. Soares, (1990) - “Modelagem e Simulação Discreta de Sistemas” - VIIEscola de Computação - IME/USP - São Paulo.

T.S. Kuhn, (1962) - "A Estrutura das Revoluções Científicas"- Tradução de B.V.Boeira e N.F. Boeira - Ed. Perspectiva (Col. Debates) 1975 - São Paulo.

P.J.G. Ramadge, Wonham, W.M. (1989) - The Control of Discrete Event Systems- Proceedings of IEEE, vol. 77, n°1, pg.81.

Documents

Modelagem e Controle de Sistemas a Eventos Discretos