🤖 AI

Online Goal Recognition using Path Signature and Dynamic Time Warping

This paper proposes a novel online goal recognition method for continuous domains that leverages path signatures to efficiently encode and compare trajectories, demonstrating superior predictive accuracy and planning efficiency compared to state-of-the-art approaches.

Original authors: Douglas Tesch, Nathan Gavenski, Leonardo Amado, Odinaldo Rodrigues, Felipe Meneguzzi

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Douglas Tesch, Nathan Gavenski, Leonardo Amado, Odinaldo Rodrigues, Felipe Meneguzzi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a friend walk through a massive, complex maze. You can only see them for a few seconds at a time, and sometimes they move quickly, sometimes slowly, and sometimes you miss a step or two. Your job is to guess where they are trying to go before they even get there.

This is the problem of Online Goal Recognition. The paper you provided introduces a new, smarter way to solve this puzzle, especially when the "maze" is a continuous space (like a robot moving on a floor) rather than a grid of squares.

Here is how the authors, Douglas Tesch and his team, solved it, explained through simple analogies.

The Problem: The "Too Many Planners" Bottleneck

Traditionally, to guess a goal, computers would act like a frantic tour guide. Every time they saw the friend take a new step, they would stop, run a simulation for every possible exit in the maze, calculate the perfect path to each one, and compare it to what they just saw.

The Issue: This is incredibly slow. If there are 100 possible exits, the computer has to run 100 simulations for every single step the friend takes. It's like asking a chef to cook 100 different meals just to guess which one you are hungry for, every time you take a bite.

The Solution: The "Fingerprint" of Movement

The authors propose a new method called GRPS (Goal Recognition with Path Signatures). Instead of simulating every path from scratch, they use two clever tools: Path Signatures and Dynamic Time Warping.

1. Path Signatures: The "DNA" of a Journey

Imagine you have a long, winding trail of footprints in the sand.

Old Way: You look at the footprints one by one, trying to remember the exact shape of every single step.
The Paper's Way (Path Signatures): You take a "snapshot" or a fingerprint of the entire trail. This fingerprint captures the essence of the movement—the curves, the turns, the rhythm—without needing to remember every single grain of sand.

The authors use a mathematical concept called a "Path Signature" to turn a long, messy path into a compact, fixed-length code.

Why it's cool: This code is unique. No two different paths have the exact same code. It's like a DNA test for movement. Even if two people walk the same route but at different speeds, the signature captures the shape of their journey, making it easy to compare.

2. The Trajectory Tree: The "Library of Routes"

Before the friend even starts walking, the computer builds a giant library of possible routes (trajectories) to every possible goal.

Instead of keeping these routes as separate, messy files, the computer organizes them into a Tree.
If two routes start by walking straight down the hallway, they share the same "branch" on the tree. They only split apart when they reach a fork in the road.
Merging and Pruning: Sometimes, two routes are almost identical (like walking 10 steps straight vs. 10.1 steps straight). The computer "merges" these similar branches to save space and "prunes" (cuts off) tiny, insignificant wiggles that don't change the destination. This keeps the library small and fast to search.

3. Dynamic Time Warping (DTW): The "Rubber Band"

Here is the tricky part: What if your friend walks fast, but the library routes were calculated for a slow walker? Or what if you missed a few seconds of watching them?

The Problem: If you try to compare a fast walk to a slow walk step-by-step, they won't match up. It's like trying to match a fast song to a slow song by lining up the beats exactly; it looks like a mess.
The Solution (DTW): Imagine the timeline of the walk is made of rubber. Dynamic Time Warping stretches or compresses the rubber band of the observed walk until it fits perfectly against the library route. It aligns the "fast steps" with the "slow steps" so you can see that they are actually going to the same place, even if the timing is off.

How It Works in Real Life

Offline (Preparation): The computer builds its "Library of Routes" (the Tree) using the Path Signatures. It cleans it up by merging similar paths and cutting off tiny details. This takes some time but only happens once.
Online (Real-Time): As the friend walks:
- The computer takes a quick "fingerprint" (signature) of the path seen so far.
- It compares this fingerprint to the Library Tree.
- If the friend is moving at a weird speed or you missed a step, it uses the Rubber Band (DTW) to stretch the comparison so it fits.
- It instantly calculates which "Goal" (exit) is the most likely match.

The Results: Faster and Smarter

The authors tested this on two types of worlds:

Continuous Worlds (Robots moving in open space): Their method was the fastest and most accurate. It was significantly better than previous methods at guessing the goal early on, and it did it without needing to run expensive simulations for every single step.
Discrete Worlds (Grid-based puzzles): It performed just as well as the best existing methods, proving it works for different types of problems.

The Bottom Line

The paper claims that by treating movement like a unique "fingerprint" (Path Signature) and using a "rubber band" to align different speeds (DTW), we can guess where an agent is going much faster and more accurately than before.

Without DTW: It's incredibly fast (about 30 milliseconds), perfect for real-time robots.
With DTW: It's slightly slower but even more accurate, perfect for situations where the data is messy or the timing is off.

The authors conclude that this approach removes the need for heavy, slow computer simulations, making goal recognition practical for real-world, fast-moving applications.

Technical Summary: Online Goal Recognition using Path Signature and Dynamic Time Warping

Problem Definition

The paper addresses Online Goal Recognition (OGR) in both continuous and discrete domains. The core challenge is to infer an agent's goal solely from sparse, sequential observations of its trajectory while the agent is still interacting with the environment.

Existing approaches in continuous domains face two primary limitations:

Computational Overhead: Traditional methods often rely on repeated calls to a planner for each new observation and each goal hypothesis, scaling linearly with the number of goals and observations. This is impractical for real-time applications.
Inadequate Representation: Current state encodings often rely on raw state information (e.g., position, velocity) which fails to capture the temporal structures and semantic behavioral patterns necessary to distinguish between goals, especially in noisy or partial observation scenarios.

