⚡ electrical engineering

On the Computation of Backward Reachable Sets for Max-Plus Linear Systems with Disturbances

本文针对具有加性扰动的不确定最大加线性系统，提出了一种基于热带多面体的计算框架，证明了相关反向算子能保持热带多面体结构，从而实现了安全分析中前向可达集的有效构造性计算。

原作者： Yuda Li, Xiang Yin

发布于 2026-03-31

📖 1 分钟阅读☕ 轻松阅读

原作者： Yuda Li, Xiang Yin

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

这篇论文探讨了一个非常有趣且实用的问题：如何在一个充满不确定性的“时间调度系统”中，确保它永远不“出事”？

为了让你轻松理解，我们可以把这篇论文里的概念想象成**“在暴风雨中驾驶一辆特殊的卡车”**。

1. 背景：什么是“最大 - 加”系统？

想象一下，你经营着一家物流车队，或者管理着一条繁忙的地铁线。

普通数学：通常我们做加法（ $1+1=2$ ）和乘法。
最大 - 加数学（Max-Plus Algebra）：在这个世界里，“加法”变成了“取最大值”（比如：两辆车同时到达，系统只关心最晚到达的那一辆），“乘法”变成了“普通加法”（比如：路程时间累加）。

这种数学非常适合描述**“等待”和“同步”**。比如，地铁要等所有乘客都上车了才能发车，或者工厂要等所有零件都到了才能组装。

2. 核心问题：暴风雨中的“安全倒车”

现在，你的卡车（系统）要执行任务，但路上有**“暴风雨”（干扰/扰动）**。

目标：你有一个**“安全区”（目标集）**，比如“必须在下午 5 点前到达仓库”。
挑战：
1. 你可以控制油门（控制输入），决定什么时候出发。
2. 但你无法控制天气（干扰），暴风雨可能让车变慢，也可能让路变堵。
3. 关键问题：为了无论暴风雨怎么刮，车都能一定在 5 点前安全到达，你现在应该站在什么位置（状态）？

这就叫**“后向可达集”（Backward Reachable Set）。简单来说，就是“为了安全，我们允许从哪些地方出发？”**

3. 以前的难题：太复杂了！

以前的方法就像是用**“笨重的计算器”**去算这个安全范围。

如果系统很简单，还能算出来。
一旦系统变大（比如几十辆车、几百个站点），或者干扰很复杂，计算量就会爆炸，算到电脑死机也算不出结果。
以前的方法通常把干扰想象成简单的“区间”（比如：延误在 0 到 10 分钟之间），但这不够灵活，无法描述复杂的干扰模式。

4. 这篇论文的妙招：热带几何（Tropical Polyhedra）

作者提出了一种全新的、更聪明的方法，他们引入了一个叫**“热带多面体”（Tropical Polyhedra）**的概念。

🌟 创意比喻：乐高积木与魔法滤镜

以前的方法：像是在用泥巴去捏形状。你想把泥巴捏成复杂的形状，稍微动一下，形状就变了，很难保持规则。
作者的方法：像是用乐高积木。
- 他们把“安全区”、“控制范围”和“干扰范围”都看作是由特定形状的**乐高积木（热带多面体）**拼成的。
- 这种积木有一个神奇的特性：无论你怎么推、怎么拉（进行数学运算），它们拼出来的新形状，依然还是乐高积木！

具体步骤如下：

把问题变成积木：
作者把“安全区”、“你能控制的油门范围”、“暴风雨的干扰范围”全部画成这种特殊的“热带积木”。
神奇的“反向过滤器”：
他们设计了三个“魔法滤镜”（算子），用来从后往前推：
- 滤镜 A（系统动态）：把时间倒流，看看车是怎么开过来的。
- 滤镜 B（干扰过滤）：这是最难的！它要确保**“无论暴风雨怎么刮”**，车都在安全区。作者发现，只要把“暴风雨”的积木和“安全区”的积木进行一种特殊的“交集”运算，就能把那些“会被吹出安全区”的坏位置剔除掉。
- 滤镜 C（控制过滤）：看看有没有一种“油门操作”，能把车推回安全区。
保持形状不变：
最厉害的地方在于，作者证明了：不管你怎么用这三个滤镜去处理，最后剩下的“安全出发区域”，依然是一个完美的“热带积木”！
这意味着，我们不需要把形状打碎重算，只需要在积木的“骨架”（生成向量）上动动手脚，就能算出新的安全范围。

