Path comparison

Problem: the cartesian position of an end effector (no orientation) of a robot arm is recorded, say, every millisecond (the time steps can not be changed), during a motion. The robot arm is commanded the same path but with different velocities. So I get different trajectories. I want to calculate the deviation of the paths, which is the distances of equivalent points of two paths. The problem is to find equivalent points. Since the two velocities are different the comparison at the same time steps of the trajectories makes no sense. I can assume that the paths underlying the trajectories to be compared are rather similar. The deviation for the ideal path being smaller than 1% of a typical length dimension of the path. I want to detect deviations of much lass than that.

I have to map the timestamp of the recorded points to the path length, and make comparison of points at the same path length. But of course also the path lengths differ for different paths, so any deviation would distort the result for all later points. How can I compensate for this ?

Is there a reliable algorithm ? Where can I find information ?

Note: time warp algorithms (even memory optimized ones) are out of the game because of memory consumption.

• Please be aware of the subtle difference between the two terms "path" and "trajectory" as used in robotics: A path is just a sequence of points and usually does not include any information about time (and neither velocity). If the time at which each point on the path is reached is relevant, you are talking about a trajectory. – sebsch Jun 27 '14 at 12:53
• @sebsch Thank you for the comment. I included a sentence to make it clear that I am not comparing trajectories but paths. – Johannes Trost Jun 27 '14 at 13:43

The problem you are describing sounds like you need to calculate Frechet distance.

If you take a point at each of your paths, connect them with a string and move them along the path (not necessarily with the same velocities), then Frechet distance of the paths is a minimum length of the string necessary. Not a good description :-)

The formula from the wikipedia page is much better:

$$F(A,B) = \inf_{\alpha, \beta}\,\,\max_{t \in [0,1]} \,\, \Bigg \{d \Big ( A(\alpha(t)), \, B(\beta(t)) \Big ) \Bigg \}$$ where $\alpha$ and $\beta$ are mappings from time to the position on the curve.

The only problem is, that calculating the Frechet distance between two polylines takes $O(n^{2}m + m^{2}n)$ of memory (and even more time). There are some approximations you could use that only take the turning points of the polyline into account, but I don't know much about them.

And some resources:

• Now that I'm thinking about it, Hausdorff distance might be enough (because the paths are similar), and only needs O(m * n) time and O(1) memory. – cube Jul 1 '14 at 9:09
• Actually the paths are not THAT similar on one hand and on the other hand there are parts of the path that are transversed several times. It is important to check the deviation for each round. – Johannes Trost Jul 7 '14 at 15:47
• Sorry for being so late. The answer was VERY helpful and I was able to solve my problem based on the links. Thank you very much ! – Johannes Trost Aug 10 '16 at 15:09