⚡ electrical engineering

Conformal Constraint Tightening for Chance-Constrained Motion Planning with Unknown Dynamics

This paper proposes a planner-agnostic method that leverages conformal prediction to tighten planning constraints based on nominal-to-true trajectory deviations, thereby providing probabilistic task-completion guarantees for autonomous robots operating under unknown dynamics.

Original authors: Shubham Natraj, Bruno Sinopoli, Yiannis Kantaros

Published 2026-07-27

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Shubham Natraj, Bruno Sinopoli, 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 teaching a robot to navigate a maze. To do this, you give the robot a map and a set of rules. But here's the catch: the map you have is just a guess. It's a "nominal" model, a best-effort sketch of how the robot moves. In the real world, the robot might be heavier than you thought, or the floor might be slippery, or its wheels might slip. This gap between your sketchy map and the messy reality is called "model mismatch." If you trust your map too much, the robot might crash into a wall it thought was far away, or miss the finish line entirely. This is a huge problem in robotics because we can't always know the exact physics of a new machine or environment before we send it out. We need a way to plan a path that is safe even when our map is imperfect. This is where the concept of "chance-constrained planning" comes in: instead of demanding a path that is always perfect (which is often impossible), we aim for a path that works most of the time, say, 95% of the time, giving us a safety net against our own ignorance.

The paper you are about to read tackles this exact problem: how to make a robot's plan safe when the robot's true behavior is unknown, but we have a rough, approximate model to work with. The authors, Shubham Natraj, Bruno Sinopoli, and Yiannis Kantaros, propose a clever trick using a statistical tool called "Conformal Prediction." Think of Conformal Prediction as a "safety inspector" that looks at a bunch of past test runs to figure out just how much the real robot might deviate from the map. They don't try to fix the map; instead, they shrink the playground. They take the safe zones on the map and make them smaller, and the goal area smaller, by a specific amount. This amount is calculated so that if the robot stays within these shrunken zones on the map, it is mathematically guaranteed to stay safe in the real world with a high probability.

Here is the story of how they did it and what they found.

The Problem: The Map vs. The Territory

Robots need to move from a starting point to a goal while avoiding obstacles. Usually, engineers use a computer model to simulate the robot's movement. They run a planning algorithm (like a smart GPS) to find a sequence of moves that looks perfect on the computer. But when they run that same sequence on the real robot, things go wrong. Maybe the robot's motor is slightly weaker, or the wind pushes it differently. The "true" path the robot takes drifts away from the "nominal" path the computer planned. If this drift is too big, the robot hits an obstacle or misses the goal.

The authors argue that we can't always know the exact physics of the robot in advance. We might have a learned model (a guess based on data) or a simplified physics model, but it will never be 100% accurate. The challenge is to compute a control sequence (a list of moves) that works on the real robot, even though we only have the approximate model to plan with.

The Solution: The "Safety Bubble" Trick

The authors' solution is a two-step process that turns a risky, uncertain problem into a safe, deterministic one.

Step 1: The Calibration (The Test Drive)
First, they need to know how bad the mismatch can be. They take their approximate model and run it on a set of test problems. For each problem, they find a path that works on the computer. Then, they actually run that same path on the real robot and see what happens. They measure the distance between where the computer thought the robot would be and where it actually was. They do this for 100 different test scenarios.

Using a statistical method called Conformal Prediction, they look at these 100 measurements and ask: "What is the maximum distance the real robot drifted from the computer's prediction in 95% (or 99%, etc.) of these cases?" This gives them a "safety radius," let's call it $\hat{q}_\alpha$ . This number represents a "worst-case" bubble. They know that with high probability, the real robot will never be more than this distance away from the computer's predicted path.

Step 2: The Tightening (Shrinking the Room)
Now comes the magic. Instead of planning on the original map, they create a new, "tightened" map.

They take the obstacles on the map and make them bigger (inflating them) by the safety radius $\hat{q}_\alpha$ .
They take the free space and the goal area and make them smaller (eroding them) by the same amount.

Imagine you are walking through a hallway with a large, clumsy backpack. If you plan your path by hugging the walls, you might hit them with your backpack. So, you pretend the walls are further out and the hallway is narrower. You walk down the center of this "imaginary" narrow hallway. If you stay in the middle of the narrow hallway, your backpack will never hit the real walls.

The authors prove that if a robot can find a path through this shrunken, "tightened" version of the map using the approximate model, then that same path is guaranteed to be safe on the real robot with the prescribed probability. The robot doesn't need to know the true dynamics; it just needs to solve the harder, shrunken problem on the map.