Furthermore, comparing trajectories of varying lengths, with noise, or non-Euclidean distances remains a significant hurdle, particularly in fast-moving robotic applications.

Methodology: GRPS

The authors propose Goal Recognition with Path Signatures (GRPS), a data-driven framework that leverages Path Signatures and Dynamic Time Warping (DTW) to encode and compare trajectories efficiently.

1. Path Signatures for Trajectory Encoding

Instead of raw states, GRPS utilizes path signatures, a mathematical tool from rough path theory.

Representation: Path signatures transform arbitrarily sized sequences of data (trajectories) into unique, fixed-length feature vectors.
Properties: These representations are invariant to reparametrization and naturally capture multi-scale dependencies and geometric/temporal structures.
Uniqueness: No two path signatures are equal unless the generating trajectories are identical, allowing for a one-to-one correspondence between trajectory prefixes and their encoded signatures.

2. Trajectory Tree Construction (Offline Stage)

To avoid real-time planning, GRPS precomputes a Trajectory Tree ($TT$):

Sampling: For each goal hypothesis $g$ , the system samples $K$ approximate optimal trajectories from the initial state $I$ to $g$ using a sampling function (e.g., $SAMPLEKTRAJ$).
Tree Structure: These trajectories are encoded into a tree where nodes represent path signatures at specific timesteps. Due to the uniqueness property, trajectories sharing a common prefix share the same branch in the tree.
Optimization (Merge & Prune): To handle minor variations and reduce redundancy, the tree undergoes:
- Merging: Nodes at the same level with Euclidean distances below a threshold ( $M_T$ ) are merged, averaging their signatures.
- Pruning: Nodes within a distance threshold ( $P_T$ ) of their parent are removed, with the parent inheriting the children. This eliminates semantically insignificant observations (e.g., small steps) while preserving structural distinctions critical for goal inference.

3. Online Inference

When new observations $O$ arrive:

Signature Computation: The system computes the partial path signature $\beta(O)$ for the observed sequence.
Comparison: The observed signature is compared against all branches in the Trajectory Tree.
- Standard Mode (GRPS): Assumes perfect synchronization between observations and trajectories. It calculates the likelihood of a branch based on the Euclidean distance between the observed signature and the branch's signature.
- Enhanced Mode (GRPS+DTW): Integrates Dynamic Time Warping (DTW) to align the observation sequence with trajectory branches. This addresses issues of non-synchronized sampling (e.g., agents with different velocities) and partial observability (missing time steps). DTW finds the optimal alignment path to minimize distance, replacing the simple Euclidean comparison with a warping path-based metric.

4. Probability Estimation

The system calculates the probability $P(g)$ for each goal by taking the maximum likelihood across all branches leading to that goal. This avoids diluting high-confidence signals from specific branches with lower scores from suboptimal paths.

Key Contributions

Novel Encoding: The introduction of path signatures as a compact, expressive representation for online goal recognition, capturing semantic features of trajectories that raw state vectors miss.
Efficient Inference: A framework that eliminates the need for repeated planner calls during the online phase, relying instead on precomputed trajectory trees.
Robust Similarity Measure: The integration of DTW to handle noisy, misaligned, or incomplete observations, significantly improving predictive accuracy in challenging settings.
Versatility: A unified approach that achieves state-of-the-art results in continuous domains while remaining competitive in discrete domains.

Experimental Results

The authors evaluated GRPS and GRPS+DTW on the Moving-AI dataset (continuous, StarCraft-based) and a STRIPS-based dataset (discrete).

Continuous Domains

Performance: GRPS+DTW achieved the highest Positive Predictive Value (PPV) of 53.6% and Accuracy (ACC) of 86.7%, outperforming the state-of-the-art Vector method (47.9% PPV, 86.4% ACC).
Efficiency: The standard GRPS mode reduced online inference time to 30ms (from 39ms in Vector) while maintaining high accuracy.
Scalability: Both modes required only 7 planner calls (for offline sampling) compared to dozens or hundreds for other methods, demonstrating superior computational efficiency.
Parameter Sensitivity: Experiments showed that moderate pruning improves efficiency without sacrificing accuracy, while aggressive pruning degrades performance by removing essential trajectory depth.

Discrete Domains

Performance: GRPS and GRPS+DTW remained competitive with existing methods (e.g., Vector, Mirroring), achieving PPV scores around 52% and ACC around 85%.
Limitations: The authors note that path signatures rely on geometric information, which is less effective in discrete STRIPS environments where states are often one-hot encoded without inherent spatial relationships. Consequently, merge and prune thresholds were optimal at zero, and performance gains over other methods were less pronounced than in continuous domains.

Significance and Claims

The paper claims that GRPS advances the state-of-the-art by providing a meaningful and coherent comparison mechanism between agent behavior and candidate trajectories without relying on optimality assumptions or costly planner interactions.

Practicality: The method is lightweight enough for real-time applications (30ms inference) while offering a high-precision alternative (GRPS+DTW) for offline or high-stakes scenarios.
Generalization: The approach demonstrates robust generalization across diverse scenarios and parameter settings.
Future Direction: The authors acknowledge that while the current method assumes access to a projection function (or identity mapping between states and observations), future work could integrate learned projection functions (e.g., via autoencoders) to handle high-dimensional raw sensor data. They also highlight the need for more efficient hyperparameter tuning for merge and prune operations and improved vector encoding for discrete domains.

In summary, the paper presents a shift from planner-heavy, cost-based goal recognition to a signature-based, data-driven approach that balances computational efficiency with high predictive accuracy, particularly in continuous, dynamic environments.