Adaptive Conformal Prediction for Motion Planning among Dynamic Agents

1. Introduction

• Safety-critical motion planning requires systems to assess uncertainty in other agents’ motion and react when that uncertainty increases.Source: §1 · p. 1

1.1. Related Work

• Existing approaches use reactive or predictive planning, but uncertainty is often handled through simplified dynamics or bounded, Gaussian, or heuristic assumptions.Source: §1 · pp. 1–2, §1.1 · p. 2

1. Introduction

• The paper adaptively quantifies trajectory-prediction uncertainty online from past observations of a single trajectory using adaptive conformal prediction.Source: §1 · p. 2
• The proposed MPC uses these uncertainty quantifications to plan probabilistically safe paths and respond to changes in prediction quality and agent motion.Source: §1 · p. 2
• The method is empirically evaluated in a drone scenario that avoids a flying frisbee.Source: §1 · p. 2

1.1. Related Work

• Prior conformal-prediction planners provide probabilistic safety but require offline trajectory data and cannot account for changes in the agents’ motion distribution.Source: §1.1 · p. 3

2. Problem Formulation and Preliminaries

• The environment contains N dynamic agents with unknown trajectories drawn from an otherwise unrestricted distribution D, and the planner predicts H future states from past observations.Source: §2 · p. 3
• The control objective is to choose inputs so a Lipschitz continuous constraint is satisfied with probability at least 1 − δ at each time.Source: §2 · p. 3
• The formulation allows the agent distribution D(x) to depend on the system trajectory, representing interactions such as an agent stopping when approached.Source: §2 · pp. 3–4
• The resulting online uncertainty sets are used within MPC, without assuming a distribution for prediction errors or exchangeability between validation and training data.Source: §2 · p. 4
• Trajectory predictors map observed agent states to multistep-ahead predictions and may be classical autoregressive models or neural networks.Source: §2 · p. 4
• Conformal prediction forms uncertainty regions from empirical nonconformity-score quantiles, while ACP adapts the quantile level online for time-series data.Source: §2 · pp. 4–5
• ACP uses past overcoverage or undercoverage to adjust prediction regions and thereby track changes in the uncertainty distribution.Source: §2 · p. 5

• The method constructs prediction regions from nonconformity scores, where larger scores indicate less accurate trajectory predictions.Separate regions Cτ are maintained for each prediction horizon τ.Source: §3 · p. 5
• Adaptive conformal prediction uses time-lagged nonconformity scores so multistep prediction errors can be updated online after future observations arrive.The lag aligns each evaluated error with the prediction horizon that produced it.Source: §3 · pp. 5–6
• The multistep regions are intended to quantify uncertainty without requiring exchangeability of time-series errors or separate validation data.The construction is compatible with a sliding window of recent observations and can be extended to candidate learning rates.Source: §3 · pp. 6–7
• For one-step-ahead prediction errors, p1 and p2 tend to 0 as the number T of recursion computations tends to infinity, starting from an initial recursion value in (0, 1).Source: §3 · p. 6

Example 1

• In a chaotic double-pendulum example, ACP produced 90% coverage regions for one- and six-step errors using online data from a single trajectory.The regions were compared with true multistep errors for two of the six pendulum states.Source: §3 · p. 7, Figure 1 · p. 7
• The one-step misprediction percentages for x1, x2, y1, and y2 were 2.36%, 0.94%, 1.57%, and 1.73%, respectively.The adaptive regions became larger where the linear predictor performed poorly and smaller where it performed well.Source: §3 · p. 7

