PaperlayerView exact revision on arXiv

Source-linked AI summary

Interpretable Collision Avoidance and Feasibility Guarantees through an Uncertainty Aware Pipeline

Doris Xu, Jin Hyun Park, Guadalupe Alvarado Fernandez, Adhyan Prasad, Mark Campbell

arXiv:2610.33186v1cs.RO

TL;DR

Autonomous-vehicle planners must address uncertain collision avoidance and real-time feasibility, but existing approaches struggle to guarantee both. This paper propagates uncertainty through a modular pipeline and constructs convex safe sets for planning. In 100 Monte Carlo trials, it reports 0% collisions and 0% solver infeasibility at 12.7 ms per cycle, alongside lower collision rates than the cited baselines.

  • Problem

    Intersection planning must guarantee collision avoidance under uncertainty while remaining computationally feasible in real time.

    Source: §I · p. 1

  • Method

    The modular pipeline propagates intent, forecast, and localization uncertainty as structured quantities, computes collision probabilities upstream, and plans within convex safe sets.

    Source: §I · pp. 1–2

  • Results

    Across 100 Monte Carlo trials, the pipeline achieved 0% collisions and 0% solver infeasibility at 12.7 ms per cycle, versus 36% collisions for deterministic MPC and 10% collisions with 14.2% infeasibility for CC-MPC.

    Source: §V · p. 8

  • Takeaways & Limitations

    The ablation study identifies intent estimation, forecasting, and localization covariance as necessary for collision avoidance, and Jackal UGV deployment validates both guarantees on physical platforms.

    Source: §I · p. 2

Abstract

from arXiv · show

Autonomous vehicles (AVs) operating in dynamic, challenging conditions such as intersections and roundabouts must guarantee collision avoidance under uncertainty while maintaining real-time feasibility. Most existing planners struggle to simultaneously guarantee both requirements. Chance-constrained formulations embed safety constraints directly in the optimization but become infeasible as uncertainty compounds; deterministic planners provide feasible solutions but fail to address the uncertainty that causes collisions; end-to-end learned policies provide neither guarantee in an interpretable form. We present a modular perception-prediction-planning pipeline that closes this gap by propagating uncertainty as structured, interpretable quantities across module boundaries. Rather than embedding probabilistic risk directly in the optimization, our pipeline resolves collision probabilities upstream and constructs convex safe sets within which the planner provides a guaranteed feasible solution at every cycle -- decoupling the safety guarantee from solver feasibility. Across Monte Carlo trials in a four-way unsignalized intersection, our pipeline achieves 0% collisions and 0% solver infeasibility at 12.7ms per cycle, compared to 36% and 10% collision rates for deterministic and chance-constrained baselines respectively. The ablation study confirms the necessity of each uncertainty source and the hardware deployment on Clearpath Jackal UGVs validates the pipeline's real-time viability on physical platforms.

I. INTRODUCTION

Intersection planners must handle uncertain measurements, ambiguous intent, branching trajectories, and compressed planning time while guaranteeing collision avoidance and real-time feasibility. The paper addresses a gap in propagating these uncertainties across modules without sacrificing either guarantee.

I. INTRODUCTION

  • Intersections pose challenges from noisy sensing, ambiguous intentions, maneuver-dependent trajectories, and compressed planning windows.Intersections account for approximately one quarter of annual U.S. traffic fatalities.Source: §I · p. 1
  • Deterministic MPC is efficient but assumes known trajectories, while chance-constrained MPC – can become infeasible as uncertainty compounds over multi-step horizons.End-to-end learned methods, lack explicit, interpretable safety margins and formal feasibility guarantees.Source: §I · p. 1
  • The proposed pipeline propagates intent, forecasting, and localization uncertainty as structured quantities, resolves collision probabilities upstream, and plans inside convex safe sets.An IMM estimates intent and state distributions; a CBF safety filter enforces forward invariance of the safe set [12].Source: §I · pp. 1–2

II. RELATED WORKS

  • Robust set-based methods avoid over-approximated reachable sets, but collapsing maneuver intents regardless of likelihood can cause freezing or numerical infeasibility.Source: §II · p. 2
  • Sampling-based methods trade stronger full-horizon collision-probability bounds for more computation, while POMDP planners, face exponentially growing belief trees.POMDP approximations can shorten horizons or coarsen actions, limiting real-time applicability and safety-guarantee quality.Source: §II · p. 2
  • Existing planners lack a principled way to propagate multi-modal uncertainty across modules while guaranteeing both collision avoidance and planner feasibility.The paper identifies intent probabilities, forecasted trajectories, and localization errors as uncertainties that must remain structured and interpretable.Source: §II · p. 2

III. METHODS

