Teoria de Controle Supervisório

Teoria de Controle Supervisório

(Parte 1 de 8)

V Simposio Brasileiro de Automacao Inteligente

Teoria de Controle Supervisorio de Sistemas a Eventos Discretos

Prof. Jose Eduardo Ribeiro Cury

Universidade Federal de Santa Catarina Departamento de Automacao e Sistemas cury@das.ufsc.br

Canela-RS, Novembro de 2001

Agradecimentos

Esta apostila foi elaborada a partir da minha experiencia como professor, orientador e pesquisador na area de Sistemas a Eventos Discretos e Sistemas Hıbridos, nos ultimos dez anos, inicialmente no Departamento de Engenharia Eletrica e mais recentemente no Departamento de Automacao e Sistemas da Universidade Federal de Santa Catarina. Ela nao poderia ter sido realizada sem o apoio direto ou indireto de todos os meus alunos de Graduacao e Pos Graduacao e orientados de Mestrado e Doutorado. Partes do documento devem inclusive ser creditadas a documentos que foram elaborados por estes. Neste sentido, agradeco a todos estes alunos, alguns hoje colegas de profissao, em particular ao Antonio, Cesar, Jose Miguel, Max, Tati e Ziller, de quem “roubei”ideias, paragrafos e/ou figuras.

Sumario

1 Introducao 7

2.1 Definicao e Caracterısticas9
2.2 Exemplos de Sistemas a Eventos Discretos12

2 Sistemas a Eventos Discretos 9

3.1 Linha de Producao de Cervejas20
3.2 Consideracoes acerca da Resolucao do Problema23
3.3 Conclusao24

3 Um Problema Motivador 20

4.1 Notacao e definicoes basicas25
4.2 Operacoes sobre linguagens26
4.3 Representacao de SEDs por linguagens27
4.4 Expressoes Regulares29
4.5 Conclusao31

4 Linguagens como modelos para SEDs 25

5.1 Automatos Determinısticos de Estados Finitos32
5.2 Linguagens representadas por automatos34
5.3 Linguagens Regulares e Automatos de Estados Finitos35
5.4 Acessibilidade e co-acessibilidade de um ADEF36
5.5 Bloqueio num SED37
5.6 Automatos nao determinısticos40
5.7 Determinizacao de um ANDEF41
5.8 Minimizacao de automatos42
5.9 Composicao de Automatos43

Sumario 4

6.1 Introducao48
6.2 O problema de controle49
6.3 Controlabilidade e Solucao do PCS51
6.4 Conclusao52

6 Controle Supervisorio de SEDs 48

7.1 Obtencao de um modelo para a planta53
7.2 Obtencao de um modelo para a especificacao5
7.3 Sıntese do supervisor nao bloqueante otimo58
7.3.1 Definicao de maus estados58
7.4 Implementacao / Realizacao do supervisor59
7.5 Exemplos61
7.6 Consideracoes sobre a resolucao do PCS6
7.6.1 Complexidade Computacional67
7.6.2 Legibilidade/estruturacao67
7.6.3 Ferramentas68
7.7 Conclusao68

7 Metodologia para a sıntese de supervisores otimos 53

8.1 Referencias69
A.1 Introducao71
A.2 FM — Maquinas de estado finitas71
A.3 Exemplo72
A.4 Utilizacao do Grail76

A Resumo Ferramenta Grail 71 9 Referencias Bibliograficas 71

