CS Paper Radar

Filtering for Liveness: Recurrence via Backup Reachability Control Barrier Functions

David E. J. van Wijk, Pio Ong, Aaron D. Ames, Joel W. Burdick

eess.SY cs.RO ·submitted 2026-10-12 19:44 UTC · v1

Abstract

Liveness requires a dynamical system to repeatedly accomplish a desired objective over time. In this work, we consider a particular form of liveness known as recurrence, which requires the closed-loop trajectory to regularly revisit a prescribed set, with no more than a specified amount of time between visits. Inspired by the control barrier function (CBF) safety-filter paradigm, we develop a controller-filtering framework that makes adjustments to a nominal controller only when necessary to guarantee recurrence. Unlike conventional CBF methods, which enforce set forward invariance, our framework allows the trajectory to leave the set while guaranteeing its timely return. To achieve this, our framework combines two components: a backup reachability CBF that preserves the ability to return to the prescribed set within the allowable time, and a timing-based mechanism that invokes a reaching controller only when the nominal behavior would otherwise fail to meet the return-time requirement. The resulting framework guarantees recurrence while preserving the nominal behavior when possible, enabling control objectives that require temporary excursions from the set, such as traversal between disjoint regions. Our method is successfully utilized in a drone racing example with a recurrence constraint on beacon visibility.

Comment
6 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Backup Control Barrier Functions with Memory for Online Set Expansion

eess.SY ·2026-10-04 ·M. Yusuf Uzun, Ersin Das
similarity 0.67
Abstract

Backup control barrier functions (bCBFs) construct implicit safe sets for nonlinear systems with bounded inputs using finite-horizon predictions under a backup controller. As in model predictive control, an invariant backup set serves as a terminal set that guarantees safe continuation beyond the prediction horizon. However, reaching a small terminal set may require long prediction horizons, increasing the cost of online prediction. In this paper, we introduce an online construction that builds a certified region from sets stored along backup trajectories while keeping the prediction horizon fixed. The method stores finite collections of balls and connects each newly certified collection to the backup set or to previously stored balls. We derive conditions that guarantee forward invariance of the union of these balls and the backup set under a fixed backup controller. These conditions also ensure that every stored state reaches the backup set in finite time. The resulting union serves as an enlarged terminal set, allowing safety to be certified with shorter prediction horizons. We formulate a feasible quadratic program for safe control and prove that safety is preserved as additional certified collections are stored online. Simulations on a quadrotor demonstrate safe task completion with a shorter prediction horizon than the standard bCBF.

0.16

Timely Activation of Safety Filters via One-Step Reachability Expansion

cs.RO ·2026-09-15 ·Javier Borquez
published similarity 0.65
Abstract

Least-restrictive safety filters based on Hamilton-Jacobi reachability provide strong safety guarantees by overriding a nominal controller only when the system reaches the boundary of the set of unsafe states defined as a Backward Reachable Tube (BRT). These guarantees, however, rely on the continuous-time nature of the underlying formulation. In practice, robotic systems apply control at discrete sampling intervals, which creates a mismatch where the system may jump into the unsafe BRT between updates, allowing failures that are theoretically avoidable. This work introduces a principled solution based on a one-step expanded BRT that predicts all states capable of reaching the true BRT within a single timestep. By using this expanded boundary as the activation condition for the safety filter, safety interventions occur early enough to ensure correctness under discrete-time execution. We formulate this expanded set as a modified reachability problem and compute it using standard continuous-time solvers.

0.40

A Recursive CBF Framework for Safety under State Uncertainty

eess.SY ·2026-09-16 ·Rahal Nanayakkara, Aaron D. Ames, Paulo Tabuada
similarity 0.64
Abstract · 8 pages, 4 figures, IEEE CDC 2026

The practical implementation of Control Barrier Functions (CBFs) for safety-critical control is often hindered by uncertainty in the knowledge of the state. While existing robust CBF methods address state uncertainty, they often lack recursive feasibility guarantees or fail when uncertainty levels are high, allowing the system to enter regions where no safe control input exists. To resolve this, we propose a novel framework of enforcing recursive CBFs. Rather than merely ensuring the invariance of the original safe set, this approach enforces the forward invariance of a subset of the safe region where a robustly safe control input is guaranteed to exist. This holistic framework ensures that the system never strays into ambiguous regions, providing continued feasibility and safety guarantees, regardless of the level of state uncertainty.

0.27

Backup Control Barrier Function Synthesis using Sum-of-Squares Reachability

eess.SY ·2026-08-28 ·Jungbae Chun, Shima Sadat Mousavi, David E. J. van Wijk, Ersin Daş, Aaron D. Ames +1 more
similarity 0.64
Abstract

Backup control barrier functions (bCBFs) enforce safety for input-constrained nonlinear systems using a pre-certified backup set and controller, but their performance depends strongly on this prescribed pair. This letter develops a constructive method for synthesizing a less conservative backup pair via finite horizon sum-of-squares (SOS) backward reachability. Starting from an initial backup set, we compute an SOS-certified finite horizon backward reachable set and controller that satisfy safety and input constraints while steering trajectories to the original backup set. We then provide conditions under which this certified set becomes a valid backup set for a piecewise backup controller. The resulting backup pair is integrated into the bCBF framework to certify larger safe sets.

0.23

Timed Games under Environmental Interference with Real-Time Objectives

cs.LO ·2026-11-04 ·Andrea Manini, Matteo Rossi, Pierluigi San Pietro
top venue similarity 0.62
Abstract

