Five Robots, One Guaranteed Map: How Robot Swarms Can Now Certify Their Perception

A swarm of robots is exploring a collapsed building after an earthquake. Each one carries a LiDAR scanner, weaving through debris while building a mental picture of its surroundings. Alone, each robot sees only a fragment — maybe 60% of the total space — and that fragment is blurred by sensor noise and corrupted by the robot's own uncertain position estimate. Together, though, their fragments overlap and fill in. A corner that one robot could only guess about becomes confirmed when three others agree. A hallway that seemed clear turns out to be blocked when two robots' readings conflict with a third's. This is the promise of multi-robot mapping: wisdom of the crowd applied to physical space.

But there is a catch that most research papers mention only in passing. Every mapping system must eventually answer a single, blunt question: is this particular point in space free to traverse, or is something there? That answer — the binary occupancy classification — is what planning and safety systems actually consume. And getting it wrong can mean sending a robot into a wall, or worse, into a hazard. Yet every mainstream approach to this problem either produces a probabilistic score (a number between 0 and 1 that says "probably free") or forces the user to pick an arbitrary threshold to convert that score into a yes/no answer. Neither path offers any guarantee about how often the final answer is right.

A new paper from researchers at KTH Royal Institute of Technology in Stockholm takes direct aim at this gap. Ritvik Mahajan, Aneesh Raghavan, and Karl Henrik Johansson have developed a distributed algorithm that lets a team of robots fuse their individual, imperfect maps into a single shared map — and they prove that this shared map comes with a mathematical guarantee: at least 95% of the time (or whatever target level you choose), the map's answer includes the true state of the world. Not probably. Not on average. With probability at least 1 minus whatever error rate you specify, the true label is inside the map's set of admissible answers.

That guarantee holds regardless of how noisy the sensors are, how sparse the data is, or how the robots are arranged in communication networks. The robots never share raw sensor readings — only lightweight numerical summaries called e-values. And the theoretical guarantee is finite-sample, meaning it kicks in from the very first batch of data, not just in the limit as data accumulates. For safety-critical applications — search-and-rescue, autonomous vehicles operating in shared spaces, inspection of hazardous environments — this kind of certifiable reliability is not a nice-to-have. It is the entire ballgame.

The Science

The core problem the paper addresses is called occupancy mapping: assigning each point in a 2D workspace either a "free" or "occupied" label. This is distinct from likelihood mapping, which produces a continuous score — essentially a probability or log-odds value — for each location. Every deployed planning or navigation system ultimately needs the occupancy classification. Somewhere between the probability score and the robot's wheel commands, someone has to draw a line and say "below this threshold, treat it as traversable; above it, treat it as blocked."

The classical approach is the Occupancy Grid Map (OGM), which discretizes the workspace into a grid and estimates each cell's occupancy independently. It is computationally tractable and widely used, but it has a fundamental weakness: it throws away spatial correlations. The fact that two adjacent cells are both likely free is information, and discarding it means your map is strictly weaker than it could be.

More sophisticated approaches use Gaussian Process Occupancy Mapping (GPOM), which models the entire occupancy field as a smooth spatial function. A GP can predict occupancy at any location — not just at grid cells — and it provides a natural uncertainty estimate: the predictive variance tells you how confident the model is at each point. Recent work has extended GPOM to handle incremental updates as new sensor data arrives and to scale to larger environments using techniques like Hilbert Maps.

But here is the problem that Mahajan and colleagues identify with surgical precision: none of these methods offer finite-sample guarantees. Their uncertainty estimates come from assumptions — that the GP's hyperparameters are tuned correctly, that the sensor noise follows a particular distribution, that future data will resemble past data. In real deployments, those assumptions break. A robot's trajectory creates temporal correlation in its data. Different parts of the environment have different structures. Sensor noise varies with conditions. The uncertainty estimates become heuristics, and the guarantee evaporates.

The authors' starting point is conformal prediction, a distribution-free framework for constructing prediction sets with provable finite-sample coverage. The idea, in its standard form, is elegant: you have a sequence of exchangeable data points, a model fit to most of them, and a held-out calibration set. For any new query point, you compute a "nonconformity score" — essentially a measure of how surprising the point would be under the model — and compare it to the scores of the calibration points. The set of labels for which the query's score is not unusually large forms the prediction set. Under exchangeability, this set covers the true label with probability at least 1 minus your chosen error rate, from the first sample onward.

