Certifiable Range-Aided SLAM on SE(2)

This notebook solves an $SE(2)$ range-aided SLAM problem with GTSAM’s Burer-Monteiro Riemannian Staircase and checks an SDP certificate that, when it passes, establishes global optimality. It extends the landmark example with range measurements to fixed beacons.

A raw range residual $(\lVert \ell_k - t_i \rVert - d_{ik})^2$ is not polynomial, so it cannot enter a QCQP. Each range instead gets an auxiliary unit direction $u_m$ and becomes

\nu_{ik}\lVert \ell_k - t_i - d_{ik}\, u_m \rVert^2 \quad\text{subject to}\quad \lVert u_m \rVert = 1,

(1)

whose minimum over the unit sphere is the raw residual, so the reformulation is exact. QuadraticRangeFactor2 contributes that term. The auxiliary is a Rot2, which lifts to a 2-by- $p$ block whose first row carries the direction.

A grid world with range beacons¶

rows, cols, spacing = 4, 4, 2.0

# Boustrophedon ("lawnmower") visit order through the grid.
order, cell_index = [], {}
for row in range(rows):
    columns = range(cols) if row % 2 == 0 else reversed(range(cols))
    for col in columns:
        cell_index[(row, col)] = len(order)
        order.append((row, col))

positions = np.array([[col * spacing, row * spacing] for row, col in order])

# Each pose faces along its direction of travel.
truth = []
for k in range(len(order)):
    step = positions[min(k + 1, len(order) - 1)] - positions[max(k - 1, 0)]
    truth.append(
        gtsam.Pose2(positions[k][0], positions[k][1], np.arctan2(step[1], step[0]))
    )

beacons = np.array([[-2.0, 2.0], [8.0, 1.0], [3.0, 8.0]])

beacon_range = 7.0

odometry = [(k, k + 1) for k in range(len(order) - 1)]
ranges = [
    (k, b)
    for k in range(len(order))
    for b in range(len(beacons))
    if np.linalg.norm(beacons[b] - positions[k]) < beacon_range
]
print(f"{len(order)} poses, {len(beacons)} beacons")
print(f"{len(odometry)} odometry edges, {len(ranges)} range measurements")

16 poses, 3 beacons
15 odometry edges, 34 range measurements

Generative model¶

kappa, tau, nu = 100.0, 25.0, 40.0  # rotation, odometry, range precisions

# Isotropic Langevin on rotation has sigma = 1 / sqrt(2 kappa) in the
# small-dispersion limit; the others are plain Gaussians.
sigma_R = 1.0 / np.sqrt(2.0 * kappa)
sigma_t = 1.0 / np.sqrt(tau)
sigma_d = 1.0 / np.sqrt(nu)

graph = gtsam.NonlinearFactorGraph()
rot_noise = gtsam.noiseModel.Isotropic.Variance(1, 1.0 / kappa)

for i, j in odometry:
    relative = truth[i].between(truth[j])
    measured = gtsam.Pose2(
        relative.x() + rng.normal(scale=sigma_t),
        relative.y() + rng.normal(scale=sigma_t),
        relative.theta() + rng.normal(scale=sigma_R),
    )

    graph.add(
        gtsam.FrobeniusBetweenFactorRot2(R(i), R(j), measured.rotation(), rot_noise)
    )
    graph.add(
        gtsam.RelativeTranslationFactor2(R(i), T(i), T(j), measured.translation(), tau)
    )

# One auxiliary direction per range measurement.
for m, (k, b) in enumerate(ranges):
    measured = np.linalg.norm(beacons[b] - positions[k]) + rng.normal(scale=sigma_d)
    graph.add(gtsam.QuadraticRangeFactor2(T(k), L(b), U(m), measured, nu))

print(f"rotation: kappa = {kappa:g}, sigma = {np.rad2deg(sigma_R):.2f} deg")
print(f"odometry: tau   = {tau:g}, sigma = {sigma_t:.2f} m")
print(f"range:    nu    = {nu:g}, sigma = {sigma_d:.2f} m")
print(f"{graph.size()} factors")

rotation: kappa = 100, sigma = 4.05 deg
odometry: tau   = 25, sigma = 0.20 m
range:    nu    = 40, sigma = 0.16 m
64 factors

Lifted initial values¶

rank = 2  # p = d for the first staircase level

