Dynamic Time Warping

• Also called: DTW
• Category: Learning & autonomy › Learning from demonstration
• Tags: time-series, sequence-alignment, dynamic-programming, learning-from-demonstration, trajectory-analysis

A dynamic programming algorithm that aligns two time series of different speeds or lengths by finding the order-preserving pairing of their samples with the lowest total distance.

Definition

Dynamic time warping (DTW) compares two sequences that follow a similar pattern but at different speeds, such as two demonstrations of the same motion where one operator paused and the other moved quickly. Instead of comparing sample i with sample i, DTW searches for a warping path, a pairing of samples from the two sequences that starts at both beginnings, ends at both ends and never goes backward in time. Each sample may be matched to one or several samples of the other sequence, so stretches and compressions in time are absorbed by the alignment. The DTW distance is the total cost along the best path, and the path itself tells which moments correspond.

The standard algorithm fills a cost matrix by dynamic programming. With a local distance d(i, j) between sample i of one sequence and sample j of the other, the cumulative cost is D(i, j) = d(i, j) + min(D(i−1, j), D(i, j−1), D(i−1, j−1)), and backtracking from the final cell recovers the path. This takes time and memory proportional to the product of the two lengths. Sakoe and Chiba (1978) popularized the method for spoken word recognition and introduced a band around the diagonal that limits how far the alignment may drift; the Itakura parallelogram is a related constraint. Such windows speed up computation and prevent pathological warps in which one sample is matched to a long stretch of the other.

Several variants matter in robotics. Subsequence DTW relaxes the start and end conditions so a short query can be matched to the best-fitting segment of a long trajectory, which supports retrieval from large logs. Derivative DTW aligns on local slopes rather than raw values. Soft-DTW, introduced by Cuturi and Blondel in 2017, replaces the minimum with a smooth version so the alignment cost is differentiable and can be used as a training loss. DTW aligns only in time: features must be comparable and usually normalized, and the resulting distance is not a true metric because it does not satisfy the triangle inequality.

Why it matters

Robot data rarely arrives at a common speed. Demonstrations, executed trajectories and sensor recordings differ in timing, and DTW is the standard tool for putting them on a shared timeline before averaging, comparing, retrieving or scoring them.

Key applications

• Aligning multiple demonstrations before averaging or fitting movement primitives
• Comparing executed robot trajectories with reference trajectories
• Retrieving matching segments from large trajectory or sensor logs
• Gesture and activity recognition from motion or inertial data
• Scoring navigation paths against reference paths with normalized DTW metrics
• Synchronizing sensor streams recorded at different rates

In practice

A team collects ten kinesthetic demonstrations of a pouring motion, each with a different duration and pauses in different places. To build a single reference for a movement primitive, they pick one demonstration as a template, align each other demonstration to it with DTW on normalized joint positions and end-effector velocity, and resample all of them onto the template's timeline using the warping paths. Averaging the aligned trajectories gives a clean mean motion and a per-timestep variance that shows where demonstrations agree. A Sakoe-Chiba band keeps the alignment from collapsing pauses into single samples. Later, the same subsequence DTW code searches the fleet's stored trajectories for segments that best match a short query motion.

Common misconceptions

• DTW distance is a metric — it does not satisfy the triangle inequality, which matters for indexing and clustering methods that assume one
• DTW handles any difference between sequences — it absorbs differences in timing, not offsets or scaling in values, so features usually need normalization first
• Unconstrained DTW gives the best alignment — without a window it can match a single sample to long stretches of the other sequence, producing warps with no physical meaning
• DTW is too slow for practical use — banding, lower bounds and approximate methods make it fast enough for many real-time and large-scale uses

Who should know this

• Learning-from-demonstration researchers
• Engineers analyzing robot trajectories and logs
• Gesture and activity recognition developers
• Researchers evaluating navigation and manipulation policies

Related technologies

• Soft-DTW
• Sakoe-Chiba Band
• Subsequence DTW
• FastDTW
• tslearn

Related terms

• Dynamic Movement Primitive
• Imitation Learning
• Kinesthetic Teaching
• Behavior Cloning
• Success Weighted by Path Length

Related projects

• PlotJuggler: Fast time-series visualization tool for ROS topics, rosbags, and robot debugging

Videos

• How DTW (Dynamic Time Warping) algorithm works: Thales Sehn Körting