The problem is that standard conformal prediction assumes exchangeability, and real robot data is anything but. A robot moving through an environment takes measurements that are correlated over time: if the robot is at position A and sees an occupied cell, it is likely to still be near that cell a moment later, taking measurements that are not independent draws from the same distribution. The paper formalizes this using two assumptions: local stationarity (within each block of time, the data distribution is approximately constant, quantified by total variation distance) and β-mixing (temporal dependence decays as the gap between measurements grows). These are mild assumptions that any real robot with continuous motion will satisfy.

Even with these assumptions, each robot's local conformal guarantee is degraded in two ways. First, the robot covers only a limited spatial region, so its guarantee only applies to locations it has actually observed. Second, the temporal correlations within its trajectory mean the conformal calibration is less reliable than it would be with independent data. The authors take these degraded local guarantees as given and ask: can we recover the target coverage level by combining them across a team of robots?

The key insight is that robots do not need to share their raw data — only lightweight scalar summaries. The paper uses e-values (expectation values), which are non-negative numbers with the property that their expectation under a null hypothesis is at most 1. If you observe an e-value that is much larger than 1, that is calibrated evidence against the null. E-values have a crucial property: they are closed under deterministic convex averaging. If each robot produces an e-value with expectation at most 1 under the null, then any weighted average of those e-values also has expectation at most 1. This is what allows distributed fusion without a central coordinator and without sharing raw data.

What They Found

The paper's technical contribution is a fusion algorithm that operates in a single communication round. At the end of each block of data collection, every robot computes e-values for every query location in a shared query set — a common reference grid over the workspace, fixed across all blocks. For each query location and each candidate label (free or occupied), the robot computes an e-value that combines four ingredients: a conformal p-value from its local GP model, a recalibrated detection threshold matched to its neighborhood's miscoverage budget, an observation gate that activates the robot only where it has actually collected data, and an uncertainty attenuation that down-weights queries where the robot is highly uncertain.

The observation gate is crucial. The authors show that the GP's natural uncertainty measure — predictive standard deviation — is unsuitable for this role because a stationary Matérn kernel saturates at the prior variance even far from observed regions. Instead, they gate on Euclidean proximity to the robot's actual training inputs: a robot is "active" at a query location if that location is within a radius r of at least one point the robot has observed. This confines each robot's contribution to the region where its local conformal guarantee is meaningful.

The miscoverage budget is split across the neighborhood. If an agent has d neighbors (including itself), it allocates β = α/d as its per-agent budget. Each robot recalibrates its conformal threshold to this budget, then constructs an e-value that fires (equals 1, scaled by attenuation) whenever the p-value falls below that threshold, but only within its observation gate. The e-value is zero everywhere else.

At fusion time, each robot receives e-values from all its neighbors and averages them. The fused prediction set is simple: for each query location and label, include that label in the set if the averaged e-value is less than 1/α. In other words, if the combined evidence across the neighborhood says the label is unlikely at your target error rate, exclude it. Otherwise, include it. If the evidence is too ambiguous — if no agent has sufficient data or confidence — the map returns both labels, declining to commit.

The authors prove (Theorem IV.1) that this fused set satisfies the coverage guarantee at every agent, regardless of the communication graph topology or the sensor noise distribution. The proof relies on the e-value property: since each local e-value has expectation at most β under the null, and averaging preserves the e-value property, the fused e-value has expectation at most 1. Applying Markov's inequality then yields the coverage bound. The temporal mixing assumptions enter because they ensure the local conformal calibration is valid — that the local miscoverage rate is indeed bounded by β.

There is a second theoretical result (Proposition 2) that justifies the uncertainty attenuation. When the local guarantee is loose — when the robot is uncertain but confident — the attenuation supplies the margin needed to recover the target coverage level. If a robot's predictive variance is high at a query location, the attenuation factor exp(−λσ) shrinks the e-value, making it less likely to exclude a label even if the p-value is low. This prevents overconfident exclusions in regions of high uncertainty.

The empirical results validate the theory and illustrate its practical implications. In a simulated 2D environment, the authors deploy 1 to 5 robots along trajectories that cover partially overlapping regions of the workspace. They vary the LiDAR range-noise standard deviation (σᵣ from 0 to 0.1 m) and the retained-scan fraction (from 0.1 to 1.0), and they test two communication topologies: a sparse graph (agents connected only to nearby neighbors) and a dense graph (every agent connected to every other).

Noise Degradation in Single-Robot Mapping

Label	Value
σᵣ = 0.00	0.86
σᵣ = 0.02	0.85
σᵣ = 0.04	0.84
σᵣ = 0.06	0.83
σᵣ = 0.08	0.82
σᵣ = 0.10	0.82

