Globally Optimal Data-Association-Free Landmark-Based Localization Using Semidefinite Relaxations
Vassili Korotkine, Mitchell Cohen, James Richard Forbes · 2025
Read Globally Optimal Data-Association-Free Landmark-Based Localization Using Semidefinite Relaxations by Vassili Korotkine, Mitchell Cohen, James Richard Forbes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-08547.txt.
Introduction
Vassili Korotkine, Mitchell Cohen, and James Richard Forbes locate a robot that cannot tell its landmarks apart. Their paper came out in two thousand twenty-five. The robot measures relative positions to known landmarks. It does not know which landmark each reading came from. Guessing wrong can wreck the position estimate. Local solvers often settle into that wrong guess.
Their method casts the problem as a semidefinite relaxation. It solves for robot states and landmark matches together. The answer is globally optimal, not just a local best. For moderate noise, the relaxation is tight in most cases. Tests in simulation and experiment beat Gauss-Newton baselines started from dead reckoning. The team also shares software for the method. Certifiable localization gains a practical tool.
Catalog record
| CREATOR | Vassili Korotkine, Mitchell Cohen, James Richard Forbes |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-08547
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Globally Optimal Data-Association-Free Landmark-Based Localization Using Semidefinite Relaxations Vassili Korotkine, Mitchell Cohen, James Richard Forbes Abstract This paper proposes a semidefinite 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 fixed 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 significantly 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/certifiable_uda_loc . I Introduction and Related Work Fig. 1: Algorithm comparison on a subsequence of the Lost in the Woods dataset. The proposed SDP method converges to a solution with the correct data associations, while the local method initialized using dead-reckoning is unable to find the globally optimal data associations, leading to an incorrect robot trajectory estimate. The poses are labeled \text{T}_{i} , where i corresponds to the time index. Adjacent poses are 20 seconds apart. Estimating the state of a robot from noisy and incomplete sensor data is a central task associated with autonomy. In the landmark-based localization task, the robot infers its position and orientation from measurements from landmarks with known positions. State estimation methods for localization can be split into filtering methods and batch optimization methods [ 1 ] . Filtering methods include Monte Carlo based localization [ 2 ] , where probabilistic sampling is used to represent the posterior belief on the robot state. This work focuses on batch optimization methods, where all data over a given time window is used to estimate all the robot states within the window. An example is [ 3 ] , where a joint probability data association algorithm is used to perform localization based on a high-definition map. An important component of landmark-based localization is determining the data associations between measurements and landmarks, where a correspondence must be drawn between the measurements received and the landmark they are assumed to be received from. The data associations can either be solved for before, or simultaneously with, the robot states. Solving for the data associations before the robot states can be done with a front-end sensor dependent system, such as by tracking specific camera pixel coordinates between frames [ 4 ] , or it can be done in the optimization back-end by using the provided data. In practice, the need to explicitly estimate data associations in the backend can arise from landmark detections that do not provide rich information, as is common in semantic object-level SLAM [ 5 ] , or failures due to incorrect data association in the frontend [ 6 ] . Algorithms such as joint compatibility branch and bound [ 7 ] , combined constraint data association [ 8 ] , and the CLEAR alignment and rectification algorithm [ 9 ] fall into this category. In all of the above algorithms [ 7 , 8 , 9 ] , the data associations are solved for before solving for the robot states with the data associations fixed, which can result in a suboptimal solution if the initial data associations are incorrect. Another approach consists of solving for the data associations simultaneously with the robot states, a problem that is NP-hard and combinatorial in nature [ 6 ] . When applied to this problem formulation, the Max-Mixture approach of [ 10 ] iterates through optimization steps selecting the most likely data association at each step. The data-association-free landmark-based simultaneous localization and mapping (SLAM) algorithm of [ 6 ] simultaneously solves for robot states, landmark positions, and the data associations in an inner loop using the Max-Mixture algorithm, while solving for the number of landmarks in an outer solver loop. Probabilistic data association in a Max-Mixture framework is also presented in [ 5 ] for the application of semantic SLAM. DC-SAM [ 11 ] is a general purpose method for problems involving continuous and discrete variables that involves alternation of solving for the continuous variables and then solving for the discrete variables. The algorithms described above that simultaneously solve for the data associations and robot state are inherently local in nature, as they require an initial guess that is refined to obtain the optimal solution. The quality of the solution is impacted by the initial guess. Furthermore, global optimality of the algorithm is not guaranteed. The incorrect minimum may be reached without any indication that it is the local minimum. The present work focuses on globally optimal solutions obtained from semidefinite relaxations of the problem. Globally optimal methods based on semidefinite relaxations are applicable to problems that may be formulated as polynomial optimization problems, which are written as quadratically constrained quadratic programs (QCQPs) using a suitable change of variables. The QCQP admits a semidefinite program (SDP) relaxation, termed Shor’s relaxation [ 12 , Chap. 3] . The SDP relaxation may be solved to global optimality, and if the result is feasible for the non-relaxed problem, it is guaranteed to be the global optimum of the non-relaxed problem. SDP relaxations have been used to treat outlier rejection [ 13 , 14 ] , where the algorithm must decide if a given measurement is an outlier or not, a choice that is encoded using discrete boolean states that are solved for alongside the continuous robot states. The contribution of this paper may thus be stated as a relaxation-based globally optimal method, in an optimization cost sense, for the data-association-free planar landmark-based localization problem where the number of landmarks is known . To the best of the authors’ knowledge, this is the first such method that scales in polynomial time. An example result is presented in Fig. 1 , where for an example with five poses and three landmarks, the proposed method obtains the globally optimal solution with the correct data associations, unlike the local method initialized using dead-reckoning. The method is applicable to ground vehicle localization, in situations where relative pose measurements as well as measurements to known landmarks are available. The implementation is open-sourced at https://anonymous.4open.science/r/certifiable_uda_loc-9BCF/README.md . Supplementary material at the same URL contains further details on the cost and constraint matrix setup. The rest of this paper is organized as follows. Sec. II describes the problem setup of landmark-based localization with unknown data associations. Sec. III describes the proposed SDP relaxation. Sec. IV presents results on simulated and experimental data, while Sec. V concludes and provides directions for future work. TABLE I: Notation Table Indices i \triangleq Timestep, sometimes generic index {N} \triangleq Number of timesteps j \triangleq Landmark index, sometimes generic index {n_{\ell}} \triangleq Number of landmarks {k} \triangleq Index of measurement received at given timestep, sometimes generic index {K} \triangleq Number measurements received at given timestep {n_{\theta}} \triangleq Number of discrete problem variables n_{x} \triangleq Number of columns in optimization variable \mbf{X} Quantities \mbf{1} \triangleq Identity matrix with unspecified dimension \mbf{1}^{n\times n} \triangleq Identity matrix of dimension n\times n \mbf{T}_{i}\in SE(3) \triangleq Robot