Research & Publications

LaplacianOpt is developed alongside research on mathematical optimization methods for maximizing graph algebraic connectivity and designing robust networks.

Graph sparsification for pose-graph SLAM

Pose-graph Simultaneous Localization and Mapping (SLAM) estimates a set of unknown robot poses from noisy relative-pose measurements and is the standard formulation in modern SLAM (Cadena et al., 2016). Estimation accuracy depends on both the precision of individual measurements and the structure of the measurement graph: the Fisher information matrix of pose-graph optimization is expressed in terms of weighted graph Laplacians (Chen et al., 2021). For rotation synchronization, the Cramér–Rao bound is governed by the pseudoinverse of the weighted measurement-graph Laplacian, so increasing the algebraic connectivity $\lambda_2$ lowers this bound (Boumal et al., 2014). Sparse graphs that keep $\lambda_2$ bounded away from zero remain well suited to accurate estimation and 3D reconstruction.

That turns measurement selection into a graph-design problem. When sensing, communication, or computation allow only $K$ loop closures, which $K$ should be kept? Given a fixed spanning-tree backbone and a pool of candidate loop closures weighted by their measurement precision, LaplacianOpt selects the $K$ loop closures that maximize $\lambda_2$ of the resulting graph, either to global optimality or quickly with heuristics. Because $\lambda_2$ is small whenever part of the graph hangs on by only a few weak edges, maximizing it spends the budget on loop closures that brace weakly constrained regions, not on redundant measurements where the graph is already rigid.

Example: recovering a 3D surface

The ground truth is a three-dimensional $\lambda$-shaped surface. It is used only to generate the noisy measurements and to score the final reconstruction; neither the edge selection nor the estimator ever sees it. Every selection receives the same backbone, the same pool of candidate loop closures with their uncertainties, the same noisy measurements, and the same budget. Each selected graph is then solved with a standard nonlinear pose-graph estimator. The better connected the selected graph, the closer its reconstruction stays to the ground truth.

Publications

Select a publication to read a short overview and follow its paper links or copy its BibTeX citation. If you find LaplacianOpt useful, we request that you cite the papers most relevant to your work.

@article{LOpt_TCNS2024,
  title={Optimal Robust Network Design: Formulations and Algorithms for Maximizing Algebraic Connectivity},
  author={Somisetty, Neelkamal and Nagarajan, Harsha and Darbha, Swaroop},
  journal={IEEE Transactions on Control of Network Systems},
  pages={918--929},
  volume={12},
  number={1},
  year={2024},
  doi={10.1109/TCNS.2024.3431408},
  publisher={IEEE}
}

@inproceedings{LOpt_CDC2024,
  title={Spectral Graph Theoretic Methods for Enhancing Network Robustness in Robot Localization},
  author={Somisetty, Neelkamal and Nagarajan, Harsha and Darbha, Swaroop},
  booktitle={IEEE 63rd Conference on Decision and Control (CDC)},
  pages={8811--8818},
  year={2024},
  doi={10.1109/CDC56724.2024.10886863},
  organization={IEEE}
}

@inproceedings{LOpt_ECC2015,
  title={On Maximizing Algebraic Connectivity of Networks for Various Engineering Applications},
  author={Nagarajan, Harsha and Rathinam, Sivakumar and Darbha, Swaroop},
  booktitle={European Control Conference (ECC)},
  pages={1626--1632},
  year={2015},
  doi={10.1109/ECC.2015.7330770},
  organization={IEEE}
}