Conformal Prediction in The Loop: A Feedback-Based Uncertainty Model for Trajectory Optimization

AI summary

Overview

Research area: Trajectory optimization (TO) under uncertainty, conformal prediction (CP), chance-constrained control, and safe decision-making (arXiv category math.OC).

Technical level: Advanced. The paper relies on conformal prediction theory, exchangeability arguments, Boole's inequality for joint chance constraints, nonconvex trajectory optimization, and bilevel (lower-stage/upper-stage) optimization.

Scope: The paper proposes Fb-CP, a closed-loop framework in which information from realized trajectories is fed back into conformal prediction so that obstacle prediction regions are reshaped online while retaining their coverage guarantees, for shrinking-horizon trajectory optimization with a joint risk constraint over the entire mission time.

What This Paper Is About

Robots that must avoid moving obstacles need to predict where those obstacles will go, but predictions are never exactly right, so planners typically use conformal prediction to build regions that contain the true obstacle trajectory with probability at least 1 − α. In existing approaches this is a one-way pipeline: CP produces regions, and the planner consumes them. The paper's goal is to reverse part of that flow — the realized trajectory (which encodes how conservative the previous predictions turned out to be) is used to recompute the allowable risk for future time steps, tightening the prediction regions and improving the achieved trajectory without ever violating the coverage guarantee.

Key Contributions

1. Fb-CP framework. The authors propose what they describe as the first feedback-based conformal prediction framework closely coupled with downstream decision-making, enabling prediction regions to be adjusted using feedback information embedded in previously realized decisions, for shrinking-horizon TO with a joint risk constraint over the whole mission time.
2. Validity and performance guarantees. They prove that (i) the feedback-based adjustments in Fb-CP do not compromise the coverage guarantees of the prediction regions, and (ii) Fb-CP provides guarantees for decision-making performance improvement — i.e., Fb-CP enjoys both validity and superior performance.
3. Decision-focused iterative risk allocation (IRA). They develop a risk allocation algorithm with theoretical convergence analysis that aligns with Fb-CP and optimizes the allocation of allowable risk to enhance decision-making performance, in contrast to the simple Average-based Risk Allocation (ARA) baseline.
4. Distribution shift extension. They extend Fb-CP to handle distribution shift by applying a weighting scheme to the test and calibration data, and demonstrate its effectiveness.

Main Findings

• Posterior risk can be computed from realized trajectories. The paper introduces a nonconformity score based on the realized system state, yielding a posterior violation probability bound β_τ = (1 + Σ_{i=1}^{L} 𝕀(S_τ^{(K+i)} < 0)) / (1 + L), computed using only the second calibration subset D_cal².
• Exchangeability breaks for half the calibration data. Because the realized state x_τ* is obtained by solving the TO problem at time τ − 1, it depends on D_cal¹, so the scores S_τ, S_τ^{(1)}, …, S_τ^{(K)} are no longer exchangeable; only the L samples in D_cal² are used. This is the technical reason the calibration set is split into subsets of size K and L with K + L = N.
• Feedback keeps the coverage guarantee. The paper proves that the feedback-based adjustments do not compromise validity of the prediction regions, so safety remains provable rather than empirical.
• Provable online performance improvement. Reformulating the joint chance constraint so that past risk terms α_τ are replaced by posterior terms β_τ frees risk budget for future time steps; since β_τ is very likely to be smaller than α_τ, more risk is reserved for the future, producing more compact prediction regions and improved optimization performance.
• Risk allocation is monotone in cost. Lemma 5.1 establishes ∂J*(α_{t+1:T})/∂α_τ ≤ 0 for all τ = t+1, …, T, meaning that increasing the allocated risk at any time step strictly decreases the optimal cost of the trajectory optimizer.
• Convergence of IRA. The algorithm constructs a tightened allocation α̃ then a relaxed allocation α^{n+1}, giving J*(α_{t+1:T}^{n+1}) ≤ J*(α̃_{t+1:T}^{n}) = J*(α_{t+1:T}^{n}); recursively, J* monotonically decreases across iterations.
• Deterministic tightening bound. Lemma 5.2 provides a lower bound for the tightened risk at inactive time steps, ᾱ_τ^n = (1 + Σ_{i=1}^{K} 𝕀(c(x_τ^n, Ŷ_{τ|t}) < L R_{τ|t}^{(i)})) / (1 + K), and shows deterministically that ᾱ_τ^n ≤ α_τ^n.
• ARA as a baseline. A simple Average-based Risk Allocation, α_τ = (α − Σ_{τ=0}^{t} β_τ)/(T − t), is computationally efficient but fixes the proportions and reduces flexibility in reshaping future prediction regions.
• Empirical claims. The authors report the empirical observation that the method consistently tends to improve performance in practice, and that the approach handles distribution shift when a weighting scheme is applied. Numerical results: the paper states that effectiveness and superiority are demonstrated through benchmark experiments, but no specific benchmark names, numbers, dataset sizes, or model results are reported in the available content — the text is truncated during the description of Algorithm 1, before the experiments section. The paper also notes that distribution-shift handling for differing initial-state distributions and for state-dependent (rather than i.i.d.) noise ω_t is deferred to Appendix G.

Methodology in Plain English