5. 结果与意义

结果：作者不仅证明了这种方法是可行的，还给出了具体的**“计算公式”**（算法），告诉计算机如何一步步把这些“积木”拼好、切好，最后得到那个完美的“安全出发区域”。
意义：
- 更安全：对于地铁、工厂流水线、交通网络，这种方法能更精确地算出“只要在这个范围内，无论发生什么意外，系统都不会崩溃”。
- 更高效：因为保持了“积木”的结构，计算机算起来快得多，不再容易死机。
- 更灵活：以前只能处理简单的“区间”干扰，现在可以处理更复杂、更真实的干扰模式。

总结

这篇论文就像是给**“不确定性系统”设计了一套“乐高安全指南”**。

它告诉我们：面对复杂的干扰（暴风雨），我们不需要惊慌失措地用笨办法去算。只要把问题转化成特殊的“热带积木”语言，利用它们**“怎么算都不变形”的几何特性，我们就能轻松、精确地找到那条“绝对安全”的出发路线**。

这对于未来设计更智能、更安全的自动驾驶、智能电网和物流系统，提供了非常强大的数学工具。

这是一份关于论文《On the Computation of Backward Reachable Sets for Max-Plus Linear Systems with Disturbances》（带扰动的 Max-Plus 线性系统逆向可达集计算）的详细技术总结。

1. 研究背景与问题定义 (Problem Definition)

背景：
Max-Plus 线性系统（MPLS）是描述离散事件系统（如制造、交通调度）的重要模型，特别适用于处理同步和延迟效应。然而，实际应用中系统常受扰动、建模误差或参数变化的影响，这使得可达性分析和控制器设计极具挑战性。

核心问题：
本文研究的是**带扰动的 Max-Plus 线性系统的单步逆向可达性（Backward Reachability）**问题。

输入： 给定一个目标集 $E$ （Target Set）。
目标： 计算所有初始状态 $x$ 的集合，使得存在一个允许的控制输入 $u$ ，对于所有允许的扰动 $w$ ，系统的下一状态 $x_{k+1}$ 都能保持在目标集 $E$ 内。
数学表述：
$\Upsilon(E) = \{ x \mid \exists u \in U, \forall w \in W, A \otimes x \oplus B \otimes u \oplus C \otimes w \in E \}$
其中 $U$ 为控制集， $W$ 为扰动集。该问题与安全性分析（Safety Analysis）和受控不变性（Controlled Invariance）紧密相关。

挑战：
现有的基于差界矩阵（DBM）的方法在处理高维系统或复杂不确定性结构时计算复杂度极高。此外，扰动带来的“全称量词”（ $\forall w$ ）使得逆向算子的结构分析比无扰动情况困难得多。

2. 方法论 (Methodology)

本文提出了一种基于**热带凸几何（Tropical Convexity）和热带多胞形（Tropical Polyhedra）**的计算框架。

2.1 核心假设

目标集 $E$ 、控制集 $U$ 和扰动集 $W$ 均被建模为热带多胞形（Tropical Polyhedra）。
利用热带多胞形的“外表示”（M-形式，即半空间交集）和“内表示”（V-形式，即生成元集合）之间的转换特性。

2.2 算子分解

逆向可达算子 $\Upsilon$ 被分解为三个基本集合值算子的复合：
$\Upsilon = A^{-1} \circ \gamma_U \circ \phi_W$

$A^{-1}$ (逆算子)： 处理系统动力学 $x \to Ax$ 。
$\gamma_U$ (存在性逆算子)： 处理控制输入 $\exists u$ 。
$\phi_W$ (全称逆算子)： 处理扰动 $\forall w$ ，这是最复杂的部分。

2.3 关键算法步骤

A. 保持结构性质 (Structure Preservation)
论文证明了上述三个算子均能保持热带多胞形的结构。即，如果输入集是热带多胞形，输出集仍然是热带多胞形。这使得可以在同一框架下进行迭代计算。

B. $A^{-1}$ 和 $\gamma_U$ 的计算

利用线性映射和投影的性质，将问题转化为热带锥（Tropical Cone）的投影问题。
通过构造增广矩阵，将逆向集表示为新的热带多胞形的外表示（M-形式）。

