⚡ electrical engineering

Finite-Sample Conformal Coverage Recovery via Fusion under Degraded Local Guarantees in Occupancy Map Estimation

This paper proposes a distributed fusion algorithm that exchanges lightweight scalar e-values among robots to recover finite-sample conformal coverage guarantees in occupancy map estimation, effectively compensating for degraded local predictions caused by temporal correlations and limited observations while ensuring the fused map meets user-specified reliability bounds regardless of communication topology or sensor noise.

Original authors: Ritvik Mahajan, Aneesh Raghavan, Karl Henrik Johansson

Published 2026-07-17

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Ritvik Mahajan, Aneesh Raghavan, Karl Henrik Johansson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to draw a map of a giant, dark cave using only a small, flickering flashlight. You are one of many explorers, and each of you is walking a different path. The problem is that your flashlight is a bit shaky, and the air is full of dust that makes the light bounce around. If you try to draw the map based only on what you see, you might make mistakes: you might think a wall is there when it isn't, or miss a hole in the floor entirely. In the world of robots, this is the challenge of "occupancy mapping"—figuring out where things are and where there is empty space so a robot can move safely without crashing.

To solve this, scientists often use a clever trick called "conformal prediction." Think of this as a robot's internal "safety net." Instead of just guessing, "I think this spot is a wall," the robot says, "I am 95% sure this spot is a wall, and I promise that if I make a mistake, it will happen no more than 5% of the time." This is great for a single robot, but it gets tricky when a team of robots tries to work together. Why? Because robots don't just take random, independent photos; they move in a line, and their path creates patterns that confuse the safety math. Also, one robot might only see the left side of the cave, while another sees the right. If they just mash their maps together, the "safety net" might tear, and the team could end up with a map that looks good but is actually dangerous.

This paper, titled "Finite-Sample Conformal Coverage Recovery via Fusion under Degraded Local Guarantees in Occupancy Map Estimation," tackles exactly that problem. The authors, Ritvik Mahajan, Aneesh Raghavan, and Karl Henrik Johansson, propose a new way for a team of robots to share their maps without sharing all their raw data. They developed a method where robots exchange tiny, lightweight "confidence scores" (called e-values) with their neighbors. By combining these scores using a special math recipe, the team can rebuild a map that is just as safe as if they had perfect data, even though each robot's individual view was flawed and correlated.

The researchers tested this idea in a computer simulation with five robots exploring a 30-by-20 meter area filled with walls and obstacles. They found that when the robots shared their confidence scores, the final map was incredibly reliable. In fact, the team's map was correct about 97% to 99% of the time, which is even better than the 80% safety guarantee they asked for. However, there is a catch: sometimes, if the robots didn't have enough information to be sure, the map would simply say, "I don't know," leaving a spot unclassified rather than guessing wrong. The study showed that if the robots could talk to more neighbors (a "denser" network), they could fill in more of these "I don't know" spots, making the map more useful without losing its safety.

The Robot Team's Dilemma

Imagine a group of five friends trying to draw a map of a giant, foggy warehouse. Each friend has a flashlight, but the light is a bit wobbly, and the fog makes it hard to see clearly. They are also walking in a line, so what one friend sees is very similar to what the friend right behind them sees. This is a problem because if they all try to draw the map together, they might all make the same mistake in the same place, thinking a shadow is a wall.

In the world of robotics, this is the difference between a "likelihood map" (a guess about how likely a spot is to be a wall) and an "occupancy map" (a definite "yes, wall" or "no, free space"). Most robots are great at making the guess, but they struggle to prove that their "yes" or "no" is actually safe. They can't just say, "I'm 90% sure," because in a safety-critical situation, you need a guarantee: "I promise I will be wrong no more than 1 time out of 10."

