⚡ electrical engineering

A Luenberger Observer for P-Time Event Graphs

本文提出了一种针对 P-Time 事件图（P-Time Event Graphs）的 Luenberger 观测器算法，该算法通过引入停留时间上界约束来估计未观测转换的触发时刻，从而实现比传统定时事件图（Timed Event Graph）观测器更准确的结果。

原作者： Dominik Tirpák, Davide Zorzenon, Jörg Raisch

发布于 2026-08-04

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Dominik Tirpák, Davide Zorzenon, Jörg Raisch

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在观察一个繁忙的工厂车间，但你只能看到原材料进入的前门和成品离开的后门。在内部，机器、传送带和工人正在进行一场复杂的舞蹈，但中间部分是一个黑匣子。你了解规则：一个组件不能过早离开某个站台（它需要冷却时间），也不能停留太久（它可能会熔化或过期）。这就是离散事件系统（Discrete Event Systems）的世界，它是研究事物如何以步骤而非像水流一样连续变化的一门科学。为了理解这些系统，科学家们使用了一种名为Petri网（Petri Net）的工具，它就像是一张由在场所（places）和变迁（transitions）之间移动的令牌（小点）组成的地图。当时间被加入其中时，它就变成了一个定时事件图（Timed Event Graph），其中每一次移动都有其预定的时间表。但现实生活是复杂的；有时任务会有截止日期。这篇论文探讨了P-时间事件图（P-Time Event Graphs），这是该地图的一个增强版本，它为每一个步骤都包含了“最早可能”和“最晚可能”的时间限制。为什么这很重要？因为在制造业或食品加工等行业中，错过截止日期可能会毁掉一件产品，而无需打开黑匣子就能精确了解内部发生的情况，是实现高效生产的终极目标。

本文的作者 Dominik Tirpák、Davide Zorzenon 和 Jörg Raisch 正试图解决一个特定的谜题：一个外部观察者在仅知道可见的起始和结束事件的时间的情况下，如何推测 P-时间事件图中隐藏事件的确切时机？他们基于一个经典的工具——Luenberger 观测器（Luenberger Observer），它就像一个聪明的猜测者，利用系统的模型来预测未来。然而，旧版本的观测器是为更简单的系统设计的，那些系统只关心最小等待时间。它不知道如何利用 P-时间事件图中拥有的“必须完成”的截止日期。作者的主要发现是一种升级了该观测器的新算法。通过结合上界约束（即截止日期），他们的新观测器能够对隐藏事件何时发生做出更敏锐、更准确的猜测。他们在数学上证明了这种新方法提供了一种“最佳”估计——即在不违反规则的前提下，隐藏事件可能发生的最后时间——且这种估计是基于现有信息的。

为了理解其运作方式，请想象一场接力赛，跑者（令牌）在各个站台之间传递接力棒（任务）。在简单的比赛中，你只知道一名跑者必须至少等待 5 秒才能传递接力棒。但在本文的版本中，还有一个规则：跑者必须在 10 秒内传递接力棒，否则就会被取消资格（令牌“死亡”）。观测器就像站在赛道外的教练，他只能看到发令枪响和终点线。教练拥有关于这场比赛的心智模型。如果教练只知道最小等待时间，他可能会猜测隐藏的跑者移动得很慢。但因为教练也知道 10 秒的截止日期，他可以意识到：“等等，如果终点线的跑者刚刚在 10 秒时跨过终点，那么隐藏的跑者现在肯定已经完成了接力棒的传递，否则他们就会被取消资格。”这一额外的信息迫使教练更新他的猜测，使其更加精确。

论文详细介绍了如何利用一种被称为**最大-加法代数（Max-Plus Algebra）**的工具，将这种直觉转化为严谨的数学配方。可以将它看作一种特殊的数学，其中“加法”意味着取两个数中的最大值，而“乘法”则意味着常规的加法。它是调度工作的完美语言，因为它能自然地处理“事情发生的最后时间”。作者将复杂的网络系统转化为描述时间流动的巨大无限矩阵（数字表格）。然后，他们设计了一个特定的“观测器矩阵”（用于教练心智模型的权重集），通过过滤来自起始线和终点线的数据来重建隐藏的时间线。

作者在涉及三个内部变迁（隐藏跑者）和各种时间窗口的具体案例上测试了他们的新算法。他们模拟了一个场景：隐藏事件在特定时间发生，但观测器只能看到输入和输出。结果显示，使用截止日期约束的新观测器迅速收敛到了正确的隐藏时间。例如，在某一时刻，观测器意识到一个隐藏事件不可能发生在时间 5，因为它会导致“令牌死亡”（违反时间窗口），因此它将猜测调整为时间 6。相比之下，他们将此与忽略截止日期的旧观测器进行了对比。旧的观测器准确性要低得多，经常给出过早的时间，并且完全忽略了约束条件。论文得出结论，通过同时遵循“最早”和“最晚”规则，新的观测器能为系统的内部运作提供更清晰的图景，同时其运行效率足以用于实时应用。

技术摘要：针对 P-Time 事件图的 Luenberger 观测器