The Experiments: Does it Work?

To test this, the authors ran two different scenarios.

Scenario 1: The Slow-Down Car (Dubins Vehicle)
They used a simple car model that turns but can't move sideways. The "true" car had a hidden flaw: it was slower than the model predicted because of friction (simulated by a parameter $\beta_v$ ). They tested mismatch levels of 0.05, 0.10, 0.15, and 0.20.

The Result: When they used their "tightened" method, the robot successfully reached the goal and avoided crashes at a rate that matched or exceeded their safety guarantee. For example, if they asked for a 90% success rate, the robot actually succeeded more than 90% of the time.
The Trade-off: As they asked for higher safety (e.g., 99% instead of 90%), the "safety bubble" got bigger, the hallway got narrower, and it became harder for the planner to find any path. The success rate of finding a path dropped, but the paths it did find were much more reliable.
Comparison: They compared this to a standard planner that ignored the mismatch. The standard planner found paths more often, but those paths failed on the real robot much more frequently. The authors' method was much more successful at actually completing the task safely.

Scenario 2: The Wobbly Drone (Planar Quadrotor)
They tested a more complex, 6-dimensional drone that has random noise (wind gusts) and uses a learned neural network model (which is often imperfect).

The Result: Even with the added chaos of random noise and a learned model, the method held up. The "empirical coverage" (how often the robot stayed within the safety bubble) was consistently higher than the target.
Performance: At a 90% target safety level, their method achieved a 100% task-completion rate on the real drone, whereas the standard "nominal" planner only managed about 55%. This shows that by being a bit more careful in the planning phase, you get a much better result in the real world.

What They Found and What It Means

The paper demonstrates that you don't need to know the exact physics of a robot to plan a safe path. You just need a rough model and some data to measure how wrong that model might be. By using Conformal Prediction to create a "safety bubble" and shrinking the planning space accordingly, you can turn a risky, uncertain problem into a safe, solvable one.

The authors show that this approach is "planner-agnostic," meaning it works with any planning algorithm (like the RRT algorithm they used). It doesn't matter how the planner finds the path; as long as the path stays within the shrunken zones, the guarantee holds.

However, there is a cost. The more safety you demand (the higher the probability you want), the more conservative the plan becomes. The "hallway" gets narrower, and sometimes the planner can't find a path at all. The authors found that while the planner's success rate (finding any path) drops as safety demands rise, the reliability of the paths it does find skyrockets. In their experiments, the method consistently outperformed standard planning that ignored model errors, proving that a little bit of mathematical caution goes a long way in keeping robots safe.

In short, the paper provides a robust, mathematically backed way to say, "I don't know exactly how this robot moves, but I know how far off my guess could be, so I'll plan as if the world is a bit more dangerous than it looks." And the experiments show that this strategy works, turning a potentially dangerous gamble into a reliable mission.

Technical Summary: Conformal Constraint Tightening for Chance-Constrained Motion Planning with Unknown Dynamics

1. Problem Formulation

The paper addresses the challenge of motion planning for autonomous robots where the true system dynamics are unknown, but an approximate deterministic nominal model is available. The objective is to compute a control sequence that drives the robot from an initial state to a goal region while avoiding unsafe states (obstacles) with a prescribed probability of success ( $1-\alpha$ ).

Crucially, the paper defines this as a chance-constrained planning problem over a distribution of planning problems ( $D_M$ ). Unlike traditional approaches that assume a known stochastic model or structural assumptions on uncertainty (e.g., Gaussian noise), this work assumes:

The true dynamics $f$ are unknown.
Only a nominal model $\hat{f}$ is accessible.
The nominal and true systems share the same state and control spaces.
Planning problems (obstacle configurations, initial states, goals) are drawn i.i.d. from an unknown distribution.

The core difficulty is that unmodeled effects, parameter uncertainty, or approximation errors in learned dynamics can cause trajectories that are safe under the nominal model to fail on the true system.

2. Methodology

The proposed framework is planner-agnostic, meaning it can be integrated with any existing motion planning algorithm (e.g., RRT, MPC, deep RL). The methodology consists of three main stages:

A. Conformal Prediction (CP) for Uncertainty Quantification

The authors leverage Conformal Prediction to quantify the discrepancy between nominal and true trajectories without assuming a specific distribution for the model error.

