🤖 AI

Online Goal Recognition using Path Signature and Dynamic Time Warping

本文提出了一种面向连续域的新型在线目标识别方法，该方法利用路径签名高效编码与比较轨迹，在预测准确性和规划效率方面均展现出优于最先进方法的性能。

原作者： Douglas Tesch, Nathan Gavenski, Leonardo Amado, Odinaldo Rodrigues, Felipe Meneguzzi

发布于 2026-05-11

📖 1 分钟阅读☕ 轻松阅读

原作者： Douglas Tesch, Nathan Gavenski, Leonardo Amado, Odinaldo Rodrigues, Felipe Meneguzzi

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

想象一下，你正在观察一位朋友穿过一个巨大而复杂的迷宫。你只能每隔几秒钟看到他们一次，有时他们走得快，有时走得慢，有时你甚至会错过一两个步骤。你的任务是在他们到达之前，猜出他们试图前往哪里。

这就是在线目标识别（Online Goal Recognition）的问题。你提供的这篇论文介绍了一种更聪明的方法来解决这个谜题，特别是当“迷宫”是连续空间（例如机器人在地板上移动）而非网格方格时。

以下是作者道格拉斯·特施（Douglas Tesch）及其团队如何解决这一问题的解释，通过简单的类比进行说明。

问题：“规划器过多”的瓶颈

传统上，为了猜测目标，计算机会表现得像一位 frantic 的导游。每当看到朋友迈出新的步伐，他们就会停下来，为迷宫中的每一个可能的出口运行模拟，计算通往每个出口的完美路径，并将其与刚刚观察到的情况进行比较。

问题所在：这极其缓慢。如果有 100 个可能的出口，计算机必须在朋友迈出每一步时运行 100 次模拟。这就像每次你咬一口食物时，都要让厨师烹饪 100 道不同的菜肴，只为猜测你渴望的是哪一道。

解决方案：移动的“指纹”

作者提出了一种名为GRPS（基于路径签名的目标识别）的新方法。他们不使用从头模拟每条路径的方式，而是利用两个巧妙的工具：路径签名（Path Signatures）和动态时间规整（Dynamic Time Warping）。

1. 路径签名：旅程的"DNA"

想象你在沙滩上有一长串蜿蜒的脚印。

旧方法：你逐个查看脚印，试图记住每一步的确切形状。
论文的方法（路径签名）：你拍摄整个路径的“快照”或指纹。这个指纹捕捉了移动的本质——曲线、转弯、节奏——而无需记住每一粒沙子。

作者使用一个名为“路径签名”的数学概念，将漫长而杂乱的路径转化为紧凑的、固定长度的代码。

为何酷：这个代码是独一无二的。没有两条不同的路径拥有完全相同的代码。这就像移动的 DNA 测试。即使两个人以不同的速度走同一条路线，签名也能捕捉旅程的形状，使其易于比较。

2. 轨迹树：路线的“图书馆”

在朋友开始行走之前，计算机为每个可能的目标构建了一个巨大的可能路线（轨迹）库。

计算机不是将这些路线作为单独的、杂乱的文件保存，而是将它们组织成一个树状结构。
如果两条路线开始时都是沿着走廊直走，它们就在树上共享同一个“分支”。只有当它们到达分岔路口时，才会分开。
合并与剪枝：有时，两条路线几乎完全相同（例如直走 10 步与直走 10.1 步）。计算机将这些相似的分支“合并”以节省空间，并“剪除”（切断）那些不改变目的地的小幅、无意义的晃动。这使得图书馆保持小巧且搜索迅速。

3. 动态时间规整（DTW）：“橡皮筋”

这里是棘手之处：如果你的朋友走得很快，但图书馆中的路线是为慢速行走者计算的呢？或者如果你错过了观察他们的几秒钟呢？

