← Back ICRA 2026

Globally Optimal Data-Association-Free Landmark-Based Localization Using Semidefinite Relaxations

Vassili Korotkine, Mitchell Cohen, James Richard Forbes

PDF

AI summary

Key figure (auto-extracted from paper)

A tightened semidefinite relaxation solves for robot poses and landmark associations simultaneously, guaranteeing global optimality where local methods fail.

Semidefinite programming Data association Landmark localization Global optimization Robotics SLAM

Problem

Landmark-based localization requires matching sensor measurements to known landmarks, but when associations are unknown, existing optimization methods are local and prone to converging to incorrect solutions without reliable initialization.

Approach

The authors formulate the joint estimation of robot states and data associations as a quadratically constrained quadratic program and solve it using a tightened semidefinite relaxation that guarantees global optimality when the relaxation is tight.

Key results

The SDP relaxation is tight and yields globally optimal solutions for moderate noise levels.
Significantly outperforms local Gauss-Newton baselines initialized with dead-reckoning in both simulation and real-world trials.
Correctly recovers true data associations and robot trajectories in ambiguous landmark environments.
Provides the first polynomial-time scalable method for certifiably optimal data-association-free localization.

Why it matters

Enables reliable, certifiably optimal robot localization in ambiguous environments where traditional sensor fusion methods frequently fail, benefiting autonomous navigation and SLAM systems.

Abstract

This paper proposes a semidenite relaxation for landmark-based localization with unknown data associations in planar environments. The proposed method simultaneously solves for the optimal robot states and data associations in a globally optimal fashion. Relative position measurements to a xed set of known landmarks are used, but the data association is unknown in that the robot does not know which landmark each measurement is generated from. The relaxation is shown to be tight in a majority of cases for moderate noise levels. The proposed algorithm is compared to local Gauss-Newton baselines initialized at the dead-reckoned trajectory, and is shown to signicantly improve convergence to the problem’s global optimum in simulation and experiment. Accompanying software and supplementary material can be found at https: //github.com/decargroup/certiable uda loc.

Index terms

Localization Optimization and Optimal Control Probabilistic Inference