The paper starts by showing that when a single robot tries to do this alone, it hits a wall. Even if the robot collects a huge amount of data, its "safety promise" gets weaker because the data is too connected (it's all from the same path) and the robot only sees a small part of the warehouse. It's like trying to guess the weather for an entire continent by only looking out your own window for an hour.

The Magic of the "Confidence Score"

So, how do the robots fix this? The authors came up with a clever system where the robots don't share their raw photos or their complex math models. That would be too heavy and slow. Instead, they share something much simpler: a "confidence score" for every spot on the map.

Think of this score like a vote in a game of "True or False."

The Local Vote: Each robot looks at a spot on the map. If it has never been there, it stays silent. If it has been there, it checks its internal safety math. If it's very sure a spot is a wall, it casts a strong "Wall" vote. If it's unsure, it casts a weak vote or stays silent.
The Safety Net: The robots use a special math trick (conformal prediction) to make sure that if they cast a vote, they are statistically unlikely to be wrong. But because the data is "correlated" (they walked in a line), their individual safety nets are a bit leaky.
The Fusion: This is where the magic happens. The robots pass their votes to their neighbors. They don't just add the votes up; they use a special "budget" system. Imagine the team has a total "mistake budget" of 5%. They split this budget among all the friends in the group. If one friend is super confident and has seen a spot clearly, they can use their share of the budget to make a decision all by themselves. If no one is sure, the group admits, "We don't know," and leaves the spot blank.

The paper calls these votes "e-values." They are like little packets of evidence that say, "I have enough proof to bet against this being a free space." The robots combine these packets using a simple average. The beauty of this method is that it works no matter how the robots are connected. Whether they are in a circle, a line, or a big web, the math guarantees that the final map will be safe.

What the Simulations Showed

To test this, the authors ran a simulation with five robots in a 30-meter by 20-meter room. They gave the robots noisy sensors (like a flashlight that flickers) and made them walk in overlapping paths. They compared two ways the robots could talk to each other:

The Ring: Robots only talk to the two neighbors right next to them, like people in a circle holding hands.
The Mesh: Every robot talks to every other robot, like a group of friends all shouting to each other at once.

The results were impressive. In both cases, the robots successfully kept their promise: they were wrong less than 20% of the time (actually, they were wrong less than 3% of the time, which is even better!). But the "Mesh" network was much better at filling in the map.

In the Ring, the robots could only decide on about 44% of the map spots. The rest were left as "I don't know" because the robots didn't have enough neighbors to help them feel confident.
In the Mesh, the robots could decide on about 85% of the map spots. Because they could hear from everyone, they had enough combined confidence to make a call on almost everything.

The paper also showed that if the robots were extra cautious (by turning up a "dial" called attenuation), they could become even more sure, but they would decide on fewer spots. It's a trade-off: you can be super safe and leave many blanks, or be a bit more decisive and fill in more of the map.

The Bottom Line

This paper doesn't claim to have solved every problem in robot mapping. It admits that their safety guarantee is an "average" promise—it works for the whole map, but it doesn't guarantee that every single specific spot is correct if you look at it in isolation. It also relies on the robots moving in a somewhat predictable way. If the robots were jumping around wildly, the math might need to be adjusted.

However, the core finding is solid: by sharing simple confidence scores instead of complex data, a team of robots can build a map that is both safe and useful. They can recover the "safety promise" that gets lost when robots work alone. And the more they talk to each other, the more of the map they can confidently fill in. It's a step toward robots that can explore dangerous places, like collapsed buildings or deep caves, and come back with a map they can truly trust.

Technical Summary: Finite-Sample Conformal Coverage Recovery via Fusion under Degraded Local Guarantees in Occupancy Map Estimation

1. Problem Statement

Accurate environmental mapping is critical for multi-robot autonomy. While continuous mapping techniques like Gaussian Process Occupancy Mapping (GPOM) provide rich spatial correlation and uncertainty estimates, they lack formal, finite-sample guarantees on predictive reliability. Conversely, Conformal Prediction (CP) offers distribution-free coverage guarantees but relies on the assumption of exchangeable (i.i.d.) data. In multi-robot scenarios, this assumption is violated due to:

Temporal Correlation: Data collected along a robot's trajectory are temporally correlated, breaking the exchangeability required for standard CP calibration.
Spatial Limitations: Individual robots observe only a non-uniform, spatially limited portion of the environment.

Consequently, when a single robot applies conformal prediction to its local map, the resulting coverage guarantee degrades below the target level. Existing distributed fusion methods (e.g., using Gaussian Mixture Models or distributed factor graphs) fail to provide formal, distribution-free guarantees on the fraction of correctly answered map queries. The core problem addressed is Coverage Retrieval: designing a distributed fusion rule that recovers a user-specified coverage level ( $1-\alpha$ ) across a team of robots, despite degraded local guarantees caused by temporal correlations and partial spatial coverage, without exchanging raw sensor data.

2. Methodology

The proposed approach decouples local model fitting from distributed fusion, utilizing e-values (non-negative random variables with expectation $\le 1$ ) to aggregate evidence.

A. Local Estimation and Calibration
Each agent $i$ operates in temporal blocks. Within each block:

Training: An Exact Gaussian Process (GP) with a Matérn-3/2 kernel is fitted to a training dataset to model the occupancy likelihood.
Calibration: A calibration dataset is used to compute nonconformity scores (normalized residuals).
Recalibration: To account for the degraded local guarantee, the agent recalibrates its internal threshold $a^i_k$ based on a per-neighborhood miscoverage budget $\beta_i = \alpha / d_i$ , where $d_i$ is the size of the agent's communication neighborhood (including itself).
E-value Construction: For a query location and candidate label, the agent computes a scalar e-value. This e-value incorporates:
- Observation Gate: A binary indicator ensuring the agent only contributes evidence where it has actually observed data (proximity to training inputs).
- Uncertainty Attenuation: A factor $g^i_k(x) = \exp(-\lambda \hat{\sigma}^i_k(x))$ that down-weights contributions where the local GP predictive uncertainty is high.
- Normalization: The indicator is divided by the estimated local miscoverage $\epsilon^i_k$ (estimated on a held-out fold) to ensure the expectation remains $\le 1$ .

B. Distributed Fusion
Agents communicate only lightweight scalar e-values to their immediate neighbors over a communication graph $\mathcal{G}$ .

Fusion Rule: Each agent aggregates received e-values using a fixed, uniform weighted average: $e^{\text{fused}}_k = \sum_{j \in \mathcal{N}(i) \cup \{i\}} w^j_k e^j_k$ , where $w^j_k = 1/d_i$ .
Prediction Set: The fused e-value is converted to a fused p-value ( $p^{\text{fused}} = \min(1, 1/e^{\text{fused}})$ ). The final prediction set includes labels where $p^{\text{fused}} > \alpha$ .
Output: The result is a set-valued map. If the evidence is insufficient to exclude a label, the map returns both "free" and "occupied" (an abstention), rather than forcing a potentially incorrect binary decision.

3. Key Contributions

Algorithm for Coverage Recovery: The paper presents an algorithm (Algorithm 1) that recovers the target coverage level $1-\alpha$ for distributed occupancy mapping under non-i.i.d. conditions. It relies on splitting the target miscoverage budget among neighbors and using e-value fusion.
Theoretical Guarantees: The authors prove (Theorem 4.1) that the fused prediction set satisfies the coverage guarantee $P(Y^* \notin \Gamma^{\text{fused}}) \le \alpha$ for any communication graph topology and any sensor noise distribution, provided the data satisfies local stationarity and temporal mixing assumptions.
Uncertainty Attenuation: A mechanism is introduced to handle cases where local guarantees fail due to high predictive uncertainty. By tuning the attenuation parameter $\lambda$ , the system can trade off between map efficiency (decisiveness) and strict validity, ensuring the e-value property holds even when local bounds are loose.
Communication Efficiency: The method requires only the exchange of scalar e-values, avoiding the transmission of raw point clouds or full GP model parameters.

4. Experimental Results

Simulations were conducted with 5 robots in a 2D environment using LiDAR data with noise. Two communication topologies were compared: a Ring (degree 3) and a Mesh (complete graph, degree 5).

Validity: Both topologies achieved empirical coverage significantly higher than the nominal target ( $1-\alpha = 0.8$ ). The mesh topology achieved ~0.976 coverage, and the ring achieved ~0.990, confirming the theoretical bounds hold.
Efficiency and Topology: The Mesh topology significantly outperformed the Ring in terms of map utility.
- Classified Fraction: The Mesh decided 84.8% of queries (singleton sets), whereas the Ring decided only 43.6%.
- No-Data Fraction: The Mesh reduced the fraction of unclassified queries (where no neighbor had data) to 1.7%, compared to 17.4% for the Ring.
- Accuracy: For the cells where a decision was made, accuracy was high (97–99%) for both topologies.
Attenuation: Sweeping the attenuation parameter $\lambda$ demonstrated a "validity-efficiency dial": increasing $\lambda$ raised coverage toward 1.0 but reduced the classified fraction toward 0, confirming the trade-off between conservativeness and informativeness.

5. Significance and Claims

The paper claims to bridge the gap between scalable continuous mapping and the reliability requirements of safety-critical autonomy. Its primary significance lies in:

Formal Guarantees under Realism: It provides the first formal, finite-sample, distribution-free coverage guarantees for distributed multi-agent occupancy fusion under correlated, non-i.i.d. data.
Robustness to Topology: The validity of the coverage guarantee is independent of the communication graph structure, making the approach robust to intermittent connectivity or varying network densities.
Handling Degraded Local Data: It explicitly addresses the degradation of local conformal guarantees caused by temporal correlations and partial observation, recovering the global target through fusion rather than requiring perfect local conditions.

The authors acknowledge limitations: the guarantee is marginal (averaged over test points) rather than pointwise conditional; it relies on assumptions of local stationarity and temporal mixing; and communication costs still scale with the size of the shared query set. However, the work establishes a principled framework for certifying map predictions in multi-robot systems without exchanging raw data.