Fast Trajectory Simplification Algorithm for Natural User Interfaces in Robot Programming by Demonstration

Abstract

Trajectory simplification is a problem encountered in areas like Robot programming by demonstration, CAD/CAM, computer vision, and in GPS-based applications like traffic analysis. This problem entails reduction of the points in a given trajectory while keeping the relevant points which preserve important information. The benefits include storage reduction, computational expense, while making data more manageable. Common techniques formulate a minimization problem to be solved, where the solution is found iteratively under some error metric, which causes the algorithms to work in super-linear time. We present an algorithm called FastSTray, which selects the relevant points in the trajectory in linear time by following an open loop heuristic approach. While most current trajectory simplification algorithms are tailored for GPS trajectories, our approach focuses on smooth trajectories for robot programming by demonstration recorded using motion capture systems.Two variations of the algorithm are presented: 1. aims to preserve shape and temporal information; 2. preserves only shape information. Using the points in the simplified trajectory we use cubic splines to interpolate between these points and recreate the original trajectory. The presented algorithm was tested on trajectories recorded from a hand-tracking system. It was able to eliminate about 90% of the points in the original trajectories while maintaining errors between 0.78-2cm which corresponds to 1%-2.4% relative error with respect to the bounding box of the trajectories.