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

Motion planning algorithms compute control sequences that drive autonomous robots to goal regions while avoiding unsafe states. However, most existing methods—from sampling-based planners to deep reinforcement learning—provide task-completion guarantees only with respect to a nominal model or simulator. When the true system dynamics are unknown or difficult to model accurately, these guarantees may be invalidated. This paper proposes a planner-agnostic constraint-tightening procedure that leverages conformal prediction (CP) to quantify the discrepancy between nominal and true trajectories, using this bound as a tightening radius so that any control sequence solved on the tightened nominal model completes the task on the unknown true system with a user-specified probability.

1. Problem Motivation and Core Challenge

Consider a discrete-time robotic system with unknown true dynamics:

$$\mathbf{x}_{t+1} = f(\mathbf{x}_t, \mathbf{u}_t)$$

where $\mathbf{x}_t \in \mathcal{X} \subset \mathbb{R}^n$ is the state, $\mathbf{u}_t \in \mathcal{U}$ is the control input, and the true dynamics $f$ are unknown. We only have access to an approximate nominal model:

$$\hat{\mathbf{x}}_{t+1} = \hat{f}(\hat{\mathbf{x}}_t, \mathbf{u}_t)$$

The goal is to compute a control sequence $\mathbf{u}_{0:T-1}$ within a finite horizon $H$ that drives the true system trajectory to the goal region $\mathcal{X}_{\text{goal}}$ while always avoiding unsafe states $\mathcal{X}_{\text{obs}}$, with probability at least $1-\alpha$:

$$\mathbb{P}\left(\bigwedge_{t=0}^{T}(\mathbf{x}_t \in \mathcal{X}_{\text{free}}) \wedge (\mathbf{x}_T \in \mathcal{X}_{\text{goal}})\right) \geq 1 - \alpha$$

Here $\mathcal{X}_{\text{free}} := \mathcal{X} \setminus \mathcal{X}_{\text{obs}}$ is the safe state space. Crucially, this probabilistic guarantee is a marginal probability over planning problems drawn from a distribution $\mathcal{D}_\mathcal{M}$, not a per-task guarantee—highly relevant for robotic applications where a planner is repeatedly invoked across new environments and missions.

2. Conformal Prediction Background

Conformal prediction provides distribution-free, finite-sample valid uncertainty quantification for any fixed predictive model. Given a calibration dataset $\mathcal{S}_{\text{cal}} = \{(X_i, Y_i)\}_{i=1}^{N_{\text{cal}}}$ and a nonconformity score (NCS) function $s: \mathbb{X} \times \mathbb{Y} \to \mathbb{R}$, for a target failure probability $\alpha \in (0,1)$, CP computes a threshold $\hat{q}_\alpha$ satisfying:

$$\mathbb{P}(R_{\text{test}} \leq \hat{q}_\alpha) \geq 1 - \alpha$$

where $\hat{q}_\alpha$ is the $(1-\alpha)$-th empirical quantile of $\{R_1, \dots, R_{N_{\text{cal}}}, \infty\}$. CP makes no assumptions about the underlying model or data distribution, relying solely on the user-defined NCS to measure prediction error.

3. Quantifying Trajectory-level Model Mismatch with CP

This work applies CP at the planning-problem level—unlike prior work applying CP at the state-control pair level. The nonconformity score is defined as the worst-case nominal-to-true trajectory deviation over all nominally feasible control sequences:

$$R(\mathcal{M}) := \sup_{\mathbf{u}_{0:T-1} \in \mathcal{U}(\mathcal{M})} \max_{t \in \{0,\dots,T\}} \|\mathbf{x}_t - \hat{\mathbf{x}}_t\|_2$$

where $\mathcal{U}(\mathcal{M})$ is the set of all control sequences feasible on the nominal model. By computing this score over calibration planning problems and applying CP, we obtain the key nominal-to-true model error bound:

$$\mathbb{P}\left(\sup_{\mathbf{u}_{0:T-1} \in \mathcal{U}(\mathcal{M})} \max_{t \in \{0,\dots,T\}} \|\mathbf{x}_t - \hat{\mathbf{x}}_t\|_2 \leq \hat{q}_\alpha\right) \geq 1 - \alpha$$

Geometrically, this means that with probability at least $1-\alpha$, for every nominally feasible control sequence, the true states lie inside radius-$\hat{q}_\alpha$ balls centered at the nominal states.

Figure 1 illustrates the proposed CP-based planning framework: the conformal threshold $\hat{q}_\alpha$ induces a planning problem with tightened constraints such that any control sequence solving it inherits the reach-avoid guarantee of Proposition III.4.

