Expressiveness, Equivalence, and Uncertainty in Velocity Obstacles and Closest Point of Approach Metrics

Elizabeth Dietrich; Liam M. Imagawa; Hanna Krasowski; Aurora Haraldsen; Murat Arcak; Kristin Y. Pettersen

cs.ROOct 5, 2026

Expressiveness, Equivalence, and Uncertainty in Velocity Obstacles and Closest Point of Approach Metrics

Authors: Elizabeth Dietrich, Liam M. Imagawa, Hanna Krasowski, Aurora Haraldsen, Murat Arcak, Kristin Y. Pettersen

Organizations: University of California, Berkeley, USA · Norwegian University of Science and Technology, Trondheim, Norway

Abstract

Time to Closest Point of Approach (TCPA), Distance to Closest Point of Approach (DCPA), and Velocity Obstacles (VOs), are widely used to assess and mitigate collision risk in autonomous navigation, yet their relationship and behavior under uncertainty remain largely unexplored. Assuming perfect state information, we establish a relationship between these representations over finite and infinite prediction horizons and derive conditions under which they provide equivalent characterizations of collision risk. Under bounded uncertainty, we extend the Closest Point of Approach (CPA) metrics and VO to convex relative-state sets. We show that in this setting, independently computed TCPA and DCPA bounds lose the joint relationship required for VO membership, while uncertainty-aware VOs preserve this relationship through a set-valued representation of collision-inducing velocities.

Figures & tables

Panel of Figure 1 — Fig. 1: Overview of risk metrics. Left: DCPA is the perpendicular distance from the position $\mathbf{p}_{E}$ of agent $E$ , to the relative trajectory (gray dashed line). The relative trajectory passes through $\mathbf{p}_{O}$ and is aligned with $\mathbf{v}_{\mathrm{rel}}$ . TCPA is the time until the agents reach the CPA and is proportional to the distance between $\mathbf{p}_{O}$ and the CPA . Right: The VO represented as a collision cone in relative-velocity space. The cone is bounded by tangent rays extending from the ego reference point $\mathbf{p}_{E}$ to the circular collision region centered at $\mathbf{p}_{O}$ , with radius $r_{E}+r_{O}$ .

Set	$h_{\mathcal{S}}(\mathbf{d})$	$v_{\mathcal{S}}(\mathbf{d})$	Complexity
Unit Ball : $\{\mathbf{x}\in\mathbb{R}^{2}:\\|\mathbf{x}\\|\leq 1\}$	$\\|\mathbf{d}\\|$	$\frac{\mathbf{d}}{\\|\mathbf{d}\\|}$	$\mathcal{O}(1)$
Circle : $\{\mathbf{x}\in\mathbb{R}^{2}:\\|\mathbf{x}-\mathbf{c}\\|\leq r\}$	$\mathbf{d}^{\top}\mathbf{c}+r\left\lVert\mathbf{d}\right\rVert$	$\mathbf{c}+r\frac{\mathbf{d}}{\left\lVert\mathbf{d}\right\rVert}$	$\mathcal{O}(1)$
Ellipse : $\{\mathbf{x}\in\mathbb{R}^{2}:(\mathbf{x}-\mathbf{c})^{\top}Q^{-1}(\mathbf{x}-\mathbf{c})\leq r\}$	$\mathbf{d}^{\top}\mathbf{c}+\sqrt{\mathbf{d}^{\top}(rQ)\mathbf{d}}$	$\mathbf{c}+\frac{(rQ)\mathbf{d}}{\sqrt{\mathbf{d}^{\top}(rQ)\mathbf{d}}}$	$\mathcal{O}(1)$
Polygon : $\{\mathbf{x}\in\mathbb{R}^{2}:H\mathbf{x}\leq\mathbf{b}\}$	$\max_{\mathbf{x}\in\mathbb{R}^{2}}\mathbf{d}^{\top}\mathbf{x},\text{ s.t. }H\mathbf{x}\leq\mathbf{b}$	$\argmax_{\mathbf{x}\in\mathbb{R}^{2}}\mathbf{d}^{\top}\mathbf{x},\text{ s.t. }H\mathbf{x}\leq\mathbf{b}$	$\mathcal{O}(m)$

TABLE I: Support functions, support vectors, and computational complexity for common convex sets in

\mathbb{R}^{2}

Panel of Figure 3 — Fig. 2: Investigated encounters for evaluating collision risk metrics in 2D surface navigation.

Panel of Figure 4 — Fig. 3: Evaluation of CPA metrics for a crossing encounter with sampled relative velocities in $[-10,10]^{2}$ . DCPA defines two cones, while TCPA identifies the region of possible future collisions. Their conjunction, evaluated using quantitative semantics, recovers the VO in Corollary 3 . Color indicates the normalized magnitude of each metric, signed positive for satisfaction and negative for violation, scaled to $[0,1]$ using the 95th percentile of each metric.