OGM ROC-AUC vs. ground truth. Noise degrades map quality even for grid-based methods. Source: Mahajan et al., 2026

The first chart shows how single-agent mapping quality degrades with noise. The grid-based OGM's ROC-AUC (a measure of classification accuracy, where 1.0 is perfect) falls from 0.86 to 0.82 as σᵣ increases from 0 to 0.1 m. The GP-based approach resists noise better but costs roughly 18 times more computation and still saturates below 1.0. This illustrates the fundamental limitation the paper starts from: more noise means worse maps, and you cannot eliminate this degradation by changing the algorithm alone.

Diminishing Returns of Additional Data

Label	Value
0.1	0.87
0.3	0.88
0.5	0.89
0.7	0.91
0.9	0.92
1.0	0.93

IGPOM ROC-AUC and training time vs. retained scan fraction. More data yields negligible improvement while compute increases ~10×. Source: Mahajan et al., 2026

The second chart shows that collecting more data does not close this gap. As the retained-scan fraction grows from 0.1 to 1.0, the GP's ROC-AUC stays within [0.87, 0.93] and never approaches 1.0. Meanwhile, the GP training time rises roughly tenfold, from 14 seconds to 134 seconds. The achievable single-agent quality is bounded away from perfect and cannot be bought with more measurements. This is a key motivation for collaboration: no single robot, no matter how long it maps, can produce a perfect occupancy classification of the entire workspace.

Multi-Agent Collaboration Improves Map Quality

Label	Value
1 agent	0.8
2 agents	0.92
3 agents	0.93
4 agents	0.94
5 agents	0.95

Fused whole-workspace ROC-AUC vs. number of agents. Collaboration fills coverage gaps no single robot can address. Source: Mahajan et al., 2026

The third chart shows what collaboration actually buys. Fusing more agents' local maps raises the whole-workspace ROC-AUC from 0.80 with one agent (which individually covers only ~60% of the map) to 0.95 with five agents. Strikingly, the gains are not linear: two complementary robots, each scoring 0.79 individually, reach 0.92 when fused. The marginal value of each additional agent decreases, but there is still substantial improvement even at five. This demonstrates that collaboration extends coverage — it maps regions that no single robot ever observes.

But the most important empirical finding is about coverage, not ROC-AUC. Across all experiments — varying α from 0.01 to 0.2, both communication topologies, and all noise levels — the fused predictor reliably meets its theoretical coverage bounds. The empirical miscoverage rate never exceeds the target α. This is the core empirical contribution: the theoretical guarantee is not a paper theorem that fails in practice. It holds.

The paper also quantifies a tradeoff that emerges from the algorithm's design: wherever the fused evidence is insufficient to exclude a label at the 1/α threshold, the map returns both labels (free and occupied), effectively declining to classify. This leaves a significant fraction of the domain unclassified rather than thresholded into a single decision. The denser communication topology significantly shrinks this unclassified fraction because more agents contribute evidence to more locations. In the sparse topology, many query points fall outside every agent's observation gate; in the dense topology, the agents' coverage regions overlap more, and more points receive enough evidence to decide.

Why This Changes Things

The significance of this work is not that it produces better-looking maps. It is that it produces maps with a provable, distribution-free guarantee on correctness. In robotics, this distinction is enormous.

Existing mapping systems — GPOM, Hilbert Maps, OGM variants, learned approaches — are all heuristic at their core. They produce probability estimates that reflect assumptions about data distributions, noise models, and prior beliefs. When those assumptions hold, the maps are good. When they do not, the maps may be confidently wrong. A GP that assumes Gaussian observation noise will misbehave when the noise is heavy-tailed. A method that assumes the environment is stationary will fail when conditions change. These are not edge cases; they are the norm in real deployments.

