Learning to Stay Certifiably Localizable: Certificate-Shaped Multi-Agent Policies

Robot teams that see each other only through cameras often know only the direction to a teammate. They do not know the distance, and they cannot tell which identical-looking robot they are looking at. Recovering everyone's relative position and orientation from such data is a hard non-convex problem. Local solvers fall into wrong answers, but a semidefinite relaxation can solve it globally. A semidefinite relaxation replaces the hard problem with a convex one over a larger matrix and, when the relaxation is "tight," returns the exact global answer together with a proof, called a certificate. Whether that proof exists depends on where the robots are. Some formations make the joint state uniquely recoverable. Others, such as symmetric or occluded layouts, leave it ambiguous. This proposal trains decentralized multi-agent policies, in which each robot acts only on its own sensor stream, using a reward derived from the certificate. The aim is for the team to learn to move in ways that keep its shared state provably recoverable while it does its task.

The opportunity is concrete. Certifiable Mutual Localization and Trajectory Planning for Bearing-Based Robot Swarms showed that the smallest nonzero eigenvalue of a certificate matrix measures how robustly the team's pose estimate stays certifiably optimal, and that planning trajectories to keep it high works. That system, however, uses a designated host robot that collects all data and runs a centralized deterministic trajectory optimizer. We ask whether the same signal can be compiled into learned, peer-to-peer policies that act under partial observability. We also ask whether it carries information that cheaper "observability" rewards miss.

Core Claim

The certificate eigenvalue measures global identifiability. It drops when the measurements admit a different, wrong joint configuration, which happens under anonymous-identity aliasing and near-symmetric formations. Standard information measures such as the minimum eigenvalue of the Fisher information matrix capture only local curvature around the true state, so they cannot see these failures. We claim that teams trained with a certificate-based reward will be certified more often and suffer far fewer gross localization failures than teams trained with Fisher-information or visibility rewards. The gap should be largest in aliasing-heavy regimes. Outside those regimes the certificate should offer little extra, and we will report that honestly.

Concretely, let $\lambda_t$ be the smallest nonzero eigenvalue of the certificate matrix $K$ for the team's bearing measurements over a sliding window ending at step $t$, computed as in Certifiable Mutual Localization and Trajectory Planning for Bearing-Based Robot Swarms. Let $B$ be that paper's precomputed noise-robustness threshold. The shaped team reward is

$$r_t = r^{\text{task}}_t + \beta \min(\lambda_t - B,\, 0),$$

where $r^{\text{task}}_t$ is the environment's task reward and $\beta > 0$ is a weight. The term penalizes only shortfalls below the threshold, so the policy is not rewarded for over-spreading once the team is already safely certifiable.

Research Program

The estimation component is reused, not invented. Measurement-to-robot association and relative poses are solved with the relaxation of Certifiably Optimal Mutual Localization with Anonymous Bearing Measurements. That paper casts anonymous bearing localization as a mixed-integer quadratic program and relaxes it to a semidefinite program. Its distance-marginalization trick makes cost scale with team size rather than measurement count, and the paper reports solving 200-measurement problems in milliseconds. That speed is what makes a per-window certificate affordable inside reinforcement-learning rollouts. The same paper also constrains the design. Tightness is proven only noise-free and when the number of measurements $n$ satisfies $n \ge 18N + 2$ for $N$ robots, and rank-one recovery empirically breaks down near 0.4 radians of angular noise. Our noise sweep is therefore centered on that boundary.

The learning component uses centralized training with decentralized execution. During training a critic may see privileged information, including the certificate. At execution each robot's policy sees only its own anonymous bearings, field-of-view mask, and odometry. We train with both a centralized-critic method (MAPPO) and independent learners (IPPO). COMRAD: A Benchmark for Embodied Cooperative Multi-Agent Reinforcement Learning found that independent learners beat centralized critics on role-asymmetric tasks, and certificate maintenance may be such a task: one robot "anchors" the formation while others move. We do not assume which method will win.

A team-level certificate reward creates a credit-assignment problem, because it does not say which robot broke identifiability. Following the counterfactual idea in Counterfactual Multi-Agent Policy Gradients, we also test a per-agent difference reward: $\lambda_t$ minus the certificate eigenvalue recomputed with agent $a$'s bearings removed. This needs only one extra certificate evaluation per agent. It is the proposal's secondary ingredient, and it gets its own ablation.

The environment will be built by us, because the file contains no existing multi-agent benchmark with anonymous bearing sensing. It will have 3 to 8 point-mass or quadrotor-dynamics agents in 3D obstacle fields. Agents carry limited-field-of-view anonymous bearing sensors with Gaussian angular noise. The task is to traverse to a goal region, and each robot's low-level controller consumes the team's relaxation-based relative pose estimate. A wrong estimate therefore degrades the task directly, which keeps the certificate from being a decorative auxiliary objective.

Baselines

The naive reference is the same MAPPO and IPPO training with task reward only. It shows how often teams stay certifiable when nothing asks them to. If this already yields near-universal certification, the problem is not real in our environment and we will redesign the scenarios.