问题陈述
本文研究了 P-Time 事件图（P-TEGs）的状态估计问题。P-TEGs 是一类用于建模制造和工业过程中同步及时间窗口约束的离散事件系统。与标准的定时事件图（TEGs）不同，P-TEGs 在标记（token）在库所（places）中的停留时间上同时包含了下界和上界约束。核心挑战在于，在仅能直接测量一部分转换（输出转换和可观测输入转换）的情况下，如何实时（在线）估计内部及不可观测转换的触发时刻。观测器必须在尊重系统结构约束并避免“标记死亡”（违反时间窗口约束）的前提下，提供尽可能准确的估计（即真实触发时间的最大下近似值）。

方法论
作者将先前基于 max-plus 代数建立在 TEG 上的经典 Luenberger 观测器框架，扩展到了更为复杂的 P-TEG 领域。该方法论依赖于以下技术支柱：

无穷向量表示法： 为了处理由上界约束和各种初始条件引入的不等式，本文采用了 dater 函数（将转换的第 $k$ 次触发映射到其发生时刻）的“无穷向量表示法”。这种方法作为 $\gamma$ 变换的一种灵活替代方案，后者在处理 P-TEGs 特有的特定不等式结构时表现较差。
代数公式化： P-TEG 的动力学通过线性 max-plus 差分方程和不等式系统进行建模。系统在无穷维向量空间中表示，通过涉及矩阵 $A$ 、 $B$ 、 $R$ 、 $C$ 以及编码上界约束的不等式矩阵 $U$ 的代数方程，将动态行为转化为代数方程。
观测器设计： 观测器的设计旨在寻找状态向量 $x$ $x$ 的最大子近似（greatest sub-approximation）。设计过程包括：
- 推导出一个封装了系统动力学和上界约束的“最大状态矩阵” $M^*$ 。
- 构建观测器方程 $\hat{x} = x_0 \oplus M \hat{x} \oplus Bu \oplus L(y \oplus \hat{y})$ ，其中 $L$ 是观测器增益矩阵。
- 通过求解不等式系统来确定最优观测器矩阵 $L_{opt}$ 。作者证明了 $L_{opt}$ 可以计算为 $J_{opt} \otimes C^T$ ，其中 $J_{opt}$ 是由系统矩阵和输入/输出矩阵的 Kleene 星号（Kleene star）导出的。
在线估计算法： 所提算法分为两个步骤运行。首先，离线计算最优增益 $L_{opt}$ 。其次，在在线运行期间，仅利用截至时间 $t$ 的观测事件历史（ $u$ 和 $y$ 的触发时刻），在任何时间 $t$ 更新状态估计值 $\hat{x}_t$ 。作者证明，尽管矩阵具有无穷维特性，但估计过程相对于系统转换数量和观测事件数量而言是多项式时间可行的。

核心贡献

Luenberger 观测器的扩展： 本文成功地将 Luenberger 观测器从 TEGs 推广到 P-TEGs，使得利用上界约束来改进状态估计成为可能。
处理上界约束： 通过利用无穷向量表示法，作者提供了一个严谨的代数框架，将时间窗口约束直接纳入观测器设计中，从而实现“精细化估计”，防止预测出不可能的轨迹（即导致标记死亡的轨迹）。
最优增益推导： 本文提供了一个闭式解（closed-form solution）来计算最优观测器矩阵 $L_{opt}$ ，并证明了它能产生与所有可用测量值及系统约束相一致的最大状态估计值。
计算效率： 本研究确立了在线估计步骤在计算上的可行性（多项式时间），使其适用于实际应用中的在线监控。

结果
本文通过一个数值示例（一个具有三个内部转换和时间窗口约束的 P-TEG）验证了所提方法。

收敛性： 随着输出数据变得更加丰富，观测器会收敛到内部转换的实际触发时刻，唯独有一个特定的触发时刻（转换 $x_1$ 的第二次触发）会始终被低估 1 个时间单位。
精度提升： 对比分析表明，所提观测器由于利用了上界约束，其提供的估计值大于或等于基于标准 TEG 的观测器（后者忽略了上界）。对于测量的输出转换，两种观测器产生的估计值相同。对于未测量的内部转换，所提观测器在大多数情况下提供了更优（更大）的估计；例如，在特定时间步，所提观测器为了避免预测到的标记死亡，将估计值从 5 修正为 6，而标准观测器未能做出此项修正，导致了较差（较小）的估计。
一致性： 该算法确保了估计的轨迹与 P-TEG 的结构约束保持一致，避免了预测出不一致的轨迹。

意义与主张
作者声称，这项工作为 P-TEG 提供了一种系统性的状态估计方法，能够充分利用这些图的全套建模能力，特别是现实世界系统中常见的上界约束（如截止日期、处理时间窗口）。论文强调，与以往计算所有可能的一致序列（这可能涉及高昂的计算成本且不要求有限的可达集）的 P-时间 Petri 网方法不同，本观测器能直接提供“最佳”的发生时刻估计。其意义在于，能够在无需底层网具有有限可达集的情况下，对时间约束至关重要的复杂离散事件系统进行精确的在线监控。该工作被视为对现有 TEG 观测器理论的直接扩展，并针对处理 P-TEG 所带来的特定代数挑战进行了适配。

类似论文