Conformal prediction sidesteps this entire class of problems. It does not assume a particular noise distribution. It does not assume that future data will look like past data in any parametric sense. It only assumes exchangeability (or, in this paper's formulation, locally stationary β-mixing, which is weaker). And it delivers a guarantee that is finite-sample: from the very first batch of calibration data, you know that at most α fraction of your queries will have the true label outside the prediction set.

For multi-robot systems, this is especially valuable because the data distribution is inherently non-uniform and evolving. Different robots cover different regions. The spatial sampling distribution changes as exploration proceeds. Heterogeneous sensing means different agents have data of different quality. All of this makes parametric uncertainty quantification unreliable. The conformal approach absorbs this heterogeneity into the guarantee: you do not need the data to be identically distributed across agents or across time; you only need the local mixing conditions to hold.

The distributed nature of the algorithm is also a practical breakthrough. Traditional conformal prediction requires a central calibration set — a batch of labeled examples held out from training, used to compute the nonconformity scores. In a multi-robot setting, there is no natural central coordinator, and sharing raw calibration data may be impossible (privacy constraints, communication bandwidth, adversarial concerns). By using e-values that are closed under averaging, the paper achieves conformal guarantees through local computation and a single round of message passing. Each robot broadcasts only a scalar for each (query location, label) pair — a handful of floating-point numbers — and the fusion rule is a simple average. This is communication-efficient, privacy-preserving, and robust to network topology.

For real-world deployment, consider what this means. A team of autonomous drones is surveying a construction site for safety hazards. Each drone flies its own route, observes its own subset of the environment, and maintains its own local map. At the end of each mapping run, the drones exchange e-values — tiny messages that convey no raw sensor data, no images, no trajectory information. Every drone fuses the received e-values with its own to produce a shared occupancy map. That map comes with a formal guarantee: at least 95% of the time (or 99%, depending on your choice of α), the true state of every point is inside the map's set of admissible answers. If the map says a region is free, it is free with high probability. If it says occupied, there is something there with high probability. If it says both, then the evidence is insufficient to decide, and a conservative planner should treat it as potentially occupied.

This kind of guarantee is transformative for regulatory approval. Autonomous systems operating in human environments face increasing scrutiny, and regulators need evidence that the systems will not cause harm. A map with a 95% coverage guarantee is categorically different from a map with a heuristic confidence score. One is a mathematical statement backed by a proof; the other is a number that looks precise but has no certified meaning.

The tradeoff — unclassified regions — is also worth dwelling on. The algorithm's conservative nature means it will sometimes decline to classify a point rather than risk being wrong. In sparse networks, this can be a substantial fraction of the workspace. But this is a feature, not a bug. A planner that receives "don't know" can fall back to conservative behavior — slow down, request more data, treat the region as potentially occupied. This is exactly the kind of uncertainty-aware decision-making that safety-critical systems require. The worst alternative is a map that gives you a confident wrong answer.

What's Next

The paper is careful to acknowledge its limitations and to point toward fruitful extensions. The most immediate open question is whether the unclassified fraction can be reduced without sacrificing coverage. The authors show that denser communication topologies help, but there may be other ways to improve efficiency: adaptive query selection (actively querying regions where the current evidence is ambiguous), iterative fusion rounds (instead of a single broadcast, allowing agents to build up evidence over time), or hierarchical fusion (agents with strong local evidence can propagate confidence to neighbors who in turn share it further).

The current formulation is static: given a block of data, produce a map with a coverage guarantee for that block. An important extension would be to streaming data, where the environment is not fixed and the map must be updated continuously. Conformal prediction has been extended to online settings, and the authors' use of block-wise calibration is a step in that direction, but a fully dynamic version with anytime guarantees remains open.

Another limitation is the assumption that the GP hyperparameters are known or estimated correctly. In practice, the choice of kernel lengthscale and signal variance can substantially affect the GP's predictions. The paper assumes these are fixed per-agent, but misspecification could degrade the local conformal guarantee. Robust conformal prediction under model misspecification is an active area of research, and applying those techniques here could make the approach more practical.

The paper focuses on occupancy classification (binary free/occupied), but the framework extends naturally to other settings. Any spatial estimation problem — temperature mapping, pollution monitoring, infrastructure inspection — where multiple agents collect correlated data and a guarantee on prediction correctness is required, could benefit from this approach. The key requirements are: a conformalizable base learner, temporal mixing in the data, and a shared query set across agents.

Finally, the communication model assumes all agents agree on a common query set (a shared reference grid over the workspace). In some deployments, defining this grid may be nontrivial — for example, if agents operate in 3D environments or if the query set must be adaptive to the explored region. Extensions to dynamically defined query sets, or to continuous query sets where the guarantee holds for any point in space rather than a predefined grid, would broaden the applicability.

Despite these open questions, the paper's core contribution stands: a distributed algorithm that achieves finite-sample conformal coverage guarantees for multi-robot occupancy mapping, without sharing raw data, under realistic assumptions about temporal correlation and non-uniform spatial coverage. This is a foundational result for certifiably reliable robot perception. As autonomous systems move from controlled environments into the messy, uncertain, human-populated world, guarantees like these are not optional. They are the only basis for responsible deployment. Mahajan, Raghavan, and Johansson have shown how to get them — and the path forward is rich with opportunity.