One-sentence Summary

The authors introduce an exact feasibility certificate for multi-robot CBF safety filters that separates safety demand from actuator supply to quantify a feasibility reserve, along with an optimal allocation algorithm that maximizes the worst local feasibility margin, reducing infeasible control steps from roughly 50% to 6.2% and safety-violating runs from 118/160 to 24/160, while the certificate identifies an interaction whose relaxation restores feasibility in 94% of infeasibility events.

Key Contributions

• An exact conic feasibility certificate for multi-robot CBF filters is derived that decomposes pointwise feasibility into a constraint demand term and an actuator supply term, applicable to heterogeneous control-affine dynamics and convex input sets.
• The certificate characterizes when CBF gain tuning or increased actuation can resolve infeasibility, identifies the specific agents and interactions responsible for a conflict via dual variables, and quantifies the marginal value of additional actuation.
• A certificate-based responsibility allocation is proposed that maximizes the worst local feasibility margin; for polyhedral input sets it reduces to a linear program, and in closed-loop simulations it cuts infeasible control steps from roughly 50% to 6.2% and safety-violating runs from 118/160 to 24/160.

Introduction

Control barrier function (CBF) safety filters offer a principled way to enforce safety without discarding a nominal controller, but in multi-robot systems several pairwise or higher-order constraints often need to hold at once. Even if each constraint is feasible individually, their conjunction can be infeasible, and a standard quadratic program returns only a binary infeasibility flag with no diagnosis of which interaction caused the conflict or how to resolve it. Prior work includes feasibility-guaranteeing constructions, compatibility conditions, nonsmooth barrier compositions, actuation-aware formulations, and online adaptation; the closest methods give feasibility tests for stacked constant-norm linear time-invariant barrier constraints or opposing higher-order CBF bounds for one underactuated system, but they do not quantify the gap between constraint demand and actuator supply or cover state-dependent normals, arbitrary convex input sets, and multi-agent settings. The authors derive an exact conic certificate that characterizes pointwise feasibility and separates constraint demand from actuator supply, enabling diagnosis of whether infeasibility should be addressed by CBF encoding, added actuation, or redistribution of constraint responsibility; the certificate also yields decentralized responsibility allocation that maximizes the worst local feasibility margin, reducing to a linear program for polyhedral input sets.

Method

The authors develop a certificate-based safety filtering framework for decentralized multi-agent systems with high-order control barrier function constraints. The method separates global feasibility certification from local responsibility allocation, allowing each agent to act locally while guaranteeing that the collection of local actions satisfies all coupled HOCBF constraints.

For a system of $N$N agents with heterogeneous control-affine dynamics

$$\dot{x}_i=f_i(x_i)+g_i(x_i)u_i,\qquad u_i\in\mathcal U_i,$$x˙i​=fi​(xi​)+gi​(xi​)ui​,ui​∈Ui​,

each safety constraint $k$k is represented by a barrier function $h_k$hk​ whose support $S_k$Sk​ contains the agents that affect it. For constraints with uniform relative degree $r_k$rk​, the authors construct a HOCBF chain

$$\psi_{k,0}=h_k,\qquad \psi_{k,j}=\dot\psi_{k,j-1}+\alpha_{k,j},\quad j=1,\dots,r_k,$$ψk,0​=hk​,ψk,j​=ψ˙​k,j−1​+αk,j​,j=1,…,rk​,

where $\alpha_{k,j}$αk,j​ are class-$\mathcal K$K functions. Under the relative degree assumption, the final stage of the chain is affine in the control inputs. Stacking all constraints gives the coupled affine condition

$$G(x)u\ge -b(x).$$G(x)u≥−b(x).

For each constraint $k$k and agent $i\in S_k$i∈Sk​, the coefficient direction is

$$G_{k,i}=L_{g_i}\psi_{k,r_k-1},\qquad b_k=L_f\psi_{k,r_k-1}+\alpha_{k,r_k}.$$Gk,i​=Lgi​​ψk,rk​−1​,bk​=Lf​ψk,rk​−1​+αk,rk​​.

The instantaneous feasible set is therefore

$$\mathcal F=\{x:\exists u\in\mathcal U,\ G(x)u\ge -b(x)\}.$$F={x:∃u∈U, G(x)u≥−b(x)}.

A central component of the method is an exact scalar feasibility certificate. Let $\nu_{k,i}=G_{k,i}^\top$νk,i​=Gk,i⊤​ denote the input-space direction associated with constraint $k$k for agent $i$i. For a nonnegative weighting $\lambda\in\Delta$λ∈Δ, where $\Delta$Δ is the probability simplex over the constraints, define the combined direction for agent $i$i as