1. Set up the safety requirement. The planner must satisfy a joint chance constraint: the probability of avoiding all obstacles over all T time steps is at least 1 − α, with α ∈ (0, 1). Using Boole's inequality, this is conservatively decomposed into one constraint per time step with per-step risks α_τ that must sum to at most α. A naive choice assigns α_τ = α/T once, at t = 0, and never changes it.
2. Turn prediction into a deterministic constraint. The calibration dataset D_cal of N obstacle trajectories is split into D_cal¹ (K trajectories) and D_cal² (L trajectories). Nonconformity scores are the prediction errors R_{τ|t} = ||Y_τ − Ŷ_{τ|t}||. A quantile of these scores gives the radius C of the (1 − α_τ)-coverage prediction region. Because the constraint function c is L-Lipschitz, satisfying c(x_τ, Ŷ_{τ|t}) ≥ L·C_{τ|t}^{1−α_τ} implies the per-step chance constraint holds — for a collision constraint this means the robot must stay a prediction-inflated radius away from the predicted obstacle location.
3. Compute the posterior risk. At time t the realized states x_τ* for all past τ are known. The authors score each calibration trajectory in D_cal² against the actual realized state and count how many would have collided, producing the posterior violation bound β_τ. This number can be much smaller than the pre-allocated α_τ, because α_τ was an a priori guess made before the robot's motion was known.
4. Feed the saving forward. The risk budget constraint for the remaining horizon becomes the sum of future α_τ ≤ α minus the sum of attained β_τ over past times. Past decisions therefore reshape the future prediction regions in an end-to-end way.
5. Allocate the budget smartly. Instead of splitting the remaining risk evenly (ARA), the authors extend Iterative Risk Allocation. Each iteration solves the trajectory problem with the current risk allocation (lower stage), classifies each time step's constraint as active or inactive, tightens the inactive ones using Lemma 5.2, then relaxes the active ones by distributing the leftover budget equally among them (upper stage). Monotonicity of the optimal cost guarantees this does not worsen the cost.
6. Close the shrinking horizon. Only the first computed control input u_t* is applied. As real time advances, the horizon shrinks, new obstacle observations arrive, predictions are regenerated with a Long Short-Term Memory (LSTM) predictor over a window of length h, and the whole loop repeats.

Why This Matters

Impact on research. The paper targets an explicit gap: CP theory work focuses on improving upstream predictions, while CP-in-decision-making work uses CP sequentially, so decision outcomes never inform the uncertainty model. Fb-CP is presented as a general uncertainty-quantification framework that is tightly coupled to downstream decisions, and the authors claim it is the first such framework in the literature. It also connects to prior lines on feedback covariate shift, adaptive conformal inference, and conformal decision theory, which the paper cites as related but distinct.

Real-world applications (drawn from domains the paper cites as motivating contexts):

• Autonomous driving, where other vehicles' intentions are unknown and collision-free planning must be probabilistic.
• Autonomous surface vessels navigating among moving traffic.
• Multi-robot systems, where each robot must avoid the others while planning safely.
• Coverage control and single-robot safe planning, where a robot must maintain safety relative to dynamic obstacles.

Industry relevance. Any autonomy stack that must make certified-safety claims — that a mission-level risk bound holds — benefits from a method that tightens uncertainty regions as data arrives without surrendering the statistical guarantee. The shrinking-horizon formulation matches how real systems actually operate: replanning online as new obstacle observations arrive.

Future Directions

• Empirical validation on physical or high-fidelity systems. The paper states benchmark experiments demonstrate effectiveness, but the available content reports no benchmark names or numerical results, so independent reproduction on new scenarios is an open step.
• Distribution shift beyond the stated assumptions. The main analysis assumes i.i.d. and exchangeable trajectories; the extension for shifted initial-state distributions and state-dependent noise ω_t is placed in Appendix G, leaving scope for a fuller treatment and evaluation.
• Computational cost and scaling. The authors note that treating the risk allocation α_{t+1:T} as decision variables jointly with states and controls is computationally demanding for larger T and K, which is precisely why the two-step allocation scheme is used. How the method scales in mission length and calibration size remains a practical question.
• Choice of the calibration split and step size. The framework introduces a split into K and L calibration trajectories and a step size η ∈ (0, 1); how best to choose these, and how sensitive performance is to them, is not reported in the content available.

Target Audience

Researchers and graduate students in control, optimization, and machine learning safety who are familiar with conformal prediction, chance-constrained optimization, or trajectory optimization; robotics engineers working on probabilistic collision avoidance; and readers interested in closing the loop between statistical uncertainty quantification and downstream decision-making. A reader without background in exchangeability and chance-constraint reformulation will find the theoretical core difficult.

Authors’ abstract

Conformal Prediction (CP) is a powerful statistical machine learning tool to construct uncertainty sets with coverage guarantees, which has fueled its extensive adoption in generating prediction regions for decision-making tasks, e.g., Trajectory Optimization (TO) in uncertain environments. However, existing methods predominantly employ a sequential scheme, where decisions rely unidirectionally on the prediction regions, and consequently the information from decision-making fails to be fed back to instruct CP. In this paper, we propose a novel Feedback-Based CP (Fb-CP) framework for shrinking-horizon TO with a joint risk constraint over the entire mission time. Specifically, a CP-based posterior risk calculation method is developed by fully leveraging the realized trajectories to adjust the posterior allowable risk, which is then allocated to future times to update prediction regions. In this way, the information in the realized trajectories is continuously fed back to the CP, enabling attractive feedback-based adjustments of the prediction regions and a provable online improvement in trajectory performance. Furthermore, we theoretically prove that such adjustments consistently maintain the coverage guarantees of the prediction regions, thereby ensuring provable safety. Additionally, we develop a decision-focused iterative risk allocation algorithm with theoretical convergence analysis for allocating the posterior allowable risk which closely aligns with Fb-CP. Furthermore, we extend the proposed method to handle distribution shift. The effectiveness and superiority of the proposed method are demonstrated through benchmark experiments.