2.1 Trajetoria tıpica de um sistema a eventos discretos10
2.2 Trajetoria tıpica de um sistema dinamico com variaveis contınuas1
2.3 Filas13
2.4 Redes de Filas14
2.5 Sistema de Computacao15
2.6 Linha de Transferencia17
2.7 Sistema de Trafego18
3.1 Estacao de envasilhamento21
4.1 Sistema robo-esteira29
5.1 Automato determinıstico3
5.2 Exemplo de automato35
5.3 Problema fila infinita35
5.4 Automato fila infinita36
5.5 SED nao bloqueante38
5.6 SED com bloqueio38
5.7 Sistema usuario-recurso40
5.8 Automato para Lm(G) = (a + b)∗ab40
5.9 Automato determinıstico42
5.10 Automato que detecta sequencia 12343
5.1 Automato mınimo que detecta sequencia 1234
5.12 Automato sistema usuario-recurso4
5.13 Modelo usuario US145
5.14 Modelo usuario US245
5.15 Restricao recurso R145
5.16 Restricao recurso R246
6.1 SED em malha fechada49
7.1 Automatos para Gi, i = 0,, 4. . . . . . . . . . . . . . . . . . . . . . . . . 54
7.2 Linha de transferencia5
7.3 Modelo das maquinas M1 e M25
7.4 Modelo da planta56
7.5 Especificacao de nao overflow e nao underflow do buffer57
7.6 Automato para E58
7.7 Automatos G e C = ‖Ei59
7.8 Automato R = G‖C59
7.9 Automato G (exercıcio 7.1)60
7.10 Maxima linguagem controlavel60
7.1 Modelo das maquinas com quebra M1 e M261
7.12 Nao overflow e underflow do armazem, e prioridade de reparo de M262
7.13 Maxima linguagem controlavel62
7.14 Linha de transferencia62
7.15 Modelo dos componentes do sistema63

Lista de Figuras 6

B263
7.17 Lei de controle otima para a linha com retrabalho63
7.18 Sistema AGV64
7.19 Modelo das maquinas M1 e M264
7.20 Modelo do AGV64
7.21 Modelo de M1||M265
7.2 Modelo de M1||M2||AGV65
7.23 Restricao E16
7.24 Automato para E6
7.25 Automato para sup C(E)67
A.1 Maquina de estados finitos72
A.2 Pequena fabrica72
A.3 Modelo maquina 174
A.4 Modelo maquina 274

Capıtulo 1 Introducao

A tecnologia moderna tem produzido, em escala crescente, sistemas com a finalidade de executar tarefas que, seja pela importancia que adquirem em seu contexto, seja por sua complexidade e seu custo, justificam o esforco despendido na sua otimizacao e automacao. Tais sistemas estao presentes em uma serie de aplicacoes, incluindo por exemplo a automacao da manufatura, a robotica, a supervisao de trafego, a logıstica (canalizacao e armazenamento de produtos, organizacao e prestacao de servicos), sistemas operacionais, redes de comunicacao de computadores, concepcao de software, gerenciamento de bases de dados e otimizacao de processos distribuıdos. Tais sistemas tem em comum a maneira pela qual percebem as ocorrencias no ambiente a sua volta, o que se da pela recepcao de estımulos, denominados eventos. Sao exemplos de eventos o inıcio e o termino de uma tarefa e a percepcao de uma mudanca de estado em um sensor. Estes eventos sao, por sua natureza, instantaneos, o que lhes confere um carater discreto no tempo. Sistemas com estas caracterısticas sao denominados sistemas a eventos discretos (SED), em oposicao aos sistema de variaveis contınuas, tratados pela Teoria de Controle classica. A natureza discreta dos SEDs faz com que os modelos matematicos convencionais, baseados em equacoes diferenciais, nao sejam adequados para trata-los. Por outro lado, a sua importancia faz com que seja altamente desejavel encontrar solucoes para problemas relacionados ao seu controle. Em razao disso, existe uma intensa atividade de pesquisa voltada a busca de modelos matematicos adequados a sua representacao, sem que se tenha conseguido ate agora encontrar um modelo que seja matematicamente tao conciso e computacionalmente tao adequado como o sao as equacoes diferenciais para os sistemas dinamicos de variaveis contınuas. Nao existe, por isso, consenso sobre qual seja o melhor modelo. Dentre os modelos existentes, destaca-se o proposto por Ramadge e Wonham, baseado em Teoria de

Introducao 8