$$\nu_i(\lambda)=\sum_{k:i\in S_k}\lambda_k\nu_{k,i}.$$νi​(λ)=k:i∈Sk​∑​λk​νk,i​.

The maximum input contribution available along this direction is the support function

$$\sigma_{\mathcal U_i}(\nu)=\max_{u_i\in\mathcal U_i}\langle \nu,u_i\rangle.$$σUi​​(ν)=ui​∈Ui​max​⟨ν,ui​⟩.

The feasibility reserve is defined as

$$M(x)=\min_{\lambda\in\Delta} \left[ \lambda^\top b(x)+\sum_{i=1}^{N}\sigma_{\mathcal U_i}\bigl(\nu_i(\lambda)\bigr) \right].$$M(x)=λ∈Δmin​[λ⊤b(x)+i=1∑N​σUi​​(νi​(λ))].

The authors prove that this minimization is a convex program with an attained minimum and that the safety filter is feasible at $x$x if and only if

$$M(x)\ge 0.$$M(x)≥0.

The certificate decomposes into a demand term $\lambda^\top b$λ⊤b, imposed by the barrier conditions, and a supply term $\sum_i\sigma_{\mathcal U_i}(\nu_i(\lambda))$∑i​σUi​​(νi​(λ)), representing the available actuation capability. Feasibility holds when supply meets demand for every weighting of the constraints.

When the input sets can be expressed as

$$\mathcal U_i=o_i+\mathcal W_i,$$Ui​=oi​+Wi​,

with $\mathcal W_i$Wi​ symmetric, convex, and compact, the support function decomposes into an offset term and a centered supply term. The reserve becomes

