CS Paper Radar

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.RO eess.SY ·submitted 2026-10-05 20:39 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Interpretable Collision Avoidance and Feasibility Guarantees through an Uncertainty Aware Pipeline

cs.RO ·2026-10-23 ·Doris Xu, Jin Hyun Park, Guadalupe Alvarado Fernandez, Adhyan Prasad, Mark Campbell
similarity 0.69
Abstract

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.

0.09

ColNav: Uncertainty-Aware Spacetime Collision Checking with Bounding Volume Hierarchies

cs.RO ·2026-11-08 ·Sanjeev Ramkumar Sudha, Lars Ivar Hatledal, Erlend M. Coates
similarity 0.68
Abstract

Safe navigation for mobile robots in dynamic and uncertain environments requires planning paths that avoid collisions with other moving targets. Typically this involves forward propagating the robot motion and checking for collisions at sampled points in space and time. Such methods can miss collisions between sampled points and are not robust to uncertainty in the state estimates. We propose ColNav, a robust collision check formulation with geometric volumes. The key aspect of our approach is encoding the uncertainty in the targets' and the ego robot's positions and velocities into spacetime tubes, in two variants that consume bounded-set and Gaussian uncertainty descriptions, respectively. The tubes are organised in bounding volume hierarchies, so that a single tree traversal covers the entire horizon, rather than testing sampled time instants, and returns a robust geometric certificate together with an estimate of the time to collision. Static and dynamic obstacles share the same representation. Our approach reaches the goal with a 100% success rate under prediction model mismatch, where the best baseline reaches 65%, and maintains up to three times the clearance in dense traffic. We also validate real-time operation on a physical robot.

0.26

Probability-Based Collision Risk Evaluation of Trajectories for Optimal Control Problems with Moving Obstacles

eess.SY ·2026-09-29 ·Florian Steppich, Matthias Gerdts
similarity 0.65
Abstract · 27 pages, 15 figures, presented 2024 on IFIP TC7, Hamburg, Germany

This paper presents a method for approximating occupancy distributions, a common probabilistic representation used in trajectory planning for autonomous vehicles operating in uncertain environments. The proposed method employs B-spline surfaces in conjunction with regularization techniques to ensure smoothness and differentiability. Interpreting the resulting approximation as an intensity function of a Poisson random field enables seamless integration of multiple occupancy distributions into a coherent risk representation, while retaining compatibility with the semantics of probability distributions. The method is tailored to optimal control problems (OCPs), where solvers benefit from gradient and higher-order derivative information. It also preserves information about the spatial and temporal structure of occupancy distributions, which is critical for handling dynamic obstacles. We demonstrate the feasibility of the approach in a trajectory planning scenario involving autonomous vehicles and moving obstacles with time-varying uncertainty. By enabling controlled risk acceptance, our formulation extends beyond conservative "no-collision" strategies and allows for admissible trajectories that would otherwise be ruled out. In our application scenario, we report a reduction in solver computational load of up to 50\% through proper tuning of the regularization.

0.28

Risk Density RRT$^*$: Planning in the Space of Probability

cs.RO ·2026-11-17 ·Lorenzo Paiola, Giorgio Grioli, Antonio Bicchi
published similarity 0.65
Abstract · Accepted for publication in The International Journal of Robotics Research (IJRR)

Planning under uncertainty is a fundamental problem in robotics. While much of the literature seeks minimum-cost paths subject to probabilistic constraints, this paper instead considers collision probability, or risk classically defined as probability times severity, directly as the planning objective. We propose Risk Density RRT$^*$ (RD-RRT$^*$), an extension of RRT$^*$ for high-level planning in environments with deterministic and uncertain obstacles. RD-RRT$^*$ builds on Risk Density, a functional that evaluates a continuous path as a whole and provides a tractable approximation of its collision probability. The framework also supports severity-weighted risk and a hybrid variant that adds a path-length penalty, balancing risk and geometric efficiency while regularizing exploration in low-density regions. We validate the method across a wide range of scenarios. The results show that RD-RRT$^*$ consistently finds paths with lower estimated collision probability by optimizing a global risk-based objective. We further demonstrate the fidelity of the underlying approximation through Monte Carlo simulations. Finally, we discuss how the topological structure induced by Risk Density may provide a useful representation of the environment and offer insights into risk-aware planning.

0.21

RL-Guided PAC-NMPC for Probabilistically-Safe Perception-Based Navigation in Unknown Environments