The pipeline estimates other road users’ intent and state distributions, then carries these structured estimates downstream for forecasting and collision analysis. Its IMM uses parallel mode-specific filters and updates both mode probabilities and state estimates.

1) Agent Intent & Tracking:

  • The IMM maintains a discrete distribution over maneuver modes and a continuous distribution over the tracked vehicle’s state.Each mode corresponds to a possible intent.Source: 1) Agent Intent & Tracking · p. 2
  • At each timestep, the IMM runs a filter for each road-geometry-derived feasible maneuver and recursively updates the state estimate and mode probability.The example four-way intersection modes are keep straight, turn left, and turn right.Source: 1) Agent Intent & Tracking · p. 2

III. METHODS

  • The pipeline connects IMM intent and state estimates to forecasting, collision-probability computation, safe-set construction, flat MPC, and a CBF safety filter.Source: Figure 2 · p. 3

1) Agent Intent & Tracking:

  • The IMM combines mode probabilities with mode-conditioned state estimates to provide state covariance and intent probabilities to downstream modules.Source: 1) Agent Intent & Tracking · p. 3

2) Agent Trajectory Forecasting:

For each intent, the forecaster propagates the IMM state estimate and covariance over a horizon using a Sigma Point Filter. It produces timestamped Gaussian state distributions for analytical collision-probability evaluation.

2) Agent Trajectory Forecasting:

3) Ego Localization:

Ego localization uncertainty is combined with agent and forecast uncertainty to estimate collision probabilities for each intent. The collision detector uses vehicle geometry and closest approach to pass those probabilities to decision making, which constructs a safe set and goal pose.

3) Ego Localization:

  • Noisier ego localization raises estimated collision probabilities across all intent modes, leading to more cautious driving behavior.The ego vehicle’s position covariance is combined with agent uncertainty at each forecast timestep.Source: 3) Ego Localization · p. 3

B. Integrated Pipeline

  • The collision detector converts agent intents, forecast trajectories, localization errors, and vehicle geometry into a scalar collision probability for each intent.The resulting per-intent probabilities go to decision making to construct the safe set and determine the planner’s goal pose.Source: 1) Collision Detection · pp. 3–4, B. Integrated Pipeline · p. 3

1) Collision Detection:

  • The detector finds closest approach using OBB geometry, whose heading-dependent projected extents can shift it from minimum center-to-center distance.Bounding-circle radii enclosing each OBB at any orientation make the resulting collision probability an upper bound on true risk.Source: 1) Collision Detection · p. 4

2) Decision Making:

Decision making selects the most likely intent and uses its collision probability to construct a convex safe set and intermediate goal pose. The safe set supports recursive MPC feasibility while retaining probabilistic safety bounds.

2) Decision Making:

  • The decision module selects the most likely intent rather than combining intent risks as a weighted sum, which can underestimate risk.When intent probabilities are close, the IMM covariance grows, increasing collision probability and producing a more conservative safe set.Source: 2) Decision Making · p. 4
  • The safe set is an AABB aligned with lane geometry, constructed from the unsafe region swept along the most likely forecast.The module also selects an intermediate goal pose within the safe set; in the yield case, the set is bounded by ysafe.Source: 2) Decision Making · p. 4
  • Because the safe set is convex and probabilistically safe, paths within it preserve the safety bounds and ensure recursive MPC feasibility.Its AABB form also gives the safety filter linear inequality constraints and preserves QP tractability and forward invariance.Source: 2) Decision Making · p. 5

3) Planner and Safety Filter:

The planner generates a trajectory toward an intermediate goal, while a CBF safety filter keeps the ego within the safe set. Linear dynamics and a quadratic cost make the planner’s optimization small, and the pipeline is presented as computationally tractable.

3) Planner and Safety Filter:

  • The planner uses a double-integrator model in flat-output space, with linear dynamics and a quadratic cost yielding an optimization solved in approximately 5 ms.The state is ζ = [x, y, vx, vy]ᵀ, with acceleration inputs.Source: 3) Planner and Safety Filter · p. 5
  • The CBF safety filter enforces the safe-set boundaries through a QP that minimally modifies the planner’s reference acceleration.For the double integrator, each CBF condition is linear in acceleration input; safe flat-space controls are mapped back to unicycle controls.Source: 3) Planner and Safety Filter · p. 5
  • The pipeline propagates structured uncertainty and uses convex safe sets to provide interpretable collision avoidance guarantees with computational tractability.The planner targets an intermediate goal pose, and the safety filter keeps the ego within the safe set.Source: 3) Planner and Safety Filter · p. 5

A. Monte Carlo Simulation Results

Across 100 four-way-intersection trials, the pipeline avoided collisions and solver infeasibility, while completing cycles faster than both baselines. Tests also covered three-way and multi-agent extensions.