Linguagens e de Automatos e denominado “modelo RW”. Este faz uma distincao clara entre o sistema a ser controlado, denominado planta, e a entidade que o controla, que recebe o nome de supervisor. A planta e um modelo que reflete o comportamento fisicamente possıvel do sistema, isto e, todas as acoes que este e capaz de executar na ausencia de qualquer acao de controle. Em geral, este comportamento inclui a capacidade de realizar determinadas atividades que produzam um resultado util, sem contudo se limitar a esse comportamento desejado. Por exemplo, dois robos trabalhando em uma celula de manufatura podem ter acesso a um deposito de uso comum, o que pode ser util para passar pecas de um ao outro. No entanto, cria-se com isso a possibilidade fısica de ocorrer um choque entre ambos, o que e, em geral, indesejavel. O papel do supervisor no modelo RW e, entao, o de exercer uma acao de controle restritiva sobre a planta, de modo a confinar seu comportamento aquele que corresponde a uma dada especificacao. Uma vantagem desse modelo e a de permitir a sıntese de supervisores, sendo estes obtidos de forma a restringir o comportamento da planta apenas o necessario para evitar que esta realize acoes proibidas. Desta forma, pode-se verificar se uma dada especificacao de comportamento pode ou nao ser cumprida e, caso nao possa, identificar a parte dessa especificacao que pode ser implementada de forma minimamente restritiva. Um criterio de aceitacao pode entao ser utilizado para determinar se, com a parte implementavel da especificacao, o sistema trabalha de maneira satisfatoria. Neste documento serao apresentados os principais conceitos basicos da Teoria de Controle Supervisorio, como introduzida por Ramadge e Wonham. Os conceitos de base da teoria de Linguagens e Automatos serao apresentados, bem como os principais resultados basicos de sıntese de supervisores para SEDs. A forma de apresentacao procurara se adaptar a um curso que possa ser facilmente assimilado por alunos em nıvel de Graduacao em cursos de Engenharia ou Ciencias de Computacao.

Capıtulo 2 Sistemas a Eventos Discretos

De um modo geral, um sistema e uma parte limitada do Universo que interage com o mundo externo atraves das fronteiras que o delimitam. Este conceito se aplica tambem aos sistemas tratados no presente documento, que apresentam ainda as caracterısticas descritas a seguir. Os sistemas de interesse percebem as ocorrencias no mundo externo atraves da recepcao de estımulos, denominados eventos. Sao exemplos de eventos o inıcio e o termino de uma tarefa (mas nao sua execucao), a chegada de um cliente a uma fila ou a recepcao de uma mensagem em um sistema de comunicacao. A ocorrencia de um evento causa, em geral, uma mudanca interna no sistema, a qual pode ou nao se manifestar a um observador externo. Alem disso, uma mudanca pode ser causada pela ocorrencia de um evento interno ao proprio sistema, tal como o termino de uma atividade ou o fim de uma temporizacao. Em qualquer caso, essas mudancas se caracterizam por serem abruptas e instantaneas: ao perceber um evento, o sistema reage imediatamente, acomodando-se em tempo nulo numa nova situacao, onde permanece ate que ocorra um novo evento. Desta forma, a simples passagem do tempo nao e suficiente para garantir que o sistema evolua; para tanto, e necessario que ocorram eventos, sejam estes internos ou externos. Note ainda que a ocorrencia desses eventos pode depender de fatores alheios ao sistema, de modo que este nao tem, em geral, como preve-los. O que se disse acima permite apresentar agora a seguinte definicao:

Definicao 2.1 Sistema a eventos discretos (SED) e um sistema dinamico que evolui de acordo com a ocorrencia abrupta de eventos fısicos, em intervalos de tempo em geral

Sistemas a Eventos Discretos 10 irregulares e desconhecidos.

Diz-se ainda que, entre a ocorrencia de dois eventos consecutivos, o sistema permanece num determinado estado. A ocorrencia de um evento causa entao uma transicao ou mudanca de estado no sistema, de forma que sua evolucao no tempo pode ser representada pela trajetoria percorrida no seu espaco de estados, conforme ilustrado na figura 2.1.

Figura 2.1: Trajetoria tıpica de um sistema a eventos discretos

Nesta trajetoria ocorrem eventos representados pelas letras α, β e λ. Ve-se que um mesmo evento pode ter efeitos diferentes, dependendo do estado em que ocorre. Por exemplo, se o sistema esta no estado x1 e ocorre o evento α, o proximo estado sera x4; se α ocorre em x3, volta-se para x1. A trajetoria pode continuar indefinidamente, inclusive com a ocorrencia de outros eventos, nao representados na figura. Para todos os sistemas tratados, porem, assume-se que o numero total de eventos diferentes que podem ocorrer e finito. O numero de estados pode ser ilimitado no caso geral, embora a classe de sistemas com um numero finito de estados seja um caso particular importante. Costuma-se distinguir um dos estados do sistema dos demais, o qual recebe o nome de estado inicial. Este e o estado em que o sistema se encontra antes de ocorrer o primeiro evento. Na pratica, em geral e possıvel forcar um sistema a voltar a esse estado, antes de iniciar sua utilizacao para um determinado fim, processo denominado de reinicializacao.

