cs.RONov 8, 2026

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

Authors: Sanjeev Ramkumar Sudha, Lars Ivar Hatledal, Erlend M. Coates

Organizations: Norwegian University of Science and Technology, 6009 Ålesund, Norway

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.

Figures & tables

Explore similar work

Aug 7, 2026

CoCoNav: Conformal Control for Safe Robot Navigation in Crowds

Safe and efficient robot navigation in crowds requires anticipating pedestrian motion despite uncertain and potentially shifting prediction errors. Existing reactive methods can produce oscillatory behavior, while predictive planners often treat forecasts as exact or rely on restrictive error models. Incorporating conservative uncertainty sets as hard constraints can also render model predictive control (MPC) infeasible. We propose CoCoNav, a crowd-navigation framework that combines online conformal calibration with runtime-certified planning. A horizon-specific conformal proportional--integral controller adapts trajectory-error bounds to regulate long-run empirical coverage, enabling the framework to respond to changing prediction errors. A relax-then-verify planner preserves solver feasibility by generating nominal trajectories with soft-constrained MPC and separately certifying them, together with contingency maneuvers, against the calibrated bounds before execution. Simulations and quadruped experiments show that CoCoNav achieves a favorable balance among collision avoidance, task success, and navigation efficiency relative to the evaluated baselines.
May 25, 2026

RCSP: Risk-Sensitive Conjectural Scenario Planning for Safe Dynamic Robot Navigation

Mobile robots can fail before they collide: a velocity that is safe now may commit the robot to a passage that moving obstacles will soon close. We study this predictive near-miss commitment problem and propose Risk-Sensitive Conjectural Scenario Planning (RCSP), a planning layer that evaluates candidate commands against plausible short-horizon obstacle futures. RCSP maintains a lightweight belief over local motion conjectures, samples future interactions, penalizes high-risk tails, and executes through a local safety check. In controlled MuJoCo bottleneck tasks, the RCSP planner reaches the goal without collisions and yields higher secondary safety and path-quality point estimates than a non-adaptive predictor, with additional latency. In ROS2/Gazebo, adding the local safety layer to a standard Nav2 stack reduces dynamic near-miss failures. On official DynaBARN/Jackal transfer, tuned DWA and TEB remain stronger on strict benchmark success, revealing the boundary of the approach. These simulation results position RCSP as a predictive-risk module that complements existing navigation stacks in dynamic bottleneck regimes.
Oct 7, 2026

Adaptive Risk-Certified Event-Triggered Replanning for Dynamic Navigation

Safe navigation in dynamic environments requires robots to plan under obstacle predictions whose errors are uncertain, non-stationary, and can induce rare but safety-critical failures. Existing control-barrier-function safety filters can reject immediately unsafe controls, but they provide little guidance on when the current finite-horizon planning mode itself is becoming unsafe as prediction uncertainty evolves. We propose Conformal Event-Triggered Risk-Certified Replanning (CERT-Replan), a framework that uses calibrated barrier risk as an early-warning signal for replanning. CERT-Replan calibrates horizon-indexed obstacle-prediction residuals online and uses the resulting uncertainty radii to evaluate dynamic-obstacle safety margins. A one-step safety filter protects the next applied control, while a horizon-level risk monitor evaluates the upper-tail CVaR of predicted barrier-violation losses along the current MPC rollout. When this risk exceeds an allocated budget, CERT-Replan rejects the current planning mode and selects a lower-risk alternative, such as a different speed profile, corridor, or homotopy class, rather than repeatedly correcting the same nominal plan. In a non-stationary benchmark, CERT-Replan achieves an 83.3%83.3\% collision reduction relative to the safety-filter-only baseline \textcolor{black}{and a 77.8%77.8\% reduction relative to simple replanning triggers}, while reducing average safety-filter intervention by 32.4%32.4\%. \textcolor{black}{With Trajectron++, CERT-Replan achieves 96%96\% collision-free operation. Hardware experiments and onboard runtime profiling demonstrate computational feasibility.}