initial = gtsam.Values()
for index in range(len(truth)):
    perturbed = gtsam.Rot2.fromAngle(truth[index].theta() + rng.normal(scale=0.3))
    initial.insert(R(index), perturbed.matrix().T)                   # d x p
    initial.insert(T(index), rng.normal(scale=0.5, size=(1, rank)))  # 1 x p

# Beacons are unconstrained rows, the same shape as a translation.
for b in range(len(beacons)):
    initial.insert(L(b), rng.normal(scale=0.5, size=(1, rank)))

# Each auxiliary is a lifted Rot2: a 2-by-p block whose rows are orthonormal.
for m in range(len(ranges)):
    initial.insert(U(m), gtsam.Rot2.fromAngle(rng.normal()).matrix().T)

print("rotation slice:  ", initial.atMatrix(R(0)).shape)
print("beacon slice:    ", initial.atMatrix(L(0)).shape)
print("auxiliary slice: ", initial.atMatrix(U(0)).shape)

rotation slice:   (2, 2)
beacon slice:     (1, 2)
auxiliary slice:  (2, 2)

Run and certify¶

alm_params = gtsam.AugmentedLagrangianParams()
alm_params.maxIterations = 200

params = gtsam.RiemannianStaircaseParams()
params.pMin = rank
params.pMax = 6
params.eta = 1e-3
params.setAlmParams(alm_params)

result = gtsam.RiemannianStaircaseOptimizer(graph, initial, params).optimize()

print(f"Certified:    {result.certified}")
print(f"Final rank:   {result.finalRank}")
print(f"Ranks tried:  {np.asarray(result.getRanksVisited()).astype(int)}")
print(f"Solver time:  {result.totalTime:.4f} s")

Certified:    True
Final rank:   5
Ranks tried:  [2 3 4 5]
Solver time:  0.0659 s

Round back to $SE(2)$ ¶

if not result.hasRoundedSolution():
    raise RuntimeError("The staircase did not return a rounded solution.")

rounded = result.roundedValues()
blocks = {i: rounded.atMatrix(R(i)).copy() for i in range(len(truth))}
rows = {i: rounded.atMatrix(T(i)).copy() for i in range(len(truth))}
marks = {b: rounded.atMatrix(L(b)).copy() for b in range(len(beacons))}

# Certifiable methods optimize over O(d); undo a global reflection if present.
if sum(np.linalg.det(block) < 0.0 for block in blocks.values()) > len(truth) // 2:
    for block in blocks.values():
        block[:, -1] *= -1.0
    for row in list(rows.values()) + list(marks.values()):
        row[:, -1] *= -1.0

def project_to_so(matrix):
    """Return the closest proper rotation to a square matrix."""
    left, _, right_transpose = np.linalg.svd(matrix)
    correction = np.eye(matrix.shape[0])
    correction[-1, -1] = np.linalg.det(left @ right_transpose)
    return left @ correction @ right_transpose

def rotation_from_matrix(matrix):
    """Rebuild a Rot2 from a proper 2-by-2 rotation matrix."""
    return gtsam.Rot2.fromAngle(np.arctan2(matrix[1, 0], matrix[0, 0]))

estimate = gtsam.Values()
for index in range(len(truth)):
    estimate.insert(R(index), rotation_from_matrix(project_to_so(blocks[index].T)))
    estimate.insert(T(index), gtsam.Point2(rows[index][0]))
for b in range(len(beacons)):
    estimate.insert(L(b), gtsam.Point2(marks[b][0]))

# The optimal auxiliary is the unit vector between the two positions it links,
# so recover it from the recovered geometry rather than from its own block.
for m, (k, b) in enumerate(ranges):
    offset = np.asarray(estimate.atPoint2(L(b))) - np.asarray(estimate.atPoint2(T(k)))
    estimate.insert(U(m), gtsam.Rot2.fromAngle(np.arctan2(offset[1], offset[0])))

relaxation_bound = float(np.asarray(result.getCostPerLevel())[-1])
rounded_objective = graph.error(estimate)

print(f"Relaxation lower bound: {relaxation_bound:.6f}")
print(f"Rounded objective:      {rounded_objective:.6f}")

Relaxation lower bound: 0.472442
Rounded objective:      26.866212

