Outlier-Robust Spatial Perception

Spatial perception is the backbone of many robotics applications, and spans a broad range of research problems, including localization and mapping, point cloud alignment, and relative pose estimation from camera images. Robust spatial perception is jeopardized by the presence of incorrect data association, and in general, outliers. Although techniques to handle outliers do exist, they can fail in unpredictable manners (e.g., RANSAC, robust estimators), or can have exponential runtime (e.g., branch-and-bound).

In our recent paper (Antonante et al., 2021) we showed that that even a simple linear instance of outlier rejection is inapproximable: in the worst-case one cannot design a quasi-polynomial time algorithm that computes an approximate solution efficiently and provided the first per-instance sub-optimality bounds to assess the approximation quality of a given outlier rejection outcome.

One main goal of this research is to propose computationally feasible agorithms with performance guaranteed to address this class of problem, we recently proposed a simple general-purpose algorithm, named adaptive trimming (ADAPT), to remove outliers for a wide class of problems including 2D/3D SLAM to 3D point cloud registration and 2-View Geometry.

References

  1. Antonante, P., Tzoumas, V., Yang, H., & Carlone, L. (2021). Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications. IEEE Trans. Robotics, 38(1), 281–301.