CS Paper Radar

Exact Feasibility Certification and Optimal Responsibility Allocation for Multi-Robot CBF Safety Filters

Chandan Kumar Sah, Jishnu Keshavan

cs.RO cs.MA ·submitted 2026-09-14 02:29 UTC · v1
hot direction

Abstract

Multi-robot Control Barrier Function (CBF) safety filters can become infeasible, but a failed quadratic program (QP) does not indicate why the conflict occurred or how to resolve it. To address this, we develop an exact feasibility certificate for multi-agent CBF filters with heterogeneous control-affine dynamics and convex input sets. The certificate quantifies a feasibility reserve by separating the demand imposed by safety constraints from the available actuator supply. This decomposition shows when CBF gain tuning or increased actuation can and cannot resolve infeasibility, and identifies the agents and interactions responsible for the conflict. We further propose an algorithm to optimally allocate shared safety constraints by maximizing the worst local feasibility margin, yielding a linear program for polyhedral input sets. In $320$ paired closed-loop simulations, the proposed allocation reduces infeasible control steps from roughly $50\%$ to $6.2\%$, and reduces safety-violating runs from $118/160$ to $24/160$. In addition, across $52$ infeasibility events, the certificate identifies an interaction whose relaxation restores feasibility in $94\%$ of cases.

Closest papers

Nearest neighbours by meaning across the whole index.

Finite-Step Algorithms for Input-Constrained Control Barrier Function-Based Safety Filters

eess.SY math.OC ·2026-11-16 ·Johannes Autenrieb, Mark Spiller, Mayank S. Jha
similarity 0.70
Abstract · 8 pages, 3 figures

Control barrier function (CBF) safety filters commonly rely on quadratic programs (QPs) to modify nominal control inputs while satisfying safety constraints. For safety-critical applications, however, the solution must be computed reliably under actuator limitations and with predictable computational effort. General-purpose QP solvers typically rely on numerical convergence criteria, which do not directly provide finite bounds on algorithmic steps or distinguish solver failure from mathematical infeasibility. This paper considers CBF-QPs with a single affine safety constraint, componentwise input bounds, and diagonal quadratic weights. Exploiting the established scalar dual structure of continuous quadratic knapsack problems, we obtain a necessary and sufficient pointwise feasibility condition and an exact breakpoint-based solution procedure. The algorithm requires at most 2n positive breakpoint events for n inputs, reducing to at most n events when the nominal input is admissible. In the latter case, an exact saturation--redistribution algorithm computes the optimal solution in at most n passes. We further describe how the structured solution can be combined with verified floating-point constraint evaluation to distinguish certified feasible commands, certified infeasibility, and unresolved numerical cases. The resulting framework provides an exact and computationally predictable solution procedure for a practically relevant class of input-constrained CBF safety filters.

0.35

A Coupled Control Barrier Function Approach to Deadlock-Free Multi-Robot Conflict Resolution

cs.RO eess.SY ·2026-11-12 ·Gary Rostomyan, Ketan Savla, Petros A. Ioannou
similarity 0.70
Abstract

Many robotic applications involve scenarios where multiple robots interact and the decisions of one robot influence the behavior of others. This paper presents a quadratic programming (QP)-based feedback controller for multi-robot conflict resolution with input constraints. Safety is enforced using coupled Control Barrier Function (CBF), while a yielding matrix encodes how robots influence each other. Unlike existing methods with fixed or hard priorities, the proposed framework enables yielding preferences while guaranteeing deadlock-free operation by design. Sufficient conditions are established for the controller to be locally Lipschitz. The optimal CBF sign- indefinite slack is shown to admit a finite uniform bound, which is compensated through an enlarged CBF safety margin to obtain a forward invariant set contained within the desired safe set. The analysis also identifies an irreducible slack component due to finite maximum deceleration that cannot be eliminated by increasing the slack penalty. Finally, sufficient conditions on the yielding matrix and nominal controller are derived to exclude deadlock states. Simulations demonstrate adaptive coordination across yielding preferences and robustness to robot failures.

0.19

Jacobian State Augmented Viable Kinematic Safety Filter

cs.RO eess.SY ·2026-10-11 ·Siddharth Singh, Joshua Vaughan
similarity 0.70
Abstract · 8 pages, 8 figures, conference submission

Safety Filters (SF) are leveraged to design certifiably safe controllers, which ensures forward invariance on a defined safe set when the filter is feasible. Predictive Safety Filters (PSF) embed these constraints to a closed-loop model-based optimization method to improve constraint satisfaction, and reduce feasibility loss caused by myopic, one-step filtering. Related viability-based methods emphasize approximating a viability kernel which ensures admissible control for all future time, but requires significant computational expense. This work introduces a Jacobian-based kinematic safety filter leveraging an augmented state variable with task-space velocity and filters task-space acceleration to preserve the feasibility of a low-level filter while enforcing joint position and velocity. The proposed method introduces a nested Quadratic Program (QP) formulation, defines a conservative inner approximation of viability envelope and computes a viable planner online. The method is validated in a simplified 2R planar manipulator simulation environment and shows significant improvement compared to a baseline Control Barrier Function Quadratic Program (CBF-QP) based filter. The experiments highlights the improvements in terms of computation time compared to traditional PSF and Reference Governor approach while also showing significant reduction in feasibility violations. Lastly, a simplified demonstration on a simulated 6-DoF manipulator highlights the potential scalability of the method to higher degree-of-freedom setups.

0.13

FAITH: Feasibility-Aware Safety-Filtered RL for High-Dimensional Systems

cs.RO cs.LGeess.SY ·2026-10-08 ·Songyuan Zhang, Baljeet Singh, Sarthak Ranjeet Kaingade, Chuchu Fan, Bryan Trinh
similarity 0.69
Abstract · 8 pages, 7 figures