问题：如果你尝试将快走与慢走进行逐步比较，它们将无法匹配。这就像试图通过将节拍完全对齐来将一首快歌与一首慢歌匹配；结果看起来一团糟。
解决方案（DTW）：想象行走的时间线是由橡胶制成的。动态时间规整会拉伸或压缩观察到的行走的“橡皮筋”，直到它与图书馆中的路线完美契合。它将“快步骤”与“慢步骤”对齐，这样你就能看到它们实际上正前往同一个地方，即使时间上有偏差。

在现实生活中的运作方式

离线（准备阶段）：计算机使用路径签名构建其“路线库”（树）。它通过合并相似路径并切断微小细节来清理它。这需要一些时间，但只发生一次。
在线（实时）：随着朋友行走：
- 计算机对迄今为止看到的路径快速提取“指纹”（签名）。
- 它将此指纹与图书馆树进行比较。
- 如果朋友以奇怪的速度移动，或者你错过了一步，它会使用橡皮筋（DTW）来拉伸比较，使其吻合。
- 它立即计算出哪个“目标”（出口）是最可能的匹配项。

结果：更快、更智能

作者在两种类型的世界中测试了这种方法：

连续世界（机器人在开放空间中移动）：他们的方法是最快且最准确的。在早期猜测目标方面，它显著优于以前的方法，并且无需为每一步运行昂贵的模拟。
离散世界（基于网格的谜题）：它的表现与现有最佳方法一样好，证明它适用于不同类型的问题。

核心结论

该论文声称，通过将移动视为独特的“指纹”（路径签名），并使用“橡皮筋”来对齐不同的速度（DTW），我们可以比以前更快、更准确地猜测智能体将前往何处。

不使用 DTW：速度极快（约 30 毫秒），非常适合实时机器人。
使用 DTW：速度稍慢，但更准确，非常适合数据杂乱或时间不准的情况。

作者得出结论，这种方法消除了对繁重、缓慢的计算机模拟的需求，使目标识别适用于现实世界中快速移动的应用场景。

技术摘要：基于路径签名与动态时间规整的在线目标识别

问题定义

本文探讨了连续域和离散域中的**在线目标识别（OGR）**问题。核心挑战在于，在智能体仍与环境交互的过程中，仅根据其轨迹的稀疏、序列观测来推断其目标。

连续域中的现有方法面临两个主要局限：

计算开销：传统方法通常依赖对每个新观测和每个目标假设重复调用规划器，其计算量随目标数量和观测数量线性增长。这对于实时应用而言是不切实际的。
表征不足：当前的状态编码往往依赖原始状态信息（如位置、速度），无法捕捉区分不同目标所需的时序结构和语义行为模式，特别是在噪声或观测不完整的情况下。

此外，比较长度各异、含噪声或具有非欧几里得距离的轨迹仍然是一个重大障碍，特别是在高速移动的机器人应用中。

方法论：GRPS

作者提出了基于路径签名的目标识别（GRPS），这是一个数据驱动框架，利用**路径签名（Path Signatures）和动态时间规整（DTW）**来高效地编码和比较轨迹。

1. 用于轨迹编码的路径签名

GRPS 不使用原始状态，而是利用来自粗糙路径理论（rough path theory）的数学工具——路径签名。

表征：路径签名将任意大小的数据序列（轨迹）转换为唯一的、固定长度的特征向量。
性质：这些表征具有重参数化不变性，并能自然地捕捉多尺度依赖关系以及几何/时序结构。
唯一性：除非生成轨迹完全相同，否则没有两个路径签名是相等的，这使得轨迹前缀与其编码签名之间能够建立一一对应关系。

2. 轨迹树构建（离线阶段）

为了避免实时规划，GRPS 预先计算一个轨迹树（$TT$）：

采样：对于每个目标假设 $g$ ，系统使用采样函数（例如 $SAMPLEKTRAJ $）从初始状态$ I $到$ g $采样$ K$ 条近似最优轨迹。
树结构：这些轨迹被编码为一棵树，其中节点代表特定时间步的路径签名。由于唯一性属性，共享共同前缀的轨迹在树中共享同一条分支。
优化（合并与剪枝）：为了处理微小差异并减少冗余，该树经历以下过程：
- 合并：同一层级中欧氏距离低于阈值（ $M_T$ ）的节点被合并，并平均其签名。
- 剪枝：与其父节点距离在阈值（ $P_T$ ）内的节点被移除，父节点继承子节点。这消除了语义上不重要的观测（例如微小的步长），同时保留了对于目标推断至关重要的结构差异。