The two numbers are far apart, and that is expected here. Certification says the relaxation was solved to global optimality, not that the relaxation is tight. Dropping $\lVert u_m \rVert = 1$ to $u_m$ free lets every range term shrink toward zero, so the bound can sit well below anything achievable on the sphere. Judge the estimate by its geometry below rather than by the gap; the pose-graph and landmark notebooks, whose relaxations are tight, are where the bound is worth reading as a certificate of the answer itself.

# Each odometry edge contributes 3 residuals. A range gives only its radial
# component, and the auxiliary direction that absorbs the other 1 is fixed by
# the geometry at the optimum, so it adds no free parameter. The gauge removes
# one pose.
residuals = len(odometry) * 3 + len(ranges)
parameters = len(truth) * 3 + len(beacons) * 2 - 3
dof = residuals - parameters
print(f"residuals {residuals} - parameters {parameters} = {dof} dof")
print(f"Expected optimal cost (0.5 * chi^2): {0.5 * dof:.1f}")
print(f"Observed optimal cost:               {rounded_objective:.1f}")
print(f"Ratio:                               {rounded_objective / (0.5 * dof):.2f}")

residuals 79 - parameters 51 = 28 dof
Expected optimal cost (0.5 * chi^2): 14.0
Observed optimal cost:               26.9
Ratio:                               1.92

The estimated map¶

def procrustes(source, target):
    """Best rigid alignment of source onto target."""
    source_centre, target_centre = source.mean(0), target.mean(0)
    A, B = source - source_centre, target - target_centre
    left, _, right_transpose = np.linalg.svd(A.T @ B)
    return (A @ (left @ right_transpose)) + target_centre

positions_est = np.array([estimate.atPoint2(T(i)) for i in range(len(truth))])
beacons_est = np.array([estimate.atPoint2(L(b)) for b in range(len(beacons))])

# The relaxation fixes no gauge, so align poses and beacons together.
aligned = procrustes(np.vstack([positions_est, beacons_est]),
                     np.vstack([positions, beacons]))
aligned_poses = aligned[: len(positions)]
aligned_beacons = aligned[len(positions) :]

figure = go.Figure()
figure.add_trace(go.Scatter(x=positions[:, 0], y=positions[:, 1], mode="lines+markers",
                            name="ground truth", line=dict(color="#2a78d6", width=2)))
figure.add_trace(go.Scatter(x=aligned_poses[:, 0], y=aligned_poses[:, 1],
                            mode="lines+markers", name="estimate",
                            line=dict(color="#eb6834", width=2)))
figure.add_trace(go.Scatter(x=beacons[:, 0], y=beacons[:, 1], mode="markers",
                            name="beacons (truth)",
                            marker=dict(color="#2a78d6", size=13, symbol="square-open",
                                        line=dict(width=2))))
figure.add_trace(go.Scatter(x=aligned_beacons[:, 0], y=aligned_beacons[:, 1],
                            mode="markers", name="beacons (estimate)",
                            marker=dict(color="#eb6834", size=13, symbol="x")))
figure.update_layout(width=680, height=560, xaxis_title="x [m]", yaxis_title="y [m]",
                     yaxis=dict(scaleanchor="x", scaleratio=1))
figure.show()

error = np.linalg.norm(aligned_poses - positions, axis=1)
print(f"RMS position error after alignment: {np.sqrt((error ** 2).mean()):.4f} m")

RMS position error after alignment: 0.2290 m

Where the time goes¶

ranks = np.asarray(result.getRanksVisited()).astype(int)
phases = {
    "QCQP build": np.asarray(result.getQcqpBuildTimePerLevel()),
    "local solve": np.asarray(result.getNlpTimePerLevel()),
    "verify": np.asarray(result.getVerifyTimePerLevel()),
}

timing = go.Figure()
for name, seconds in phases.items():
    timing.add_trace(go.Bar(x=[f"p = {level}" for level in ranks], y=seconds, name=name))
timing.update_layout(
    barmode="stack", title="Time per staircase level",
    xaxis_title="staircase rank", yaxis_title="seconds",
    height=380, margin=dict(l=0, r=0, t=40, b=0))
timing.show()

for name, seconds in phases.items():
    print(f"{name:>12}: {seconds.sum():.5f} s")

  QCQP build: 0.00047 s
 local solve: 0.06121 s
      verify: 0.00393 s