$$M(x)=\min_{\lambda\in\Delta} \left[ \lambda^\top b'(x)+S(x,\lambda) \right],$$M(x)=λ∈Δmin​[λ⊤b′(x)+S(x,λ)],

where

$$b'_k=b_k+\sum_{i\in S_k}\langle \nu_{k,i},o_i\rangle$$bk′​=bk​+i∈Sk​∑​⟨νk,i​,oi​⟩

absorbs asymmetric input offsets into the effective demand, and

$$S(x,\lambda)=\sum_{i}\sigma_{\mathcal W_i}(\nu_i(\lambda))$$S(x,λ)=i∑​σWi​​(νi​(λ))

is the symmetric actuation supply. This separation is used throughout the framework. The authors also show that, apart from a penultimate exception not used by the allocation algorithm, the coefficient direction $G_{k,i}$Gk,i​ reduces to $L_{g_i}L_f^{r_k-1}h_k$Lgi​​Lfrk​−1​hk​ and does not depend on the class-$\mathcal K$K tuning parameters. Thus tuning changes the demand but not the available input supply.

The certificate also supports diagnosis of infeasibility. Define the minimum supply as

$$S^\star(x)=\min_{\lambda\in\Delta}S(x,\lambda).$$S⋆(x)=λ∈Δmin​S(x,λ).

The authors show that $S^\star(x)=0$S⋆(x)=0 exactly when there exists a weighting $\lambda^\star\in\Delta$λ⋆∈Δ such that

$$\nu_i(\lambda^\star)\perp \operatorname{span}\mathcal W_i$$νi​(λ⋆)⊥spanWi​

for every agent $i$i. If every $\mathcal W_i$Wi​ is full-dimensional, this reduces to

$$A\lambda^\star=0,$$Aλ⋆=0,

where $A\lambda=(\nu_i(\lambda))_i$Aλ=(νi​(λ))i​. Equivalently, the origin lies in the convex hull of the constraint directions. Under this degeneracy condition, scaling all input sets by any positive factor cannot increase the supply. If the corresponding demand is negative, no scaling of the actuators can render the state feasible. The method therefore distinguishes infeasibility caused by actuator geometry from infeasibility caused by conflicting or excessive barrier demand.

The certificate additionally yields a marginal sensitivity result. When the minimizer $\lambda^\star$λ⋆ is unique,

$$\frac{\partial M}{\partial\rho_i}(x;\rho) = \sigma_{\mathcal W_i}\bigl(\nu_i(\lambda^\star)\bigr)\ge 0.$$∂ρi​∂M​(x;ρ)=σWi​​(νi​(λ⋆))≥0.

A zero marginal value indicates that increasing the actuation authority of agent $i$i cannot improve feasibility. The authors also give a sparsity result: there exists a minimizer $\lambda^\star$λ⋆ whose support size is at most

$$\operatorname{rank}[A;\mathbf 1^\top] \le \sum_i m_i+1.$$rank[A;1⊤]≤i∑​mi​+1.

Thus an irreducible conflict involves at most one more constraint than the total actuated degrees of freedom, making the bound dimensional rather than combinatorial.

For decentralized execution, the authors introduce responsibility weights $\theta_{k,i}\ge 0$θk,i​≥0 satisfying

$$\sum_{i\in S_k}\theta_{k,i}=1.$$i∈Sk​∑​θk,i​=1.

Each shared constraint is divided among the agents that affect it. If agent $i$i satisfies its assigned local share

$$\theta_{k,i}b_k(x)+G_{k,i}(x)u_i\ge 0,\qquad k\in E_i,$$θk,i​bk​(x)+Gk,i​(x)ui​≥0,k∈Ei​,

then summing over $i\in S_k$i∈Sk​ recovers the original HOCBF condition. Therefore, the choice of $\theta$θ affects local feasibility but does not compromise safety.

For a fixed allocation, the local feasibility margin of agent $i$i is

$$m_i^{\mathrm{loc}}(x;\theta) = \max_{u_i\in\mathcal U_i} \min_{k\in E_i} \left( \theta_{k,i}b_k(x)+G_{k,i}(x)u_i \right).$$miloc​(x;θ)=ui​∈Ui​max​k∈Ei​min​(θk,i​bk​(x)+Gk,i​(x)ui​).

This is exactly the worst-case slack that agent $i$i can achieve with its own input set. If $m_i^{\mathrm{loc}}(x;\theta)\ge 0$miloc​(x;θ)≥0 for every agent, then the global feasibility reserve satisfies $M(x)\ge 0$M(x)≥0.

The authors cast the selection of $\theta$θ as an optimization problem that maximizes the worst local margin. For polytopic input sets, this becomes the linear program

$$\max_{t,\theta,u}\ t$$t,θ,umax​ t

subject to

$$t\le \theta_{k,i}b_k+G_{k,i}u_i,\quad k\in E,\ i\in S_k,$$t≤θk,i​bk​+Gk,i​ui​,k∈E, i∈Sk​, $$\sum_{i\in S_k}\theta_{k,i}=1,\quad \theta\ge 0,\quad u_i\in\mathcal U_i.$$i∈Sk​∑​θk,i​=1,θ≥0,ui​∈Ui​.

If the optimal value satisfies $t^\star\ge 0$t⋆≥0, the resulting allocation makes all local programs feasible and certifies global feasibility. If $t^\star<0$t⋆<0, no admissible allocation can make all local programs feasible. The gap between $M(x)\ge 0$M(x)≥0 and $t^\star<0$t⋆<0 characterizes the feasibility loss introduced by decentralization.

The resulting control step solves the above allocation program on the joint state and broadcasts only the scalar responsibility weights $\theta^\star$θ⋆ to the agents. Each agent then solves a small local program over its own input set and incident constraints. The program also returns a candidate input $u^\star$u⋆. When $t^\star\ge 0$t⋆≥0, $u^\star$u⋆ is discarded because it only certifies feasibility, and each agent instead selects the input closest to its nominal control that satisfies its assigned share. When $t^\star<0$t⋆<0, $u^\star$u⋆ is used as the least infeasible action, keeping the worst local margin as high as possible. For non-polytopic input sets, the same construction yields a convex program instead of a linear program.

Experiment

The evaluation uses closed-loop simulations of underactuated planar vehicles with random start and goal positions that create dense conflicts, testing both conflict localization and responsibility allocation. The dual multiplier correctly identifies the single interaction causing infeasibility in 94% of cases, and the proposed allocation redistributes responsibility to resolve local program infeasibility, reducing infeasible control steps from roughly 50% for uniform and capability-weighted heuristics to about 6%, nearly matching a centralized filter. Closed-loop results show that this certificate-optimal allocation substantially improves safety, with fewer constraint violations and a positive mean closest approach, while capability weighting provides negligible benefit over uniform allocation.

The certificate-optimal allocation achieves infeasible-step rates near 6%, closely matching the centralized reference, while uniform and capability-weighted heuristics cause infeasibility in roughly half of all control steps. The heuristics’ failure rate grows steeply with the number of agents, whereas the proposed method remains consistently low. Capability weighting provides almost no benefit over uniform allocation. The certificate-optimal allocation yields infeasible-step rates around 6%, nearly identical to the centralized reference, compared to roughly 50% for the heuristics. Under uniform and capability-weighted allocations, infeasibility increases from ~27% at N=6 to ~69% at N=12, and capability weighting offers negligible improvement over uniform allocation.

The certificate-optimal allocation achieves infeasible-step rates around 6%, nearly matching the centralized reference, while uniform and capability-weighted heuristics cause infeasibility in roughly half of all control steps. The heuristics' failure rate rises sharply with the number of agents, whereas the proposed method remains consistently low, and capability weighting provides almost no benefit over uniform allocation.