Calibration Dataset: A dataset is constructed by executing nominally feasible control sequences on the true system to collect corresponding true trajectories.
Nonconformity Score (NCS): For each planning problem in the calibration set, a score is computed representing the worst-case Euclidean deviation between the nominal trajectory and the true trajectory over the planning horizon:
$R(M) := \sup_{u} \max_{t} \|x_t - \hat{x}_t\|_2$
Note: In practice, this is approximated using a finite subset of feasible control sequences.
Threshold Calculation: Given a target failure probability $\alpha$ , CP computes a threshold $\hat{q}_\alpha$ as the $(1-\alpha)$ -th empirical quantile of the calibration scores. This threshold provides a probabilistic bound on the nominal-to-true deviation for unseen planning problems drawn from the same distribution.

B. Constraint Tightening

Using the conformal threshold $\hat{q}_\alpha$ , the authors define a tightened planning problem ( $M_\alpha$ ) under the nominal model:

Tightened Free Space ( $X^{\hat{q}_\alpha}_{free}$ ): The original free space is shrunk by "eroding" the boundaries. A state $x$ is included only if a ball of radius $\hat{q}_\alpha$ centered at $x$ is entirely contained within the original free space.
Tightened Goal Region ( $X^{\hat{q}_\alpha}_{goal}$ ): Similarly, the goal region is contracted such that a ball of radius $\hat{q}_\alpha$ centered at any point in the new goal region is contained within the original goal region.

Geometrically, this is equivalent to inflating obstacles and contracting the goal region by the radius $\hat{q}_\alpha$ .

C. Theoretical Guarantee

The paper proves that if a control sequence solves the tightened problem $M_\alpha$ using the nominal model, it satisfies the original chance-constrained problem on the true system with probability at least $1-\alpha$ . This is because the conformal bound ensures that the true trajectory remains within the $\hat{q}_\alpha$ -ball of the nominal trajectory; if the nominal trajectory stays within the eroded free space, the true trajectory is guaranteed to stay within the original free space.

3. Key Contributions

CP-Based Uncertainty Quantification: Development of a framework that uses only a nominal model and calibration data to provide a probabilistic bound on trajectory-level model mismatch over a distribution of planning problems, without requiring parametric uncertainty models.
Planner-Agnostic Constraint Tightening: A method to convert the chance-constrained problem into a deterministic planning problem with tightened constraints. The paper proves that solving this deterministic problem is a sufficient condition for satisfying the original probabilistic requirement.
Empirical Validation: Demonstration of the framework's effectiveness in both deterministic (parameter mismatch) and stochastic (learned model + process noise) settings, showing improved task completion rates compared to nominal-model planning.

4. Experimental Results

The framework was evaluated on two scenarios:

Dubins Vehicle: A deterministic system with incorrect translational parameters (simulating surface resistance).
Planar Quadrotor: A higher-dimensional, underactuated system with stochastic dynamics and a learned neural network model.

Key Findings:

Empirical Coverage: In all experiments, the empirical coverage (the fraction of true trajectories satisfying the safety/goal constraints) consistently exceeded the prescribed target level ( $1-\alpha$ ), validating the theoretical guarantees.
Trade-off: As the prescribed probability ( $1-\alpha$ ) increased, the conformal threshold $\hat{q}_\alpha$ increased, leading to more conservative constraint tightening. This resulted in a decrease in the planner success rate (the ability to find a solution within the tightened space) but a significant increase in task-completion rate (the ability to successfully execute the task on the true system).
Performance vs. Baseline: The proposed method consistently outperformed a baseline RRT planner that used the nominal model without constraint tightening. For the quadrotor, at a 90% target coverage, the proposed method achieved a 100% task-completion rate compared to ~55% for the nominal baseline.

5. Significance and Claims

The paper claims to address a critical limitation in existing motion planning literature: the reliance on accurate models or simulators for safety guarantees. By decoupling the planning algorithm from the uncertainty quantification, the proposed framework allows existing planners to operate safely on systems with unknown dynamics.

The authors emphasize that their approach provides a marginal probabilistic guarantee over a distribution of planning problems, rather than a per-task guarantee. This is particularly relevant for robotic applications where planners are repeatedly invoked in varying environments and mission specifications. The work demonstrates that it is possible to achieve high reliability in task completion for unknown systems by trading off some planner success rate (conservativeness) through conformal constraint tightening.

The paper acknowledges limitations, noting that the approach can be conservative, particularly when the disturbance set is large or the model mismatch is significant. Future work is suggested to focus on reducing this conservativeness and developing adaptive-risk strategies when no solution can be found for the tightened problem.