The strongest existing method is the centralized certificate-aware planner of Certifiable Mutual Localization and Trajectory Planning for Bearing-Based Robot Swarms. It computes visibility-preserving corridors and optimizes trajectories so the certificate eigenvalue stays above $B$, with a host robot that sees everything. It is the strongest competitor because it directly optimizes the quantity we care about with full information. It is the upper reference our decentralized policies try to approach, not a method we expect to beat on certification. The file reports that its estimator reached the global optimum in 100% of noise-free simulation cases. It gives no numeric translation or rotation error, so no reported error result was found on Lacuna for this planner, and we will rerun it in our environment on identical obstacle layouts, start states, and noise draws. Beating it means matching its certified-step fraction within a few points while executing without a host and at a fraction of its per-step compute. We additionally hope to exceed it under communication dropout, where a host-based design should degrade.

For the estimator itself, the reference numbers come from Certifiably Optimal Mutual Localization with Anonymous Bearing Measurements. It reports a 100% global-optimum rate versus local solvers failing nearly 80% of the time from random initialization. On a real three-robot test it reports 0.77 m relative translation error versus more than 7 m for local optimization. We include the local-solver estimator as a downstream ablation to confirm that the relaxation, not just the policy, matters.

The decisive competitors are alternative shaping rewards, each plugged into the same $\min(\cdot - \text{threshold}, 0)$ form. Every reward gets the same environment-step budget, the same number of hyperparameter configurations (including its own weight $\beta$ and threshold), the same network architecture, and the same ten seeds. The first is a Fisher-information reward, using the minimum eigenvalue of the bearing Fisher information at the true configuration. The second is a visibility heuristic that counts in-view teammate bearings against the $18N+2$ measurement requirement. The third is a privileged reward on the true estimation error, which is available only in simulation. Two ablations isolate our ingredients: team-shared versus counterfactual certificate credit, and certificate evaluated at the ground-truth configuration versus at the current estimate.

Why not just…?

Why not just reward low Fisher information or low covariance, as active-perception work usually does? This is the real threat. In low-noise, well-separated formations, Fisher information and the certificate may rank configurations almost identically, and Fisher information is cheaper and smoother. The argument for the certificate is specific: Fisher information is a local quantity and cannot detect that a symmetric formation admits a second, wrong association of bearings to robots. That is exactly the failure anonymous sensing creates and the one Certifiably Optimal Mutual Localization with Anonymous Bearing Measurements addresses. Our aliasing-heavy scenarios are built to separate the two. If the Fisher reward matches the certificate reward there too, we will conclude the certificate is unnecessary for learning and report it as a negative result.

Why not just reward true estimation error directly, since the simulator knows the ground truth? This privileged reward is a strong training signal, but it is sparse and delayed in the way that matters. Error is small until an aliasing flip occurs, then catastrophically large, so the policy gets little warning about the approaching ambiguity. The certificate eigenvalue shrinks continuously before certification fails, which is the point of the threshold $B$ in Certifiable Mutual Localization and Trajectory Planning for Bearing-Based Robot Swarms. We test this directly by comparing learning curves and gross-failure rates. If the error reward wins, the practical value of the certificate reduces to its use at deployment, where ground truth is absent.

Why not just run the centralized certificate planner online? It requires a host robot and full data aggregation, and its eigenvalue-constrained trajectory optimization becomes expensive as team size grows. The broader certifiable-estimation literature reports similar scaling pain: Convex Relaxations for Pose Graph Optimization With Outliers notes general-purpose solvers failing beyond about 50 poses, and Optimal Initialization Strategies for Range-Only Trajectory Estimation reports 3.15 s for a dynamic relaxation. A learned policy moves that cost into training. We measure the planner's per-step time and certification under link dropout to show where amortization pays off. If the planner remains cheap and robust at our team sizes, the contribution narrows to decentralization.

Why not just let a recurrent multi-agent policy learn good formations from task reward alone? The naive baseline tests this. COMRAD: A Benchmark for Embodied Cooperative Multi-Agent Reinforcement Learning reports that coordination requiring implicit signaling under occlusion remained unsolved by all baselines at 100M steps. That suggests observability-preserving behavior rarely emerges from sparse task reward, but our environment, not that benchmark, will decide.

Proposed Experiments

The main experiment sweeps team size (3, 5, 8), angular noise (0.05 to 0.5 rad, straddling the reported 0.4 rad breakdown), and obstacle density. Each reward variant is trained under MAPPO and IPPO. The primary metric is the fraction of execution steps in which the relaxation is certified tight. Secondary metrics are the rate of gross localization failures (translation error above 1 m), median relative translation and rotation error, task success, collisions, and certificate compute per training step.

The decisive check is a pair of scenario families. In the "aliasing" family, identical robots must pass through narrow symmetric passages where mirror-image associations are plausible. In the "benign" family, robots move in open space with no symmetric configurations. The core claim predicts that the certificate reward beats the Fisher-information reward clearly on the aliasing family and ties it on the benign family. A tie on both falsifies the claim. A win on both would suggest the certificate is simply a better-conditioned reward, a weaker but still useful finding.

Two further checks probe generality. Policies trained with 5 robots are evaluated with 3 and 8 robots, and at noise levels outside training, to test whether they learned identifiability-preserving geometry rather than memorized formations. The counterfactual-credit ablation is run under both MAPPO and IPPO, to see whether per-agent certificate credit removes the centralized-critic penalty reported by COMRAD on role-asymmetric tasks.