💻 computer science

Safe Planning in Unknown Environments Using Conformalized Semantic Maps

This paper introduces a novel, model-free planning framework that utilizes conformal prediction to quantify perceptual uncertainty in semantic maps, enabling robots to safely execute reach-avoid tasks in unknown environments with guaranteed user-defined mission completion rates without prior knowledge of sensor models.

Original authors: David Smith Sundarsingh, Yifei Li, Tianji Tang, George J. Pappas, Nikolay Atanasov, Yiannis Kantaros

Published 2026-02-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David Smith Sundarsingh, Yifei Li, Tianji Tang, George J. Pappas, Nikolay Atanasov, Yiannis Kantaros

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 driving a self-driving car through a brand-new city where the street signs are blurry, the fog is thick, and the map you were given might be wrong. Your goal is to get to a specific destination, but you have a strict rule: you must never get too close to certain things. For example, you must stay 3 meters away from cars, but you can get closer to trees.

The problem is, your car's "eyes" (cameras and sensors) aren't perfect. Sometimes it thinks a person is a tree, or it misses a car entirely because of a shadow. Most current self-driving systems either:

Trust the map blindly: They assume the blurry image is 100% real. If they think a tree is a car, they might stop unnecessarily. If they think a car is a tree, they might crash into it.
Guess the odds: They try to calculate the probability of error based on how the camera works, but if the camera acts weirdly (like in the fog), their math breaks down.

This paper introduces a new, super-cautious way to drive that doesn't need to know exactly how the camera works or what kind of "noise" it makes. It uses a statistical trick called Conformal Prediction to guarantee safety.

Here is how it works, using simple analogies:

1. The "Safety Bubble" (Conformal Prediction)

Imagine you are playing a game where you have to guess what's in a box. Instead of saying, "I'm 90% sure this is a cat," the new system says, "I will put a safety bubble around my guess. Inside this bubble, I guarantee that the real answer is hiding, 95% of the time."

How it's built: Before the robot goes into the unknown city, it practices in a training ground. It makes mistakes, records them, and figures out the "worst-case scenario" for how wrong it could be.
The Result: When the robot sees a blurry object, instead of picking just one label (e.g., "Tree"), it creates a list of possibilities: {Tree, Human, Car, Empty Space}. It knows that the real object is definitely in that list.

2. The "Worst-Case Driver" (Conservative Planning)

Now, the robot has to plan its path. It looks at its list of possibilities for every object on the map.

If the list says an object could be a Tree (safe to get close to) OR a Human (must stay far away), the robot assumes it is a Human.
It drives as if the worst possible thing is true. It takes the "scariest" path that is still safe.

This is like walking through a dark room with a stick. If you aren't sure if the object in front of you is a harmless bush or a sharp cactus, you treat it like a cactus and walk around it.

3. The "Explorer Mode" (When the Map is Too Foggy)

Sometimes, the list of possibilities is so long (e.g., "It could be a car, a truck, a person, a dog, or a rock") that the robot can't find any safe path without hitting something.

The Switch: The robot stops trying to drive straight to the goal. Instead, it switches to Explorer Mode.
The Action: It drives in a zig-zag pattern or spins around to get a better look at the blurry object.
The Goal: Once it gets a clearer view, the "safety bubble" shrinks. Maybe it realizes, "Oh, it's just a tree!" Now the list is just {Tree}, and the robot can drive closer and faster again.

Why is this a big deal?

No "Black Box" Assumptions: Old methods needed to know exactly how the camera fails (e.g., "The camera gets 10% grainy in the rain"). This new method doesn't care. It just learns from experience how wrong it actually got, regardless of why.
Guaranteed Safety: The math proves that if you set the safety level to 95%, the robot will actually succeed 95% of the time, even if the environment is totally unknown.
Better than "Best Guess": In tests, robots using this method crashed far less often than robots that just guessed the most likely answer or tried to calculate complex probabilities.

The Trade-off

The only downside is that the robot might take a longer path. Because it is so cautious, it might drive around a bush just in case there's a person hiding behind it. But the paper argues that taking a 10% longer route is a small price to pay for not crashing into a pedestrian.

In short: This paper teaches robots to be paranoid but smart. Instead of guessing, they create a "safety net" of possibilities and drive based on the worst-case scenario, only stopping to look closer when they are truly unsure. This ensures they reach their destination safely, even in a world they've never seen before.

1. Problem Statement

The paper addresses the challenge of semantic reach-avoid planning for robots operating in unknown environments under perceptual uncertainty.

The Task: A robot must navigate to a goal region while maintaining class-dependent safety distances from unknown semantic objects (e.g., maintaining 1m from cars, 3m from trees).
The Challenge: Existing planners often treat semantic maps generated by AI perception systems (like semantic segmentation) as ground truth, ignoring inherent uncertainty. This leads to a lack of correctness guarantees. Other methods that do account for uncertainty typically rely on known sensor models or assume specific noise distributions (e.g., Gaussian), which are often inaccurate in real-world scenarios.
The Goal: Design a planning algorithm that guarantees a user-defined mission completion probability ( $1-\alpha$ ) without requiring knowledge of the sensor model or noise characteristics.