4. Probabilistically Safe Planning and Core Theorems

Based on the deviation bound, define the tightened free space and goal region:

$$\mathcal{X}_{\text{free}}^{\hat{q}_\alpha} := \{\mathbf{x} \in \mathcal{X} : \mathcal{B}(\mathbf{x}, \hat{q}_\alpha) \subseteq \mathcal{X}_{\text{free}}\}$$ $$\mathcal{X}_{\text{goal}}^{\hat{q}_\alpha} := \{\mathbf{x} \in \mathcal{X} : \mathcal{B}(\mathbf{x}, \hat{q}_\alpha) \subseteq \mathcal{X}_{\text{goal}}\}$$

Intuitively, this shrinks the free space and goal set by $\hat{q}_\alpha$—in planar navigation, this is equivalent to inflating obstacles, eroding the workspace boundary, and contracting the goal region.

Proposition III.1 (Planning Guarantee): If the sequence of radius-$\hat{q}_\alpha$ balls centered at nominal states is contained in the free space, and the terminal ball is contained in the goal region:

$$\mathcal{B}(\hat{\mathbf{x}}_t, \hat{q}_\alpha) \subseteq \mathcal{X}_{\text{free}}, \quad \forall t \in \{0,\dots,T\}$$ $$\mathcal{B}(\hat{\mathbf{x}}_T, \hat{q}_\alpha) \subseteq \mathcal{X}_{\text{goal}}$$

then the control sequence solves the original problem with probability at least $1-\alpha$. The proof uses equation (6): with probability at least $1-\alpha$, $\|\mathbf{x}_t - \hat{\mathbf{x}}_t\|_2 \leq \hat{q}_\alpha$ for all $t$, so the true trajectory is contained within the ball sequence, remaining in free space and eventually reaching the goal.

Proposition III.4 (Planner Guarantee): Every control sequence that solves the tightened problem $\mathcal{M}_\alpha$ for the nominal model also solves the original problem $\mathcal{M}$ for the true system with probability at least $1-\alpha$. This is the paper's most central result—chance-constrained planning under unknown dynamics is reduced to deterministic planning under the nominal model, solvable by any planner capable of enforcing the tightened constraints.

graph TD
    A[Calibration Dataset
N_cal=100 planning problems] --> B[Execute on True System
Collect true trajectories]
    B --> C[Compute NCS
R_i = sup ||x_t - x_hat_t||]
    C --> D[Conformal Prediction
Compute threshold q_hat_alpha]
    D --> E[Tighten Free Space
X_free^q = erode]
    D --> F[Shrink Goal Region
X_goal^q = erode]
    E --> G[Solve on Nominal Model
Tightened problem M_alpha]
    F --> G
    G --> H[Control sequence completes task
on true system with prob 1-alpha]
    style D fill:#f9f,stroke:#333,stroke-width:2px
    style H fill:#bfb,stroke:#333,stroke-width:2px

The first page of the paper presents the overall CP framework approach: quantifying model mismatch via calibration data and tightening constraints to guarantee probabilistic safety on the true system.

5. Experimental Validation

The authors validate the framework on two scenarios representing common forms of model mismatch:

5.1 Experimental Setup

Scenario 1: Dubins Vehicle (Deterministic, Parameter Mismatch). The nominal model uses standard Dubins dynamics, while the true system experiences translational slowdown:

$$\hat{\mathbf{x}}_{t+1} = \hat{\mathbf{x}}_t + \Delta t [\cos(\hat{\theta}_t), \sin(\hat{\theta}_t), u_t]^\top$$ $$\mathbf{x}_{t+1} = \mathbf{x}_t + \Delta t [(1-\beta_v)\cos(\theta_t), (1-\beta_v)\sin(\theta_t), u_t]^\top$$

The parameter $\beta_v \in \{0.05, 0.10, 0.15, 0.20\}$ controls the model mismatch magnitude, yielding four distinct true system models. This simulates surface or drivetrain resistance unaccounted for in the nominal model.

Scenario 2: Planar Quadrotor (Stochastic, Learned Model + Noise). 6D state $\mathbf{x}_t = [x_t, y_t, \theta_t, v_{x,t}, v_{y,t}, \omega_t]^\top \in \mathbb{R}^6$, 2D control $\mathbf{u}_t = [\delta T_t, \tau_t]^\top \in \mathbb{R}^2$. The true dynamics include process disturbances:

