Online Tracking with Predictions for Nonlinear Systems with Koopman Linear Embedding

本文针对具有 Koopman 线性嵌入结构的未知非线性系统，提出了一种基于 Willems 基本引理和滚动时域框架的无模型预测跟踪算法，证明了该算法在非线性系统中的累积代价与动态 regret 等同于其提升后的线性系统，并实现了随预测视界增加而指数级衰减的动态 regret。

要点

这篇论文讲述了一个关于**“如何在看不见的未来中，让机器人或系统完美跟随目标”**的故事。

想象一下，你正在玩一个极其复杂的**“无人驾驶赛车游戏”**。

1. 核心挑战：迷雾中的追逐

在这个游戏中，你的任务是驾驶一辆车（系统），紧紧跟随前方一辆不断变速、变向的“目标车”（目标轨迹）。

• 困难点一（非线性）： 你的车不是普通的汽车，它的物理规则非常奇怪（非线性）。比如，你踩一点油门，速度可能不是线性增加，而是突然爆发；或者转弯时，车身会像液体一样晃动。你根本不知道这辆车的内部构造（未知动力学）。
• 困难点二（只有短视）： 你手里没有全剧透的剧本。你只能看到前方短短几秒的目标车会去哪里（短视预测）。几秒之后，目标车要去哪，完全未知，甚至可能是个故意捣乱的对手（对抗性环境）。
• 困难点三（不能试错）： 你不能像新手一样乱撞来学习规则，因为一旦撞车（误差太大），后果很严重。你需要一种聪明的方法，利用过去的数据来指导现在的行动。

2. 天才的解决方案：给世界“升维”

论文提出了一种名为**“Koopman 线性嵌入”**的魔法。

通俗比喻：把“乱舞的蝴蝶”变成“整齐的方阵”
想象你的车在三维空间里乱飞，轨迹像醉汉走路一样难以预测（非线性）。

• 传统方法： 试图去解这个醉汉的每一步方程，太难了。
• Koopman 魔法： 作者说，如果我们把视角拉高，或者把这个世界“升维”（Lifting），进入一个更高维度的空间，你会发现，那个醉汉的轨迹在这个新空间里，竟然变成了一条笔直的线！
  • 在这个“新空间”里，原本复杂的非线性规则，瞬间变成了简单的线性规则（就像 $y = ax + b$ 一样简单）。
  • 虽然我们在现实中看到的是乱飞的蝴蝶，但在“升维”后的空间里，它们排着整齐的队伍在走直线。

3. 核心算法：不用说明书的“数据驱动”

既然知道了在“新空间”里规则很简单，那怎么控制呢？
通常，我们需要知道车的说明书（模型）才能设计控制器。但作者说：“不需要说明书！”

