Source-linked AI summary
Safe Planning in Dynamic Environments using Conformal Prediction
Lars Lindemann, Matthew Cleaveland, Gihyun Shim, George J. Pappas
TL;DR
Planning around agents with unknown trajectories requires uncertainty-aware control with formal safety guarantees. The paper combines flexible trajectory predictors with conformal prediction regions inside an MPC, demonstrating probabilistic safety in robot and autonomous-driving experiments while identifying conservatism and horizon-related trade-offs.
Problem
Safety-critical systems must plan around agents whose intentions and trajectories are unknown, while existing approaches lack valid safety guarantees without strong distributional assumptions.
Method
The framework uses any trajectory predictor, conformal prediction to construct valid uncertainty regions, and an MPC that incorporates both into planning.
Results
Numerical experiments cover a mobile robot and a self-driving vehicle, with one safety-constraint violation in 100 MPC runs and 99.985% one-step prediction-region coverage.
Takeaways & Limitations
The approach provides probabilistic safety guarantees for dynamic-environment planning while supporting predictors such as RNNs and LSTMs without assumptions on the underlying trajectory distribution.
Takeaways & Limitations
Smaller failure probabilities and longer prediction horizons can make paths less optimal, while overly short horizons may cause recursive-feasibility issues.
Abstract
from arXiv · showhide
We propose a framework for planning in unknown dynamic environments with probabilistic safety guarantees using conformal prediction. Particularly, we design a model predictive controller (MPC) that uses i) trajectory predictions of the dynamic environment, and ii) prediction regions quantifying the uncertainty of the predictions. To obtain prediction regions, we use conformal prediction, a statistical tool for uncertainty quantification, that requires availability of offline trajectory data - a reasonable assumption in many applications such as autonomous driving. The prediction regions are valid, i.e., they hold with a user-defined probability, so that the MPC is provably safe. We illustrate the results in the self-driving car simulator CARLA at a pedestrian-filled intersection. The strength of our approach is compatibility with state of the art trajectory predictors, e.g., RNNs and LSTMs, while making no assumptions on the underlying trajectory-generating distribution. To the best of our knowledge, these are the first results that provide valid safety guarantees in such a setting.
1 Introduction
The paper addresses safety-critical planning around agents with unknown trajectories by combining trajectory prediction, conformal prediction regions, and model predictive control. It targets valid probabilistic safety guarantees while remaining compatible with modern predictors and making no assumptions about the trajectory distribution.
- Motivation: Unknown agent intentions and trajectories make planning for autonomous systems in shared environments safety-critical and challenging.The motivating settings include self-driving cars in urban traffic and service robots avoiding pedestrians.
- Related Work: Prior dynamic-environment planners often omit predicted trajectories, although predictions can improve path safety and performance.The related work includes dynamic window approaches, navigation functions, and prediction-integrating methods.
- Related Work: Existing interactive prediction-and-planning approaches model action-agent coupling but generally lack quantifiable safety guarantees.The paper therefore focuses on non-interactive planning with valid safety guarantees.
- Approach: The proposed algorithm combines trajectory predictions with tight, easily obtained conformal prediction regions in a computationally tractable planning formulation.Under reasonable assumptions, the resulting optimization problem is convex.
- Guarantees: Safety is guaranteed with a user-defined probability, with larger probabilities producing more conservative plans.The framework supports state-of-the-art RNN and LSTM predictors without assumptions on the underlying trajectory-generating distribution.
- Evaluation: Numerical experiments evaluate a mobile robot and a self-driving car using TrajNet++, ORCA, and CARLA.The self-driving scenario places the vehicle at a pedestrian-filled intersection.
2 Problem Formulation
The paper formulates safe planning as control under unknown dynamic-agent trajectories and a probabilistic constraint, then constructs prediction models and conformal regions from trajectory data for MPC.
- 2 Problem Formulation: The section introduces safe planning in dynamic environments and trajectory prediction as the two core components of the problem formulation.The formulation proceeds from the planning problem to methods for predicting dynamic agents.
- 2.1 Safe Planning in Dynamic Environments: Agent trajectories are modeled by an unknown distribution D, with observations of past agent states available and no assumed distributional form.The distribution is assumed independent of the system dynamics and controls.
- 2.1 Safe Planning in Dynamic Environments: The framework assumes training and calibration trajectories drawn independently from D, an availability condition motivated by pedestrian data in autonomous driving.The paper notes that distribution shifts are reserved for future treatment.
- 2.1 Safe Planning in Dynamic Environments: The planning objective is to choose controls so a Lipschitz constraint c involving the system and N agents is satisfied with probability at least 1 − δ.The constraint can encode collision avoidance or tracking another agent, and the formulation also includes cost optimality.
- 2.2 Trajectory Predictors for Dynamic Environments: A measurable predictor maps observed agent states through time t to predictions of future states from t+1 through T.The dataset is split into training and calibration subsets, and the predictor is learned from the training data.
- 2.2 Trajectory Predictors for Dynamic Environments: Recurrent neural networks provide one predictor class, using sequential inputs and hidden states to estimate the next agent state.LSTMs are identified as an example of the parameterized recurrent architecture.
- 2.2 Trajectory Predictors for Dynamic Environments: The recurrent predictor generates later future-state estimates recursively by feeding its own predictions in place of unknown future observations.The state-dimension assumption is explicitly described as generalizable, and the constraint is initially assumed satisfied.
3 Conformal Prediction Regions for Trajectory Predictors
Conformal prediction constructs uncertainty regions around trajectory predictions without assuming a specific trajectory distribution or predictive model. These regions support validity guarantees across multiple future steps and individual agents, including recursively generated predictions.
- Motivation: Conformal prediction addresses complex trajectory distributions and potentially inaccurate, nonlinear predictors without requiring standard distributional assumptions.The method is designed for predictive models such as neural networks.
- Score construction: Nonconformity scores measure prediction error, with larger scores indicating poorer predictive accuracy.For trajectory prediction, the score is based on the norm between the actual and predicted future state.
- Calibration: The prediction-region threshold C is the pth smallest calibration nonconformity score, where p = ⌈(k + 1)(1 − δ)⌉.The quantile construction uses calibration scores together with an added infinite score.
- Multi-step validity: For multiple future times, Boole’s inequality combines per-time guarantees by setting the per-time failure probability to δ̄ = δ/T.The resulting threshold increases with longer horizons or smaller overall failure probabilities.
- Guarantees: Theorem 1 guarantees simultaneous validity of all τ-step-ahead regions at time zero and all one-step-ahead regions over the horizon with probability at least 1 − δ.The one-step guarantee is important for correctness guarantees of the proposed MPC.
- Applicability: The framework permits any measurable predictor, including recursive RNNs, and can construct prediction regions individually for each agent.The individual-agent construction uses the corresponding agent state and prediction in the nonconformity score.
4 Model Predictive Control with Conformal Prediction Regions
The paper embeds conformal prediction regions into an MPC optimization problem to plan safely around predicted dynamic agents. Receding-horizon feedback reduces the conservatism of open-loop planning, while safety guarantees hold under feasibility and the stated distributional assumptions.
- MPC formulation: The MPC optimizes a control sequence subject to system dynamics, admissible states and inputs, and uncertainty-aware collision-avoidance constraints.The constraint requires c(x_τ, Ŷ_τ|t) ≥ L C_τ|t across the prediction horizon.
- Open-loop guarantee: If the optimization is feasible initially with H = T, the resulting open-loop sequence solves the safe planning problem.The guarantee follows from the optimization constraint, Lipschitz continuity, and the conformal prediction result.
- Receding-horizon control: The open-loop controller can be conservative or infeasible because prediction regions grow as long-horizon predictions lose accuracy.The paper therefore proposes receding-horizon control to reduce conservatism and add feedback robustness.
- Algorithm: Algorithm 1 computes conformal regions offline, then repeatedly senses the system, updates predictions, resolves the MPC, and applies only the current control.Calibration predictions and nonconformity scores determine the regions before the real-time planning loop.
- Closed-loop guarantee: Under Theorem 1, Assumption 1, and feasibility at every time, the closed-loop controller satisfies the paper’s safety guarantee.The proof uses the MPC constraint, Lipschitz continuity, and the conformal coverage relation.
- Parameter choices: Smaller failure probabilities enlarge prediction regions and can worsen cost, while too-small prediction horizons may create recursive-feasibility issues.The paper assumes recursive feasibility and notes it is reasonable when future agent displacement changes little.
5 Case Studies
The case studies evaluate conformal-prediction-based MPC for pedestrian avoidance in simulated mobile-robot and autonomous-driving settings. Prediction regions empirically satisfy their guarantees, while closed-loop updating reduces conservatism relative to open-loop planning.
- Case-study setup: Two case studies test pedestrian avoidance for a mobile robot using ORCA trajectories and a self-driving car in CARLA.The CARLA scene contains an intersection populated by four pedestrians; the ORCA scene contains three.
- Scenario 1 (ORCA): 4500 ORCA trajectories were split into 2000 training, 2000 calibration, and 500 test trajectories.The sampling time was Δ := 1/8, with prediction regions evaluated for τ ∈ {15, 18} at t := 10.
- Scenario 1 (ORCA): 498 of 500 ORCA test trajectories satisfied the prediction-region condition, empirically confirming the stated 95% coverage target.The regions were calculated with δ := 0.05 and T := 20.
- Scenario 2 (CARLA): CARLA used 2600 trajectories split into 1000 training, 1500 calibration, and 100 test trajectories, with an LSTM predicting pedestrian motion.The MPC used H := 10, corresponding to five seconds, while prediction regions used T := 30 because calibration data were limited.
- Scenario 2 (CARLA): In CARLA, one of 100 MPC runs violated the safety constraint, within the at-most-5 violations guaranteed by Theorem 3.One-step-ahead prediction regions held in 99.985% of cases, exceeding the theoretically ensured 99.83%.
6 Conclusion
The paper presents an MPC that combines trajectory predictors with conformal prediction regions for probabilistically safe planning. Numerical experiments demonstrate safe navigation around other agents, while future work targets predictor comparisons, arbitrary agent counts, and potential conservatism.
- Conclusion: The proposed MPC uses conformal prediction to incorporate valid uncertainty regions around complex trajectory predictions.The framework supports predictors such as LSTMs without assumptions on the predictor or environment.
- Conclusion: Two numerical experiments demonstrate mobile-robot and self-driving-vehicle navigation around other agents with valid safety guarantees.The paper characterizes these as the first such results without assumptions on the predictor or environment.
- Future work: Future work will compare trajectory predictors, analyze their MPC interplay, handle arbitrary agent counts, and investigate conservatism from union bounding.Adaptive methods are proposed for studying potential conservatism in the prediction regions.