3. 在线推理

当新观测 $O$ 到达时：

签名计算：系统计算观测序列的部分路径签名 $\beta(O)$ 。
比较：将观测签名与轨迹树中的所有分支进行比较。
- 标准模式（GRPS）：假设观测与轨迹之间完美同步。它基于观测签名与分支签名之间的欧氏距离计算分支的可能性。
- 增强模式（GRPS+DTW）：整合动态时间规整（DTW），将观测序列与轨迹分支对齐。这解决了非同步采样（例如具有不同速度的智能体）和部分可观测性（缺失时间步）的问题。DTW 寻找最优对齐路径以最小化距离，用基于扭曲路径的度量取代简单的欧氏比较。

4. 概率估计

系统通过取通向该目标的所有分支中的最大似然值来计算每个目标的概率 $P(g)$ 。这避免了用次优路径的较低分数稀释来自特定分支的高置信度信号。

主要贡献

新颖编码：引入路径签名作为在线目标识别的紧凑且富有表现力的表征，捕捉了原始状态向量所遗漏的轨迹语义特征。
高效推理：该框架消除了在线阶段重复调用规划器的需求，转而依赖预计算的轨迹树。
鲁棒的相似度度量：整合 DTW 以处理噪声、未对齐或不完整的观测，显著提高了在挑战性设置下的预测准确性。
通用性：一种统一的方法，在连续域中实现了最先进的成果，同时在离散域中保持竞争力。

实验结果

作者在Moving-AI数据集（连续域，基于 StarCraft）和STRIPS 基础数据集（离散域）上评估了 GRPS 和 GRPS+DTW。

连续域

性能：GRPS+DTW 实现了最高的正预测值（PPV）为53.6%，准确率（ACC）为86.7%，优于最先进的 Vector 方法（PPV 47.9%，ACC 86.4%）。
效率：标准 GRPS 模式将在线推理时间缩短至30ms（Vector 方法为 39ms），同时保持了高准确率。
可扩展性：两种模式仅需7 次规划器调用（用于离线采样），而其他方法则需要几十次甚至上百次，展示了卓越的计算效率。
参数敏感性：实验表明，适度的剪枝能在不牺牲准确性的情况下提高效率，而激进的剪枝则会因移除必要的轨迹深度而降低性能。

离散域

性能：GRPS 和 GRPS+DTW 与现有方法（如 Vector、Mirroring）保持竞争力，PPV 得分约为52%，ACC 约为85%。
局限性：作者指出，路径签名依赖几何信息，这在离散 STRIPS 环境中效果较差，因为这些环境中的状态通常是独热编码（one-hot encoded），缺乏固有的空间关系。因此，合并和剪枝阈值在零时达到最优，且性能提升不如连续域中显著。

意义与主张

本文主张，GRPS 通过提供一种有意义且连贯的智能体行为与候选轨迹之间的比较机制，推动了现有技术的发展，而无需依赖最优性假设或昂贵的规划器交互。

实用性：该方法轻量级，足以满足实时应用需求（30ms 推理），同时为离线或高风险场景提供了一种高精度替代方案（GRPS+DTW）。
泛化能力：该方法展示了在多样化场景和参数设置下的鲁棒泛化能力。
未来方向：作者承认，虽然当前方法假设可以访问投影函数（或状态与观测之间的恒等映射），但未来的工作可以集成学习到的投影函数（例如通过自编码器）来处理高维原始传感器数据。他们还强调，需要更高效的超参数调优以优化合并和剪枝操作，并改进离散域的向量编码。

总之，本文提出了一种从依赖规划器、基于成本的目标识别向基于签名、数据驱动的方法的转变，该方法在计算效率与高预测准确性之间取得了平衡，特别是在连续动态环境中。