Distributed Certifiably Correct Range-Aided SLAM

I. INTRODUCTION

• Certifiably correct algorithms recover globally optimal solutions within a restricted but operationally relevant set of problem instances, supporting formal guarantees for safety-critical autonomy.The motivation includes coordinated multi-agent autonomy in safety-critical cyberphysical systems and post-disaster evaluation.Source: §I · p. 1
• DCORA is presented as the first certifiably correct algorithm for distributed range-aided SLAM.It solves an SDP relaxation of the RA-SLAM maximum-likelihood formulation through distributed Riemannian optimization and the Riemannian Staircase.Source: §I · p. 1
• The paper benchmarks DCORA against centralized certifiably correct RA-SLAM on real-world datasets and studies parameter effects using synthetic data.The listed parameters include agent count, landmark count, and range-measurement density.Source: §I · pp. 1–2

II. RELATED WORKS

• The related-works section reviews DCORA’s method class, distributed Riemannian optimization, and existing distributed RA-SLAM algorithms.Source: §II · p. 2

A. Certifiably Correct Perception via the Riemannian Staircase

• The Riemannian Staircase solves an SDP through lower-dimensional rank-restricted SDPs, equivalently expressed as manifold optimization problems.SE-Sync applied it to pose graph optimization, while DC2-PGO distributed SE-Sync’s optimization and certification procedures; CORA applied it to centralized RA-SLAM.Source: A. Certifiably Correct Perception via… · p. 2

B. Distributed Riemannian Optimization Algorithms

• RBCD/RBCD++ performs distributed block-coordinate descent over products of smooth Riemannian manifolds and converges to first-order critical points at a global sublinear rate.The methods assume agent synchronization; the section also reviews asynchronous and accelerated alternatives.Source: B. Distributed Riemannian Optimization… · p. 2

C. Distributed RA-SLAM Algorithms

• Existing distributed RA-SLAM methods address specific problem instances or lack formal guarantees on returned-estimate quality.The described limitations motivate a unified approach across RA-SLAM state and measurement combinations.Source: C. Distributed RA-SLAM Algorithms · p. 2

III. METHODOLOGY

• The methodology section formulates RA-SLAM, connects it to Riemannian optimization, and presents DCORA with variable ownership for efficient communication and computation.Source: §III · p. 2

A. RA-SLAM Problem Formulation and the Riemannian Staircase

• The maximum-likelihood formulation uses relative-pose and point-to-point distance measurements, with measurement precisions weighting their residuals.The formulation includes rotation and translation variables and auxiliary unit-norm vectors for range terms.Source: A. RA-SLAM Problem Formulation and the… · p. 3
• The RA-SLAM formulation is relaxed from a QCQP to an SDP using Shor’s relaxation.The QCQP relaxes rotations from SO(d) to O(d) and represents range costs with auxiliary unit-norm vectors.Source: A. RA-SLAM Problem Formulation and the… · p. 3
• Because the SDP often admits low-rank solutions, the Burer-Monteiro method factors the solution as X^⊤X and optimizes over a lower-dimensional variable.The factorization constrains solution rank to at most p.Source: A. RA-SLAM Problem Formulation and the… · p. 3
• The rank-restricted problem is equivalently expressed as optimization over Stiefel, sphere, and Euclidean factors in the RA-SLAM product manifold.The Stiefel factor generalizes the orthogonal group, while the auxiliary range vectors remain unit-norm in dimension p.Source: A. RA-SLAM Problem Formulation and the… · p. 3

B. DCORA Algorithm

• DCORA starts with distributed initialization at rank d, then lifts the initial point to the chosen starting rank p0.The lift uses a random Stiefel element.Source: B. DCORA Algorithm · p. 4
• At each staircase level, RBCD finds a first-order critical point, which is lifted to the next rank for distributed verification.The algorithm constructs a dual certificate matrix and checks its minimum eigenpair.Source: B. DCORA Algorithm · p. 4
• A non-optimal critical point yields a second-order descent direction, followed by line search and renewed RBCD optimization.The staircase continues until it recovers a certified globally optimal value for the SDP relaxation.Source: B. DCORA Algorithm · p. 4
• After the SDP value is recovered, distributed rounding projects the estimate onto the feasible set to return poses and landmarks.Source: B. DCORA Algorithm · p. 4

1) Variable Partitioning:

