Source-linked AI summary
OcclusionCBF: Backup Control Barrier Functions for Safe Navigation Among Hidden Dynamic Obstacles
Taekyung Kim, Hun Kuk Park, Renya Wada, Nikolay Atanasov, Shumon Koga, Dimitra Panagou
TL;DR
Occlusion can leave robots without an admissible input to avoid a dynamic obstacle once it becomes visible. OcclusionCBF certifies a backup rollout against predicted occupancy and a verified terminal set, then filters the nominal input through a minimally invasive QP. It achieves the highest success rate among hard-constrained benchmark variants and shows safe goal completion in simulation and hardware.
Problem
A robot that avoids only detected obstacles may enter a state where no admissible input can prevent collision once a hidden obstacle becomes visible.
Source: §I · p. 1Method
OcclusionCBF extends Backup CBFs by certifying a prescribed backup rollout against reachable occupancy for hidden dynamic obstacles and a verified terminal set.
Source: §I · p. 1Results
OCBF-QP achieved the highest success rate among hard-constrained variants across both robot models and every tested density, reaching 86% in unicycle trials at the highest densities.
Source: C. Benchmark Results · p. 7Takeaways & Limitations
Under the stated assumptions, the filter provides recursive feasibility and collision avoidance for covered hidden-obstacle motions, with low-millisecond computation and safe goal completion in MetaUrban and hardware experiments.
Source: C. Benchmark Results · p. 7, §VI · p. 8
Abstract
from arXiv · showhide
Robots navigating under occlusion may enter states from which no admissible input can avoid a dynamic obstacle once it becomes visible. We present OcclusionCBF, a safety filter that extends backup control barrier functions to reachable-occupancy predictions for potentially hidden dynamic obstacles in occluded regions. The method certifies a prescribed backup rollout against collision-inflated occupancy and a verified terminal set, yielding affine constraints for minimally invasive quadratic-program filtering. We establish recursive feasibility of the resulting safety filter, and collision avoidance for every hidden-obstacle motion covered by the occupancy prediction. Randomized benchmarks, MetaUrban simulations, and hardware experiments demonstrate improved task success over reactive and occlusion-aware predictive baselines with millisecond-scale computation.
I. INTRODUCTION
Occlusion can leave a robot without enough control authority to avoid a hidden obstacle, so safety filtering must account for possible obstacle motion before detection. OcclusionCBF extends Backup CBFs into a planner-agnostic filter that certifies a backup maneuver against predicted occupancy.
I. INTRODUCTION
- Detected-obstacle-only control can steer a robot into a state where no admissible input prevents collision after a hidden obstacle becomes visible.The risk arises from uncertain hidden-obstacle occupancy interacting with robot dynamics and finite control authority, not sensing latency alone.Source: §I · p. 1
A. Related Work
- Prior occlusion-aware planners incorporate hidden-obstacle reachability into trajectory optimization, while OcclusionCBF makes safety filtering modular for arbitrary nominal controllers.Visibility-aware planning and set-based verification address related problems, but generally do not model worst-case future motion of unseen dynamic obstacles.Source: §I · p. 1, A. Related Work · p. 2
B. Contributions
- OcclusionCBF extends Backup CBFs to conservative reachable-occupancy predictions and certifies backup maneuvers without embedding safety in a specific trajectory optimizer.It derives input-affine rollout and terminal constraints and proves recursive feasibility and collision avoidance for every obstacle motion covered by the prediction.Source: B. Contributions · p. 2
- Across five baselines, randomized tests achieve the highest hard-constrained success rate at every tested density, with millisecond-scale computation.MetaUrban and hardware results show intervention before detection and safe goal completion.Source: B. Contributions · p. 2
II. PRELIMINARIES
The preliminaries define the robot, nominal controller, and time-varying safety constraints, then introduce Backup CBFs as a way to characterize recoverable states through a prescribed backup policy.
A. Robot Dynamics and Time-Varying Safety
- The robot has control-affine dynamics, a workspace position extracted from its state, and a nominal controller whose input can be modified by a minimally invasive safety filter.The filter chooses the feasible input closest to the nominal input in a prescribed norm.Source: A. Robot Dynamics and Time-Varying… · p. 2
- A time-varying barrier function defines the safe set, and satisfying its CBF constraint makes that set forward invariant when the initial state is safe.Membership in the safe set alone does not guarantee CBF constraint feasibility under input limits.Source: A. Robot Dynamics and Time-Varying… · p. 2
B. Backup Control Barrier Functions
- A Backup CBF defines recoverable states as those whose backup-policy rollouts remain safe and reach a forward-invariant terminal set within a finite horizon.The choice of backup policy affects the size of the induced recoverable set.Source: B. Backup Control Barrier Functions · p. 2
- The backup policy induces closed-loop dynamics whose flow map describes the state reached after a specified backup-rollout time.For a fixed backup policy, the closed-loop dynamics are autonomous and the flow satisfies the stated flow-composition property.Source: B. Backup Control Barrier Functions · p. 3
III. PROBLEM FORMULATION
The problem is to filter a nominal controller so the robot remains recoverable and avoids hidden dynamic obstacles despite limited, occluded sensing. The occupancy predictor represents where unseen obstacles may be and how their occupancy can evolve over the backup horizon.
III. PROBLEM FORMULATION
- Each obstacle has a known speed bound, so its displacement over any interval up to T lies within a ball of radius proportional to elapsed time.The occupancy predictions are recomputed when new observations arrive; region indexing remains fixed between updates.Source: §III · p. 3
- The predictor represents potentially hidden obstacle locations as a finite union of occluded regions and returns collision-inflated reachable-occupancy sets.The inflation radius accounts for robot and obstacle footprints, localization and perception uncertainty, and prescribed clearance.Source: §III · p. 3
- A minimally invasive filter must remain feasible on its certified recoverable set and avoid every hidden-obstacle motion covered by the prediction, under input constraints.The predictor is assumed to satisfy occupancy coverage and temporal consistency; after a discontinuous prediction update, the current state requires recertification.Source: §III · p. 3
IV. OCCLUSION CBF
OcclusionCBF certifies a finite-horizon backup maneuver against time-varying reachable occupancy and requires it to end in a verified terminal set. Polyhedral outer approximations and differentiable conservative separation margins make occupancy constraints usable along the backup rollout.
IV. OCCLUSION CBF
- The backup maneuver must remain outside every time-varying reachable-occupancy set and terminate in a verified set that is forward invariant under the backup policy.Preserving this certificate supports recoverability and collision avoidance for all hidden-obstacle motions covered by the prediction.Source: §IV · p. 3
A. Polyhedral Reachable-Occupancy Margin
- The method constructs conservative polyhedral outer approximations of occluded regions, then derives a differentiable separation margin from their facet margins.For polygonal regions, the approximation can be obtained from their vertices using a convex-hull algorithm.Source: A. Polyhedral Reachable-Occupancy Margin · p. 4
- The enclosure expands both with elapsed time since the last update and with look-ahead time, accounting for bounded obstacle motion and collision clearance.Between updates, temporal consistency holds with equality because the elapsed-time expansion advances at the obstacle speed bound.Source: A. Polyhedral Reachable-Occupancy Margin · p. 4
- A shifted log-sum-exp margin smooths the facet-based separation condition while retaining a conservative bound on the smoothing gap.The margin imposes separation from every reachable-occupancy set; changes to facet number or geometry trigger current-state recertification.Source: A. Polyhedral Reachable-Occupancy Margin · p. 4
B. Backup Rollout and Terminal Set
The backup rollout is certified against moving occupancy sets and must end in a time-varying terminal set. The terminal-set assumption ensures forward invariance under the backup policy between prediction updates.
B. Backup Rollout and Terminal Set
- The backup policy is held fixed on each update interval and must keep the rollout outside every time-varying occupancy set.The terminal set is defined by nonnegative terminal barrier margins and is forward invariant under the backup policy between discontinuous prediction updates.Source: B. Backup Rollout and Terminal Set · p. 4
- The endpoint margins express whether the backup flow reaches the terminal set at time t+T.The terminal condition holds exactly when all indexed endpoint margins are nonnegative.Source: B. Backup Rollout and Terminal Set · p. 4
- The terminal condition also implies the corresponding occupancy constraint at the backup-horizon endpoint, with additional clearance when ρT is positive.The terminal clearance is an additional nonnegative design quantity.Source: B. Backup Rollout and Terminal Set · p. 4
C. Occlusion-Aware Recoverable Set and OCBF-QP
The recoverable set is defined by enforcing occupancy and terminal conditions through a quadratic program. Separate barrier inequalities cover the occupancy constraints over the horizon and the terminal condition.
C. Occlusion-Aware Recoverable Set and OCBF-QP
- The method defines a time-varying recoverable set induced by the backup policy and enforces its occupancy and terminal conditions through a QP.The occupancy inequalities are imposed for future times from t through t+T.Source: C. Occlusion-Aware Recoverable Set and… · p. 5
- The occupancy quantities are evaluated at the corresponding look-ahead time, while terminal quantities are evaluated at the backup-horizon endpoint.The notation suppresses their dependence on the current state and time.Source: C. Occlusion-Aware Recoverable Set and… · p. 5
- The OCBF-QP combines occupancy and terminal quantities into constraints that are affine in the control input.The objective uses a positive-definite weight matrix W.Source: C. Occlusion-Aware Recoverable Set and… · p. 5
D. Recursive Feasibility and Safety Guarantees
The OCBF-QP is feasible on the recoverable set, and its constraints preserve that set across prediction updates. Under the theorem’s assumptions, this gives recursive feasibility and collision avoidance for hidden-obstacle motions covered by the occupancy prediction.
D. Recursive Feasibility and Safety Guarantees
- Because prediction updates can change the recoverable set discontinuously, the proof reinitializes its preservation argument after each update.The continuous physical state need not satisfy membership in the preceding recoverable set.Source: D. Recursive Feasibility and Safety… · pp. 5–6
- At every state in S(t), the backup input satisfies all OCBF-QP constraints, establishing pointwise feasibility on the recoverable set.This holds between updates when the stated regularity, input admissibility, and backup-flow assumptions are met.Source: D. Recursive Feasibility and Safety… · p. 5
- Under the theorem’s assumptions, the OCBF-QP remains recursively feasible and avoids hidden-obstacle motions covered by the occupancy prediction.The proof preserves occupancy and terminal margins, keeping the state in the recoverable set.Source: D. Recursive Feasibility and Safety… · pp. 5–6
- Scalar comparison preserves initialized occupancy and terminal margins, while advancing-horizon occupancy constraints are initialized as they enter the enforced interval.The proof therefore preserves the conditions defining S(t) between updates.Source: D. Recursive Feasibility and Safety… · pp. 5–6
E. Practical Implementation
The implementation discretizes the look-ahead interval and enforces trajectory constraints at sampled times, unlike the ideal continuous-time constraint family.
E. Practical Implementation
- The implemented QP enforces trajectory constraints only at sampled look-ahead times, so it does not exclude intersample violations.The continuous-time guarantees apply to the ideal constraint family over the full interval.Source: E. Practical Implementation · p. 6
- The look-ahead interval is discretized from s_0 = 0 to s_N = T, with constraints enforced at τ_i = t + s_i.Source: E. Practical Implementation · p. 6
- The paper points to prior treatments of semi-infinite safety constraints and time-discretization error.Source: E. Practical Implementation · p. 6
V. RESULTS
The results section describes evaluation across randomized benchmarks, MetaUrban simulation, and hardware, and includes an empirical relaxed-terminal ablation.
V. RESULTS
- OCBF-QP is evaluated in randomized planar benchmarks, MetaUrban simulation, and hardware experiments.Source: §V · p. 6
- All constraints are hard by default, and a relaxed-terminal ablation assesses conservatism introduced by the terminal condition.Source: §V · p. 6
- The relaxed-terminal variant uses penalized slack only for terminal inequalities; trajectory occupancy constraints remain hard.This empirical variant is not covered by Theorem 1.Source: §V · p. 6
A. Randomized Benchmark Setup
The randomized benchmark setup specifies robot dynamics, shared trial conditions, and hidden-obstacle occupancy predictions with a prescribed backup policy.
A. Randomized Benchmark Setup
- The double integrator models bounded acceleration and speed, while the unicycle models bounded speed and turning; both robots have radius 0.25 m.Source: A. Randomized Benchmark Setup · p. 6
- Trials use a 30 m × 30 m workspace, a fixed waypoint sequence, 10 m sensing range, 360° field of view, and line-of-sight occlusion.Visible obstacles’ positions and velocities are provided to every controller.Source: A. Randomized Benchmark Setup · p. 6
- The tests vary moving-obstacle counts by robot model and initially place hidden obstacles behind another obstacle.Obstacle sizes and tested counts are specified for the unicycle and double integrator.Source: A. Randomized Benchmark Setup · p. 6
- At each update, occluder-induced unseen regions are enclosed and propagated into time-indexed occupancy sets; the backup policy steers away from selected sets.The double-integrator and unicycle use different backup implementations and horizons.Source: A. Randomized Benchmark Setup · pp. 6–7
- Each robot model and obstacle density is tested on 100 randomized scenarios replayed across methods using shared models and a 0.05 s time step.Trials have a 500 s limit; controller hyperparameters are tuned using Optuna.Source: A. Randomized Benchmark Setup · p. 7
B. Compared Methods
The section compares OcclusionCBF with reactive and predictive baselines, then reports benchmark, simulation, and hardware results. OCBF-QP leads hard-constrained success across tested densities, runs at millisecond scale, and shows proactive hardware intervention.
B. Compared Methods
- Baselines span reactive visible-obstacle CBF-QP, reachable-set OA-MPC, branched Control-Tree MPC, Single-Hypothesis MPC, and OACP.OA-MPC assumes static occluding geometry, unlike the benchmark's moving obstacles that can create or remove occlusions.Source: B. Compared Methods · p. 7
C. Benchmark Results
- In dense double-integrator navigation, OCBF-QP intervenes only when the nominal command would compromise the certified backup maneuver and leaves compliant commands unchanged.The illustrated scenario completes its waypoint sequence.Source: C. Benchmark Results · p. 7
- OCBF-QP achieves the highest hard-constrained success rate at every tested density, reaching 86% of unicycle trials and 70% of double-integrator trials at the highest densities.Figure 4 summarizes 100 paired trials; compared methods increasingly terminate through collision or controller infeasibility.Source: Figure 4 · p. 7, C. Benchmark Results · p. 7
- OCBF-QP requires 4.1–4.5 ms per unicycle update and 1.6–3.9 ms per double-integrator update, substantially faster than predictive-planning baselines.Reactive CBF-QP is faster because it performs neither occupancy propagation nor backup certification; Table I reports average controller computation time per update.Source: Table I · p. 7, C. Benchmark Results · p. 7
D. High-Fidelity Simulation and Hardware Experiments
- MetaUrban demonstrations cover a unicycle and double-integrator quadruped; in hardware blind crossing, OcclusionCBF intervenes before detection and reaches the goal while CBF-QP collides.The hardware comparison uses a TurtleBot 4 ego robot, a TurtleBot 3 dynamic obstacle, and a wall creating the occluded region.Source: D. High-Fidelity Simulation and… · p. 7, Figure 5 · p. 8
VI. CONCLUSION
- OcclusionCBF certifies a backup rollout against time-indexed reachable occupancy and a verified terminal set, yielding minimally invasive QP constraints and conditional recursive-feasibility and collision-avoidance guarantees.The guarantees cover hidden-obstacle motions included in the occupancy prediction and hold under the stated assumptions.Source: §VI · pp. 7–8