• The proposed MPC uses adaptive uncertainty quantifications together with trajectory predictions to plan probabilistically safe paths around dynamic obstacles.It is the control layer built on the prediction regions from the preceding method.Source: §4 · p. 7
• The optimization enforces system dynamics and admissibility constraints on controls and states over the prediction horizon.The dynamics are xk+1 = f(xk, uk), with uk ∈ U and xk+1 ∈ X.Source: §4 · p. 8
• The MPC formulation is convex when J and f are convex, c is convex in its first argument, and U and X are convex.L is the Lipschitz constant of the constraint function, J is the step-wise cost, and the controls form the optimization sequence.Source: §4 · p. 8
• At each time step, the controller updates states and predictions, computes ACP regions, solves the finite-horizon optimization, and applies only the current control input.This implements a receding-horizon strategy in a real-time loop.Source: §4 · p. 8
• The implementation can use multiple candidate learning rates, while physical acceleration limits replace an unbounded prediction region with a finite bound Rmax.The latter enforces 0 ≤ δt+1 ≤ 1 and Ct+1 ≤ Rmax in practice.Source: §4 · p. 8
• If the optimization remains recursively feasible, the controller inherits a probabilistic constraint-satisfaction guarantee from the adaptive prediction result.The proof uses Lipschitz continuity to show that an appropriate prediction-error bound suffices for constraint satisfaction.Source: §4 · pp. 8–9

Experimental setup

• The MPC has a 10-step horizon, updates at 20 Hz, and is implemented using Sequential Convex Programming.The vehicle is constrained to θ and ϕ between −0.45 and 0.45 radians.Source: §5 · p. 9
• The experiments simulate a multirotor dodging a Frisbee thrown from varied initial positions, velocities, and rotation speeds using linear predictions of nonlinear Frisbee dynamics.The multirotor operates under small-angle state constraints and uses the specified linear dynamics.Source: §5 · p. 9

Evaluation

• The study uses 1000 Monte Carlo simulations per allowed failure probability level δ to evaluate feasibility, obstacle-avoidance success, and conservativeness.Conservativeness is measured by the minimum distance between obstacle and agent centers, summarized by d̄_min and σ(d_min).Source: §5 · pp. 9–10
• Three uncertainty methods are compared: ACP, empirical bootstrap prediction, and a sliding linear predictor with an EKF-based Gaussian uncertainty approximation.The comparison is summarized in Table 1.Source: §5 · p. 10, Table 1 · p. 10

Results

• The proposed ACP planner successfully avoids the Frisbee while achieving significantly smaller average divergence distances than the compared uncertainty-quantification methods.The reported distance measures are d_min and σ(d_min), averaged across simulations.Source: §5 · p. 10, Table 1 · p. 10

Limitations

• ACP feasibility is worse than the alternatives because overly large learning rates can cause sudden changes in uncertainty-set size.The authors identify recursive-feasibility tools and backup controllers as future remedies.Source: §5 · p. 10

Conclusion

• The paper combines trajectory prediction, adaptive conformal prediction, and uncertainty-informed MPC for safe navigation among dynamic agents.The control system is deterministic, while dynamic agents’ future motion is predicted from an online data stream.Source: §6 · p. 10
• The approach quantifies prediction uncertainty in a distribution-free, adaptive manner rather than using heuristic uncertainty estimates.The adaptive formulation is intended to capture changes in prediction quality and agents’ motion.Source: §6 · p. 10

Model and objective

• The baseline assumes smooth unknown state-transition and observation functions, with observables corrupted by independent identically distributed Gaussian noise.The predictor aims to estimate H future observations from the history available at time t.Source: §3 · p. 5, Appendix A · p. 15

Data representation

• Delay embeddings and trajectory matrices are constructed from sequential observations before forming a Page-matrix representation.The Page matrix uses the observable sequence without the repeated entries characteristic of Hankel matrices.Source: Appendix A · p. 15

Rank estimation

• The optHSVT procedure selects a singular-value threshold that separates the estimated signal from noise in the Page matrix.Its stated criterion is optimal mean-squared-error hard thresholding for noisy matrices with zero-mean independent identically distributed noise.Source: Appendix A · p. 15
• Because Page and Hankel constructions share the same rank, the method uses the Page matrix to recover system rank and avoid ill-conditioned matrix inversion.The recovered rank determines which singular eigenvector and eigenvalue pairs reconstruct the Hankel matrices.Source: Appendix A · pp. 15–16

Prediction

• A pseudoinverse of the reconstructed matrix produces a linear predictor, whose H-step forecast extracts the final H elements of a propagated column.The predictor maps past observations to future agent-state observations.Source: Appendix A · pp. 15–16

Online update

• The linear predictor is updated immediately as new measurements arrive, while an EKF incorporates those measurements over time.The instantaneous transition matrix is approximated by the Jacobian of the agent’s state-transition function.Source: Appendix A · p. 16