Certifiably correct machine perception

Examples of correct (globally optimal, center) and incorrect (suboptimal, right) solutions of a simple robotic mapping problem for an autonomous ground vehicle.

Many fundamental machine perception tasks are known to be computationally hard to solve in general.  This class includes (for example) simultaneous localization and mapping (SLAM) and 3D reconstruction (among many others), both of which are essential for physically-embodied autonomous agents.

Standard approaches to machine perception address this computational hardness through the use of heuristic approximations that (while computationally tractable) do not provide any guarantees on the quality of the solutions that they return.  The result is that existing machine perception algorithms can be surprisingly brittle, often returning egregiously wrong solutions even when the problem to which they are applied is well-posed.  This brittleness is a major obstruction to the real-world deployment of autonomous systems, especially in safety-critical applications (such as autonomous ground vehicles, drones, autonomous underwater vehicles, or space systems) where the failure of a perception system could lead to loss of the vehicle, destruction of property, or even loss of life.

NEURAL is addressing these challenges by developing novel classes of certifiably correct machine perception algorithms that deliver both fast computation and provably-good solutions.  Our work applies a combination of tools from geometry, convex analysis, and probability theory to devise convex approximations of generally-intractable estimation problems that we prove are both (i) efficiently-solvable and (ii) provide provably-good approximate solutions in operational regimes typical of real-world robotic deployments.  In particular, our methods admit practically-computable suboptimality bounds that enable autonomous agents to monitor the performance of their own perception systems at run-time; we believe that this capacity for introspection will be an essential ingredient in enabling the high-reliability autonomous systems of the future.

Research themes

Optimization, geometry, convex analysis, convex relaxation, numerical linear algebra, probability (concentration of measure)

Selected publications

  • D.M. Rosen, L. Carlone, A.S. Bandeira, and J.J. Leonard. “SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group”. International Journal of Robotics Research 38.2–3 (Mar. 2019), pp. 95–125. DOI.
  • D.M. Rosen. “Scalable Low-Rank Semidefinite Programming for Certifiably Correct Machine Perception”. International Workshop on the Algorithmic Foundations of Robotics. June 2020. DOI.
  • F. Dellaert*, D.M. Rosen*, J. Wu, R. Mahony, and L. Carlone. “Shonan Rotation Averaging: Global Optimality by Surfing SO(p)n”. European Conference on Computer Vision. Aug 2020. DOI.
  • D.M. Rosen, K.J. Doherty, A. Terán Espinoza, and J.J. Leonard. “Advances in Inference and Representation for Simultaneous Localization and Mapping”. Annual Review of Control, Robotics, and Autonomous Systems 4 (May 2021), pp. 215–242. DOI.
  • Y. Tian, K. Khosoussi, D.M. Rosen, and J.P. How. “Distributed Certifiably Correct Pose-Graph Optimization”. IEEE Transactions on Robotics 37.6 (Dec. 2021), pp. 2137–2156. DOI.
  • K.J. Doherty, D.M. Rosen, and J.J. Leonard. “Performance Guarantees for Spectral Initialization in Rotation Averaging and Pose-Graph SLAM”. IEEE International Conference on Robotics and Automation. Philadelphia, PA, May 2022, pp. 5608–5614. DOI.