Identificação de Sistemas a Eventos Discretos Maxplus lineares - Automação (2024)

Prévia do material em texto

IDENTIFICAÇÃO DE SISTEMAS A EVENTOS DISCRETOS MAXPLUSLINEARESCarlos Andrey Maia∗maia@cpdee.ufmg.brRafael Santos Mendes†rafael@dca.fee.unicamp.brLaurent Hardouin‡laurent.hardouin@istia.univ-angers.fr∗Depto. de Engenharia Elétrica - UFMGAv. Antônio Carlos 6627 - Pampulha31270-010 Belo Horizonte - MG - Brasil†Faculdade de Engenharia Elétrica e de Computação - UNICAMPDCA/FEEC/UNICAMP-C.P. 610113083-970 Campinas - SP - Brasil‡Laboratoire d’Ingénierie des Systèmes Automatisés - ISTIA/Université d’AngersAv. Notre Dame du Lac 6249000 Angers - FrançaABSTRACTThis paper deals with the identification problem of Max-pluslinear Discrete Event Systems with single input and singleoutput. The objective is to estimate the temporal parametersof the system by using the observation of input and outputtransition firing times assuming that some structural param-eters are known. With those assumptions, the identificationmethod is developed by using an upper bound for cycle du-ration. The paper presents a sufficient excitation condition,concerning the input signal, for the convergence of the algo-rithm. Examples Illustrate the proposed method.KEYWORDS: Discrete Event Systems, System Identifica-tion, Max-plus Algebra, Timed Event Graphs.ARTIGO CONVIDADO:Versão completa e revisada de artigo apresentado no CBA-2004Artigo submetido em 15/12/20041a. Revisão em 04/02/2005;2a. Revisão em 12/04/2005;Aceito sob recomendação do Ed. Assoc. Prof. Paulo Eigi MiyagiRESUMOEste artigo trata do problema de identificação de Sistemas aEventos Discretos Max-plus lineares mono-entrada e mono-saída. O objetivo é estimar os parâmetros temporais do sis-tema a partir da observação dos instantes de disparo das tran-sições de entrada e de saída, supondo que alguns parâmetrosestruturais sejam conhecidos. A partir dessas condições, ométodo de identificação proposto é desenvolvido tendo comobase o cálculo de um limitante superior para o parâmetro detemporização do ciclo. Obtém-se uma condição suficientede excitação, relativa à variável de entrada, para a conver-gência do algoritmo proposto. Exemplos ilustram o métodoproposto.PALAVRAS-CHAVE: Sistemas a Eventos Discretos, Identi-ficação de Sistemas, Álgebra Max-plus, Grafos de EventosTemporizados.Revista Controle & Automação/Vol.16 no.4/Outubro, Novembro e Dezembro 2005 4071 INTRODUÇÃODiversas tecnologias presentes em processos de manufatura,redes de comunicação, controle de tráfego aéreo, etc., po-dem ser descritas por modelos com algumas característicasem comum. Nestes sistemas, o espaço de estados é em ge-ral discreto (em muitos casos finito) e mudanças de estadoacontecem somente em resposta à ocorrência de eventos. Es-sas características os distinguem dos sistemas que tem suadinâmica dirigida pelo tempo e seu espaço de estado con-tínuo, cuja modelagem é tradicionalmente feita através dasequações diferenciais e das equações a diferenças. Tais sis-temas são denominados Sistemas a Eventos Discretos (SED)(Cassandras e Lafortune, 1999). Uma maneira formal de des-crever SED é através de Redes de Petri (Murata, 1989) sendoas Redes de Petri temporizadas particularmente úteis quandohá interesse em avaliar o desempenho do sistema.Este artigo trata da abordagem Max-plus. Esta técnicafundamenta-se em resultados algébricos relativos aos semi-anéis idempotentes (também chamados de dióides) e na Te-oria de Residuação, cujas bases são sumariadas na seção 2.Sua principal característica é descrever a dinâmica de SED apartir de um sistema de equações algébricas lineares, escritasnuma álgebra não convencional (Cohen et al., 1985). QuandoSED apresentam fenômenos de sincronização de tarefas e deretardo no tempo, mas não há conflito na utilização de recur-sos, eles podem ser descritos pela álgebra Max-plus, sendodenominados SED Max-plus lineares (SEDMpl). Exemplosdesses sistemas são as linhas de montagem em processos demanufatura. Conforme será discutido na seção 2, o compor-tamento desses tipos de SED coincide com o comportamentodos Grafos de Eventos Temporizados (GET) que são umasubclasse de Redes de Petri na qual todos os lugares têm umaúnica transição de entrada e uma única transição de saída(Baccelli et al., 1992). O uso dos GET como ferramenta grá-fica facilita a compreensão da dinâmica dos SEDMpl.Dois problemas centrais no estudo de SEDMpl são a iden-tificação e o controle do sistema. O problema de controleé usualmente formulado dentro de um contexto just-in-timevisando à minimizaçao dos estoques do sistema (Menguyet al. (2000b), Cottenceau et al. (2001), Lüders e Santos-Mendes (2002), Maia, Hardouin, Santos-Mendes e Cotten-ceau (2003)). O estudo da identificação de SEDMpl é abor-dado por Boimond et al. (1995) que propõem a identifica-ção paramétrica baseada na resposta impulsiva do modelo. Aabordagem considera a estimação de dois modelos ARMA:um para o regime transitório e outro para o comportamentoperiódico. Gallot et al. (1998) consideram a identificação apartir da resposta impulsiva do sistema baseada na decompo-sição do sistema em uma soma de sub-sistemas de primeiraordem (a resposta impulsiva é decomposta em uma soma determos chamados elementos simples). Dessa forma o mé-todo consiste na estimação de parâmetros de diversos siste-mas de primeira ordem. Menguy et al. (2000a) desenvolvemum algoritmo para a identificação não-paramétrica (direta)baseado no refinamento da estimativa da resposta impulsiva.Este trabalho apresenta novos resultados (notadamente so-bre as condições de excitação do sistema) para o métodode identificação paramétrica de SEDMpl com uma entrada euma saída (SEDMpl SISO) similar aos propostos por Maia,Santos-Mendes e Hardouin (2003) e Maia (2003). Nesse mé-todo supõem-se conhecidos o número de disparos durante operíodo transitório (i.e. o comprimento do transitório) e onúmero de disparos ocorridos em cada ciclo do regime per-manente. Este último parâmetro está relacionado com o nú-mero de fichas no circuito crítico do GET. Por outro lado, sãoconsideradas desconhecidas as durações temporais do transi-tório e do ciclo do regime permanente. Estes parâmetros de-vem ser estimados juntamente com os parâmetros que defi-nem completamente a resposta transitória e o comportamentoem regime do sistema. A principal contribuição em relaçãoaos métodos propostos anteriormente é que, conhecida a es-trutura do modelo, o modelo estimado é mais próximo domodelo real do sistema do que o obtido pelo cálculo diretoda maior resposta impulsiva.O artigo é organizado da maneira seguinte. A introduçãoàs ferramentas matemáticas básicas para a compreensão doartigo é feita na seção 2. O método de identificação é apre-sentado na seção 3, na qual os parâmetros supostos conhe-cidos e os parâmetros a serem estimados são formalmenteexplicitados. Na seção 4, são apresentados alguns exemplosilustrativos e a conclusão é feita na seção 5.2 PRELIMINARES2.1 Sistemas max-plus linearesOs resultados apresentados a seguir são extensivamente abor-dados em Baccelli et al. (1992).Considere-se, a título de exemplo, o GET ilustrado pela fi-gura 1, representando um sistema de montagem cuja produ-ção máxima é de uma peça a cada duas unidades de tempo.Nessa figura u é a transição de entrada à qual serão associa-dos os instantes de admissão de matéria-prima ao sistema; xisão as transições internas (doravante também chamadas deestados) e y é a transição de saída, que representa a conclu-são do processo de montagem. Como é usual na literatura, amesma notação será utilizada para designar uma transição deum GET e o instante de tempo de disparo (admissão de umproduto em um dado setor do sistema) da transição. Dessaforma, o comportamento dinâmico do sistema é descrito pe-408 Revista Controle & Automação/Vol.16 no.4/Outubro, Novembro e Dezembro 2005u yM2x 1 x 2Figura 1: Descrição de um processo de montagem simplesatravés de GETlas equações a seguir.x1(k) = max(x2(k− 1), u(k))x2(k) = 2 + x1(k)y(k) = x2(k).A variável inteira k corresponde à numeração do disparo,convencionando-se que k=0 corresponde ao primeiro disparoe k=n ao (n+1)-ésimo disparo.Renomeando o operador max como sendo ⊕ e o operador +como sendo ⊗, pode-se reescrever:x1(k) = x2(k − 1) ⊕ u(k) (1)x2(k) = 2 ⊗ x1(k)y(k) = x2(k).Tem-se portanto um sistema de equações recursivas linea-res numa nova álgebra que é um semi-anel idempotente (oudióide) e se caracteriza por um conjunto e duas operações(soma e produto), notado (D,⊕,⊗), tal que a soma seja as-sociativa, comutativa e idempotente (a⊕ a = a), e o produtoseja associativo (mas não necessariamente comutativo) e dis-tributivo à esquerda e à direita em relação à soma. Alémdisso, devem existir elementos neutros para ambas as opera-ções, notados por ε (elemento nulo) e por e (elemento uni-tário), e o elemento nulo deve ser absorvente em relação aoproduto, isto é, ∀a ∈ D, a ⊕ ε = a; a ⊗ e = a; a ⊗ ε = ε.Percebe-se que o conjunto Z∪ {−∞} munido das duas ope-rações ⊕ ≡ max e ⊗ ≡ + é um dióide, no qual ε = −∞ ee = 0. Num dióide uma relação de ordem é definida comoa � b ⇔ b = a ⊕ b. Em geral, um dióide é completose ele for fechado em relação a somas infinitas e se o pro-duto for distributivo em relação a somas infinitas, sendo oseu maior elemento denotado por > (topo). A operação ∧(ínfimo) é definida em a ∧ b como sendo o maior elementodo dióide menor do que a e menor do que b. A estrutura(Z ∪ {−∞} ∪ {∞}, max, +) é um dióide completo usual-mente denominado “max-plus” e notado por Zmax.O exemplo mostrado na figura 1 utiliza o que se convencionachamar de datadores, isto é, sequências crescentes {x(k)}que representam as datas ou instantes de ocorrência dos dis-paros da transição x.De modo análogo ao que ocorre na teoria de sistemas contí-nuos, as manipulações das equações de SEDMpl ficam fa-cilitadas se forem utilizadas transformadas das sequênciasde datadores definidas de modo semelhante ao das clássi-cas transformadas Z. Define-se, portanto, a γ-transformadade uma sequência {x(k)} como sendo x(γ) =⊕k∈Z+x(k)γk ,sendo γ uma variável abstrata cujo significado é o de umoperador “atraso em contagem”, pois é imediato constatarque y(γ) = γx(γ) ⇔ {y(k)} = {x(k − 1)}. As equações1, submetidas à γ-transformada resultam no seguinte sistemade equações algébricas:x1(γ) = γx2(γ) ⊕ u(γ) (2)x2(γ) = 2x1(γ)y(γ) = x2(γ)É possível definir operações de soma e multiplicação entreséries formais do tipo⊕k∈Z+x(k) γk, utilizando-se para issoa soma e o produto adotados para Zmax combinados comos procedimentos usuais para somar e multiplicar séries for-mais. O conjunto de todas as séries formais em γ, munidodessas duas operações também é um dióide, isto é, satisfaz atodas as propriedades utilizadas para caracterizar um dióide,sendo denominado Zmax[[γ]]. A valoração, um conceito queserá utilizado a seguir, de uma série h em Zmax[[γ]] é o me-nor expoente de coeficiente não-nulo, sendo representado porval(h).A equação 2 pode ser colocada em forma matricial, re-sultando em x(γ) = A(γ)x(γ) ⊕ B(γ)u(γ) e y(γ) =C(γ)x(γ), sendo A, B e C matrizes na variável abstratagama de dimensões apropriadas e u(γ), y(γ) e x(γ) veto-res associados respectivamente às transições de entrada, desaída e internas ao sistema. De modo geral, em qualquerdióide, equações do tipo x = ax ⊕ b tem como solução mí-nima x = a∗b, sendo a∗ =⊕∞i=0 ai e a0 = e . Esse resul-tado, chamado de teorema da estrela 1 (Baccelli et al., 1992),pode ser generalizado para as equações matriciais anteriores,levando a y = CA∗Bu, ou de modo sintético:y(γ) = h(γ)u(γ). (3)Nessa equação, h(γ) = CA∗B é chamada de função detransferência do sistema e (como na teoria de sistemas con-tínuos) coincide com a resposta do sistema a uma entradaimpulsiva, u(γ) = e, que corresponde a infinitos disparosda transição de entrada em t = 0. Conforme mostrado emBaccelli et al. (1992) todo SEDMpl SISO tem uma respostaimpulsiva periódica que pode ser colocada na seguinte forma:h(γ) = p(γ) ⊕ q(γ)γν(sγr)∗, (4)1A operação ∗ é a clássica estrela de Kleene utilizada em Teoria de Autô-matos e Linguagens Formais.Revista Controle & Automação/Vol.16 no.4/Outubro, Novembro e Dezembro 2005 409sendo p(γ) =⊕ν−1i=0 pi γi, pi ∈ N e q(γ) =⊕r−1j=0 qj γj ,qi ∈ N polinômios e ν ∈ N, s ∈ N e r ∈ N respectivamenteo comprimento do transitório, a duração e o comprimento doregime permanente. O algoritmo de identificação propostodeverá, portanto, estimar os coeficientes dos polinômios p(γ)e q(γ) assim como o parâmetro s (duração do ciclo do regimepermanente)2. Vale observar na equação 4, que h(i) = pipara (i < ν) e que h(j) = qi para (j < r). A figura 2 ilustragraficamente o comportamento de uma série periódica.tn sT r a n s i t ó r i o R e g i m e P e r i ó d i c o nrq 0Figura 2: Comportamento da série h(γ).Em algumas situações pode ser interessante trabalhar no do-mínio dos datadores. Nesse domínio a equação 3 é escritacomoy(k) =k⊕l=0h(l) ⊗ u(k − l). (5)Em outras palavras, isso significa que a saída é o resultadoda convolução da entrada e da resposta ao impulso do GET.Esse resultado é obtido diretamente a partir da substituiçãoda equação 4 na equação 3.2.2 Teoria da residuaçãoAs formulações discutidas na próxima seção envolvem a in-versão de funções, isto é, a solução em x de equações do tipoy = f(x). Diferentemente do caso da álgebra tradicional asolução desse tipo de equação no dióide pode apresentar umnúmero infinito de soluções ou nenhuma solução. A Teoriada Residuação (Blyth e Janowitz, 1972) se ocupa justamenteda solução deste problema em conjuntos parcialmente orde-nados. A seguir, alguns resultados fundamentais relativos aessa teoria serão apresentados.Consideram-se inicialmente os mapeamentos f : D → E ,sendo D e E dióides completos. Se f for isotônico (preservao ordenamento, i.e, x � y ⇔ f(x) � f(y) ) e se existirum elemento máximo xop do conjunto {x | y � f(x), x ∈2Observa-se que os graus dos polinômios p(γ) e q(γ) são respectiva-mente ν − 1 e r − 1.D, y ∈ E}, diz-se que xop é o resíduo do mapeamento fem y. Se f tiver um resíduo em qualquer ponto y ∈ E , omapeamento f é dito residuável, sendo o resíduo denotadopor f ](y) (Baccelli et al., 1992). Dualmente, o mínimo doconjunto {x | y � f(x), x ∈ D, y ∈ E}, se ele existir,é denominado resíduo dual sendo denotado por f [(y) e omapeamento f é dito dualmente residuável.As funções La(x) = a⊗x e Ra(x) = x⊗a são residuáveis,sendo seus resíduos denotados respectivamente por L]a = a◦\e R]a = x◦/a. No caso particular do dióide Zmax tem-se L]a =R]a = x − a (operação de subtração da álgebra tradicional).A definição de residuação assegura que:a(a◦\x) � x. (6)A função T (x) = x ⊕ a é dualmente residuável, sendo seuresíduo dual denotado por x ◦− a. Por exemplo, no dióideZmax, 3 ◦− 1 = 3, pois, pela definição de resíduo dual, 3 ◦− 1é a menor solução da equação max(x, 1) ≥ 3.Conforme visto anteriomente, o dióide Zmax[[γ]] é importantepara a descrição da dinâmica de um GET. Algumas propri-edades das séries descritas nesse dióide, fundamentais paraeste artigo, são apresentadas a seguir.Propriedade 1 (Maia (2003)) O datador associado à série(trajetória não decrescente) w(γ) = y(γ) ◦− x(γ) é dado porw(k) =⊕i≤k(y(i) ◦− x(i)).Lema 2 (Residuação de séries) Sejam duas séries dodióide Zmax[[γ]], u(γ) =⊕k∈Z+u(k) γk e v(γ) =⊕k∈Z+v(k) γk, então:v(γ)◦\u(γ) =⊕k∈Z+∧l∈Z+(v(l)◦\u(l + k))γk. (7)Vale dizer que a expressão∧l∈Z+(v(l)◦\u(l + k)) correspondeao coeficiente de γk, sendo (∧) o operador min3 e v(l)◦\u(l+k) = u(l+k)−v(l) (operação de subtração da álgebra tradi-cional). Convém ainda relembrar a definição de residuação,que assegura que y(γ) = v(γ)◦\u(γ) é a maior série tal quev(γ)⊗ y(γ) � u(γ). Maiores detalhes sobre a residuação deséries são apresentados por Baccelli et al. (1992). Programaspara a manipulação de séries na álgebra de dióides usandoo pacote computacional SCILAB podem ser encontrados emhttp://www.istia-angers.fr/~hardouin/outils.html.3 MÉTODO DE IDENTIFICAÇÃONo desenvolvimento do método proposto, assume-se que ummodelo para o sistema existe e é expresso pela equação 3.3a ∧ b é o maior elemento menor que a e menor que b.410 Revista Controle & Automação/Vol.16 no.4/Outubro, Novembro e Dezembro 2005A estrutura, i.e. parâmetros ν e r (equação 4 ), é tambémsuposta conhecida. O objetivo do método de identificaçãoé, então, estimar os polinômios desconhecidos p(γ), q(γ) ea duração do período s. Mostra-se (Maia, 2003) que essesistema pode ser representado pelas equações seguintes nodióide Zmax:z(k) = s ⊗ z(k − r) ⊕ u(k)y(k) = p0u(k) ⊕ . . . ⊕ pν−1u(k − ν + 1)⊕q0z(k − ν) ⊕ . . . ⊕ qr−1z(k − ν − r + 1)(8)com condições iniciais tais que z(k) = u(k) = y(k) = εpara k < 0, sendo z(k) uma variável que modela o compor-tamento do ciclo.Seguindo o mesmo raciocínio clássico da teoria de identifica-ção para sistemas dinâmicos contínuos (Ljung, 1987), y(k)pode ser reescrito como:y(k) = ϕTk ⊗ θ, (9)sendo ϕTk = [u(k) . . . u(k−ν+1)z(k−ν) . . . z(k−ν−r+1)]o vetor de regressão e θ = [p0 . . . pν−1q0 . . . qr−1]T o vetorde parâmetros a ser estimado.Dessa forma, a partir da observação de N disparos das tran-sições de saída e de entrada, obtém-se a equação matricial:Y = Φ ⊗ θ, (10)na qual Φ = [ϕ0 . . . ϕN ]T é a matriz de regressão e Y =[y(0) . . . y(N)]T é o vetor de saída observado.Para estimação do parâmetro θ, é conveniente a definição deum critério de erro comoJ(θ̃) =⊕k(y(k) − ỹ(k)), (11)sendo a saída do modelo estimado (ỹ(k) = Φ ⊗ θ̃) tal queỹ(k) ≤ y(k). Esse critério significa que, para uma mesmaentrada, o melhor modelo deve produzir a maior saída possí-vel que seja menor que a saída observada, i.e., deve-se esco-lher o maior θ̃ tal que Φ ⊗ θ̃ � Y .Por enquanto, apenas para o desenvolvimento do algoritmo,assume-se que a variável z é conhecida. Assim, um estima-dor ótimo para o critério J(θ̃) é obtido diretamente atravésda Teoria da Residuação,θ̂ =⊕Φ⊗eθ�Yθ̃ = Φ◦\Y. (12)Explicitamente, a solução dessa equação é dada por:p̂i =∧Nk=0 u(k − i)◦\y(k), i ∈ [0 ν − 1],q̂j =∧Nk=0 z(k − ν − j)◦\y(k), j ∈ [0 r − 1].(13)Nota-se que p̂i ≥ pi e q̂j ≥ qj pois θ̂ é a maior soluçãode Φ ⊗ θ̃ � Y . Conseqüentemente, θ̂ é uma solução para aequação (10), i.e., Y = Φ⊗ θ̂. Esse resultado implica que p̂ie q̂j satisfazem a equação (8) para k = 1, ..., N . Atribuindou(k) = y(k) = > para k > N (isso significa que nenhumevento ocorre para k > N ), a equação (8) é satisfeita paratodo k ∈ Z. Dessa maneira, a aplicação da transformação γresulta emy(γ) = [p̂(γ) ⊕ q̂(γ)γν(sγr)∗]u(γ). (14)Propriedade 3 A condição necessária e suficiente para aconvergência do estimador p̂ apresentado nas equações 13 é:∀i ∈ [0 ν−1], ∃k′ ∈ [0 N ] tal que y(k′) = p(i)+u(k′−i).Analogamente, para q̂ a condição necessária e suficiente é:∀j ∈ [0 r − 1] , ∃k′ ∈ [0 N ] tal que y(k′) = q(j) + z(k −ν − j).Prova: Como p̂i =∧Nk=0 u(k − i)◦\y(k), a necessidade éobtida lembrando-se que para u(k − i) e y(k) finitos tem-seu(k−i)◦\y(k) = y(k)−u(k−i). A suficiência é obtida atravésdo fato de que p̂ é máximo e de que y(k′) = p(i) + u(k′− i)implica em p̂i ≤ pi, ou seja, esses dois fatos resultam emp̂i = pi. Para q̂, a demonstração é análoga. 2Contudo esse resultado tem pouca utilidade prática já quenão explicita como deve ser a excitação do sistema para que aestimação seja correta. Uma condição de excitação suficienteé apresentada na proposição 5.Lema 4 Se a excitação do GET é tal que 0 ≤ u(k) ≤(h(γ)◦\h(γ))(k) para 0 ≤ k ≤ N então y(k) = h(k).Prova: Pela fórmula 5, y(k) =⊕kl=0 h(l) ⊗ u(k −l). Dessa forma, y(k) ≥ h(k) pois u(i) ≥ 0para 0 ≤ i ≤ N . Por outro lado: y(k) ≤⊕kl=0 h(l)(h(γ)◦\h(γ))(k−l) =⊕kl=0 h(l)(∧i∈Z+h(i)◦\h(i+k−l)) ≤⊕kl=0 h(l)(h(l)◦\h(k)), pois o lema 2, assegura que(h(γ)◦\h(γ))(k − l) =∧i∈Z+h(i)◦\h(i + k − l). Assim pelainequação 6,⊕kl=0 h(l)(h(l)◦\h(k)) ≤⊕kl=0 h(k) = h(k)e, portanto, y(k) ≤ h(k) para 0 ≤ i ≤ N . Como já foimostrado que y(k) ≥ h(k), conclui-se que y(k) = h(k). 2Como conseqüência desse lema, se e � u(γ) � h(γ)◦\h(γ)então y(γ) = h(γ), em outras palavras h(γ)◦\h(γ) é a maiorentrada tal que a saída seja igual à resposta ao impulso. Ainterpretação desse resultado para um sistema de manufaturaé que h(γ)◦\h(γ) fornece os instantes máximos de disparo datransição de entrada u(γ) de forma que a saída permaneçainalterada e igual a h(γ). Em teoria de identificação de sis-temas contínuos (Ljung, 1987), quando um sinal consegueRevista Controle & Automação/Vol.16 no.4/Outubro, Novembro e Dezembro 2005 411excitar toda a faixa dinâmica de um sistema, diz-se que essesinal é um "sinal de excitação rico" para o sistema. Analo-gamente, devido ao lema 4, uma seqüência de disparos datransição de entrada será considerada um "sinal de excitaçãorico" para um GET, se a condição e � u(γ) � h(γ)◦\h(γ)for verificada.Proposição 5 Se o parâmetro s é conhecido e o sinal deentrada u é suficientemente "rico" (i.e., 0 ≤ u(k) ≤(h(γ)◦\h(γ))(k) para 0 ≤ k ≤ N sendo N ≥ ν + r − 1)então os estimadores dados em 13 convergem para os parâ-metros reais do sistema, precisamente p̂i = pi e q̂j = qj parai ∈ [0 ν − 1] e j ∈ [0 r − 1].Prova: As hipóteses desta proposição para o sinal de entradaimplicam, de acordo com o lema 4, que y(k) = h(k) para0 ≤ k ≤ N . Dessa forma, p̂i =∧Nk=0 u(k − i)◦\h(k) ≤u(0)◦\h(i) ≤ h(i) = pi (i < ν) pois u(0) ≥ 0. Alémdisso, se s é conhecido, então z é também conhecido e osestimadores propostos sempre asseguram que p̂i ≥ pi e q̂j ≥qj , pois eles são as maiores soluções para o problema. Assim,conclui-se que p̂i = pi . O mesmo raciocínio é aplicado paraa estimativa q̂j lembrando que qj = h(ν + j) para j < r. 2Convém observar que se u(k) − u(0) ≤ (h(γ)◦\h(γ))(k),o estimador também converge. De fato, fazendo u(k) =u(k) + u(0) = u(k) ⊗ u(0) , então y(k) = y(k) ⊗ u(0)sendo y(k) =⊕kl=0 h(l) ⊗ u(k − l). Do mesmo modo,mostra-se que z(k) = z(k)⊗u(0). Dessa forma, a diferençaentre os datadores (u, y, z) e (u, y, z) é o termo u(0). Comoos resíduos das equações 13 são calculados a partir de dife-renças entre datadores, o resultado obtido utilizando (u, y, z)é mesmo que se obtém utilizando (u, y, z).Nota 6 Se u(k1) >> u(k1 − 1) para k1 > 0, entãoy(k1+j) = u(k1)⊗(⊕jl=0h(j−l)⊗u(l)) para j ≥ 0, sendou(k1+j) = u(k1)+u(j) = u(k1)⊗u(j). Esse resultado per-mite escrever a saída como y(k1 + j) = u(k1) ⊗ y(j) sendoy a saída do sistema para a entrada u, ou seja, a partir do k1-ésimo disparo, o sistema desconsidera a influência dos dispa-ros anteriores. Do mesmo modo, a variável interna é escritacomo z(k1 + j) = u(k1) ⊗ z(j) sendo z a trajetória obtidautilizando a entrada u. Como conseqüência dessa observa-ção, se u(i) ≤ (h(γ)◦\h(γ))(i) para 0 ≤ i ≤ ν + r−1, entãoos estimadores também convergem conforme observado an-teriormente. De fato, sabe-se que:y(k1 + j) =⊕k1−1i=0 (h(k1 + j− i)⊗u(i))⊕⊕k1+ji=k1(h(k1 +j − i) ⊗ u(i)).Como u é crescente e u(k1) >> u(k1 − 1) então o segundosomatório é maior que o primeiro. Assim, como u(k1 +j) =u(k1) ⊗ u(j), tem-se que:y(k1 + j) = u(k1) ⊗ (k1+j⊕i=k1h(k1 + j − i) ⊗ u(i − k1)).Fazendo l = i − k1, obtém-se que y(k1 + j) =u(k1)(⊕jl=0h(j−l)⊗u(l)). Seguindo o mesmo argumento,mostra-se que z(k1 + j) = u(k1)⊗ z(j) sendo z a trajetóriaobtida utilizando a entrada u. ♦Uma interpretação para a situação apresentada na nota 6 éque após o (k1 − 1)-ésimo disparo da transição de entradaespera-se um tempo tal que o sistema retorne à condição de"relaxado"4 para só assim disparar novamente essa transição.Dessa forma, a menos da translação temporal u(k1), o sis-tema passa a responder a partir do k1-ésimo disparo como seestivesse no início do processo.Propriedade 7 Para o estimadorproposto tem-se semprep̂0 = p0, ou seja, p̂0 sempre converge para o valor real in-dependentemente das condições de excitação do sistema.Prova: Isso se deve o fato de que p̂0 =∧Nk=0 u(k)◦\y(k) ≤u(0)◦\y(0) = y(0) − u(0). Como y(0) = p0 ⊗ u(0) =p0 + u(0), então p̂0 ≤ p(0). Entretanto, como discutido an-teriormente, p̂0 ≥ p0, logo p̂0 = p0. 2A estimação dos parâmetros qj apresentada nas equações 13requer o conhecimento da variável z. Essa variável é des-conhecida mas pode ser estimada. Se uma estimativa de s(representada por ŝ) é disponível, então uma estimativa de z(representada por ẑ) é obtida iterativamente segundo a equa-ção (8), ou seja,ẑ(k) = ŝ ⊗ ẑ(k − r) ⊕ u(k). (15)Dessa forma, estima-se a variável z a partir da estimativa des. Para a estimativa da duração do período, s, deve-se recor-dar que as estimativas dadas na equação 13 devem satisfazera equação 14. A partir desse resultado, demonstra-se a pro-posição 8.Proposição 8 Um limitante superior de s é calculado a partirdas expressões abaixo:winf (γ) = y(γ) ◦− p̂(γ)u(γ)c(γ) = winf (γ)◦\y(γ)sup = mini=1,...,Lbc(ir)ic,4O sistema é dito relaxado num determinado instante de tempo se ne-nhum disparo puder ocorrer, a partir desse instante, nas transições internas ede saída do sistema, supondo que não ocorra nenhum disparo nas transiçõesde entrada do sistema.412 Revista Controle & Automação/Vol.16 no.4/Outubro, Novembro e Dezembro 2005sendo L = bNrc e u(γ) e y(γ) respectivamente 5 as sériescorrespondentes aos dados da entrada e da saída do sistema.Prova: A demonstração é apresentada por Maia (2003) e uti-liza os resultados da propriedade 1 e do lema 2. 2Dessa forma, utiliza-se neste artigo o estimador para s comosendo ŝ = sup.Uma condição suficiente para a convergência do estimadorproposto é apresentada a seguir. Convém lembrar que paraque os efeitos da periodicidade da função de transferênciasejam percebidos na saída é sempre necessário pelo menosν + r observações dos disparos da transição de saída (verfigura 2).Proposição 9 (Maia (2003)) Sejam winf (γ) 6= ε, vw =val(winf (γ)) e o número de observações tal que N ≥ r+vw .Se 0 ≤ u(k) ≤ (h(γ)◦\h(γ))(k) para 0 ≤ k ≤ N , entãoŝ = s.Vale ressaltar que a condição de convergência apresentadana proposição 9 é ampliada se o sinal de entrada satisfaz àshipóteses apresentadas na nota 6 para k1 ≤ k ≤ k1 + N evw ≥ k1.Finalmente, o método de identificação é sintetizado no algo-ritmo mostrado a seguir.AlgoritmobeginIniciar variáveis: z(k) = u(k) = y(k) = −∞ para k < 0.Coletar N ≥ ν + r pares de dados de entrada e saída(u(k), y(k));p̂i =∧Nk=0 u(k − i)◦\y(k) i = 0, ..., ν − 1;for k = 0, ..., N(p̂(γ)u(γ))(k) =⊕ν−1i=0 (p̂i ⊗ u(k − i));winf (k) =⊕ki=0{y(i) ◦− (p̂(γ)u(γ))(i)};endc(k) =∧N−ki=0 winf (i)◦\y(k + i) for k = 0, ..., N ;ŝ = mini=1,...,Lb c(ir)i c sendo L = bNr c;ẑ(k) = ŝ ⊗ ẑ(k − r) ⊕ u(k) for k = 0, ..., N ;5Convenciona-se que bxc é o maior inteiro menor que x.q̂j =∧Nk=0 ẑ(k − ν − j)◦\y(k) for j = 0, ..., r − 1;end4 EXEMPLOS ILUSTRATIVOSA figura 3 representa um GET que modela um sistema demontagem com 3 máquinas representadas pelos símbolosM1, M2 e M3. Sejam u e y respectivamente os datadoresdas transições de entrada e de saída e x1, x2 e x3 os datadoresdas transições internas desse GET. Utilizando a transforma-u yx 164x 3x 2331 0634M 1M 3M 2Figura 3: Exemplo de Grafo de Eventos Temporizados SISOção γ, obtém-se o sistema de equações (16) que relacionaessas variáveis no dióide Zmax[[γ]].x1(γ) = 6γx1(γ) ⊕ 3u(γ)x2(γ) = 3γx2(γ) ⊕ 10u(γ)x3γ = 4γx3(γ) ⊕ 6x1(γ) ⊕ 3x2(γ)y(γ) = 4x3(γ)(16)A partir do teorema da estrela apresentado na introdução,obtém-se a equação que relaciona a entrada e a saída do sis-temay(γ) = (17⊕ 21γ ⊕ (25γ2)(6γ)∗)u(γ), (17)sendo h(γ) = 17 ⊕ 21γ ⊕ (25γ2)(6γ)∗ = 17 ⊕ 21γ ⊕25γ2 ⊕ 31γ3 ⊕ 37γ5 ⊕ 43γ5 . . .] a função de transferênciaque apresenta parâmetros estruturais ν = 2 e r = 1. Em ou-tras palavras, a seqüência de disparos da resposta impulsivaé h = [17 21 25 31 37 43 . . .].A planta descrita pela equação 17 será utilizada a seguir emdiversas condições de excitação para ilustrar a aplicabilidadedo método de identificação proposto. Nesse caso, a máximaentrada que garante a "excitação rica" do sistema é uh(γ) =h(γ)◦\h(γ) = 0⊕4γ⊕8γ2⊕14γ3⊕20γ5⊕26γ5 . . ., ou seja,a seqüência de disparos é dada por uh = [0 4 8 14 20 26 . . .].Revista Controle & Automação/Vol.16 no.4/Outubro, Novembro e Dezembro 2005 413Em cada exemplo, o par de entrada e saída (uh, h) é mos-trado nos gráficos em linhas pontilhadas.Exemplo 10 Considere-se a seqüência de disparos da transi-ção de entrada dada por u = [0 2 5 8 17 20]. Conseqüen-temente, a seqüência de disparos da transição de saída éy = [17 21 25 31 37 43]. A figura 4 mostra essas seqüênciase o comportamento do GET em linhas pontilhadas quando aentrada é uh. Nesse caso, observa-se que u � uh e que acondição de excitação do sistema satisfaz a hipótese da pro-posição 9. Como conseqüência, a aplicação do método deidentificação proposto resulta em p̂0 = 17, p̂1 = 21, q̂0 = 25e ŝ = 6. Isto é, o método converge para os parâmetros reaisdo sistema. ♦0 1 2 3 4 5 6051 01 52 02 53 03 54 04 5 N ú m e r o d e d i s p a r o s unidades de tempo u ( k )y ( k )Figura 4: Comportamento do GET para o exemplo 10Exemplo 11 Neste exemplo, supõe-se que a seqüênciade disparos da transição de entrada seja dada por u =[0 5 9 15 19 21]. Assim, a seqüência de disparos corres-pondentes para transição de saída é y = [17 22 26 32 37 43].Esses dados são mostrados na figura 5. A aplicação do mé-todo de identificação proposto resulta em p̂0 = 17, p̂1 = 21,q̂0 = 25 e ŝ = 6. Isto é, o método converge para os parâ-metros reais do sistema embora a condição de excitação nãosatisfaça a hipótese da proposição 9 (i.e. u � uh). Esseexemplo mostra que a proposição é suficiente para conver-gência mas não necessária. ♦Exemplo 12 Um outro exemplo de simulação utiliza umaseqüência de disparos da transição de entrada dada por u =[0 3 11 15 17 27] cuja seqüência de disparos da transição desaída é y = [17 21 28 32 37 44]. Esses dados são apresenta-dos na figura 6. Neste exemplo a condição de excitação é talque u � uh e os resultados obtidos pelo método de identifi-cação são: p̂0 = 17, p̂1 = 24, q̂0 = ε e ŝ = >. Nesse caso,os parâmetros não convergiram para os valores reais. Pode-se fazer uma analogia dessa situação com o caso de excitação"pobre" em sistemas dinâmicos contínuos. ♦Exemplo 13 A figura 7 mostra outra simulação para uma0 1 2 3 4 5 6051 01 52 02 53 03 54 04 5 N ú m e r o d e d i s p a r o s Unidades de tempo u ( k )y ( k )Figura 5: Comportamento do GET para o exemplo 110 1 2 3 4 5 6051 01 52 02 53 03 54 04 5 N ú m e r o d e d i s p a r o s unidades de tempo u ( k )y ( k )Figura 6: Comportamento do GET para o exemplo 12seqüência de disparos da transição de entrada dada por u =[0 7 15 22 30 37] cuja seqüência de disparos da transição desaída é y = [17 24 32 39 47 54]. Nesse caso, novamentea condição de excitação não é satisfeita (u � uh). Os re-sultados obtidos pelo método de identificação são: p̂0 = 17,p̂1 = 24, q̂0 = ε e ŝ = >, isto é, os parâmetros não conver-giram para parâmetros reais da planta. ♦Exemplo 14 Nesta simulação a entrada é dada por u =[0 26 30 33 33 33] e a saída correspondente é y =[17 43 47 51 57 63]. A figura 8 mostra essas seqüências.Nesse caso, observar que u � uh. Como aconteceu no exem-plo 11, p̂0 = 17, p̂1 = 21, q̂0 = 25 e ŝ = 6, ou seja, mesmonão satisfazendo a condição suficiente de excitação, os resul-tados obtidos mostram que estimadores convergem para osparâmetros reais do modelo da planta. ♦Os exemplos 12 e 14 ilustram o fato que se a excitaçãou1 leva a uma estimaçãonão-convergente então a excitaçãou2 � u1 não necessariamente leva a uma estimação não con-vergente. Esse ponto pode ser compreendido com o auxílona nota 6.O exemplo 13 ilustra particularmente o fato de que se incre-414 Revista Controle & Automação/Vol.16 no.4/Outubro, Novembro e Dezembro 20050 1 2 3 4 5 6051 01 52 02 53 03 54 04 5 N ú m e r o d e d i s p a r o s unidades de tempo u ( k )y ( k )5 05 5Figura 7: Comportamento do GET para o exemplo 130 1 2 3 4 5 6051 01 52 02 53 03 54 04 5 N ú m e r o d e d i s p a r o s unidades de tempo u ( k )y ( k )5 05 56 0Figura 8: Comportamento do GET para o exemplo 14mentos na trajetória de u são muito grandes em relação aosde h, ou seja, a inclinação de u é suficientemente maior quea de h, o algoritmo de estimação sempre resulta em qj = ε es = >. Isso se deve ao fato de que se u(k)−u(k− 1) é sufi-cientemente grande para todo k ∈ N então as desigualdadesh(0)⊗u(k) � h(1)⊗u(k−1) � . . . são verdadeiras. Comoy(k) =⊕kl=0 h(l)⊗u(k−l) e pela equação 4, pi = h(i) parai ∈ [0 ν − 1], então essas desigualdades permitem escreverque y(k) =⊕ν−1l=0 p(l) ⊗ u(k − l). Dessa forma p̂ é tal quey(k) =⊕ν−1l=0 p̂l ⊗ u(k − l), ou seja, p̂ é um modelo que as-segura que o critério de erro é nulo. Intuitivamente, esse fatocorresponde à situação em que a entrada de matéria-primano sistema é lenta ao ponto de só se observarem fenômenostransitórios, isto é, a taxa de chegada de matéria-prima nãopermite que o polinômio q(γ) influencie na solução. Dessaforma, segundo o método de estimação apresentado no algo-Tabela 1: Condições de convergência observadas para osexemplosExemplo Excitação Comportamento observado10 u � uh convergência11 u � uh convergência12 u � uh não-convergência13 u � uh não-convergência14 u � uh convergênciaritmo 1, winf (γ)(k) = ε e, conseqüentemente, c(γ)(k) = >para todo k ∈ N. Finalmente, isso resulta em ŝ = > e, paraum número de observações N ≥ 2r + ν − 1, tem-se queqj = ε para j ∈ [0 r − 1].A tabela 1 resume as condições de convergência observadaspara os exemplos apresentados.5 CONCLUSÃOEste artigo apresentou alguns resultados para a estimaçãodos parâmetros temporais para SED Max-plus lineares quesão uma extensão do trabalho apresentado por Maia, Santos-Mendes e Hardouin (2003). O método se baseia no conhe-cimento do comprimento do transitório e do comprimentodo ciclo em regime permanente (respectivamente, parâme-tros ν e r) e visa à estimação das durações do transitório edo ciclo em regime permanente (respectivamente, parâme-tros qo e s) assim como a estimação dos demais coeficien-tes do polinômios p(γ) e do polinômio q(γ). As principaiscontribuições são relativas às condições de excitação do sis-tema que asseguram a convergência do método. Vale dizerque o modelo desenvolvido para a estimação utiliza uma va-riável interna desconhecida para modelar o comportamentodo circuito crítico e a estimação dessa variável interna apre-senta dificuldades e constitui uma limitação para o método,devendo portanto ser objeto de atenção em trabalhos futuros.Outro resultado apresentado é a determinação de um majo-rante para a duração do ciclo em regime permanente (parâ-metro s) mesmo que as condições suficientes de excitaçãodefinidas pela proposição 9 não sejam respeitadas.REFERÊNCIASBaccelli, F., Cohen, G., Olsder, G. e Quadrat, J. (1992). Syn-chronisation and Linearity: An Algebra for DiscreteEvent Systems, John Wiley and Sons, New York.Blyth, T. e Janowitz, M. (1972). Residuation Theory, Perga-mon Press, Oxford.Boimond, J., Hardouin, L. e Chiron, P. (1995). A Mode-ling Method of SISO Discrete-Event Systems in Max-Algebra, ECC’95, Rome, Italy, pp. 2023–2026.Revista Controle & Automação/Vol.16 no.4/Outubro, Novembro e Dezembro 2005 415Cassandras, C. G. e Lafortune, S. (1999). Introduction toDiscrete Event Systems, Kluwer Academic Publishers.Cohen, G., Dubois, D., Quadrat, J. e Viot, M. (1985). A li-near system theoretic view of discrete event processesand its use for performance evaluation in manufactu-ring, IEEE Trans. on Automatic Control AC–30: 210–220.Cottenceau, B., Hardouin, L., Boimond, J. e Ferrier, J.(2001). Model Reference Control for Timed EventGraphs in Dioid, Automatica 37: 1451–1458.Gallot, F., Boimond, J. e Hardouin, L. (1998). Identificationof Linear Systems using MA and ARMA Models in Di-oids, IFAC Conference Structure and Control, Nantes,France.Ljung, L. (1987). System Identification : Theory for the User,Prentice Hall.Lüders, R. e Santos-Mendes, R. (2002). Generalized Mul-tivariable Control of Discrete Event Systems in Dioid,6th International Workshop on Discrete Event Systems(WODES’02), Zaragoza, Spain.Maia, C. A. (2003). Identificação e Controle de Sistemas aEventos Discretos na Álgebra (max,+), Tese de douto-rado, UNICAMP, Campinas, SP, Brasil.Maia, C. A., Hardouin, L., Santos-Mendes, R. e Cotten-ceau, B. (2003). Optimal Closed-loop of Timed EventGraphs in Dioids, IEEE Trans. on Automatic Control48(12): 2284–2287.Maia, C. A., Santos-Mendes, R. e Hardouin, L. (2003). SomeResults on Identification of Timed Event Graphs in Di-oids, 11th Mediterranean Conference on Control andAutomation (MED’03), Rodes, Grécia.Menguy, E., Boimond, J., Hardouin, L. e Ferrier, J. (2000a).A First Step Towards Adaptive Control for Linear Sys-tems in Max Algebra, Discrete Event Dynamic Sys-tems.Theory and Applications 10: 347–367.Menguy, E., Boimond, J., Hardouin, L. e Ferrier, J. (2000b).Just-in-time Control of Timed Event Graphs Updateof Reference Input, Presence of Uncontrollable Input,IEEE Trans. on Automatic Control 45(11): 2155–2158.Murata, T. (1989). Petri nets : properties, analysis and appli-cations., Proceedings of the IEEE 77(4): 541–580.416 Revista Controle & Automação/Vol.16 no.4/Outubro, Novembro e Dezembro 2005