A. Monte Carlo Simulation Results

  • The study used 100 Monte Carlo trials in a four-way intersection, comparing deterministic MPC and CC-MPC, and also tested three-way and multi-agent scenarios.The collision detector used a 0.01 probability threshold; cycle time includes perception, prediction, and decision making.Source: A. Monte Carlo Simulation Results · p. 5
  • 0% collisions across 100 trials and 0% solver infeasibility; the pipeline completed cycles in 12.7 ± 3.3 ms, versus 18.0 ± 3.2 ms for deterministic MPC and 22.6 ± 5.5 ms for CC-MPC.The safe set always contains a collision-free path from the ego’s current position.Source: A. Monte Carlo Simulation Results · pp. 5–6, Table I · p. 6
  • In the three-way intersection, the pipeline maintained 0% collisions with a 7.2 ± 0.9 ms cycle time; the multi-agent extension had 0% collisions and infeasibility at 15.3 ± 1.1 ms.One three-way trial missed the goal by 6 cm, against a 5 cm threshold.Source: A. Monte Carlo Simulation Results · p. 6

B. Ablation Study

The ablations replace intent estimation, forecasting, or localization uncertainty while leaving the rest of the pipeline intact. Each removal increases collisions, while all three retain solver feasibility.

B. Ablation Study

  • No Intent uses a fixed intent-probability vector independent of the agent’s true maneuver, making the assigned intent incorrect 66.7% of the time.No Forecasting substitutes a constant-velocity EKF; No Localization supplies near-perfect location measurements and underestimates combined covariance.Source: B. Ablation Study · p. 6
  • Removing intent estimation raised collisions to 29%, replacing forecasting raised them to 9%, and removing localization uncertainty raised them to 5%.The study identifies intent, forecasting, and localization covariances as independently necessary for collision avoidance.Source: B. Ablation Study · p. 6
  • All three ablations maintained 0% solver infeasibility, while the full pipeline’s additional approximately 6 ms over the cheaper ablations was described as a modest cost for better collision avoidance.Trajectory quality may still degrade with upstream uncertainty propagation.Source: B. Ablation Study · p. 6

C. Hardware Deployment

The Jackal UGV trials test intersection crossing under uncertain agent pose and intent. Across the scenarios, the ego avoids collisions and maintains feasibility, including when the agent follows an unmodeled zig-zag path.

C. Hardware Deployment

  • A motion-capture system measured both robots at 60 Hz in a 3m × 3m intersection testbed, with no additional measurement noise added.The ego was tasked with crossing safely while the agent’s pose and intent were uncertain.Source: C. Hardware Deployment · pp. 6–7
  • The hardware pipeline used an IMM tracker and intent estimator, a 2.5s forecaster, and a collision-probability threshold of ϵ = 0.01.The planner ran at 2 Hz and the safety filter at 5 Hz.Source: C. Hardware Deployment · p. 7
  • All three nominal hardware scenarios avoided collisions, with feasibility maintained at every cycle.Keep-straight and left-turn clearances were 0.0869m and 0.2641m; the right-turn clearance was 0.6060m.Source: C. Hardware Deployment · p. 7
  • Fig. 4 depicts three scenarios at start, peak collision probability, and when the unsafe set no longer intersects the lane.Forecasts and covariance ellipsoids are blue; the planned trajectory, goal, and safe set are yellow.Source: Figure 4 · p. 7, C. Hardware Deployment · p. 7
  • In the zig-zag scenario, minimum clearance was 0.2641m and completion time was 15.33s despite oscillating intent probabilities.The safe set remained conservatively contracted throughout the maneuver.Source: C. Hardware Deployment · p. 8, Figure 5 · p. 8

V. CONCLUSION

The pipeline targets collision avoidance under uncertainty alongside real-time feasibility. In 100 Monte Carlo trials, it achieved 0% collisions and 0% solver infeasibility at 12.7 ms per cycle, and hardware deployment validated transfer to physical platforms.

V. CONCLUSION

  • In 100 Monte Carlo trials, the pipeline achieved 0% collisions and 0% solver infeasibility at 12.7 ms per cycle.Deterministic MPC had 36% collisions; chance-constrained MPC had 10% collisions and 14.2% infeasibility.Source: §V · p. 8
  • Intent estimation, forecasting, and localization covariances were each independently necessary for collision avoidance, while feasibility held structurally across all ablations.Source: §V · p. 8
  • The pipeline propagates intent probabilities, forecast covariances, localization errors, and vehicle geometry as structured quantities to produce uncertainty-adaptive convex safe sets.Source: §V · p. 8
  • Clearpath Jackal UGV deployment validated that the guarantees transfer from simulation to physical platforms.Source: §V · p. 8
Loading 2610.33186v1…