他们使用了一种基于**“威利斯基本引理” (Willems' Fundamental Lemma)** 的数据驱动预测控制 (DDPC)。

生活类比：老厨师的直觉
想象一位老厨师（算法），他不知道做菜的化学公式（没有系统模型），但他看过成千上万次别人做这道菜的过程（离线数据）。

• 当新任务来了（要跟随目标），他不需要重新学习化学，而是直接翻看过去的记录：“哦，上次在类似的情况下，加一点盐（控制动作），味道就对了。”
• 这篇论文的方法就是：利用过去收集的大量轨迹数据，直接构建出一个“预测器”。 它不需要知道车的引擎原理，只需要知道“过去怎么动，未来就会怎么动”。

4. 为什么这个方法很牛？（动态后悔值）

论文引入了一个概念叫**“动态后悔值” (Dynamic Regret)**。

• 什么是后悔？ 就是比较“你现在的表现”和“如果你拥有上帝视角（知道未来所有目标轨迹）并完美控制”之间的差距。
• 论文的发现：
  1. 等价性： 在“升维”后的空间里，控制这个复杂非线性系统的难度，和控制一个简单线性系统是一模一样的。
  2. 指数级衰减： 这是最惊人的结论。只要你的**“预测视野” (Prediction Horizon)** 稍微长一点点（比如从看前 1 秒变成看前 5 秒），你的“后悔值”就会呈指数级下降。
  • 比喻： 就像你在迷雾中开车，如果你只能看前 1 米，你会经常撞墙；如果你能看前 10 米，你不仅能避开障碍，还能丝滑过弯。这篇论文证明了，只要视野够长，即使不知道车是怎么造的，你也能开得和“上帝视角”一样好。

5. 实验验证

作者在电脑里模拟了一个复杂的非线性系统（就像那个乱飞的蝴蝶），并让算法去追踪一个正弦波动的目标。

• 结果： 随着预测视野（W）的增加，追踪误差迅速减小，曲线变得非常平滑。这证明了理论是成立的。
• 额外彩蛋： 他们还测试了一个**“两轮机器人”**（这种机器人通常很难用线性方法控制，甚至不完全符合“升维”条件）。通过一种“正则化”的变通方法（允许一点点误差，并挑选最重要的数据），机器人也能很好地追踪心形轨迹。这暗示了该方法即使在不完美条件下也有很强的鲁棒性。

总结

这篇论文的核心思想是：
面对未知且复杂的非线性世界，我们不需要知道它的物理公式。只要我们能把它“升维”到一个简单的线性空间，并利用过去的数据进行“短视预测”，我们就能以极低的代价，实现近乎完美的追踪控制。

这就好比，虽然你不懂空气动力学，但只要你看过足够多的飞鸟数据，并且能预判前方几秒的气流，你就能造出一架能完美跟随大雁迁徙的无人机。

技术摘要

这篇论文提出了一种针对未知非线性动力学系统的在线跟踪（Online Tracking）方法，特别适用于仅能获得短期目标状态预测的场景。文章的核心创新在于利用Koopman 算子理论将非线性系统嵌入到线性空间，并结合Willems 基本引理的扩展形式，设计了一种无需显式系统辨识的**数据驱动预测控制（Data-Driven Predictive Control, DDPC）算法，并给出了严格的动态遗憾（Dynamic Regret）**理论保证。

以下是该论文的详细技术总结：

1. 问题背景与定义 (Problem Setup)

• 核心问题：在未知非线性动力学系统 $z_{t+1} = f(z_t, u_t)$ 中，智能体需要在有限时间 horizon $T$ 内跟踪一个时变的目标轨迹 $r_{1:T}$。
• 约束条件：
  • 系统动力学 $f$ 未知。
  • 目标轨迹 $r$ 未知或具有对抗性，但在每个时间步 $t$，智能体可以获得未来 $W$ 步的短期预测 $r_{t:t+W-1}$。
  • 目标是极小化累积跟踪误差和控制代价：$J_T = \sum (\|z_t - r_t\|^2_{Q_z} + \|u_t\|^2_R)$。
• 性能指标：使用**动态遗憾（Dynamic Regret）**来衡量性能，即在线策略的累积代价与“事后最优（Hindsight Optimal）”非因果策略（已知完整轨迹和系统动力学）的代价之差。
• 系统假设：系统属于**Koopman 可线性化（Koopman-linearizable）**类。即存在一个提升函数 $\psi$ 和矩阵 $(A, B, C)$，使得提升后的状态 $x_t = \psi(z_t)$ 满足线性动力学 $x_{t+1} = Ax_t + Bu_t$，且原状态 $z_t = Cx_t$。

2. 方法论 (Methodology)

论文提出了一种统一的预测跟踪框架（Algorithm 1），包含三种变体，最终聚焦于数据驱动预测控制（DDPC）：

A. 理论等价性 (Theoretical Equivalence)

• Koopman 提升：利用 Koopman 嵌入，将原始的非线性跟踪问题转化为提升空间中的线性二次跟踪问题（LQT）。
• 代价等价：证明了原始非线性系统的累积代价与提升后线性系统的累积代价完全相等（Lemma 3.1）。因此，分析线性空间的动态遗憾即可代表非线性系统的性能。
• 最优策略：推导了提升空间中具有完整未来信息的离线最优策略的闭式解（基于 Riccati 递归和前馈增益）。

B. 预测控制算法 (Predictive Control)

文章对比了三种 MPC 形式：

1. 非线性 MPC (N-MPC)：直接使用非线性模型（假设已知）。
2. 提升线性 MPC (L-MPC)：使用已知的 Koopman 线性模型。
3. 数据驱动 MPC (DDPC)：本文的核心。在动力学和 Koopman 嵌入均未知的情况下，仅利用离线采集的轨迹数据 $(u_d, z_d)$。

DDPC 的核心机制：

• 基于扩展的 Willems 基本引理（Extended Willems' Fundamental Lemma）。
• 构建数据矩阵 $H_d$，将非线性系统的动力学约束转化为线性等式约束：$H_d g = [u_{ini}, u_{pred}, z_{ini}, z_{pred}]^T$。
• 在每一步，求解一个二次规划（QP）问题，在满足数据驱动动力学约束的前提下，最小化预测 horizon 内的跟踪代价。
• 优势：无需显式辨识系统模型或选择提升函数，直接将非线性约束转化为线性约束。

3. 主要贡献 (Key Contributions)

1. 首个非线性系统的动态遗憾保证：

   • 这是首次为未知 Koopman 可线性化非线性系统的在线跟踪提供动态遗憾界限。
   • 证明了累积遗憾随总时间 $T$ 线性增长，但随预测 horizon $W$ 指数级衰减。

2. 无终端代价的稳定性保证：

   • 传统 MPC 通常依赖精心设计的终端代价（Terminal Cost）来保证稳定性。
   • 本文证明，对于 Koopman 可线性化系统，仅通过足够长的预测 horizon（$W \ge \Delta_{stab}$）即可保证状态有界和稳定性，无需终端代价。

3. 弱假设下的理论分析：

   • 不同于大多数基于正定阶段代价（Positive Definite Stage Cost）的遗憾分析，本文在**半正定（Positive Semidefinite）代价矩阵和可检测性（Detectability）**的较弱假设下证明了结果。这是因为 Koopman 提升矩阵 $C$ 通常不是满秩的，导致提升后的代价矩阵 $Q$ 仅为半正定。

4. 理论界限形式：

   • 动态遗憾界限为：$\text{Reg}_T = O(W^2 \lambda_\infty^{2W} T)$，其中 $\lambda_\infty < 1$ 是与系统参数相关的衰减因子。
   • 这意味着当 $W = \Theta(\log T)$ 时，可以实现 $O(1)$ 的常数级遗憾。

4. 实验结果 (Results)

• 数值实验：
  • 在一个具体的 Koopman 可线性化非线性系统（Example 2.1 的变体）上验证了理论。
  • 结果：随着预测 horizon $W$ 的增加，跟踪误差迅速减小，动态遗憾呈指数级下降，与理论界限 $\lambda_\infty^{2W}$ 高度吻合。
  • 观察到了控制代价矩阵 $R$ 和目标幅度 $M$ 对衰减率的影响。
• 扩展实验（附录 D）：
  • 针对不可 Koopman 线性化的系统（如两轮机器人），提出了带正则化项（L1 范数）和松弛变量的改进版 DDPC。
  • 通过基于状态的数据库切换策略（根据机器人航向角选择局部数据），实现了对心形轨迹的有效跟踪，展示了方法的鲁棒性和扩展性。

5. 意义与影响 (Significance)

• 理论突破：填补了非线性系统在线控制中动态遗憾分析的空白，特别是将 Koopman 理论与在线学习（Online Learning）中的遗憾分析相结合。
• 实际应用价值：提供了一种**模型无关（Model-free）**的解决方案。在实际工程中，获取精确的非线性模型或 Koopman 提升函数往往非常困难，而该方法仅需离线数据即可实现具有理论保证的高性能跟踪。
• 算法设计启示：证明了在特定结构（Koopman 线性化）下，预测 horizon 的长度是控制性能的关键，而非传统的终端代价设计，这为简化 MPC 算法设计提供了新思路。

总结

该论文成功地将 Koopman 线性化思想应用于数据驱动的在线控制，提出了一种无需系统辨识的预测跟踪算法，并首次从理论上证明了其在动态环境下的性能界限。该方法不仅适用于理想的 Koopman 系统，还通过正则化手段扩展到了更一般的非线性系统，为机器人、自动驾驶等领域的自适应控制提供了强有力的理论工具。