Establishing correspondence between two sets of data is a fundamental problem in robotics, and is required for fusing data across multiple DCIST agents to establish global situational awareness. Real-world data contains noise and outliers. The traditional linear assignment algorithms are not robust to high-outlier regimes, leading to incorrect correspondences. To address these issues,  members of the DCIST alliance developed CLIPPER (Consistent LInking, Pruning, and Pairwise Error Rectification), a framework for robust data association in the presence of noise and outliers. CLIPPER formulates the problem in a graph-theoretic framework using the notion of geometric consistency. State-of-the-art techniques that use this framework utilize either combinatorial optimization techniques that do not scale well to large-sized problems, or use heuristic approximations that yield low accuracy in high-outlier regimes. In contrast, CLIPPER uses a computationally efficient relaxation of the combinatorial problem and provides optimality guarantees for the generated solution. Low time complexity is achieved with an efficient projected gradient ascent approach. Experiments demonstrated that CLIPPER maintains a consistently low runtime of 15 ms where exact methods can require up to 24 s at their peak, even on small-sized problems with 200 associations. When evaluated on noisy point cloud registration problems, CLIPPER achieves 100% precision in 90% outlier regimes while competing algorithms begin degrading by 70% outliers. 

Capability: T1C1C

Points of Contact: Jonathan How (PI), Kaveh Fathian

Video: https://youtu.be/QYLHueMhShY

Paper: https://arxiv.org/pdf/2011.10202.pdf

Citation: P. C. Lusk, K. Fathian, J. P. How, “CLIPPER: A Graph-Theoretic Framework for Robust Data Association,” in IEEE ICRA, 2021.