A Luenberger Observer for P-Time Event Graphs

Resumo Técnico: Um Observador de Luenberger para Grafos de Eventos P-Time

Definição do Problema
O artigo aborda o problema de estimação de estado para Grafos de Eventos P-Time (P-TEGs), uma classe de sistemas de eventos discretos usada para modelar sincronização e restrições de janelas de tempo em processos de manufatura e industriais. Diferente dos Grafos de Eventos Temporizados (TEGs) padrão, os P-TEGs incorporam tanto restrições de limite inferior quanto de limite superior nos tempos de permanência (sojourn times) de tokens em lugares. O desafio central é estimar os tempos de disparo de transições internas e não observáveis em tempo real (online), dado que apenas um subconjunto de transições (transições de saída e transições de entrada observáveis) pode ser medido diretamente. O observador deve fornecer a estimativa mais precisa possível (a maior sub-aproximação dos tempos de disparo reais) enquanto respeita as restrições estruturais do sistema e evita a "morte de tokens" (violações das janelas de tempo).

Metodologia
Os autores estendem o framework clássico do observador de Luenberger, anteriormente estabelecido para TEGs usando álgebra max-plus, para o domínio mais complexo dos P-TEGs. A metodologia baseia-se nos seguintes pilares técnicos:

1. Representação de Vetor Infinito: Para lidar com as desigualdades introduzidas pelas restrições de limite superior e diversas condições iniciais, o artigo adota uma "representação de vetor infinito" de funções de data (dater functions) — que mapeiam o k-ésimo disparo de uma transição para o seu tempo de ocorrência. Esta abordagem serve como uma alternativa flexível à transformação $\gamma$, que é menos adequada para as estruturas de desigualdade específicas encontradas em P-TEGs.
2. Formulação Algébrica: A dinâmica do P-TEG é modelada usando um sistema de equações e desigualdades de diferença max-plus lineares. O sistema é representado em um espaço vetorial de dimensão infinita, convertendo o comportamento dinâmico em equações algébricas envolvendo matrizes $A$, $B$, $R$ e $C$, juntamente com matrizes de desigualdade $U$ que codificam as restrições de limite superior.
3. Design do Observador: O observador é projetado para encontrar a maior sub-aproximação do vetor de estado $x$. O processo de design envolve:
   • Derivar uma "matriz de estado máxima" $M^*$ que encapsula tanto a dinâmica do sistema quanto as restrições de limite superior.
   • Formular a equação do observador $\hat{x} = x_0 \oplus M \hat{x} \oplus Bu \oplus L(y \oplus \hat{y})$, onde $L$ é a matriz de ganho do observador.
   • Resolver um sistema de desigualdades para determinar a matriz de ganho ótima $L_{opt}$. Os autores provam que $L_{opt}$ pode ser computado como $J_{opt} \otimes C^T$, onde $J_{opt}$ é derivado da estrela de Kleene da matriz do sistema e das matrizes de entrada/saída.
4. Algoritmo de Estimação Online: O algoritmo proposto opera em duas etapas. Primeiro, computa o ganho ótimo $L_{opt}$ offline. Segundo, durante a operação online, atualiza a estimativa de estado $\hat{x}_t$ em qualquer tempo $t$ usando apenas o histórico de eventos observados (tempos de disparo de $u$ e $y$ até o tempo $t$). Os autores demonstram que, apesar da dimensionalidade infinita das matrizes, a estimação pode ser realizada em tempo polinomial em relação ao número de transições do sistema e eventos observados.

Principais Contribuições

• Extensão dos Observadores de Luenberger: O artigo estende com sucesso o observador de Luenberger de TEGs para P-TEGs, permitindo a exploração das restrições de limite superior para uma melhor estimação de estado.
• Tratamento de Restrições de Limite Superior: Ao utilizar a representação de vetor infinito, os autores fornecem um framework algébrico rigoroso para incorporar restrições de janela de tempo diretamente no design do observador, permitindo "estimações refinadas" que evitam a previsão de trajetórias impossíveis (aquelas que levam à morte de tokens).
• Derivação de Ganho Ótimo: O artigo fornece uma solução de forma fechada para a matriz de observador ótima $L_{opt}$, provando que ela produz a maior estimativa possível do estado interno que seja consistente com todas as medições e restrições do sistema disponíveis.
• Eficiência Computacional: O trabalho estabelece que a etapa de estimação online é computacionalmente viável (tempo polinomial), tornando a abordagem viável para implementação prática.

Resultos
O artigo valida o método proposto usando um exemplo numérico (um P-TEG com três transições internas e restrições de janela de tempo).

• Convergência: O observador converge para os tempos de disparo reais das transições internas conforme mais dados de saída tornam-se disponíveis, com exceção de um tempo de disparo específico (o segundo disparo da transição $x_1$), que permanece subestimado permanentemente em 1 unidade de tempo.
• Melhoria na Precisão: Uma análise comparativa mostra que o observador proposto, que utiliza as restrições de limite superior, fornece estimativas que são maiores ou iguais às obtidas por um observador baseado em TEG padrão (que ignora os limites superiores). Para a transição de saída medida, ambos os observadores produzem estimativas idênticas. Para transições internas não medidas, o observador proposto fornece estimativas estritamente melhores (maiores) na maioria dos casos; por exemplo, em um passo de tempo específico, o observador proposto ajustou corretamente uma estimativa de 5 para 6 para evitar uma morte de token prevista, enquanto o observador padrão falhou em fazer essa correção, resultando em uma estimativa menos precisa (menor).
• Consistência: O algoritmo garante que a trajetória estimada permaneça consistente com as restrições estruturais do P-TEG, evitando a previsão de trajetórias não consistentes.

Significância e Alegações
Os autores alegam que este trabalho fornece um método sistemático para a estimação de estado em P-TEGs que aproveita todo o poder de modelagem desses grafos, especificamente as restrições de limite superior frequentemente encontradas em sistemas do mundo real (ex: prazos, janelas de tempo de processamento). O artigo enfatiza que, ao contrário de abordagens anteriores para redes de Petri de tempo P que computam todas as sequências consistentes possíveis (o que pode ser computacionalmente caro e não requer conjuntos de alcançabilidade finitos), este observador fornece as melhores estimativas de tempo de ocorrência diretamente. A significância reside na capacidade de realizar o monitoramento online preciso de sistemas de eventos discretos complexos onde as restrições de tempo são críticas, sem exigir que o conjunto de alcançabilidade da rede subjacente seja finito. O trabalho é apresentado como uma extensão direta da teoria de observadores de TEG existente, adaptada para lidar com os desafios algébricos específicos impostos pelos P-TEGs.