ULTRADES - SBAI 2015
Transcrição
ULTRADES - SBAI 2015
XII Simpósio Brasileiro de Automação Inteligente (SBAI) Natal – RN, 25 a 28 de outubro de 2015 ULTRADES - UMA BIBLIOTECA PARA MODELAGEM, ANÁLISE E CONTROLE DE SISTEMAS A EVENTOS DISCRETOS Lucas V. R. Alves∗ Hugo J. Bravo∗ Patrı́cia N. Pena† ∗ † Programa de Pós-Graduação em Engenharia Elétrica - Universidade Federal de Minas Gerais Av. Antônio Carlos 6627, 31270-901, Belo Horizonte, MG, Brasil Departamento de Engenharia Eletrônica - Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brasil Email: [email protected], [email protected], [email protected], Abstract— In this paper a library of functions and data structures for analysis and control of Discrete Event Systems based in the .NET Framework is proposed. The main objective is to create an environment for the implementation of algorithms for Discrete Event Systems, as well as the integration of these algorithms and codes in the fields of IT (Information Technology) and AT (Automation Technology). Keywords— Discrete Event Systems, Supervisory Control Theory, Software Package. Resumo— Neste artigo é proposta uma biblioteca de funções e estruturas de dados para análise e controle de Sistemas a Eventos Discretos baseada na Plataforma .NET. O principal objetivo é criar um ambiente para a implementação de algoritmos para Sistemas a Eventos Discretos, bem como a integração desses algoritmos e códigos nas áreas de TI (Tecnologia da Informação) e TA (Tecnologia da Automação). Palavras-chave— 1 Sistemas a Eventos Discretos, Teoria do Controle Supervisório, Pacote de Software. Introdução desenvolvimento de soluções customizadas e novos algoritmos. Já os softwares de código aberto são desenvolvidos para uma linguagem de programação especı́fica como C++ no caso do libFAUDES ou Python para o DESLAB. Neste artigo, propõe-se uma biblioteca, denominada UltraDES, orientada a objetos composta por estruturas de dados e algoritmos para a modelagem, análise e controle de SED. O UltraDES foi desenvolvido na linguagem C#, muito utilizada na área de Tecnologia da Informação (TI) para a indústria, estando baseada no .NET Framework como plataforma de execução. Dessa maneira, o UltraDES pode ser utilizado em qualquer linguagem que suporte o .NET Framework inclusive em Visual C++ e IronPython, isto é, as versões .NET das linguagens C++ e Python. Uma grande vantagem da utilização do .NET Framework na área industrial é a existência de uma versão do protocolo OPC, um padrão de comunicação industrial, chamada OPC .NET 4.0, desenvolvida para suportar diretamente programas desenvolvidos para a plataforma .NET. No dia a dia, é comum observar pessoas interagindo com distintos sistemas tecnológicos, como máquinas de autosserviço, telefones móveis inteligentes, sistemas flexı́veis de manufatura, entre outros. Muitas atividades realizadas pelos sistemas acima citados podem ser descritas por sequências de eventos. Tais sistemas chamam-se Sistemas a Eventos Discretos (SED). Formalmente, SED são sistemas dinâmicos de estados discretos que evoluem em razão da ocorrência instantânea de eventos, em instantes de tempo geralmente assı́ncronos (Cassandras e Lafortune, 2008). A Teoria de Controle Supervisório (TCS), proposta por Ramadge e Wonham (1989), proporciona uma abordagem embasada na teoria de linguagens e autômatos (Hopcroft et al., 2001) para análise e controle de SED. Nesta abordagem, o sistema a controlar, denomina-se planta, e o agente controlador, denomina-se supervisor. O papel do supervisor é regular o comportamento da planta delimitando-o a um comportamento desejado por meio da observação dos eventos gerados pela planta e, exercendo assim, uma ação de controle na forma de desabilitação, ou inibição da ocorrência de certos eventos. Com o passar do tempo, diversos softwares para o estudo dos SED foram desenvolvidos como, por exemplo, TCT (Feng e Wonham, 2006), Supremica (Åkesson et al., 2006), DESUMA (Ricker et al., 2006), Grail (Reiser et al., 2006), libFAUDES (Moor et al., 2008), DESLAB (Clavijo et al., 2012), entre outros. Embora existam diversos programas, muitos deles são de código fechado, como o Supremica e o TCT, impedindo assim o 2 Preliminares O UltraDES foi projetado sob a abordagem proposta por Ramadge e Wonham (1989). Sob este paradigma, o comportamento lógico de SED é modelado por sequências de eventos obtidas a partir de um alfabeto Σ. O fechamento de Kleene Σ∗ é o conjunto de todas as sequências sobre Σ, incluindo a sequência vazia ε. Considere s, v e t sequências sobre Σ∗ . Se s concatenada com v forma a 600 XII Simpósio Brasileiro de Automação Inteligente (SBAI) sequência t = sv, então diz-se que s é prefixo de t, e denota-se s ≤ t. O subconjunto L ⊆ Σ∗ é denominado linguagem. O prefixo fechamento L de L é o conjunto de todos os prefixos de sequências em L. determinı́stico G e o alfabeto Σ é particionado como Σ = Σc ∪ Σnc , em que Σc é o conjunto de eventos controláveis, que podem ser inibidos de ocorrer no sistema, e Σnr é o conjunto de eventos não controláveis, que não podem ser inibidos de ocorrer no sistema. A ação do supervisor sobre a planta consiste em inibir a ocorrência de eventos não controláveis com o propósito de alcançar o comportamento desejado. A linguagem gerada e marcada por uma planta sobre a ação do supervisor é L(S/G) e Lm (S/G) ⊆ Lm (G), respectivamente. Um supervisor é não bloqueante quando Lm (S/G) = L(S/G) , em outras palavras, quando garante que não existirá bloqueio do sistema em malha fechada. Sejam G uma planta e E uma especificação, a condição necessária e suficiente para a existência de um supervisor não bloqueante S para G, tal que Lm (S/G) = L(G) k E = K, é que K seja controlável em relação a L(G) e Σnc , ou seja, KΣnc ∩ L(G) ⊆ K. Caso o supervisor não seja controlável, então deve-se calcular a máxima sublinguagem controlável da linguagem desejada ou alvo, denotada por SupC(K, G). Várias destas estruturas matemáticas devem ser representadas por meio de software e essa representação é descrita nas seções seguintes. Pelo teorema de Kleene, linguagens regulares são reconhecidas por autômatos. Assim, um autômato (não determinı́stico) de estados finitos é definido por uma quı́ntupla G = (Σ, Q, → − , Q◦ , Qm ), em que Σ é um alfabeto, Q é o conjunto finito de estados, → − ⊆ Q × Σ × Q é a relação de transição entre os estados, Q◦ ⊆ Q é o conjunto de estados iniciais, e Qm ⊆ Q é o conjunto de estados marcados. Um autômato denomina-se determinı́stico quando |Q◦ | = 1 e para cada q ∈ Q e σ ∈ Σ σ existe no máximo um q 0 ∈ Q tal que q → q 0 . Um autômato G é capaz de representar dois tipos de linguagens: a linguagem gerada L(G) que representa todas as sequências que podem ser executadas no autômato, partindo do estado inicial, e a linguagem marcada Lm (G) ⊆ L(G) que é formada por todas as sequências que partindo do estado inicial chegam a um estado marcado. Dado um autômato G, afirma-se que um σ estado q ∈ Q é acessı́vel em G se q ◦ → q tal que σ q ◦ ∈ Q◦ , e coacessı́vel se q → q 0 tal que q 0 ∈ Qm . Um autômato chama-se acessı́vel se todos seus estados são acessı́veis. A componente acessı́vel de G é obtida partir de G pela eliminação dos estados não acessı́veis e transições associadas, indicada por Ac(G). De forma semelhante, um autômato chama-se coacessı́vel se todos seus estados são coacessı́veis. A componente coacessı́vel de G é obtida partir de G pela eliminação dos estados não coacessı́veis e transições associadas, operação representada por CoAc(G). Um autômato G é considerado trim se for acessı́vel e coacessı́vel, denotando-se a operação como trim(G). 3 Estruturas de Dados A biblioteca UltraDES é composta por diversas classes que representam autômatos, seus componentes (estados, eventos e transições) e expressões regulares. Além disso, existem outras diversas classes auxiliares. 3.1 De forma geral, um SED pode ser obtido pela composição de subsistemas (Cury, 2001). Nesse caso, o modelo do sistema global é obtido por meio da composição sı́ncrona dos subsistemas, ou seja, G =kni=1 Gi , em que Gi para cada i = 1, . . . , n, representa o modelo de um subsistema. Por outro lado, a especificação global E que restringe o comportamento do sistema a um comportamento que atenda aos objetivos de controle, é obtida por meio da composição E =km j=1 Ej , em que Ej para cada j = 1, . . . , m, representa o modelo da restrição de coordenação do sistema. Estados Figura 1: Relação entre as classes que representam estados no UltraDES A principal classe que representa um estado, na biblioteca, é chamada AbstractState, que é abstrata, logo não é possı́vel instanciar um objeto a partir dela, mas define as caracterı́sticas básicas que um estado deve ter, como nome (alias) e marcação (Marking.Marked ou Marking.Unmarked ). Como a união de dois estados é muito comum em operações com autômatos, foi criada uma classe O problema de controle supervisório consiste em encontrar um supervisor capaz de regular o comportamento da planta de tal forma que os objetivos de controle sejam alcançados. Nesse contexto, uma planta é modelada por um autômato 601 XII Simpósio Brasileiro de Automação Inteligente (SBAI) derivada de AbstractState, também abstrata, chamada AbstractCompoundState que além das caracterı́sticas definidas em AbstractState, também possui um apontador para os estados originais que geraram aquele estado composto. Toda biblioteca UltraDES utiliza apenas as classes AbstractState e AbstractCompoundState como estados. Visto que não é possı́vel criar objetos a partir de AbstractState e AbstractCompoundState, foram criadas classes derivadas dessas duas classes primitivas, chamadas respectivamente State e CompoundState. pela classe Union, a concatenação de duas expressões regulares é representada por Concatenation, a estrela de Kleene de uma expressão regular é dada por KleeneStar e um sı́mbolo, por sua vez, é representado pela classe abstrata Symbol. A classe Symbol é a classe base de AbstractEvent, de forma que qualquer evento é também um sı́mbolo. 3.3 As transições entre estados são definidas por meio da classe Transition, que contém o estado de origem (Origin), o estado de destino (Destination) e o evento que aciona a transição (Trigger ). var s1 = new State ( " s1 " , Marking . Marked ) ; var s2 = new State ( " s2 " , Marking . Unmarked ) ; 3.2 Transições var t = new Transition ( s1 , e1 , s2 ) ; Eventos e Expressões Regulares 3.4 Estruturas Auxiliares Figura 3: Relação entre a interface Option e as classes Some e None utilizadas no UltraDES A principal estrutura auxiliar definida no UltraDES é a interface Option. Essa interface possui duas implementações, sendo elas Some, uma estrutura que guarda dados de determinado tipo e None, uma estrutura que representa a ausência de dados. Essa estrutura é utilizada na função de transição de estados, quando, a partir de um estado de origem, um evento realiza uma transição, retorna-se uma estrutura Some contendo o estado de destino. Caso o evento não implique em uma transição de estado, retorna-se a estrutura None. Figura 2: Relação entre as classes que representam eventos e expressões regulares no UltraDES Dentro da biblioteca, um evento é definido pela classe abstrata AbstractEvent, que estabelece suas caracterı́sticas básicas, como nome (alias) e controlabilidade (Controllability.Controllable ou Controllability.Uncontrollable). De forma semelhante ao que é feito com o estado, são definidas classes que implementam AbstractEvent. Um evento de propósito geral é definido pela classe Event, mas também são definidos dois eventos especiais, como classes singleton, sendo eles Epsilon () e Empty (∅). 3.5 Autômato Finito Determinı́stico A classe DeterministicFiniteAutomaton representa um autômato finito determinı́stico, sendo definida por uma lista de transições (Transition), um estado inicial (AbstractState) e um nome. Toda a estrutura interna da classe DeterministicFiniteAutomaton é definida utilizando as classes abstratas AbstractState, AbstractCompundState e AbstractEvent, de forma que qualquer classe derivada destas funciona da mesma maneira sem que sejam necessárias mudanças estruturais nos algoritmos já implementados. var e1 = new Event ( " e1 " , Controllab ilit y . Controllable ) ; var e2 = new Event ( " e2 " , Controllab ilit y . Uncontrollable ) ; Outra classe abstrata presente no UltraDES é a classe RegularExpression que representa uma expressão regular. Uma expressão regular é definida por meio de operações sobre expressões regulares ou sı́mbolos, dessa forma, as operações sobre expressões regulares são definidas como classes. A união de duas expressões regulares é representada var G = new D e t e r m i n i s t i c F i n i t e A u t o m a t o n ( new [] { new Transition ( s1 , e1 , s2 ) , new Transition ( s2 , e2 , s1 ) } , s1 , " G " ) ; 602 XII Simpósio Brasileiro de Automação Inteligente (SBAI) 3.5.2 Principais Operações em DeterministicFiniteAutomaton ParallelCompositionWith Quando aplicado sobre um autômato G1 e recebendo como parâmetro um autômato G2, retorna um autômato G3 = G1||G2. var G3 = G1 . P a r a l l e l C o m p o s i t i o n W i t h ( G2 ) ; ProductWith Quando aplicado sobre um autômato G1 e recebendo como parâmetro um autômato G2, retorna um autômato G3 = G1 × G2. var G3 = G1 . ProductWith ( G2 ) ; AccessiblePart Quando aplicado sobre um autômato G, retorna a parte acessı́vel do autômato Ac(G). var G1 = G . AccessiblePart ; Figura 4: Métodos e Propriedades definidos na classe DeterministicFiniteAutomaton 3.5.1 CoaccessiblePart Quando aplicado sobre um autômato G, retorna a parte acessı́vel do autômato Coac(G). var G1 = G . Coa cce ssi ble P art ; Propriedades de um DeterministicFiniteAutomaton Trim Quando aplicado sobre um autômato G, retorna o autômato aparado resultante T rim(G). States Retorna uma lista com todos os estados (AbstractState) do autômato. MarkedStates Retorna uma lista com todos os estados marcados (AbstractState) do autômato. var G1 = G . Trim ; MonoliticSupervisor O método recebe uma lista de plantas, uma lista de especificações e um valor booleano indicando se o supervisor deve ser não bloqueante (true) ou não (false). O resultado é o supervisor monolı́tico que representa a planta sob controle. InitialState Retorna o estado inicial (AbstractState) do autômato. Events Retorna uma lista com todos os eventos (AbstractEvent) do autômato. var S = D e t e r m i n i s t i c F i n i t e A u t o m a t o n . Mo n ol i t i c S up e r v i s or ( new []{ M1 , M2 } , new []{ E } , true ) ; Name Retorna o nome do autômato. Este nome é modificado indicando as operações que já foram realizadas sobre o mesmo. LocalModularSupervisor O método recebe uma lista de plantas, uma lista de especificações, opcionalmente também pode receber uma lista de supervisores que impeçam a ocorrência de conflito. O resultado é uma lista com os supervisores modulares locais. Caso seja passado como parâmetro algum supervisor para resolução de conflito, eles também são retornados pelo método. Transitions Retorna uma lista com todas as transições (Transitions) do autômato. TransitionFunction Retorna a função de transição de estados do autômato. Essa função recebe o estado de origem e um evento, retornando None, caso não exista um estado de destino, ou Some cujo valor é o estado de destino. Caso o sistema seja conflitante é lançada uma exceção indicando o erro. 603 XII Simpósio Brasileiro de Automação Inteligente (SBAI) A terceira e última planta a ser utilizada é o Sistema Flexı́vel de Manufatura (SFM) (de Queiroz e Cury, 2000), que gera dois tipos de produtos a partir de blocos e tarugos brutos: um bloco com um pino cônico no topo (Produto A) e um bloco com um pino cilı́ndrico pintado (Produto B). Os autômatos utilizados em ambas as ferramentas são idênticos visto que todos os exemplos foram modelados no UltraDES e exportados para o para o formato ADS, lido pelo TCT, utilizando o método ToAdsFile. A Tabela 1 mostra os tempos de execução da sintetização de supervisor para os problemas citados anteriormente. Os testes foram realizados em um computador com processador Intel Core i3 2100 com 4 Gb de memória RAM em uma versão 32 bits do sistema operacional Windows. O fator que mais dificulta a comparação é o fato do TCT contar o tempo em segundos e por operação, ou seja, como boa parte das operações dura milissegundos, seus tempos são apresentados como zero segundos ainda que o tempo total (soma dos tempos) seja diferente de zero. De qualquer forma, pode ser observado que o TCT é mais rápido, apesar de não ser possı́vel quantificar quanto, mas o UltraDES resolve alguns problemas que o TCT não resolve. Além disso, o UltraDES é uma biblioteca que pode ser expandida e adaptada, permitindo a implementação de novos algoritmos e novas estruturas de dados. Um ponto importante a ser observado é o fato de que as estruturas de dados utilizadas no UltraDES são muito mais informativas e flexı́veis do que aquelas utilizadas no TCT, onde estados e eventos são representados apenas por números inteiros. var Ss = D e t e r m i n i s t i c F i n i t e A u t o m a t o n . L o c a l M o d u l a r S u p e r v i s o r ( new []{ M1 , M2 , M3 , M4 , M5 , M6 } , new []{ E1 , E2 , E3 , E4 }) ; 3.5.3 Métodos de Entradas e Saı́das ToXMLFile e FromXMLFile O método ToXMLFile salva as infomações do autômato em um arquivo no formato XML e o método FromXMLFile gera um autômato a partir de um arquivo XML. ToAdsFile e FromAdsFile O método ToAdsFile salva as infomações do autômato em um arquivo ADS, utilizado pelo software TCT. Devido às caracterı́sticas do arquivo as informações referentes aos nomes dos estados e eventos são perdidas. O método FromAdsFile lê um arquivo ADS e gera um autômato. SerializeAutomaton e DeserializeAutomaton O método SerializeAutomaton gera um arquivo binário contendo as informações do autômato e DeserializeAutomaton, por sua vez, realiza a leitura de um arquivo binário e gera um autômato. ToDotCode O método ToDotCode retorna um texto (tipo string) que contém a representação do autômato em formato DOT, utilizado pelo software Graphviz para gerar visualizações. 4 Testes e Avaliação de Desempenho 5 Nesta sessão são mostrados três problemas existentes na literatura e os tempos de execução do UltraDES para a sı́ntese do supervisor monolı́tico de cada exemplo. Para critérios de comparação também foram computados os tempos de execução para cada problema no TCT. O primeiro problema trabalhado é o Cluster Tool (Su et al., 2012), que modela sistemas de manufatura de semicondutores. A grande vantagem desse tipo de sistema é a possibilidade de combinar vários cluster tools possibilitando a observação do aumento do número de estados e transições na computação do supervisor. Neste caso foram realizados testes com dois, três e quatro cluster tools. Para um número de cinco ou mais cluster tools, não é possı́vel computar o supervisor devido a limitações de memória. A segunda planta utilizada é a Industrial Transfer Line (ITL) (de Queiroz et al., 2005), uma planta composta por seis máquinas conectadas por quatro buffers de forma que deseja-se garantir que não ocorra overflow nem underflow nos buffers. Conclusões Neste artigo foi proposto o UltraDES, uma biblioteca de modelagem, análise e controle de Sistemas a Eventos Discretos para o .NET Framework. O UltraDES pode ser utilizado em diversas linguagens de programação, em diferentes plataformas e até mesmo em sistemas embarcados. Toda a biblioteca foi projetada para ser literal, mantendo sempre os nomes completos das funcionalidades. Além disso, a interface é independente da implementação, de forma que a adição de novas funcionalidades ou a modificação de estruturas internas não altera o funcionamento ou o torna incompatı́vel com aplicações que utilizam versões anteriores do UltraDES. O UltraDES e o TCT foram utilizados para realizar a sı́ntese de um supervisor monolı́tico para problemas da literatura e percebeu-se que o UltraDES permitiu a solução de problemas maiores (Cluster Tools (4) e SFM) que não foram computados pelo TCT devido a problemas de memória (mensagem Problem too large – out of memory! ). 604 XII Simpósio Brasileiro de Automação Inteligente (SBAI) Planta Cluster Tools (2) Cluster Tools (3) Cluster Tools (4) ITL SFM No de Estados do Supervisor 45 419 4184 486 45504 No de Transições do Supervisor 74 972 12630 1584 200124 Tempo de Execução no UltraDES 4, 103s 5, 876s 34, 703s 0, 087s 50, 455s Tempo de Execução no TCT 0s 0s Não Computa 0s Não Computa Tabela 1: Tempos de execução da composição monolı́tica de supervisor para seis exemplos. Agradecimentos Ramadge, P. e Wonham, W. (1989). The Control of Discrete Event Systems, Proceedings of the IEEE 77(1): 81–98. O presente trabalho foi realizado com o apoio financeiro da Fapemig, CAPES - Brasil e CNPq. Reiser, C., da Cunha, A. e Cury, J. (2006). The Environment Grail for Supervisory Control of Discrete Event Systems, Proceedings of the 8th International Workshop on Discrete Event Systems, WODES’06, Ann Arbor, MI, USA, pp. 390–391. Referências Cassandras, C. e Lafortune, S. (2008). Introduction to Discrete Event Systems, 2nd edn, New York: Springer. Ricker, L., Lafortune, S. e Genc, S. (2006). DESUMA: A Tool Integrating GIDDES and UMDES, Proceedings of the 8th International Workshop on Discrete Event Systems, WODES’06, Ann Arbor, MI, USA, pp. 392–393. Clavijo, L., Basilio, J. e Carvalho, L. (2012). DESLAB: Um Programa de Computação Cientı́fica para Análise e Sı́ntese de Sistemas a Eventos Discretos, Anais do XIX Congresso Brasileiro de Automática, CBA’12, Campina Grande, PB, Brasil, pp. 2531–2538. Su, R., van Schuppen, J. e Rooda, J. (2012). The synthesis of time optimal supervisors by using heaps-of-pieces, Automatic Control, IEEE Transactions on 57(1): 105–118. Cury, J. (2001). Teoria de Controle Supervisório de Sistemas a Eventos Discretos, V Simpósio Brasileiro de Automação Inteligente, CanelaRS. Åkesson, K., Fabian, M., Flordal, H. e Malik, R. (2006). Supremica - An integrated environment for verification, synthesis and simulation of discrete event systems, Proceedings of the 8th International Workshop on Discrete Event Systems, WODES’06, Ann Arbor, MI, USA, pp. 384–385. de Queiroz, M., Cury, J. e Wonham, W. (2005). Multitasking supervisory control of discreteevent systems, Discrete Event Dynamic Systems 15(4): 375–395. de Queiroz, M. H. e Cury, J. E. (2000). Modular supervisory control of large scale discrete event systems, in R. Boel e G. Stremersch (eds), Discrete Event Systems, Vol. 569 of The Springer International Series in Engineering and Computer Science, Springer US, pp. 103–110. Feng, L. e Wonham, W. (2006). TCT: A Computation Tool for Supervisory Control Synthesis, Proceedings of the 8th International Workshop on Discrete Event Systems, WODES’06, Ann Arbor, MI, USA, pp. 388– 389. Hopcroft, J., Motwani, R. e Ullman, J. (2001). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley. Moor, T., Schmidt, K. e Perk, S. (2008). libFAUDES - An Open Source C++ Library for Discrete Event Systems, Proceedings of the 9th International Workshop on Discrete Event Systems, WODES’08, Göteborg, Sweden, pp. 125–130. 605