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