$$v_{x,t+1} = v_{x,t} + \Delta t \left[-\frac{1}{m}(mg + \delta T_t)\sin\theta_t + w_{x,t}\right]$$ $$v_{y,t+1} = v_{y,t} + \Delta t \left[\frac{1}{m}(mg + \delta T_t)\cos\theta_t - g + w_{y,t}\right]$$ $$\omega_{t+1} = \omega_t + \Delta t \left[\frac{\tau_t}{I} + w_{\omega,t}\right]$$

where $m=1, g=9.8, I=0.25$, each disturbance component sampled independently from $\mathcal{N}(0,1)$ and clipped to $[-3,3]$. The nominal model is a trained neural network one-step predictor, with mismatch arising jointly from learned model approximation errors and stochastic execution noise.

In both scenarios, planning problems are sampled from $\mathcal{D}_\mathcal{M}$: $25 \times 25$ environments with five randomly placed circular obstacles (radii sampled from $[1,3]$), initial state sampled uniformly from free space, goal region a circle of radius 5 at least 15 units from the initial position.

5.2 Evaluation Metrics

Metric	Definition	Expected
Empirical Coverage	Fraction of plans whose true trajectories stay within $\hat{q}_\alpha$ of nominal	≥ 1-α
Planner Success Rate	Fraction of problems where the planner returns a solution on the tightened problem	Decreases with 1-α
Task Completion Rate	Fraction of returned plans whose true trajectories reach goal collision-free	≥ 1-α

5.3 Dubins Vehicle Results

Figure 2 (left column) shows Dubins vehicle results. In all cases, empirical coverage exceeds the target level (consistent with equation (6)). As model mismatch increases (larger $\beta_v$), the gap between empirical and prescribed coverage also increases—larger mismatch produces larger calibration scores, hence a larger $\hat{q}_\alpha$, making conformal balls more conservative.

$\beta_v$	Nominal Model Mismatch	Effect on $\hat{q}_\alpha$
0.05	Small	Mild tightening
0.10	Medium	Moderate tightening
0.15	Large	More conservative
0.20	Very Large	Most conservative

The task-completion rate consistently exceeds $1-\alpha$, and the proposed framework consistently outperforms the nominal planning baseline, with the performance gap increasing as both model mismatch and $1-\alpha$ increase.

5.4 Planar Quadrotor Results

Figure 2 (right column) shows stochastic quadrotor results. Despite the combination of learned-model error and stochastic execution noise, empirical coverage consistently exceeds the target level, validating the CP guarantee. The task-completion rate rises from about 80% at $1-\alpha=30\%$ to 100% at $1-\alpha=90\%$, while the nominal RRT baseline achieves only about 55%.

Coverage Level $1-\alpha$	Our Method Task Completion	Nominal Baseline
30%	~80%	~55%
90%	~100%	~55%

6. Core Innovations and Comparison

Key distinctions from existing work:

Dimension	This Paper	CC-RRT [15]	SLS-MPC [31]
Dynamics Assumption	Nominal only, true unknown	Known stochastic linear	Known model class
CP Application Level	Planning-problem level	N/A	State-control pair level
Guarantee Type	Marginal across planning problem distribution	Per-task per-step	Per-task closed-loop
Planner Dependency	Planner-agnostic	Specific to RRT	Specific to SLS-MPC

7. Limitations and Extensions

Limitation 1: Conservativeness. When the disturbance set $\mathcal{W}$ is large or model mismatch is severe, the conformal threshold $\hat{q}_\alpha$ may become excessively large, causing the tightened free space to be too small and the planner success rate to drop significantly. The stochastic dynamics extension (Remark III.3) is especially conservative.

Limitation 2: Practical NCS Approximation. Exactly computing the nonconformity score requires optimizing over all nominally feasible control sequences, which is generally intractable. The practical approximation uses a finite subset, which may underestimate deviation and weaken the tightness of the guarantee.

Extension Directions: The authors note future work will focus on reducing conservativeness and developing adaptive-risk planning strategies when no plan can be computed at the desired probability. Additionally, the CP analysis extends to stochastic true systems $\mathbf{x}_{t+1} = f(\mathbf{x}_t, \mathbf{u}_t, \mathbf{w}_t)$ using a worst-case score.

8. Conclusion

This paper addresses motion planning for systems with unknown dynamics using an approximate nominal model. Using CP, the authors derive a probabilistic bound on nominal-to-true trajectory deviation, and use this bound to construct tightened planning problems such that any control sequence solving them under the nominal model also solves the original problem on the true system with the prescribed probability. Key contributions include: (1) a CP-based uncertainty quantification framework for unknown true dynamics using only a nominal model and calibration data; (2) construction and sufficiency proof of the tightened planning problem; (3) empirical validation on Dubins vehicle and planar quadrotor demonstrating substantially improved task-completion rates over nominal planning.