A Luenberger Observer for P-Time Event Graphs

Sintesi Tecnica: Un Osservatore di Luenberger per i Grafi di Eventi P-Time

Definizione del Problema
Il documento affronta il problema della stima dello stato per i Grafi di Eventi P-Time (P-TEG), una classe di sistemi a eventi discreti utilizzati per modellare la sincronizzazione e i vincoli di finestra temporale nei processi manifatturieri e industriali. A differenza dei classici Grafi di Eventi Temporizzati (TEG), i P-TEG incorporano sia vincoli di limite inferiore che di limite superiore sui tempi di soggiorno dei token nelle "place". La sfida principale consiste nel stimare i tempi di attivazione (firing times) delle transizioni interne e non osservabili in tempo reale (online), dato che solo un sottoinsieme di transizioni (transizioni di output e transizioni di input osservabili) può essere misurato direttamente. L'osservatore deve fornire la stima più accurata possibile (la più grande sotto-approssimazione dei tempi di attivazione reali) rispettando al contempo i vincoli strutturali del sistema ed evitando la "morte del token" (violazioni dei vincoli di finestra temporale).

Metodologia
Gli autori estendono il classico framework dell'osservatore di Luenberger, precedentemente stabilito per i TEG utilizzando l'algebra max-plus, al dominio più complesso dei P-TEG. La metodologia si basa sui seguenti pilastri tecnici:

1. Rappresentazione con Vettore Infinito: Per gestire le disuguaglianze introdotte dai vincoli di limite superiore e dalle varie condizioni iniziali, il documento adotta una "rappresentazione con vettore infinito" delle funzioni dater (che mappano la $k$-esima attivazione di una transizione al suo tempo di occorrenza). Questo approccio funge da alternativa flessibile alla trasformata $\gamma$, meno adatta alle specifiche strutture di disuguaglianza presenti nei P-TEG.
2. Formulazione Algebrica: La dinamica del P-TEG è modellata come un sistema di equazioni e disuguaglianze lineari max-plus. Il sistema è rappresentato in uno spazio vettoriale a dimensione infinita, convertendo il comportamento dinamico in equazioni algebriche che coinvolgono le matrici $A$, $B$, $R$ e $C$, insieme alle matrici di disuguaglianza $U$ che codificano i vincoli di limite superiore.
3. Progettazione dell'Osservatore: L'osservatore è progettato per trovare la più grande sotto-approssimazione del vettore di stato $x$. Il processo di progettazione prevede:
   • La derivazione di una "matrice di stato massima" $M^*$ che incapsula sia la dinamica del sistema che i vincoli di limite superiore.
   • La formulazione dell'equazione dell'osservatore $\hat{x} = x_0 \oplus M \hat{x} \oplus Bu \oplus L(y \oplus \hat{y})$, dove $L$ è la matrice di guadagno dell'osservatore.
   • La risoluzione di un sistema di disuguaglianze per determinare la matrice di guadagno ottimale $L_{opt}$. Gli autori dimostrano che $L_{opt}$ può essere calcolato come $J_{opt} \otimes C^T$, dove $J_{opt}$ è derivata dalla stella di Kleene della matrice del sistema e delle matrici di input/output.
4. Algoritmo di Stima Online: L'algoritmo proposto opera in due fasi. In primo luogo, calcola il guadagno ottimale $L_{opt}$ offline. In secondo luogo, durante l'operazione online, aggiorna la stima dello stato $\hat{x}_t$ in qualsiasi istante $t$ utilizzando solo la cronologia degli eventi osservati (tempi di attivazione di $u$ e $y$ fino al tempo $t$). Gli autori dimostrano che, nonostante l'infinità della dimensione delle matrici, la stima può essere eseguita in tempo polinomiale rispetto al numero di transizioni del sistema e agli eventi osservati.

Contributi Chiave

• Estensione degli Osservatori di Luenberger: Il documento estende con successo l'osservatore di Luenberger dai TEG ai P-TEG, consentendo lo sfruttamento dei vincoli di limite superiore per migliorare la stima dello stato.
• Gestione dei Vincoli di Limite Superiore: Utilizzando la rappresentazione con vettore infinito, gli autori forniscono un rigoroso framework algebrico per incorporare i vincoli di finestra temporale direttamente nella progettazione dell'osservatore, permettendo "stime raffinate" che prevengono la previsione di traiettorie impossibili (quelle che portano alla morte del token).
• Derivazione del Guadagno Ottimale: Il documento fornisce una soluzione in forma chiusa per la matrice dell'osservatore ottimale $L_{opt}$, dimostrando che essa fornisce la più grande stima possibile dello stato interno coerente con tutte le misurazioni e i vincoli del sistema disponibili.
• Efficienza Computazionale: Il lavoro stabilisce che la fase di stima online è computazionalmente fattibile (tempo polinomiale), rendendo l'approccio praticabile per l'implementazione reale.

Risultati
Il documento valida il metodo proposto utilizzando un esempio numerico (un P-TEG con tre transizioni interne e vincoli di finestra temporale).

• Convergenza: L'osservatore converge ai tempi di attivazione effettivi delle transizioni interne man mano che i dati di output diventano disponibili, con l'eccezione di un tempo di attivazione specifico (la seconda attivazione della transizione $x_1$) che rimane permanentemente sottostimato di 1 unità temporale.
• Miglioramento della Precisione: Un'analisi comparativa mostra che l'osservatore proposto, che utilizza i limiti superiori, fornisce stime maggiori o uguali a quelle ottenute da un osservatore standard basato su TEG (che ignora i limiti superiori). Per la transizione di output misurata, entrambi gli osservatori forniscono stime identiche. Per le transizioni interne non misurate, l'osservatore proposto fornisce stime strettamente migliori (più grandi) nella maggior parte dei casi; ad esempio, in un determinato istante temporale, l'osservatore proposto ha corretto correttamente una stima da 5 a 6 per evitare una prevista morte del token, mentre l'osservatore standard non è riuscito a effettuare questa correzione, risultando in una stima meno accurata (più piccola).
• Coerenza: L'algoritmo garantisce che la traiettoria stimata rimanga coerente con i vincoli strutturali del P-TEG, evitando la previsione di traiettorie non coerenti.

Significatività e Rivendicazioni
Gli autori affermano che questo lavoro fornisce un metodo sistematico per la stima dello stato nei P-TEG che sfrutta tutto il potere di modellazione di questi grafi, specificamente i vincoli di limite superiore spesso presenti nei sistemi reali (ad esempio, scadenze, finestre di tempo di elaborazione). Il documento sottolinea che, a differenza degli approcci precedenti per le reti P-time che calcolano tutte le possibili sequenze coerenti (che possono essere computazionalmente costose e non richiedono insiemi di raggiungibilità finiti), questo osservatore fornisce le migliori stime dei tempi di occorrenza direttamente. La significatività risiede nella capacità di eseguire un monitoraggio online accurato di complessi sistemi a eventi discreti dove i vincoli temporali sono critici, senza richiedere che l'insieme di raggiungibilità della rete sottostante sia finito. Il lavoro è presentato come un'estensione diretta della teoria esistente degli osservatori TEG, adattata per gestire le specifiche sfide algebriche poste dai P-TEG.