C. $\phi_W$ (扰动处理) 的深入分析
这是本文的核心贡献，分为三个步骤：

简化步骤 (Simplification)： 利用扰动集 $W$ 的分解 $W = P \oplus R$ （有界多胞形 $P$ 与 recession 锥 $R$ 的和）。证明了如果 $R$ 包含在目标集对应的锥中，则 $\phi_W(Z) = \phi_P(Z)$ ，从而将问题简化为处理有界集。
伪半空间 (Pseudo Half-Space) 重构： 将 $\phi_P(Z)$ 表示为一系列“伪半空间”的交集。伪半空间定义为满足特定不等式条件的集合，其补集在加法和数乘下稳定。
生成集计算 (Generating Set Computation)：
- 利用类似 Minkowski-Carathéodory 定理的性质，证明了伪半空间的交集是有限生成的热带锥。
- 提出了递归算法：从一个生成集开始，逐个与伪半空间求交。
- 关键公式： 对于生成元 $v$ （在集合内）和 $w$ （在集合外），计算最大标量 $\rho$ 使得 $v \oplus \rho \cdot w$ 进入集合边界。该 $\rho$ 可通过解析公式计算：
  $\rho_{v,w} = \min_{u \in U, w \notin H^u} \left( (d|v \oplus v_1 u) - (c|w \oplus w_1 u) \right)$
- 引入了极值点过滤 (Extremal Points Filtering) 机制，利用有向超图（Directed Hypergraph）和强连通分量（SCC）来剔除冗余生成元，降低计算复杂度。

3. 主要贡献 (Key Contributions)

理论框架创新： 首次系统地建立了基于热带多胞形的带扰动 Max-Plus 系统逆向可达性分析框架。
结构保持性证明： 严格证明了在存在扰动（全称量化）的情况下，逆向可达集仍保持热带多胞形结构，解决了此前关于该结构是否保持的疑问。
构造性算法： 提出了具体的计算算法，包括：
- 扰动集 recession 锥的简化处理。
- 基于伪半空间交集的生成集递归更新方法。
- 极值点过滤优化策略，提高了算法效率。
几何视角： 为不确定性 Max-Plus 系统的安全性分析提供了新的几何和代数工具，超越了传统的区间或概率方法。

4. 实验结果 (Results)

案例研究 (Case Study)： 论文通过一个二维 Max-Plus 线性系统的数值算例进行了验证。
- 系统包含状态矩阵 $A$ 、控制矩阵 $B$ 和扰动矩阵 $C$ 。
- 扰动集 $W$ 被定义为热带多胞形，控制集 $U$ 为全空间。
- 目标集 $S$ 为热带锥。
计算过程： 逐步计算了 $\phi_W(S)$ （考虑扰动后的安全集）、 $\gamma_U(\cdot)$ （考虑控制后的集合）以及最终的 $A^{-1}(\cdot)$ 。
可视化： 论文通过图表展示了原始安全集、扰动集以及最终逆向可达集的几何形状，验证了算法能够正确计算出满足安全约束的状态区域。

5. 意义与展望 (Significance & Future Work)

意义：

安全性验证： 该方法为具有确定性边界扰动的离散事件系统提供了严格的安全性验证工具，能够计算出“安全集”（Safe Set），即从这些状态出发，总能通过控制避免进入不安全区域。
控制器综合： 逆向可达集是合成安全保持控制器（Safety-preserving controllers）的基础。
计算效率： 相比于将系统转化为分段仿射表示再使用 DBM 的方法，基于热带多胞形的方法在处理特定结构的不确定性时可能具有更好的可扩展性，且保持了紧凑的几何表示。

未来工作：

进一步优化算法的计算效率，可能通过牺牲部分精度来换取速度。
将框架扩展到系统参数本身存在不确定性的情况（而不仅仅是外部扰动）。

总结

这篇文章通过引入热带凸几何理论，成功解决了带扰动 Max-Plus 线性系统逆向可达集的计算难题。其核心在于证明了逆向算子对热带多胞形结构的保持性，并开发了一套基于生成元更新和极值点过滤的构造性算法。这为复杂离散事件系统的安全分析与控制设计提供了强有力的数学工具。