Journal
IEEE TRANSACTIONS ON ROBOTICS
Volume 38, Issue 1, Pages 281-301Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TRO.2021.3094984
Keywords
Estimation; Signal processing algorithms; Probabilistic logic; Approximation algorithms; Simultaneous localization and mapping; Particle measurements; Measurement uncertainty; Algorithms; autonomous systems; computational complexity; computer vision; maximum likelihood estimation; resilient perception; robust estimation
Categories
Funding
- ARL DCIST CRA [W911NF-172-0181]
- MathWorks
- NS CAREER award Certifiable Perception for Autonomous Cyber-Physical Systems,
- Lincoln Laboratory's Resilient Perception in Degraded Environments program
Ask authors/readers for more resources
This article introduces two unifying formulations for outlier-robust estimation, generalized maximum consensus and generalized truncated least squares, and proposes a novel algorithm for dynamically separating inliers from outliers. The research shows that these algorithms perform well on robot perception problems, outperforming existing methods even without relying on noise bounds for the inliers.
Nonlinear estimation in robotics and vision is typically plagued with outliers due to wrong data association or incorrect detections from signal processing and machine learning methods. This article introduces two unifying formulations for outlier-robust estimation, generalized maximum consensus ($\textrm{G}$-$\textrm{MC}$) and generalized truncated least squares ($\textrm{G-TLS}$), and investigates fundamental limits, practical algorithms, and applications. Our first contribution is a proof that outlier-robust estimation is inapproximable: In the worst case, it is impossible to (even approximately) find the set of outliers, even with slower-than-polynomial-time algorithms (particularly, algorithms running in quasi-polynomial time). As a second contribution, we review and extend two general-purpose algorithms. The first, adaptive trimming ($\textrm{ADAPT}$), is combinatorial and is suitable for $\textrm{G}$-$\textrm{MC}$; the second, graduated nonconvexity ($\textrm{GNC}$), is based on homotopy methods and is suitable for $\textrm{G-TLS}$. We extend $\textrm{ADAPT}$ and $\textrm{GNC}$ to the case where the user does not have prior knowledge of the inlier-noise statistics (or the statistics may vary over time) and is unable to guess a reasonable threshold to separate inliers from outliers (as the one commonly used in RANdom SAmple Consensus $(\textrm{RANSAC})$. We propose the first minimally tuned algorithms for outlier rejection, which dynamically decide how to separate inliers from outliers. Our third contribution is an evaluation of the proposed algorithms on robot perception problems: mesh registration, image-based object detection (shape alignment), and pose graph optimization. $\textrm{ADAPT}$ and $\textrm{GNC}$ execute in real time, are deterministic, outperform $\textrm{RANSAC}$, and are robust up to 80-90% outliers. Their minimally tuned versions also compare favorably with the state of the art, even though they do not rely on a noise bound for the inliers.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available