A Luenberger Observer for P-Time Event Graphs

Technical Summary: A Luenberger Observer for P-Time Event Graphs

Problem Statement
The paper addresses the state estimation problem for P-Time Event Graphs (P-TEGs), a class of discrete event systems used to model synchronization and time-window constraints in manufacturing and industrial processes. Unlike standard Timed Event Graphs (TEGs), P-TEGs incorporate both lower-bound and upper-bound constraints on the sojourn times of tokens in places. The core challenge is to estimate the firing times of internal and unobservable transitions in real-time (online), given that only a subset of transitions (output transitions and observable input transitions) can be directly measured. The observer must provide the most accurate possible estimate (the greatest under-approximation of the true firing times) while respecting the system's structural constraints and avoiding "token death" (violations of time-window constraints).

Methodology
The authors extend the classical Luenberger observer framework, previously established for TEGs using max-plus algebra, to the more complex domain of P-TEGs. The methodology relies on the following technical pillars:

1. Infinite Vector Representation: To handle the inequalities introduced by upper-bound constraints and various initial conditions, the paper adopts an "infinite vector representation" of dater functions (which map the $k$-th firing of a transition to its occurrence time). This approach serves as a flexible alternative to the $\gamma$-transform, which is less suitable for the specific inequality structures found in P-TEGs.
2. Algebraic Formulation: The dynamics of the P-TEG are modeled using a system of linear max-plus difference equations and inequalities. The system is represented in an infinite-dimensional vector space, converting the dynamic behavior into algebraic equations involving matrices $A$, $B$, $R$, and $C$, alongside inequality matrices $U$ that encode the upper-bound constraints.
3. Observer Design: The observer is designed to find the greatest sub-approximation of the state vector $x$. The design process involves:
   • Deriving a "largest state matrix" $M^*$ that encapsulates both the system dynamics and the upper-bound constraints.
   • Formulating the observer equation $\hat{x} = x_0 \oplus M \hat{x} \oplus Bu \oplus L(y \oplus \hat{y})$, where $L$ is the observer gain matrix.
   • Solving a system of inequalities to determine the optimal observer matrix $L_{opt}$. The authors prove that $L_{opt}$ can be computed as $J_{opt} \otimes C^T$, where $J_{opt}$ is derived from the Kleene star of the system matrix and the input/output matrices.
4. Online Estimation Algorithm: The proposed algorithm operates in two steps. First, it computes the optimal gain $L_{opt}$ offline. Second, during online operation, it updates the state estimate $\hat{x}_t$ at any time $t$ using only the history of observed events (firing times of $u$ and $y$ up to time $t$). The authors demonstrate that despite the infinite dimensionality of the matrices, the estimation can be performed in polynomial time relative to the number of system transitions and observed events.

Key Contributions

• Extension of Luenberger Observers: The paper successfully generalizes the Luenberger observer from TEGs to P-TEGs, enabling the exploitation of upper-bound constraints for improved state estimation.
• Handling Upper-Bound Constraints: By utilizing infinite vector representation, the authors provide a rigorous algebraic framework to incorporate time-window constraints directly into the observer design, allowing for "refined estimations" that prevent the prediction of impossible trajectories (those leading to token death).
• Optimal Gain Derivation: The paper provides a closed-form solution for the optimal observer matrix $L_{opt}$, proving that it yields the greatest possible estimate of the internal state that is consistent with all available measurements and system constraints.
• Computational Efficiency: The work establishes that the online estimation step is computationally feasible (polynomial time), making the approach viable for practical implementation.

Results
The paper validates the proposed method using a numerical example (a P-TEG with three internal transitions and time-window constraints).

• Convergence: The observer converges to the actual firing times of the internal transitions as more output data becomes available, with the exception of one specific firing time (the second firing of transition $x_1$) which remains permanently underestimated by 1 time unit.
• Accuracy Improvement: A comparative analysis shows that the proposed observer, which utilizes upper-bound constraints, provides estimates that are greater than or equal to those obtained by a standard TEG-based observer (which ignores upper bounds). For the measured output transition, both observers yield identical estimates. For unmeasured internal transitions, the proposed observer provides strictly better (larger) estimates in most cases; for instance, at a specific time step, the proposed observer correctly adjusted an estimate from 5 to 6 to avoid a predicted token death, whereas the standard observer failed to make this correction, resulting in a less accurate (smaller) estimate.
• Consistency: The algorithm ensures that the estimated trajectory remains consistent with the P-TEG's structural constraints, avoiding the prediction of non-consistent trajectories.

Significance and Claims
The authors claim that this work provides a systematic method for state estimation in P-TEGs that leverages the full modeling power of these graphs, specifically the upper-bound constraints often found in real-world systems (e.g., deadlines, processing time windows). The paper emphasizes that unlike previous approaches for P-time Petri nets that compute all possible consistent sequences (which can be computationally expensive and do not require finite reachability sets), this observer provides the best occurrence time estimates directly. The significance lies in the ability to perform accurate online monitoring of complex discrete event systems where timing constraints are critical, without requiring the reachability set of the underlying net to be finite. The work is presented as a direct extension of existing TEG observer theory, adapted to handle the specific algebraic challenges posed by P-TEGs.