Safe reinforcement learning commonly places safety and task performance in the same policy objective, where they can introduce competing updates. Safety filters separate them at action execution, but classical designs require an analytic safety function and dynamics model, and standard minimal-intervention filters are myopic to long-horizon task return because they minimize only instantaneous action deviation. Hard projections are also undefined when no safe action exists. We present FAITH, a feasibility-aware, model-free framework that approximates the optimal state-action safety value and amortizes minimal-intervention filtering with a feedforward network. The task policy optimizes the task return through the filtered dynamics, which recovers the feasible constrained problem without a competing safety term in the task-policy update. When no action satisfies the learned safety condition, the same filter approaches the action with minimum predicted peak harm. On a double integrator example and a Safety Gym environment, FAITH achieves the highest return among methods with no feasible-start violations and matches the lowest harm from infeasible starts. On a 29-DoF humanoid, it reaches a 99.95% safety rate while retaining 97% of the unfiltered return in Walking-Avoid, and obtains the highest measured safety rate in Push-Avoid by learning to sacrifice balancing and fall away from the protected region. The same policies are also demonstrated on a real-world Unitree G1 humanoid.

0.13

Exact-Safe MPPI: Safety-Aware Sampling with Nonsmooth Control Barrier Functions

eess.SY ·2026-10-05 ·Alexander Coker, Leilei Cui
code/data similarity 0.69
Abstract · 8 pages, 5 figures, 1 table. Submitted to the 2027 American Control Conference (ACC)

Model predictive path integral (MPPI) control plans actions by sampling and evaluating trajectories, but standard MPPI does not guarantee safety. Incorporating control barrier function (CBF) filters into each rollout allows the planner to account for safety corrections. However, combining multiple CBFs through a soft-minimum approximation can exclude states that satisfy the original safety constraints, restricting the trajectories available to the planner. This paper proposes Exact-Safe MPPI, which uses the exact minimum of multiple barrier functions and applies a CBF-based quadratic program during both planning and control execution. To handle nondifferentiability where multiple barriers attain the minimum, the filter simultaneously enforces the CBF conditions for all $δ$-active barriers, whose values lie within a prescribed tolerance $δ>0$ of the minimum. Under suitable feasibility and regularity assumptions, we establish forward invariance of the certified safe set without the shrinkage introduced by soft-minimum smoothing. We also characterize the state-dependent approximation gap and explain how multiple barriers with values at or near the minimum increase this shrinkage. Furthermore, we show that increasing the number of MPPI samples cannot recover trajectories excluded by the soft-minimum filter. We demonstrate the effectiveness of the proposed approach in a navigation task requiring passage through a narrow gap between two obstacles. Video demonstrations are available at https://github.com/lc-lab25/Exact-Safe-MPPI .

0.41

BubbleCBF: Constructive Safety for Second-Order Systems and Application to Autonomous Robot Navigation in Unknown Environments

cs.RO ·2026-10-14 ·Mani Amani, Mohammed Alyaseen, Zhirui Dai, Ki Myung Brian Lee, Nikolay Atanasov +1 more
theory similarity 0.69
Abstract

Satisfying safety constraints for systems with second-order dynamics is challenging because a position constraint may require infeasible deceleration. Higher-order control barrier functions (CBFs) provide an approach for expressing safety conditions for such systems but feasibility depends on the system dynamics and available control authority. We develop a constructive approach for designing feasible safety constraints for second-order control-affine systems. Starting from a signed distance function (SDF), we construct collision-free spheres, i.e., bubbles, in position space, and use their quadratic geometry and overlap to construct a velocity-dependent safety constraint. The associated safe set is represented as a union of intersections and enforced through a quadratic-program safety filter. Under mild assumptions on the dynamics, bubble overlap, and design parameters, we prove that the quadratic-program-based controller is well defined, continuous in the system state, and renders the set forward invariant. We also derive sufficient conditions for feasibility under bounded inputs. We demonstrate that our BubbleCBF, applied to a differential-drive robot, achieves safe autonomous navigation in unknown environments. Videos and results are available at: https://existentialrobotics.org/bubblecbf/.

0.17

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.68
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

Ontology-Compiled Control Barrier Functions for Heterogeneous Robot Teams

cs.RO cs.LG ·2026-11-15 ·Peng Wu, Seyede Fatemeh Ghoreishi, Nathan Bastian, Mohsen Imani, Tian Lan +1 more
theory similarity 0.68
Abstract

Safety filters for heterogeneous robot teams fail because of missing constraints, overestimated braking capabilities and conflicts between individually satisfiable constraints. We present OntoCBF, which compiles a domain ontology with a class taxonomy, typed relations, safety axioms and a dynamics profile per robot class into a control barrier function filter with one quadratic program per agent. Description-logic entailment supplies the constraints of any team online, including those that follow from chains of relations and from classes defined by what a robot carries, so the existing safety axioms cover new robot classes, payload classes and combinations. We prove that a subclass may reuse the braking capability of its parent whenever it can produce every velocity of the parent, a property separate from subsumption. For box-bounded double integrators this property is also necessary, and every loss of safety then begins with a conflict. Once three robots interact, the safe set of pairwise barriers contains states from which a collision is unavoidable, and such states persist in larger teams under any fixed capability reduction. In a simulated warehouse where humans ignore the robots, a filter written for the design classes violates safety in 89-100 % of the episodes with unseen classes. In all scenarios, including one with 32 robots, OntoCBF violates safety in 20-70 % of the episodes, each time after a conflict, with a median deepest intrusion of 10-17 % of the keep-out distance. A multi-agent PPO policy trained with the filter in the loop lowers the rate of infeasible quadratic programs, nearly all of them conflicts, by 18-41 %.

0.22