Classical Timed Games formulations may be unsuitable, or require substantial modeling effort, to capture complex interaction patterns between a controller and its surrounding environment, in which non-determinism must be resolved after the controller has chosen which action to perform. In this paper, we develop the theory of Timed CLTLoc Games (TCGs), a Timed Game variant designed to facilitate the modeling of such patterns. Unlike classical Timed Games formulations, TCGs partition locations rather than transitions, and use Constraint Linear Temporal Logic over clocks (CLTLoc) to specify the controller's objectives. We develop algorithms for solving TCGs and synthesizing winning controller strategies for games whose objectives include formal properties such as reachability and safety. For reachability objectives, our synthesis algorithm yields winning controller strategies that minimize the number of moves required to reach a goal state. Solving reachability TCGs is EXPTIME-complete, matching the complexity of solving reachability Timed Games. All of our algorithms operate backwards and are implemented in our C++ region-based library TARZAN, leveraging OpenMP for efficient parallelization. Experimental results demonstrate the feasibility of TARZAN.

0.43

A Capability-Aware Backup-Recoverability Filter for Heterogeneous Multi-Robot Navigation

cs.RO ·2026-10-30 ·Joonkyung Kim, Yanze Zhang, Wenhao Luo, Yiwei Lyu
similarity 0.61
Abstract · 8 pages, 3 figures

Safe navigation in heterogeneous multi-robot teams faces two coupled challenges: differences in robots' braking and turning capabilities limit how each robot can respond to an approaching neighbor, while simultaneous interactions require a single control action to satisfy multiple collision-avoidance constraints. Together, these challenges can make local safety constraints incompatible with a robot's admissible controls, leaving a decentralized safety controller without a feasible action. We propose a Capability-Aware Backup-Recoverability Filter (CA-BRF), based on the insight that navigation actions should preserve access to a certified recovery maneuver. First, we construct a backup-recoverable set in a shared Cartesian operational space by evaluating whether prescribed backup maneuvers maintain pairwise safety until the robots come to rest. Each maneuver respects the corresponding robot's kinematic and actuation constraints, making the recovery certificate capability-dependent. Second, CA-BRF filters candidate controls by selecting admissible interpolations between candidate and backup actions while coordinating the selection across simultaneous interactions. This preserves backup recoverability while retaining as much of the candidate action as possible and ensures that all pairwise recovery conditions are satisfied by a single executable control for each robot. Together, we establish recursive feasibility and safety for the discrete-time closed-loop system even when the nominal safety-constrained optimization becomes infeasible. The validity and effectiveness of the proposed CA-BRF are validated in simulations with up to 30 heterogeneous robots and experiments of robots with five different kinematic classes.

0.32

A Reachability-based Safety Certificate for Dynamical System Motion Policies

cs.RO ·2026-09-29 ·Aditya Vats, Tianyi Xia, Nadia Figueroa
similarity 0.61
Abstract

Dynamical Systems (DS) are reactive motion policies representing vector fields trained with theoretical guarantees of stability and convergence. To ensure safety during deployment in unknown environments they must be locally reshaped, either through modulation or geometric control barrier function strategies. However, depending on the geometry of the obstacles and the complexity of the DS, these local strategies can lead the system to unavoidable collisions or spurious attractors. In this work, we certify safety with a value function drawn from the notion of backward reachability tube, which measures the worst-case safety along a rollout trajectory of the nominal DS. Usually, such a value function is intractable for a controlled system due to curse of dimensionality. We show that in the DS-based learning-from-demonstration setting, the absence of a control input collapses the reachability problem to a deterministic rollout, and the presence of certain stability conditions truncates the infinite horizon to a finite one, resulting in a well-defined value function. We further show that the value function we devised is the maximal forward-invariant subset of the obstaclefree region for the nominal DS flow. The application of this certificate function is validated across five DS constructions - analytical, Neural ODE, diffeomorphic latent space, LPV-DS, SE(3)and validate it on a Franka manipulator. Modulation and geometric CBFs also suffer from saddle point in cases of headon approach towards an unsafe zone. We show that CBF-on-V avoids this pitfall entirely.

0.21

Reach-Avoid Certificates for Contact-based Stochastic Hybrid Systems

eess.SY cs.ROmath.PR ·2026-10-12 ·Tianyi Xia, Ryan K. Cosner
theory similarity 0.61
Abstract

This work studies certified reach-avoid control of stochastic hybrid systems in which a stochastic differential equation governs continuous flow and a controlled stochastic kernel governs guard-triggered resets. The input appears only in the reset kernel, where it determines the post-jump distribution. Certificates for such systems have so far assumed spontaneous or controller-chosen jump times, a finite horizon, or discrete-time dynamics; we certify, over the infinite horizon, that the target is reached before the unsafe set with at least a prescribed probability. First, we introduce reach-avoid contact certificates, whose flow and jump conditions are imposed only on a sublevel corridor, and prove that any such certificate with a compatible reset policy meets the specification; a pointwise safety filter extends this guarantee from verification to control by constraining arbitrary nominal controllers. Next, we prove that executions are non-Zeno and bound the expected settling time and reset count. We frame certificate search as a linear program over any twice-differentiable dictionary followed by independent verification. We illustrate our approach via comparisons where the certified region is a subset covering 93.6\% of the ground truth and where our certificate-based safety filter reaches the goal while reducing collisions from 68 to zero across 200 episodes of a dribbling ball problem.

0.26