cs.RO ·2026-09-30 ·Adam Polevoy, Dillon Capalongo, Katherine Tang, Mark Gonzales, Marin Kobilarov +1 more
similarity 0.64
Abstract

In this paper, we present an approach for combining stochastic nonlinear model predictive control (SNMPC) and reinforcement learning (RL) to enable probabilistically-safe perception-based navigation in unknown environments. Our method first uses RL to train probabilistic actor-critic and sensor prediction models. We then leverage these probabilistic models in a sampling-based SNMPC framework known as Probably Approximately Correct (PAC)-NMPC, which uses hard constraints to enforce finite-time statistical guarantees on the probability of collision and value function improvement. By ensuring that our finite-horizon SNMPC policies decrease the value function in expectation, we can approach the long-horizon performance of the RL approach while satisfying probabilistic safety constraints. Through simulation experiments, we show that our approach can improve the safety of perception-based RL navigation policies and scale to high dimensional systems with large sensor input spaces and complex nonlinear dynamics. We also demonstrate our approach through hardware experiments, showing improved performance for vision-based navigation with an agile fixed-wing aerial vehicle in unknown environments.

0.12

Estimation-Aware Reachability

cs.RO eess.SY ·2026-11-18 ·Himanshu Paudel, Javier Borquez
code/data similarity 0.64
Abstract

Hamilton-Jacobi Reachability computes the states from which a system can be kept safe under worst-case disturbances, but it assumes the state is known exactly, whereas real robots act on noisy estimates whose uncertainty evolves with their motion. We extend Hamilton-Jacobi Reachability to the robot's belief, estimate and uncertainty, treating unexpected measurements as a bounded adversary and enlarging the unsafe set by the current uncertainty, so that certified states are safe with a prescribed probability. The formulation is compatible with existing solvers. In simulation, the resulting safety filters nearly eliminate the collisions of certaintyequivalent HJ and are less conservative than equally safe uncertainty-padding baselines. The implementation code is available at https://github.com/HimanshuPaudel/Estimation-Aware-Reachability

0.42

SC3BF: Shifted Collision Cone Control Barrier Function for Dynamic Obstacle Avoidance

cs.RO cs.MAeess.SY ·2026-10-06 ·Amin Kashiri, Yasin Yazıcıoğlu
theory similarity 0.64
Abstract · Submitted to the 2027 American Control Conference (ACC)

The collision cone used by velocity-space control barrier functions is conservative: it rejects every relative velocity aimed into an obstacle, however slow. We propose the \emph{shifted collision-cone CBF} (SC3BF), which adds a state-dependent \emph{allowance} to the cone condition, so the robot may approach the obstacle at a rate that grows with distance and with its own speed. SC3BF is enforced by an ordinary quadratic program, and its safe set is forward invariant under bounded inputs without a minimum forward speed or a clearance margin. We prove that a nonzero allowance preserving safety always exists, and derive one in closed form. Against three velocity-space baselines on a kinematic bicycle among up to $100$ moving obstacles, SC3BF reaches the goal more often and modifies the nominal input less than half as much.

0.41

Which Trajectory Is Safer? Combining Rule and Learning for Safety Evaluation

cs.RO ·2026-10-13 ·Xuewen Luo, Linlian Jiang, Bo Yu, Fan Ding, Xinxin Zuo +1 more
code/data similarity 0.62
Abstract

Collision rate remains a dominant metric for evaluating autonomous driving trajectory safety, but its binary nature obscures substantial safety differences among collision-free trajectories. Existing surrogate-safety metrics provide finer-grained assessments, yet often trade off physical interpretability against adaptivity to interaction context. We introduce FutureRisk, a continuous metric that quantifies the latent future risk of a trajectory by how closely and persistently its realized interactions approach unsafe states. At its core, our Context-Adaptive Risk Model (CARM) combines a context-dependent safety-time distribution with an independently supervised critical-event-time distribution. Its safety criterion is bounded around a closed-form physical prior, while a bounded residual provides additional adaptation without abandoning this physical anchor. Experiments on DeepAccident and Bench2Drive show that FutureRisk achieves stronger agreement with native collision labels than existing surrogate-safety measures, discriminates risk among collision-free trajectories, and transfers zero-shot across datasets. Comparisons across four planners further show that FutureRisk reveals safety differences hidden by binary collision outcomes. Together, these results establish FutureRisk as a fine-grained, interpretable, and context-adaptive metric for trajectory safety evaluation. Code is available at https://github.com/Xuewen2025/safety-evaluation.

0.23