Environment-based trajectory clustering to extract principal directions for autonomous vehicles

This work presents a trajectory clustering approach that groups trajectories without the need of manually-tuned distance thresholds. Contrary to trajectory clustering approaches that use continuous, often geometrically-motivated similarity measures, path similarity is binary. Similar to homotopy classes, path equivalence is based on the obstacles in the environment. The goal states are, however, not fixed, but the paths have certain length restrictions. The equivalence is efficiently checked by closing the paths with sampled intermediate trajectories and using point-in-polygon tests. The proposed algorithm has linear complexity in the number of paths for non-overlapping clusters and, under certain assumptions, also in the case of overlapping clusters. Experimental results from an integration into a path-planning-based road course estimation system are shown and compared to a traditional distance-similarity cluster analysis to demonstrate the performance.