2. Methodology

The proposed framework integrates Conformal Prediction (CP) with semantic mapping and reactive planning. It operates in three main stages:

A. Semantic Mapping

The robot uses an existing semantic mapping algorithm (e.g., based on Detectron2 and OctoMaps) to build a probabilistic map ( $m_t$ ) of the environment. Each grid cell $j$ is assigned a probability mass function (PMF) over semantic classes based on sensor measurements. Crucially, the authors acknowledge that these PMFs do not represent true probabilities due to model inaccuracies.

B. Conformalization of Semantic Maps

To quantify uncertainty without assuming a noise model, the authors apply Conformal Prediction (CP):

Calibration: A set of calibration environments with known ground-truth labels is used.
Non-Conformity Score (NCS): For each calibration environment, an NCS ( $s_i$ ) is computed. This score represents the worst-case mapping error across all possible robot paths and time steps:
$s_i = \max_{x_{0:H}, j, t} (1 - p_t(m_j = k^{gt}_j))$
where $k^{gt}_j$ is the true label.
Quantile Selection: The $(D+1)(1-\alpha)$ -quantile of the NCSs from the calibration set is computed as $\hat{s}$ .
Prediction Sets: For a new test environment, prediction sets $C_j(m_t)$ $C_{j} (m_{t})$ are constructed for every cell. A label $k$ $k$ is included in the set if its probability in the map satisfies $p_t(m_j=k) \geq 1 - \hat{s}$ $p_{t} (m_{j} = k) \geq 1 - \overset{s}{^}$ .
- Theoretical Guarantee: These sets are guaranteed to contain the true ground-truth label for all cells with probability at least $1-\alpha$ , regardless of the underlying data distribution.

C. Safe Planning Algorithm

The planner operates in an online loop, switching between two modes:

Exploitation Mode: The planner selects the most conservative label for each cell within its prediction set (i.e., the label requiring the largest safety distance). It then uses a standard path planner (e.g., A*) to find a path to the goal that satisfies safety constraints based on these conservative labels.
Exploration Mode: If no feasible path exists in exploitation mode (due to high uncertainty making the environment appear too dangerous), the robot switches to exploration. It generates paths to reduce the size of the prediction sets (uncertainty) until a feasible exploitation path can be found.

3. Key Contributions

First Model-Agnostic Semantic Planner: The paper presents the first planner for semantic reach-avoid tasks that achieves user-specified success rates without assuming knowledge of sensor models or noise characteristics.
Conformal Prediction for Semantic Maps: It introduces the novel application of CP to quantify the uncertainty of semantic maps generated by existing AI mapping algorithms, providing rigorous statistical guarantees.
Theoretical and Empirical Guarantees: The authors prove that the generated paths satisfy the mission specification with probability $1-\alpha$ . Extensive experiments validate that the method consistently outperforms baselines in mission success rates.

4. Experimental Results

The authors evaluated the method in simulation (Gazebo) and on real hardware (Clearpath Jackal) across 61 test environments.

Performance Metrics:
- Mapping Success Rate: The percentage of cases where the prediction sets contained the true labels.
- Mission Success Rate: The percentage of cases where the robot successfully reached the goal without violating safety constraints.
Key Findings:
- Validation of Theory: For a target success rate of 95%, the empirical mapping success rate was ~93.4%, and mission success was ~98.4%, closely aligning with theoretical guarantees.
- Comparison with Baselines:
  - Uncertainty-Agnostic (UA): Treated map outputs as ground truth. Failed frequently due to misclassification (e.g., labeling a human as a tree, leading to insufficient safety distance).
  - Uncertainty-Informed (UI): Used heuristic thresholds on PMFs. Outperformed UA but underperformed the proposed method because it lacked rigorous calibration.
  - Proposed Method: Achieved the highest mission success rates (e.g., 98.36% at 95% target) by constructing conservative prediction sets that accounted for worst-case errors.
- Trade-offs: Higher required success rates ( $1-\alpha$ ) resulted in larger prediction sets, leading to more conservative paths and increased path lengths, but ensured safety.
- Out-of-Distribution (OOD): The method remained robust even when tested on environments with different lighting conditions and object distributions, though success rates dropped slightly (still above the target threshold).

5. Significance

This work bridges the gap between AI-based perception and formal safety guarantees in robotics. By leveraging Conformal Prediction, the authors provide a rigorous statistical framework that allows robots to reason about the uncertainty of "black-box" semantic maps. This is critical for deploying autonomous systems in safety-critical applications (e.g., autonomous driving, search and rescue) where relying on uncalibrated AI confidence scores is risky. The method enables robots to safely explore and navigate unknown environments while guaranteeing a specific level of mission reliability without needing to model complex sensor noise.