Os sistemas a eventos discretos, entendidos segundo a definicao 2.1, contrastam com os sistemas dinamicos a variaveis contınuas, descritos por equacoes diferenciais . E instrutivo comparar a trajetoria tıpica de um SED, apresentada na figura 2.1, com a de um sistema dinamico de variaveis contınuas, apresentada na figura 2.2.

O espaco de estados de um SED e limitado a um conjunto enumeravel, ao passo que e contınuo e portanto infinito nos sistemas contınuos. Estes, em geral, mudam de estado a cada instante, tendo o seu comportamento descrito por uma funcao que relaciona o

Sistemas a Eventos Discretos 1

Figura 2.2: Trajetoria tıpica de um sistema dinamico com variaveis contınuas estado (variavel dependente) ao tempo (variavel independente). Ja os sistemas a eventos discretos podem permanecer um tempo arbitrariamente longo em um mesmo estado, sendo que sua trajetoria pode ser dada por uma lista de eventos na forma {σ1,σ2,...}, incluindo-se eventualmente os instantes de tempo em que tais eventos ocorrem, na forma

O acima exposto permite ver a tarefa de especificar o comportamento de um sistema a eventos discretos como sendo a de estabelecer sequencias ordenadas de eventos que levem a realizacao de determinados objetivos. Com uma formulacao tao abrangente, nao e surpreendente que tenha havido esforcos em mais de uma area para abordar o problema. De fato a Teoria de Sistemas a Eventos Discretos e apresentada como pertencendo a area da Pesquisa Operacional, valendo-se ainda de resultados da Ciencia da Computacao (em particular da Inteligencia Artificial e do Processamento de Linguagens), bem como da Teoria de Controle.

Foram desenvolvidos ate o momento varios modelos para SEDs, sem que nenhum tivesse se afirmado como universal. Esses modelos refletem diferentes tipos de SEDs bem como diferentes objetivos na analise dos sistemas em estudo.

Os principais modelos utilizados para sistemas a eventos discretos sao os seguintes:

• Redes de Petri com e sem temporizacao; • Redes de Petri Controladas com e sem temporizacao;

• Cadeias de Markov;

• Teoria das Filas;

Sistemas a Eventos Discretos 12

• Processos Semi-Markovianos Generalizados (GSMP) e Simulacao; • Algebra de Processos;

• Algebra Max-Plus;

• Logica Temporal e Logica Temporal de Tempo Real;

• Teoria de Linguagens e Automatos (Ramadge-Wonham)

Dentre os modelos citados acima, dois apresentam uma caracterıstica particular: sao dotados de procedimentos de sıntese de controladores; sao eles os modelos de Ramadge- Wonham (temporizados ou nao), baseado na Teoria de Automatos e/ou Linguagens, e o de Redes de Petri Controladas (temporizadas ou nao). Pela caracterısticas citada, estes modelos tem dado forte contribuicao ao desenvolvimento da teoria de Controle de SEDs.

Os demais modelos citados servem sobretudo a analise de SEDs.

De todo modo, nenhum dos modelos serve atualmente como paradigma. Os SEDs formam uma area de pesquisa de intensa atividade e desafios.

2.2 Exemplos de Sistemas a Eventos Discretos

Nesta secao descreveremos alguns exemplos de SEDs. Iniciaremos por um sistema simples que serve como “modulo base”na representacao de muitos SEDs de interesse.

I. Sistemas de Filas: Os Sistemas de Filas tem origem no seguinte fato comum intrınseco a maioria dos sistemas que projetamos e desenvolvemos: o uso de certos recursos exige espera. Os tres elementos basicos de um sistema de filas sao:

1. As entidades que devem esperar pelo uso de recursos. Costuma-se denominar estas entidades de clientes.

(Parte 1 de 8)

Comentários