Panel of Figure 5 — Fig. 4: Collision risk metrics under bounded state uncertainty for crossing encounter: (Left) Joint distribution of $10{,}000$ TCPA and DCPA values, with collision condition of Corollary 3 (pink) and interval bounds from Eq. ( 11 ) (green). (Right) Deterministic VO (dark pink) and UVO (light pink) in velocity space, with the ego-velocity uncertainty set $\mathcal{K}_{E}$ (purple).

Metric	Cr	H	O	Co	P
$\UVO$	$1.000$	$1.000$	$1.000$	$0.999$	$1.000$
$\VO$	$0.917$	$0.776$	$0.554$	$0.017$	$0.216$
$\DCPA\wedge\TCPA$	$0.699$	$0.627$	$0.519$	$0.019$	$0.212$
$\DCPA$	$0.699$	$0.627$	$0.519$	$0.036$	$0.428$
$\TCPA$	$1.000$	$1.000$	$1.000$	$0.501$	$0.505$

TABLE II: Point Estimates of Collision Risk Identified by the CPA metrics, VO, and UVO

Explore similar work

Chance-Constrained MPPI under State and Dynamic Object Prediction Uncertainty and the Evaluation of Collision Risk Calibration
May 27, 2026Benjamin Serfling, Konrad Doll, Kati Radkhah-LensModel Predictive Path Integral Collision Prediction
University of Applied Sciences Aschaffenburg, Aschaffenburg, Germany
Driving risk emerges from the required two-dimensional joint evasive acceleration
Apr 20, 2026Hao Cheng, Yanbo Jiang, Wenhao Yu +9Collision Prediction Risk
School of Vehicle and Mobility, Tsinghua University, Beijing 100084, China · State Key Laboratory of Intelligent Green Vehicle and Mobility, Beijing 100084, China · School of Traffic & Transportation Engineering, Central South University, Changsha 410000, China +2
From Prediction Uncertainty to Conformalized Distance Fields for Safe Motion Planning
Jul 1, 2026Jaeuk Shin, Yoonseok Ra, Insoon YangMotion Planning Online Conformal Prediction
Department of Electrical and Computer Engineering, ASRI, Seoul National University, Seoul 08826, South Korea

May 27, 2026, cs.ROJ/K move · Enter open · S save

Chance-Constrained MPPI under State and Dynamic Object Prediction Uncertainty and the Evaluation of Collision Risk Calibration

Benjamin Serfling, Konrad Doll, Kati Radkhah-Lens

University of Applied Sciences Aschaffenburg, Aschaffenburg, Germany

Model Predictive Path Integral Collision Prediction Autonomous Navigation Predictive Uncertainty Probabilistic Safety Uncertainty

Open paper AskPDF arXiv

Chance-constrained Model Predictive Path Integral (MPPI) control is increasingly adopted for navigation in dynamic environments to explicitly bound collision risk. However, these probabilistic guarantees implicitly assume that upstream uncertainties from localization and perception are well-calibrated. In practice, estimators are often miscalibrated, inducing characteristic closed-loop failure modes: overconfidence leads to systematic safety violations, while underconfidence triggers overly conservative freezing or probability dilution. To address this critical gap, our primary contribution is a rigorous evaluation methodology applying proper scoring rules to assess the statistical validity of predicted collision risks during closed-loop execution. Concurrently, Dual-Uncertainty Chance-Constrained Tube MPPI (DUCCT-MPPI) is proposed as a real-time, risk-aware planning architecture. DUCCT-MPPI jointly integrates localization uncertainty via a one-tube Unscented Transform (UT) approximation and dynamic obstacle prediction uncertainty via Monte Carlo aggregation. Through extensive physics-based simulations, the framework demonstrates robust failure-mitigation, seamlessly transitioning to safe, conservative maneuvering without succumbing to functional deadlocks in highly cluttered environments. In highly cluttered environments, DUCCT-MPPI achieves superior robustness, outperforming established Monte Carlo MPPI baselines by nearly 28% in navigation success rate, while simultaneously recording the lowest travel times and minimizing induced social forces. Ultimately, these findings establish that reliable probabilistic safety in autonomous navigation dictates not only expressive risk models but statistically valid uncertainty estimates throughout the entire autonomy stack.

Abstract

Explore similar work

Chance-Constrained MPPI under State and Dynamic Object Prediction Uncertainty and the Evaluation of Collision Risk Calibration

Driving risk emerges from the required two-dimensional joint evasive acceleration

From Prediction Uncertainty to Conformalized Distance Fields for Safe Motion Planning