Certifiably Optimal Data-Association-Free Landmark-Based Localization

A certifiably optimal semidefinite-relaxation-based method for landmark-based planar localization. This repository contains the companion code for our submission IEEE Robotics and Automation Letters titled "Globally Optimal Data-Association-Free Landmark-Based Localization Using Semidefinite Relaxations".

The arXiv article may be found here. The arXiv version also contains the supplementary material.

Getting Started

This code was developed with Python 3.8.10.

PyEnv was used to manage the virtual environment, which can be installed with

curl https://pyenv.run | bash

Create and activate virtualenv,

pyenv install 3.8.10
pyenv virtualenv 3.8.10 cert-env2
pyenv activate cert-env2

Upgrade pip in case it is not the latest version,

pip install --upgrade pip

Initialize the submodules,

git submodule update --init 

Install general requirements using

python3 -m pip install -r requirements.txt

Install the submodules,

python3 -m pip install -e  ./navlie
python3 -m pip install -e  ./pyfactorgraph
python3 -m pip install -e  ./pylgmath
python3 -m pip install -e  ./constraint_learning
python3 -m pip install -e  ./certifiable-tools
python3 -m pip install -e  ./poly_matrix

Install the project library,

python3 -m pip install -e ./certifiable_uda_loc/

The paths are configured in the path_config.py. Please modify the project_root_dir variable to be the root directory of wherever this project is on your machine.

Run tests using

python3 scripts/0_tests.py

Reproducing Results From Our Paper

Please run the corresponding Python scripts. For the simulation results,

python3 scripts/1_analysis_simulation.py

For the Lost in the Woods results,

python3 scripts/2_analysis_lost_in_the_woods.py

Troubleshooting

For issues relating to finding headers for sparseqr, try

sudo apt-get install libsuitesparse-dev

Citation

If you find this code useful, please consider citing our arXiv preprint,

@misc{korotkine2025globallyoptimaldataassociationfreelandmarkbased,
      title={Globally Optimal Data-Association-Free Landmark-Based Localization Using Semidefinite Relaxations}, 
      author={Vassili Korotkine and Mitchell Cohen and James Richard Forbes},
      year={2025},
      eprint={2504.08547},
      archivePrefix={arXiv},
      primaryClass={cs.RO},
      url={https://arxiv.org/abs/2504.08547}, 
}

License

Distributed under the MIT License. See LICENSE.txt for more information.

Contact

Vassili Korotkine - @decargroup - vassili.korotkine@mail.mcgill.ca - https://vkorotkine.github.io/

Acknowledgments

• This project makes heavy use of the poly_matrix library for manipulating sparse symmetric matrices, as well as the certifiable-tools library for working with certifiable optimization problems, both built by Frederike Duembgen and Connor Holmes at University of Toronto.
• This project uses the Lost in The Woods dataset collected at the University of Toronto Autonomous Space Robotics Lab
• This project uses a modified version of PyFactorGraph developed by the Marine Robotics Group at MIT.
• The project uses navlie library for on-manifold state estimation., built by the DECAR research group at McGill University.
• The project is funded via the Natural Sciences and Engineering Research Council of Canada (NSERC) Alliance Grant in collaboration with Denso Corporation.

(back to top)