• Each decision variable is owned by a single agent, and the variables are partitioned by ownership into blocks required by RBCD.Source: 1) Variable Partitioning · p. 4
• DCORA retains DC2-PGO’s rule that agents own the pose variables describing their trajectories.Source: 1) Variable Partitioning · p. 4
• Agents own landmarks according to a consensus step and auxiliary unit-norm vectors for range measurements collected by their onboard sensors.Source: 1) Variable Partitioning · p. 4

2) Variable Labeling:

• States connected to other agents’ states through pairwise measurements are public; all other states are private.Source: 2) Variable Labeling · p. 4
• Agents sharing an inter-agent loop closure cache the neighboring agent’s public state before local search.Source: 2) Variable Labeling · p. 4
• For a range measurement taken by another agent, the corresponding auxiliary unit-norm vector is cached too; private states, intra-agent loop closures, and odometry remain private.Source: 2) Variable Labeling · p. 4

• DCORA is benchmarked against CORA on public real-world multi-agent RA-SLAM datasets; CORA is identified as the only other known certifiably correct solver for the general problem.Source: §IV · p. 4
• Synthetic datasets are formed by modifying public synthetic PGO datasets to distribute poses across agents, add landmarks, and create inter- and intra-agent range loop closures with controlled density.Source: §IV · pp. 4–5
• Parameter sweeps vary the number of agents, number of landmarks, and range-measurement density to study RA-SLAM problem structure.Source: §IV · p. 5

A. Implementation for Evaluation

• The evaluation centralizes initialization and minimum-eigenpair calculations, so it does not measure runtime; these changes affect runtime but not the measured performance metrics.Quality initialization can avoid increasing rank multiple times to escape spurious local minima; the centralized eigenpair method has the same asymptotic convergence rate as the distributed calculation.Source: A. Implementation for Evaluation · p. 5

1) Datasets:

• TIERS and MR.CLAM provide the real-world benchmark data; MR.CLAM evaluation uses sessions 2, 4, 6, and 7 because other sessions have substantial ground-truth dropouts.Source: 1) Datasets · p. 5

2) Evaluation and Results:

• The table compares DCORA and CORA on public real-world multi-agent RA-SLAM datasets, reporting translation and rotation ATE values and certification results for their solutions.ATE is calculated against ground truth at certified solutions; the supplied passages do not state the table’s cell values or a winner.Source: Table I · p. 5, 2) Evaluation and Results · p. 5

3) Discussion:

• DCORA and CORA achieve comparable ATE, although DCORA’s sublinear RBCD yields less precise estimates and requires a looser certification tolerance.The discussion says optimization order does not affect SDP optimality, so the certified solution should be mathematically identical.Source: 3) Discussion · p. 5

1) Datasets:

• Range measurements are generated with probability 0.5 or 1.0 from agent poses to random poses and landmarks within a 100 m sensing horizon.The stated range-measurement precision is ρij = 100 1/m2.Source: 1) Datasets · p. 5
• The synthetic study modifies smallGrid3D and sphere2500 into 24 instances, distributing poses among 2, 4, or 8 agents and using 8 or 16 landmarks.The modified datasets contain multiple agents, landmarks, and range measurements.Source: 1) Datasets · p. 5, Figure 2 · p. 6

2) Evaluation and Results:

• The evaluation tracks normalized relative suboptimality as a measure of relaxation tightness and Riemannian gradient norm as a measure of critical-point estimation precision.These metrics are plotted over RBCD iterations at rank three.Source: 2) Evaluation and Results · p. 6, Figure 3 · p. 6

V. CONCLUSION

• DCORA is presented as the first distributed certifiably correct RA-SLAM algorithm, generalizing the Riemannian Staircase from distributed pose graph optimization.Source: §V · p. 6

3) Discussion:

• Agent count predominantly affects convergence and precision; increasing range density can improve SDP tightness and aid solution quality as agents distribute relative-pose measurements.On modified sphere2500 with range probability 1.0, the eight-agent system improves convergence and precision compared with the four-agent system.Source: Figure 3 · p. 6, 3) Discussion · p. 6, §V · p. 6

V. CONCLUSION

• DCORA demonstrates solution quality comparable to centralized CORA on real-world datasets.Source: §V · p. 6
• Future work includes broader real-world evaluation across larger multi-agent systems and noise regimes, and runtime study using a fully distributed implementation.Source: §V · p. 6