Paper deep dive
SC3BF: Shifted Collision Cone Control Barrier Function for Dynamic Obstacle Avoidance
Amin Kashiri, Yasin Yazıcıoğlu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 10/7/2026, 7:47:19 AM
Summary
The paper introduces SC3BF (Shifted Collision Cone Control Barrier Function), a novel safety filter for dynamic obstacle avoidance in kinematic bicycle models. SC3BF modifies the conservative collision cone of existing velocity-space CBFs by adding a state-dependent allowance that permits slower approach rates based on distance and speed. The method is enforced via a standard quadratic program, ensuring forward invariance of the safe set without requiring minimum speed or clearance margin assumptions. Simulations demonstrate that SC3BF outperforms baselines (C3BF, DPCBF, VOCBF) in goal-reaching success rates and input modification efficiency across scenarios with up to 100 moving obstacles.
Entities (8)
Relation Signals (9)
SC3BF → appliesto → Kinematic Bicycle Model
confidence 95% · We introduce a velocity-space barrier for the kinematic bicycle, the shifted collision-cone CBF (SC3BF)
SC3BF → isa → Control Barrier Function
confidence 95% · We propose the shifted collision-cone CBF (SC3BF)...
SC3BF → uses → Quadratic Program
confidence 95% · SC3BF is enforced by an ordinary quadratic program
SC3BF → improvesupon → VOCBF
confidence 90% · SC3BF reaches the goal more often and modifies the nominal input less than half as much as any of them.
SC3BF → improvesupon → DPCBF
confidence 90% · SC3BF reaches the goal more often and modifies the nominal input less than half as much as any of them.
SC3BF → improvesupon → C3BF
confidence 90% · SC3BF... adds a state-dependent allowance to the cone condition... Against three velocity-space baselines... SC3BF reaches the goal more often
C3BF → isconsidered → Conservative
confidence 90% · The collision cone used by velocity-space control barrier functions is conservative: it rejects every relative velocity aimed into an obstacle, however slow.
VOCBF → usesformulation → Mixed-Integer Program
confidence 90% · Its mixed-integer formulation scales poorly in the number of obstacles.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The collision cone used by velocity-space control barrier functions is conservative: it rejects every relative velocity aimed into an obstacle, however slow. We propose the \emph{shifted collision-cone CBF} (SC3BF), which adds a state-dependent \emph{allowance} to the cone condition, so the robot may approach the obstacle at a rate that grows with distance and with its own speed. SC3BF is enforced by an ordinary quadratic program, and its safe set is forward invariant under bounded inputs without a minimum forward speed or a clearance margin. We prove that a nonzero allowance preserving safety always exists, and derive one in closed form. Against three velocity-space baselines on a kinematic bicycle among up to $100$ moving obstacles, SC3BF reaches the goal more often and modifies the nominal input less than half as much.
Tags
Links
- Source: https://arxiv.org/abs/2610.08332v1
- Canonical: https://arxiv.org/abs/2610.08332v1
Trouble viewing inline? Open PDF directly →
Full Text
56,227 characters extracted from source content.
Expand or collapse full text
SC3BF: Shifted Collision Cone Control Barrier Function for Dynamic Obstacle Avoidance Amin Kashiri Yasin Yazıcıoğlu †thanks: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.†thanks: A. Kashiri is with the Department of Electrical and Computer Engineering at Northeastern University, Boston, MA (kashiri.a@northeastern.edu).†thanks: Y. Yazıcıoğlu is with the Departments of Mechanical and Industrial Engineering and Electrical and Computer Engineering at Northeastern University, Boston, MA (y.yazicioglu@northeastern.edu). Abstract The collision cone used by velocity-space control barrier functions is conservative: it rejects every relative velocity aimed into an obstacle, however slow. We propose the shifted collision-cone CBF (SC3BF), which adds a state-dependent allowance to the cone condition, so the robot may approach the obstacle at a rate that grows with distance and with its own speed. SC3BF is enforced by an ordinary quadratic program, and its safe set is forward invariant under bounded inputs without a minimum forward speed or a clearance margin. We prove that a nonzero allowance preserving safety always exists, and derive one in closed form. Against three velocity-space baselines on a kinematic bicycle among up to 100100 moving obstacles, SC3BF reaches the goal more often and modifies the nominal input less than half as much. I Introduction A vehicle navigating among moving obstacles must avoid collisions while progressing toward its goal, subject to kinematic constraints and input limits. A common approach combines a nominal controller with a safety filter that modifies its input as little as possible. Control Barrier Functions (CBFs) [1] represent the safe set as the region where a scalar function of the state is nonnegative, and constrain how fast that function can decrease. For dynamics that are affine in the input, this is a linear inequality on the input, which can be enforced with a small quadratic program (QP). The QP is cheap to solve, but finding a suitable barrier function is difficult. For an acceleration-controlled vehicle, the distance derivative does not contain acceleration, so a distance-based barrier cannot impose braking. Braking-distance barriers [2] bring the acceleration into the inequality, but certify only the brake maneuver, and therefore reject states from which the vehicle could in fact pass safely using steering. High-order CBFs [3] instead differentiate the distance a second time, so that the acceleration appears, but certify a subset of the original safe set and introduce auxiliary class-K functions that are difficult to tune. A second line of work builds the barrier in the space of relative velocities, where the input appears after one differentiation of the barrier function. Following the classical velocity obstacle [4], the Collision-Cone CBF (C3BF) [5] keeps the relative velocity outside the cone of velocities aimed into the obstacle. The result is a valid barrier for the unicycle and the bicycle dynamics, and [6] applies the velocity-obstacle principle with CBFs to unicycle-type vehicles that must keep a positive forward speed. The cone is conservative, however, since it rejects every velocity aimed into the obstacle, however slow. The Dynamic Parabolic CBF (DPCBF) [7] reduces that conservatism by replacing the cone with a parabolic region whose boundary depends on the relative velocity, so a slow approach is allowed where a fast one is not. However, as Sec. I sets out, the parabolic region rests on minimum-speed and clearance assumptions that their controller does not enforce, and neither construction covers the singularity of the barrier at contact. The safe set need not be described by a single barrier function. Boolean compositions of several barriers are treated in [8], combinatorial compositions in [9], and the feasibility of compositions under input constraints in [10]. The velocity-obstacle-based CBF (VOCBF) [11] has this structure. It writes the outside of the cone as the union of the two half-spaces its edges define, and enforces a disjunction of the two edge-wise barrier inequalities, with binary variables selecting which holds. Its mixed-integer formulation scales poorly in the number of obstacles. We introduce a velocity-space barrier for the kinematic bicycle, the shifted collision-cone CBF (SC3BF), which adds a state-dependent allowance to the cone condition, so the robot may approach the obstacle at a rate that grows with distance and with its own speed. The resulting filter needs neither a minimum forward speed nor a clearance margin. Our contributions are as follows: 1. We construct the barrier and the quadratic program that enforces it, and prove that the safe set is forward invariant under bounded inputs, including at contact. 2. We prove, for the kinematic bicycle, that for every choice of the bicycle’s and the obstacle’s parameters some nonzero allowance preserves safety, and derive one in closed form. We also introduce a certification procedure that yields substantially larger allowances for a given system. 3. We compare SC3BF to C3BF, DPCBF and VOCBF in simulation, among up to 100100 moving obstacles. SC3BF reaches the goal more often at every obstacle count and modifies the nominal input less than half as much as any of them. I Background I-A Control Barrier Functions and the CBF-QP Consider x˙=f(x)+g(x)u,x∈⊆ℝn,u∈⊆ℝm, x=f(x)+g(x)u, x ^n, u ^m, (1) where f and g are locally Lipschitz and U is the (possibly bounded) admissible input set. A safe set is the zero-superlevel set =x∈:h(x)≥0C=\x :h(x)≥ 0\ of a continuously differentiable function h:→ℝh:X . The function h is a Control Barrier Function (CBF) on C if there exists an extended class-∞K_∞ function α such that supu∈[Lfh(x)+Lgh(x)u+α(h(x))]≥0∀x∈, _u [L_fh(x)+L_gh(x)u+α(h(x)) ]≥ 0 ∀ x , (2) where LfhL_fh and LghL_gh are the Lie derivatives of h along f and g. Under this CBF condition, any locally Lipschitz controller u(x)u(x) satisfying the barrier condition Lfh(x)+Lgh(x)u(x)≥−α(h(x))L_fh(x)+L_gh(x)u(x)≥-α(h(x)) (3) keeps the system inside C [1]. Since (3) is affine in u, the CBF can be used as a safety filter on a nominal controller unom(x)u_nom(x). The filtered control is obtained by solving the quadratic program u∗=argminu∈ u^*= _u ‖u−unom(x)‖2 \|u-u_nom(x)\|^2 (4) s.t. .t. Lfh(x)+Lgh(x)u≥−α(h(x)). L_fh(x)+L_gh(x)u≥-α(h(x)). When the safe set is an intersection of several such sets, an inequality of the form (3) is added for each. I-B Bicycle Dynamics, Obstacle Model, and Line-of-Sight Frame We consider the kinematic bicycle model [12]. Its state is =(x,y,θ,v)⊤ x=(x,y,θ,v) , where =(x,y)⊤ p=(x,y) is the position of the center of mass, θ the heading and v the forward speed, and its inputs are the acceleration a and the front-wheel steering angle δ. With ℓf _f and ℓr _r the distances from the center of mass to the front and rear axles, the steering angle determines the slip angle β=tan−1(ℓrtanδ/(ℓf+ℓr))β= ^-1 ( _r δ/( _f+ _r) ), the angle between the velocity of the center of mass and the heading, and the model is x˙=vcos(θ+β) x=v (θ+β), y˙=vsin(θ+β) y=v (θ+β), θ˙=(v/ℓr)sinβ θ=(v/ _r) β and v˙=a v=a. As in [5, 7], we assume that β is small, so that cosβ≈1 β≈ 1 and sinβ≈β β≈β, and take =(a,β)⊤ u=(a,β) as the input. This gives the control-affine model [x˙y˙θ˙v˙]⏟˙=[vcosθvsinθ00]⏟f()+[0−vsinθ0vcosθ0v/ℓr10]⏟g()[aβ]⏟. bmatrix x\\ y\\ θ\\ v bmatrix_ x= bmatrixv θ\\ v θ\\ 0\\ 0 bmatrix_f( x)+ bmatrix0&-v θ\\ 0&v θ\\ 0&v/ _r\\ 1&0 bmatrix_g( x) bmatrixa\\ β bmatrix_ u. (5) The input β turns the heading and also moves the center of mass sideways: with =(vcosθ,vsinθ)⊤ v=(v θ,v θ) the velocity along the heading, the first two rows of (5) give ˙=+vβ(−sinθ,cosθ)⊤ p= v+vβ(- θ, θ) . The admissible input set is =(a,β)⊤:|a|≤amax,|β|≤βmaxU=\(a,β) :|a|≤ a_ ,\ |β|≤ _ \. A single dynamic obstacle is modeled as a disk of radius ror_o at position o(t)∈ℝ2 p_o(t) ^2 moving with constant inertial velocity o v_o with magnitude bounded by vo,maxv_o, . The combined safety radius is r=r+ror=r_r+r_o, where r_r is the robot’s radius. Relative position and velocity are Δ=o− p= p_o- p and Δ=−o v= v- v_o, with v rather than ˙ p, so that the barrier depends on the state alone. Since the barrier depends on the obstacle, we treat o p_o as part of the state, writing x:=(,o)x:=( x, p_o) for the augmented state, with ˙o=o p_o= v_o, and take Lie derivatives along these augmented dynamics, as in [5]. We write ρ=‖Δ‖ρ=\| p\| for the relative distance, and d=ρ2−r2d= ρ^2-r^2 for the tangent distance. The forward speed is taken to lie in [0,vmax][0,v_ ], an assumption used only by the feasibility result of Sec. I-C. To bound the worst-case approach speed we define wmax:=vmax+vo,maxw_ :=v_ +v_o, , so that ‖Δ‖≤wmax\| v\|≤ w_ . The line-of-sight (LoS) frame is the frame rotated by γ=atan22(Δpy,Δpx)γ= 2( p_y, p_x) so that its first axis is aligned with Δ p. With (⋅)R(·) the planar rotation matrix, the relative velocity and the heading in this frame are Δ~=(−γ)Δ=:[Δv∥Δv⟂],θ~=θ−γ. v=R(-γ)\, v=: bmatrix v_ \\ v_ bmatrix, θ=θ-γ. (6) Thus Δv∥ v_ is the closing rate, the component of Δ v along the line of sight, which is positive whenever Δ v makes an acute angle with Δ p. The transverse component is Δv⟂ v_ , and θ~ θ is the heading measured from the line of sight. I-C Related Work: Velocity-Space CBFs A direct distance-based CBF h=ρ2−r2h=ρ^2-r^2 cannot be used in the CBF-QP (4) without modification. Its rate 2ρρ˙2ρ ρ does not contain the acceleration (see Appendix A). To avoid this, recent work [5, 6, 7, 11] maps the obstacle constraint from configuration space into the space of relative velocities, where the constraint acquires relative degree one. The Collision-Cone CBF (C3BF) [5] uses the observation that, under constant-velocity motion, collision occurs only if the relative velocity vector points into the obstacle safety disk. The set of such directions forms a cone in velocity space of half-angle arcsin(r/ρ) (r/ρ), called the collision cone. The robot is safe as long as Δ v stays outside this cone, and each obstacle contributes a cone of its own. This condition can be written as hC3BF(Δ,Δ)=−Δ⊤Δ+‖Δ‖‖Δ‖2−r2≥0,h_C3BF( p, v)=- p v+\| v\| \| p\|^2-r^2≥ 0, (7) and [5] shows that hC3BFh_C3BF has relative degree one for the kinematic bicycle, so the CBF-QP can be applied directly. C3BF is conservative because its cone half-angle depends only on ‖Δ‖\| p\| and r. The condition therefore ignores the magnitude of Δ v. DPCBF [7] reduces this by replacing each cone with a parabolic region in the same v-space, whose vertex and curvature depend on both ‖Δ‖\| p\| and ‖Δ‖\| v\|. Its result is established under two assumptions: (A1) Forward speed. v∈[vmin,vmax]v∈[v_ ,v_ ] with vmax>vmin>0v_ >v_ >0. (A2) Clearance margin. There exist s>1s>1 and a finite sensing range pmaxp_ such that sr≤ρ≤pmaxsr≤ρ≤ p_ , so d≥dmin=rs2−1>0d≥ d_ =r s^2-1>0. (A1) excludes the degeneracy v=0v=0 at which the steering authority v/ℓrv/ _r vanishes. (A2) is assumed rather than enforced by the controller, which yields h≥0h≥ 0 and not ρ≥srρ≥ sr. Under (A1)–(A2), [7] shows that at every state on the boundary of the safe set some input in U satisfies the barrier condition (3), one constraint per obstacle. A third line of work replaces the single barrier by a disjunction. VOCBF [11] imposes the barrier condition on at least one of the two half-spaces whose union is the outside of the cone, so its safe set is that of C3BF. Besides the mixed-integer program, [11] proposes a decomposition into quadratic programs and a learned selection. We compare against the mixed-integer program. These methods leave three gaps. C3BF is conservative, since its condition depends only on the direction of Δ v. DPCBF removes much of that conservatism but rests on (A1)–(A2), neither of which is enforced by the controller proposed in [7]. VOCBF needs neither assumption, but the active half-space is chosen by the solver rather than by the barrier, and its formulation is a mixed-integer program. Finally, C3BF, DPCBF and VOCBF all contain d=ρ2−r2d= ρ^2-r^2, whose derivative d˙=ρρ˙/d d=ρ ρ/d is singular at contact: [5] verifies the CBF condition (2) only where d>0d>0, [11] assumes that the robot is not in contact with the obstacle, and [7] bounds the term by (A2). I Proposed Method I-A Proposed Barrier Function A distant obstacle approached slowly can often still be avoided, yet C3BF declares any state with Δ v inside the collision cone unsafe regardless of the obstacle distance or the approach speed [7]. We therefore allow the robot to approach the obstacle at any rate up to c, imposing the cone condition only on the excess Δv∥−c v_ -c. Geometrically this slides the apex of the cone away from the origin of the relative-velocity plane, so wherever c>0c>0 motion toward the obstacle is no longer immediately unsafe. The allowance c:=κdpv2,κ≥0,p≥1,c:=κ\,d^\,pv^2, κ≥ 0, p≥ 1, (8) vanishes at contact and at rest, and grows with distance and robot speed. The cone has two edges, indexed by σ∈+1,−1σ∈\+1,-1\, as shown in Fig. 1. We define one function for each and take their maximum as the barrier function. With κ=0κ=0 the two functions describe the edges of the C3BF cone, and the barrier has the same safe set as C3BF. Since c≥0c≥ 0, a positive κ can only enlarge this set, which gives a less conservative safe set, as illustrated in Fig. 1. Fig. 1: The C3BF cone (dashed) and the SC3BF cone (solid) in the relative-velocity plane, in the line-of-sight frame. The allowance c moves the apex along the closing direction, and the gray region between the two cones is the conservatism it removes. For σ∈+1,−1σ∈\+1,-1\ let hσ h_σ :=−r(Δv∥−c)+σdΔv⟂ :=-r ( v_ -c )+σ\,d\, v_ (9) =−rΔv∥+σdΔv⟂+rκdpv2, =-r v_ +σ d v_ +rκ d^\,pv^2, and set h:=max(h+1,h−1)h:= (h_+1,h_-1) and :=x:ρ≥r,h(x)≥0C:=\x:ρ≥ r,\ h(x)≥ 0\. I-B Proposed Controller For ρ>rρ>r, differentiating hσh_σ along the augmented dynamics gives, as derived in Appendix A, h˙σ h_σ =Lfhσ+a(cσa+S)+βBσ, =L_fh_σ+a (c^a_σ+S )+β B_σ, (10) Lfhσ L_fh_σ =rΔv⟂2ρ−rΔv∥d(σrΔv⟂ρ+κpdp−1ρv2), = r v_ ^2ρ- r v_ d ( σ r v_ ρ+κ p\,d^\,p-1ρ v^2 ), cσa c^a_σ =−rcosθ~+σdsinθ~,cβσ=rsinθ~+σdcosθ~, =-r θ+σ d θ, c^β_σ=r θ+σ d θ, Bσ B_σ =v2ℓrcσβ+vρd(σΔv⟂+rκpdp−1v2)sinθ~ = v^2 _rc^β_σ+ vρd (σ v_ +rκ p\,d^\,p-1v^2 ) θ +vρ(rΔv⟂+σdΔv∥)cosθ~, + vρ (r v_ +σ d\, v_ ) θ, with S=2rκdpvS=2rκ d^\,pv. The last two terms of BσB_σ come from the sideways motion of the center of mass. The inequality h˙σ≥−α(hσ) h_σ≥-α(h_σ) cannot be imposed at contact, where ρ=rρ=r, because the formula (10) is singular there: LfhσL_fh_σ contains rΔv∥/dr v_ /d. Instead, the controller requires a nondecreasing distance and a nonincreasing closing rate, two constraints affine in u derived in Appendix B. Imposing h˙σ≥−α(hσ) h_σ≥-α(h_σ) for ρ>rρ>r and these contact constraints for 0<ρ≤r0<ρ≤ r gives ∗=argmin∈ u^*= _ u ‖−nom‖2 \| u- u_nom\|^2 (11) s.t. .t. h˙σ(x,)≥−α(hσ)if ρ>r,ρ˙≥0,dtΔv∥≤0if 0<ρ≤r, cases h_σ(x, u)≥-α(h_σ)&if ρ>r,\\[3.0pt] ρ≥ 0,\ \ ddt v_ ≤ 0&if 0<ρ≤ r, cases where α is an extended class-K function, σ=+1σ=+1 if Δv⟂≥0 v_ ≥ 0 and σ=−1σ=-1 otherwise, which selects the edge attaining the maximum since h+1−h−1=2dΔv⟂h_+1-h_-1=2d\, v_ . Because the sign of Δv⟂ v_ fixes the active edge, (11) is an ordinary quadratic program. I-C Main Results We call a pair (κ,p)(κ,p) admissible if, for every extended class-K function α, (11) is feasible at every state of C. We now show that admissible pairs exist, and that the solutions of (11) prevent collisions. At each state with ρ>rρ>r the program enforces h˙σ≥−α(hσ) h_σ≥-α(h_σ) for only the edge selected by the sign of Δv⟂ v_ . Write σ:=hσ≥0∩σΔv⟂≥0C^σ:=\h_σ≥ 0\∩\σ v_ ≥ 0\ for the part of C on which edge σ attains the maximum. Together, +1C^+1 and −1C^-1 cover C, so feasibility needs to be established only for edge σ on σC^σ. In the following proposition, we show that there always exists a pair (κ,p)(κ,p) for which (11) is feasible at every state of C with ρ>rρ>r. Proposition 3.1 (Existence of an admissible pair) For every positive safety radius r, speed bound vmaxv_ , input bounds amaxa_ and βmax _ and rear-axle distance ℓr _r, and every obstacle speed bound vo,max≥0v_o, ≥ 0, there exists a pair (κ,p)(κ,p) with κ>0κ>0 such that, for every extended class-K function α, (11) is feasible at every state of C with ρ>rρ>r. Proof: See Appendix C. At contact, where ρ=rρ=r, the program imposes the contact constraints instead, and =0 u=0 satisfies them (Appendix B). Hence (11) is feasible at every state of C. Feasibility at each state does not by itself show that C is forward invariant. The standard result of [1] assumes a single continuously differentiable h, which h=max(h+1,h−1)h= (h_+1,h_-1) is not, so Theorem 3.2 establishes invariance of C directly. Theorem 3.2 (Safety) Let x(0)∈x(0) . If the applied input satisfies the constraints of (11) at every time, then x(t)∈x(t) , and hence ρ(t)≥rρ(t)≥ r, for all t≥0t≥ 0. Proof: See Appendix D. With Proposition 3.1, Theorem 3.2 keeps (11) feasible along the trajectory: inputs that satisfy its constraints keep the state in C, where the program is feasible. I-D Choosing the Allowance Proposition 3.1 shows that a pair (κ,p)(κ,p) exists such that our controller (11) is always feasible, but does not say which value to use. At p=1p=1, Appendix C supplies a threshold κ⋆κ in closed form, and every pair (κ,1)(κ,1) with 0<κ≤κ⋆0<κ≤κ is admissible, so a usable gain requires no numerical search. This threshold is conservative because its derivation bounds LfhσL_fh_σ and the contribution of the input separately, each at its own worst case. For a given system, the numerical procedure of Appendix E can verify that (11) remains feasible with a larger κ at every state of a specified domain, rather than only at sampled states. The procedure certifies one pair (κ,p)(κ,p) at a time, and every certified pair keeps (11) feasible on the certified domain, so the guarantees of Sec. I-C hold for each. Within this range, κ is a design choice: a larger gain makes the safe set of each obstacle less conservative, but also lets the robot approach obstacles faster. The exponent p sets how quickly the allowance grows with distance. We evaluate p=1p=1 and p=1.2p=1.2. IV Evaluation IV-A Setup and Metrics The robot is the kinematic bicycle of Sec. I-B with amax=5a_ =5 m/s2, βmax=0.28 _ =0.28 rad, ℓr=0.2 _r=0.2 m, vmax=3.5v_ =3.5 m/s and radius 0.30.3 m, integrated at 5050 ms. It drives from (1,7.5)(1,7.5) to a goal at (25,7.5)(25,7.5) m, through 2020, 5050 or 100100 obstacles of radius 0.70.7 m placed uniformly at random in [5,30]×[−5,20][5,30]×[-5,20] m, each moving in a random direction at a constant speed drawn from [0,1.2][0,1.2] m/s. Every method enforces its barrier at the inflated radius Reff=1.05rR_eff=1.05\,r, which leaves a margin the continuous-time analysis does not model but a discrete time step needs. A run is cut off after 20002000 steps. The robot starts at 11 m/s, heading toward the goal. Every method uses the same nominal controller, the goal-tracking controller of the framework of [7], solves its program with Gurobi, and is given the same 100100 random instances. DPCBF uses the gains reported for this obstacle radius, kλ=0.144k_λ=0.144 and kμ=0.505k_μ=0.505. For SC3BF we use κ=0.18κ=0.18 at p=1p=1 and κ=0.1672κ=0.1672 at p=1.2p=1.2, which the procedure of Appendix E verifies at the enforced radius ReffR_eff, the first for every ρ>Reffρ>R_eff and the second for ρ≤70ρ≤ 70 m. The extended class-K function of (2) is taken linear, α(h)=kαhα(h)=k_αh, and each method is given the kαk_α with the highest success rate at each obstacle count, from a grid between 1.51.5 and 4040. A run succeeds if the robot comes within 0.30.3 m of the goal. It fails, ending the run, if the quadratic program is infeasible or cannot be solved, if the robot overlaps any obstacle at the end of a step, which we record as a collision, or if the step limit is reached first. We also report the intervention, which measures how far the filter moves the nominal input. At each step it is (a∗−anomamax)2+(β∗−βnomβmax)2, ( a^*-a_noma_ )^2+ ( β^*- _nom _ )^2, (12) so that each channel is measured relative to its input bound. For every method, we average the intervention over the steps of each successful run, and then over the successful runs. IV-B Results TABLE I: Success rate and intervention over 100 random instances per obstacle count. Intervention is averaged over successful runs. SC3BF is our method. 20 obstacles 50 obstacles 100 obstacles Method succ. interv. succ. interv. succ. interv. C3BF [5] 22 % 0.470 6 % 0.440 0 % – VOCBF [11] 53 % 0.119 38 % 0.488 12 % 0.724 DPCBF [7] 84 % 0.357 48 % 0.542 17 % 0.684 SC3BF, p=1p=1 91 % 0.052 62 % 0.120 22 % 0.222 SC3BF, p=1.2p=1.2 92 % 0.053 67 % 0.131 27 % 0.229 With p=1.2p=1.2, SC3BF reaches the goal more often than every baseline at all three obstacle counts (Table I). Its success rate exceeds DPCBF’s by 88, 1919 and 1010 percentage points: 92%92\% versus 84%84\%, 67%67\% versus 48%48\%, and 27%27\% versus 17%17\%. Among successful runs, its intervention is less than half of each baseline’s at every count. V Conclusion We introduced SC3BF, a velocity-space control barrier function that relaxes the collision-cone condition by an allowance growing with distance and robot speed. The construction is enforced by an ordinary quadratic program and keeps its safe set forward invariant under bounded inputs, including at contact. SC3BF needs neither a clearance margin nor a minimum forward speed, which are assumed in DPCBF’s theoretical guarantees. We showed that, for any choice of the bicycle and obstacle parameters, there exists a nonzero allowance that preserves safety. In simulations with up to 100100 moving obstacles, SC3BF reached the goal more often than C3BF, DPCBF and VOCBF at every obstacle count and modified the nominal input less than half as much as any of them. References [1] A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada (2017) Control barrier function based quadratic programs for safety critical systems. IEEE Transactions on Automatic Control 62 (8), p. 3861–3876. Cited by: §I, §I-A, §I-C. [2] L. Wang, A. D. Ames, and M. Egerstedt (2017) Safety barrier certificates for collisions-free multirobot systems. IEEE Transactions on Robotics 33 (3), p. 661–674. Cited by: §I. [3] W. Xiao and C. Belta (2022) High-order control barrier functions. IEEE Transactions on Automatic Control 67 (7), p. 3655–3662. Cited by: §I. [4] P. Fiorini and Z. Shiller (1998) Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research 17 (7), p. 760–772. Cited by: §I. [5] P. Thontepu, B. G. Goswami, M. Tayal, N. Singh, S. S. PI, S. S. MG, S. Sundaram, V. Katewa, and S. Kolathaya (2023) Collision cone control barrier functions for kinematic obstacle avoidance in ugvs. In 2023 Ninth Indian Control Conference (ICC), p. 293–298. Cited by: §I, §I-B, §I-B, §I-C, §I-C, §I-C, §I-C, TABLE I. [6] A. Haraldsen, M. S. Wiig, A. D. Ames, and K. Y. Pettersen (2024) Safety-critical control of nonholonomic vehicles in dynamic environments using velocity obstacles. In 2024 American Control Conference (ACC), p. 3152–3159. Cited by: §I, §I-C. [7] H. K. Park, T. Kim, and D. Panagou (2026) Beyond collision cones: dynamic obstacle avoidance for nonholonomic robots via dynamic parabolic control barrier functions. In 2026 IEEE International Conference on Robotics and Automation (ICRA), Cited by: §I, §I-B, §I-C, §I-C, §I-C, §I-C, §I-A, §IV-A, TABLE I. [8] P. Glotfelter, J. Cortés, and M. Egerstedt (2017) Nonsmooth barrier functions with applications to multi-robot systems. IEEE Control Systems Letters 1 (2), p. 310–315. Cited by: §I. [9] P. Ong, H. Lee, T. G. Molnar, D. Panagou, and A. D. Ames (2025) Combinatorial control barrier functions: nested boolean and p-choose-r compositions of safety constraints. IEEE Control Systems Letters 9, p. 2705–2710. Cited by: §I. [10] J. Breeden and D. Panagou (2023) Compositions of multiple control barrier functions under input constraints. In 2023 American Control Conference (ACC), p. 3688–3695. Cited by: §I. [11] J. Huang, J. Zeng, X. Chi, K. Sreenath, Z. Liu, and H. Su (2025) Dynamic collision avoidance using velocity obstacle-based control barrier functions. IEEE Transactions on Control Systems Technology 33 (5), p. 1601–1615. Cited by: §I, §I-C, §I-C, §I-C, TABLE I. [12] P. Polack, F. Altché, B. d’Andréa-Novel, and A. de La Fortelle (2017) The kinematic bicycle model: a consistent model for planning feasible trajectories for autonomous vehicles?. In IEEE Intelligent Vehicles Symposium (IV), p. 812–818. Cited by: §I-B. Appendix A Rates of the Relative Motion and of an Edge This appendix derives the rates used in the paper: ρ˙ ρ and d˙ d, the rate h˙σ h_σ of an edge in (10), and the rate of Δv∥ v_ , which the contact constraints of Appendix B use. Velocity along the heading. Since =v(cosθ,sinθ)⊤ v=v\,( θ, θ) , the product rule gives ˙=v˙(cosθ,sinθ)⊤+vθ˙(−sinθ,cosθ)⊤ v= v\,( θ, θ) +v θ\,(- θ, θ) . We substitute v˙=a v=a and θ˙=vβ/ℓr θ=vβ/ _r from (5) to get ˙=a(cosθ,sinθ)⊤+v2ℓrβ(−sinθ,cosθ)⊤, v=a\,( θ, θ) + v^2 _rβ\,(- θ, θ) , (13) and since o v_o is constant, dtΔ=˙ ddt v= v. Distance and line of sight. We use two identities: for every angle ϕφ, (−γ)(cosϕ,sinϕ)⊤ (-γ)( φ, φ) =(cos(ϕ−γ),sin(ϕ−γ))⊤, =( (φ-γ), (φ-γ)) , (−γ)(−sinϕ,cosϕ)⊤ (-γ)(- φ, φ) =(−sin(ϕ−γ),cos(ϕ−γ))⊤. =(- (φ-γ), (φ-γ)) . We write dtΔ ddt p in two ways and rotate both into the line-of-sight frame. First, the first two rows of (5) give ˙=+vβ(−sinθ,cosθ)⊤ p= v+vβ(- θ, θ) , and ˙o=o p_o= v_o, so dtΔ=−Δ−vβ(−sinθ,cosθ)⊤ ddt p=- v-vβ(- θ, θ) . By (6) and the second identity with ϕ=θφ=θ, (−γ)dtΔ=[−Δv∥+vβsinθ~−Δv⟂−vβcosθ~].R(-γ) ddt p= bmatrix- v_ +vβ θ\\ - v_ -vβ θ bmatrix. Second, Δ=ρ(cosγ,sinγ)⊤ p=ρ\,( γ, γ) gives dtΔ=ρ˙(cosγ,sinγ)⊤+ργ˙(−sinγ,cosγ)⊤ ddt p= ρ\,( γ, γ) +ρ γ\,(- γ, γ) , and both identities with ϕ=γφ=γ give (−γ)dtΔ=[ρ˙ργ˙].R(-γ) ddt p= bmatrix ρ\\ ρ γ bmatrix. Equating the two expressions row by row gives ρ˙=−Δv∥+vβsinθ~,ργ˙=−Δv⟂−vβcosθ~. ρ=- v_ +vβ θ, ρ γ=- v_ -vβ θ. (14) For ρ>rρ>r, taking the derivative of d2=ρ2−r2d^2=ρ^2-r^2 gives d˙=ρρ˙/d d=ρ ρ/d. Rates of Δv∥ v_ and Δv⟂ v_ . By the product rule, dt((−γ)Δ)=(−γ)˙+(dt(−γ))Δ ddt (R(-γ) v )=R(-γ) v+ ( ddtR(-γ) ) v. By the two identities with ϕ=θφ=θ, the first term is (13) with θ replaced by θ~ θ. For the second, differentiating (−γ)=[cosγsinγ−sinγcosγ]R(-γ)= [ smallmatrix γ& γ\\ - γ& γ smallmatrix ] gives dt(−γ)=γ˙[−sinγcosγ−cosγ−sinγ] ddtR(-γ)= γ [ smallmatrix- γ& γ\\ - γ&- γ smallmatrix ]. By (6), the second term is therefore γ˙(Δv⟂,−Δv∥)⊤ γ\,( v_ ,- v_ ) . We substitute γ˙ γ from (14) to get dtΔv∥ ddt v_ =acosθ~−v2ℓrβsinθ~−Δv⟂(Δv⟂+vβcosθ~)ρ, =a θ- v^2 _rβ θ- v_ ( v_ +vβ θ)ρ, (15) dtΔv⟂ ddt v_ =asinθ~+v2ℓrβcosθ~+Δv∥(Δv⟂+vβcosθ~)ρ. =a θ+ v^2 _rβ θ+ v_ ( v_ +vβ θ)ρ. Rate of an edge. For ρ>rρ>r, taking the derivative of (9), with v˙=a v=a, gives h˙σ= h_σ= −rdtΔv∥+σ(d˙Δv⟂+ddtΔv⟂) -r ddt v_ +σ ( d\, v_ +d\, ddt v_ ) +rκpdp−1d˙v2+2rκdpva. +rκ p\,d^\,p-1 d\,v^2+2rκ d^\,pv\,a. Substituting the three rates above, using ρ2−d2=r2ρ^2-d^2=r^2, and collecting the terms without input and the coefficients of a and β gives LfhσL_fh_σ, cσa+Sc^a_σ+S and BσB_σ in (10). Appendix B The Contact Constraints At contact, ρ=rρ=r, the rate (10) cannot be used, since LfhσL_fh_σ contains rΔv∥/dr v_ /d and d=0d=0. This appendix derives the constraints that (11) imposes instead, and shows that they are feasible at every state of C at contact. At contact d=0d=0, so both edges are equal to −rΔv∥-r v_ . Therefore, h=−rΔv∥h=-r v_ . Since h≥0h≥ 0 on C, a state of C at contact has Δv∥≤0 v_ ≤ 0. While contact lasts, two things must hold. The robot must not enter the obstacle, so we require ρ˙≥0 ρ≥ 0. The state must also stay in C, which at contact means that Δv∥ v_ stays nonpositive, so we require dtΔv∥≤0 ddt v_ ≤ 0. Writing both requirements with (14) and (15) gives vβsinθ~ vβ θ ≥Δv∥, ≥\ v_ , acosθ~−v2ℓrβsinθ~−vΔv⟂ρβcosθ~ a θ- v^2 _rβ θ- v v_ ρβ θ ≤Δv⟂2ρ, ≤\ v_ ^2ρ, which are the contact constraints of (11). Both are affine in u. The input =0 u=0 satisfies both, since it gives ρ˙=−Δv∥≥0 ρ=- v_ ≥ 0 and dtΔv∥=−Δv⟂2/ρ≤0 ddt v_ =- v_ ^2/ρ≤ 0. We impose them for 0<ρ≤r0<ρ≤ r, not only at ρ=rρ=r, because the proof of Theorem 3.2 argues by contradiction on an interval on which ρ<rρ<r. Appendix C Proof of Proposition 3.1 Proposition 3.1 asks for a pair (κ,p)(κ,p) for which, for every extended class-K function α, the constraint h˙σ≥−α(hσ) h_σ≥-α(h_σ) can be met at every state of σC^σ with ρ>rρ>r. On σC^σ, hσ≥0h_σ≥ 0 and so −α(hσ)≤0-α(h_σ)≤ 0. It is therefore enough to show that some input makes h˙σ h_σ nonnegative: sup∈h˙σ(x,)≥ 0on σ∩ρ>r. _ u h_σ(x, u)\ ≥\ 0 C^σ∩\ρ>r\. (16) Since h˙σ h_σ in (10) is affine in u, its largest value is reached with each input at its bound, with the sign of its coefficient: sup∈h˙σ=Lfhσ+Φσ,Φσ:=amax|cσa+S|+βmax|Bσ|. _ u h_σ=L_fh_σ+ _σ, _σ:=a_ |c^a_σ+S |+ _ |B_σ |. (17) We call LfhσL_fh_σ the drift, since it does not depend on the input, and Φσ _σ the authority, the largest increase that acceleration and steering can add. The drift can be negative, and the proof shows that the authority always makes up for it. If Δv∥≤0 v_ ≤ 0, both terms of LfhσL_fh_σ in (10) are nonnegative on σC^σ, so =0 u=0 satisfies (16). The rest of this appendix takes Δv∥>0 v_ >0 and proceeds in three steps. Appendix C-A bounds the drift and the authority from below, both in proportion to ρv2ρ v^2, which reduces (16) to a condition on the parameters alone. Appendix C-B gives a gain that satisfies this condition in closed form, and Appendix C-C completes the proof. C-A Bounds on the Drift and the Authority We state the bounds for a general exponent p≥1p≥ 1. The proof of Proposition 3.1 uses them at p=1p=1, and Appendix E for a given pair (κ,p)(κ,p). Let x∈σx ^σ with ρ>rρ>r and Δv∥>0 v_ >0, and write ζ:=σΔv⟂ζ:=σ v_ , so that ζ≥0ζ≥ 0 by the definition of σC^σ, and ζ≤‖Δ‖≤wmaxζ≤\| v\|≤ w_ . The exponent enters through dp−1d^\,p-1, which we bound on the range of distances considered by two constants, D¯≥dp−1 D≥ d^\,p-1 and Mp≥dp−1(p+r2/ρ2)M_p≥ d^\,p-1(p+r^2/ρ^2). At p=1p=1 these are D¯=1 D=1 and M1=2M_1=2, for every ρ>rρ>r. For p>1p>1, dp−1d^\,p-1 grows without bound with ρ, so the range must be bounded, and Appendix E gives the constants for p>1p>1. The following lemma bounds the drift below by −ρv2ν-ρ v^2ν, where ν:=κwmaxMp+rκ2pD¯2vmax2.ν:=κ w_ M_p+rκ^2p D^2v_ ^2. Lemma 3.1 The drift satisfies Lfhσ L_fh_σ ≥−κdp−1v2pρ2+r2ρζ−rκ2pd 2p−2ρv4 ≥\ -κ d^\,p-1v^2 pρ^2+r^2ρ\,ζ\;-\;rκ^2p\,d^\,2p-2ρ v^4 (18) ≥−ρv2ν. ≥\ -ρ v^2ν. Proof: By (10), Lfhσ=rζ2ρ−rΔv∥d(rζρ+κpdp−1ρv2)L_fh_σ= rζ^2ρ- r v_ d ( rζρ+κ p\,d^\,p-1ρ v^2 ), and the factor in brackets is nonnegative since ζ≥0ζ≥ 0. We write hσ≥0h_σ≥ 0 as −rΔv∥+dζ+rκdpv2≥0-r v_ +dζ+rκ d^\,pv^2≥ 0 and divide by d>0d>0: rΔv∥d≤ζ+rκdp−1v2. r v_ d\ ≤\ ζ+rκ d^\,p-1v^2. (19) We multiply (19) by (rζρ+κpdp−1ρv2)≥0 ( rζρ+κ p\,d^\,p-1ρ v^2 )≥ 0, and expand the right side: (ζ+rκdp−1v2)(rζρ+κpdp−1ρv2) (ζ+rκ d^\,p-1v^2) ( rζρ+κ p\,d^\,p-1ρ v^2 ) =rζ2ρ+κdp−1v2pρ2+r2ρζ+rκ2pd 2p−2ρv4. = rζ^2ρ+κ d^\,p-1v^2\, pρ^2+r^2ρ\,ζ+rκ^2p\,d^\,2p-2ρ v^4. Substituting this upper bound into the expression for LfhσL_fh_σ, the term rζ2/ρrζ^2/ρ cancels, which gives the first inequality of (18). For the second, pρ2+r2ρ=ρ(p+r2/ρ2) pρ^2+r^2ρ=ρ\,(p+r^2/ρ^2), and we use ζ≤wmaxζ≤ w_ , dp−1(p+r2/ρ2)≤Mpd^\,p-1(p+r^2/ρ^2)≤ M_p, dp−1≤D¯d^\,p-1≤ D and v≤vmaxv≤ v_ . The authority. The following lemma gives a lower bound on the authority Φσ _σ, again proportional to ρv2ρ v^2, so that it can be compared directly with the drift bound. Lemma 3.2 Let ψ:=arccos(r/ρ)ψ:= (r/ρ), φ:=ψ+σθ~ :=ψ+σ θ, ε:=ν/amax :=ν/a_ , and ξ:=εvmax2+2rκD¯vmaxξ:= v_ ^2+2rκ Dv_ . The coefficients satisfy cσa=−ρcosφc^a_σ=-ρ and Bσ=σv(Qsinφ−Pcosφ)B_σ=σ v\,(Q -P ), where P P :=d(dζ−rΔv∥)ρ2+rκpdp−1v2, := d(dζ-r v_ )ρ^2+rκ p\,d^\,p-1v^2, (20) Q Q :=vρℓr+d(rζ+dΔv∥)ρ2+rζd+r2κpdp−2v2. := vρ _r+ d(rζ+d v_ )ρ^2+ rζd+r^2κ p\,d^\,p-2v^2. If ξ<1ξ<1, then Φσ _σ ≥ρv2min(ν,βmaxΛ),where ≥\ ρ v^2 (ν,\ _ ), (21) Λ :=1−ξ2ℓr−1r(wmax+rκpD¯vmax2)(εvmax+2rκD¯). := 1-ξ^2 _r- 1r (w_ +rκ p Dv_ ^2 ) ( v_ +2rκ D ). Proof: Since r2+d2=ρ2r^2+d^2=ρ^2, we have r=ρcosψr=ρ ψ and d=ρsinψd=ρ ψ. We substitute sinθ~=σsin(φ−ψ) θ=σ ( -ψ) and cosθ~=cos(φ−ψ) θ= ( -ψ) into cσac^a_σ and BσB_σ of (10), expand, and collect the coefficients of sinφ and cosφ , which gives the two identities. On σC^σ, hσ≥0h_σ≥ 0 gives dζ−rΔv∥≥−rκdpv2dζ-r v_ ≥-rκ d^\,pv^2, so P≥rκdp−1v2(p−d2/ρ2)≥0P≥ rκ d^\,p-1v^2(p-d^2/ρ^2)≥ 0. Since Δv∥>0 v_ >0, dropping −rdΔv∥/ρ2-rd v_ /ρ^2 gives P≤ζ+rκpdp−1v2≤wmax+rκpD¯vmax2P≤ζ+rκ p\,d^\,p-1v^2≤ w_ +rκ p Dv_ ^2, and every term of Q is nonnegative, so Q≥vρ/ℓrQ≥ vρ/ _r. We consider two cases. If |cσa+S|≥ερv2|c^a_σ+S|≥ ρ v^2, then Φσ≥amaxερv2=ρv2ν _σ≥ a_ ρ v^2=ρ v^2ν. Otherwise, since S=2rκdp−1dv≤2rκD¯ρvS=2rκ d^\,p-1d\,v≤ 2rκ Dρ v, we have ρ|cosφ|≤|cσa+S|+S<ερv2+2rκD¯ρvρ| |≤|c^a_σ+S|+S< ρ v^2+2rκ Dρ v, so |cosφ|<ξ| |<ξ and |sinφ|>1−ξ2| |> 1-ξ^2. Then |Bσ| |B_σ| ≥v(Q|sinφ|−P|cosφ|) ≥\ v (Q| |-P| | ) ≥v2(ρ1−ξ2ℓr−P(εv+2rκD¯)), ≥\ v^2 ( ρ 1-ξ^2 _r-P( v+2rκ D) ), and using the upper bound on P, v≤vmaxv≤ v_ and ρ≥rρ≥ r gives |Bσ|≥ρv2Λ|B_σ|≥ρ v^2 , so Φσ≥βmaxρv2Λ _σ≥ _ ρ v^2 . The resulting condition. Adding the bounds of Lemma 3.1 and Lemma 3.2 gives suph˙σ≥ρv2[min(ν,βmaxΛ)−ν] _ u h_σ≥ρ v^2[ (ν, _ )-ν]. So (16) holds at every state of σC^σ with ρ>rρ>r in the range of distances considered if (Cκ)ξ<1andβmaxΛ≥ν.(C$κ$) ξ<1 _ \ ≥\ ν. (22) This condition involves only the parameters, not the state. Every term of the two bounds is proportional to v2v^2, so no lower bound on the speed is needed, and v=0v=0 is included. C-B A Closed-Form Gain At p=1p=1, (22) depends on κ through ν, ε and ξ. Bounding each of them linearly in κ gives an explicit gain. Lemma 3.3 Let p=1p=1, so that D¯=1 D=1, M1=2M_1=2 and ν=2κwmax+rκ2vmax2ν=2κ w_ +rκ^2v_ ^2. Let g1 g_1 :=3wmaxvmax2amax+2rvmax, := 3w_ v_ ^2a_ +2rv_ , (23) g2 g_2 :=2wmax(3wmaxvmaxamax+2r), :=2w_ ( 3w_ v_ a_ +2r ), κ⋆ κ :=min(wmaxrvmax2,(g1+ℓrg2r+3ℓrwmaxβmax)−1). := ( w_ rv_ ^2,\ (g_1+ _rg_2r+ 3 _rw_ _ )^-1 ). Then κ⋆>0κ >0, and (22) holds for every 0<κ≤κ⋆0<κ≤κ . Proof: Every term in (23) is positive, so κ⋆>0κ >0. Let 0<κ≤κ⋆0<κ≤κ . Then κ is at most each of the two terms of the minimum in (23), so rκvmax2 rκ v_ ^2 ≤wmax, ≤ w_ , κ(g1+ℓrg2r+3ℓrwmaxβmax) κ (g_1+ _rg_2r+ 3 _rw_ _ ) ≤1. ≤ 1. The first inequality gives ν≤3wmaxκν≤ 3w_ κ and wmax+rκvmax2≤2wmaxw_ +rκ v_ ^2≤ 2w_ . So ε≤3wmaxκ/amax ≤ 3w_ κ/a_ , which gives ξ≤κg1ξ≤κ g_1 and (wmax+rκvmax2)(εvmax+2rκ)≤κg2(w_ +rκ v_ ^2)( v_ +2rκ)≤κ g_2. In the second inequality, the last two terms in the bracket are positive, so κg1<1κ g_1<1, and hence ξ<1ξ<1. It remains to show βmaxΛ≥ν _ ≥ν. At p=1p=1, Λ=1−ξ2ℓr−1r(wmax+rκvmax2)(εvmax+2rκ). = 1-ξ^2 _r- 1r (w_ +rκ v_ ^2 ) ( v_ +2rκ ). Since 1−x2≥1−x 1-x^2≥ 1-x for x∈[0,1]x∈[0,1], ξ≤κg1ξ≤κ g_1 gives 1−ξ2≥1−κg1 1-ξ^2≥ 1-κ g_1. The second term is at most κg2/rκ g_2/r by the bound above. Hence Λ≥(1−κg1)/ℓr−κg2/r ≥(1-κ g_1)/ _r-κ g_2/r, and with ν≤3wmaxκν≤ 3w_ κ, βmaxΛ−ν _ -ν ≥βmax(1−κg1ℓr−κg2r)−3wmaxκ ≥\ _ ( 1-κ g_1 _r- κ g_2r )-3w_ κ =βmaxℓr[1−κ(g1+ℓrg2r+3ℓrwmaxβmax)], =\ _ _r [1-κ (g_1+ _rg_2r+ 3 _rw_ _ ) ], where the equality takes out the factor βmax/ℓr _ / _r. The bracket is nonnegative by the second inequality above. C-C Completing the Proof Take p=1p=1 and 0<κ≤κ⋆0<κ≤κ , which is possible because κ⋆>0κ >0. By Lemma 3.3, (22) holds, so (16) holds at every state of σC^σ with ρ>rρ>r. Since hσ≥0h_σ≥ 0 on σC^σ and α is extended class-K, α(hσ)≥0α(h_σ)≥ 0, so suph˙σ≥0≥−α(hσ) _ u h_σ≥ 0≥-α(h_σ). At a state of C with ρ>rρ>r, the edge selected by (11) is the one with the larger hσh_σ, so the state lies in σC^σ for that edge, and (11) is feasible there. ■ Appendix D Proof of Theorem 3.2 We prove a stronger statement: the theorem holds for every absolutely continuous trajectory whose input satisfies the constraints of (11) at almost every time. We show that the state stays in C, that is, ρ≥rρ≥ r and h≥0h≥ 0 at every time. Since h contains d=ρ2−r2d= ρ^2-r^2, it is defined only where ρ≥rρ≥ r, so h≥0h≥ 0 at every time already includes ρ≥rρ≥ r. The barrier constraint, however, controls h only where h is defined, and cannot alone prevent entry into the obstacle: at contact, h≥0h≥ 0 gives only Δv∥≤0 v_ ≤ 0, which by (14) does not prevent ρ˙<0 ρ<0. We therefore first show ρ≥rρ≥ r from the contact constraints (Step 1), and then show that h stays nonnegative by combining the barrier constraint, which holds away from contact, with the contact constraints, which hold at contact (Step 2). Away from contact, h=max(h+1,h−1)h= (h_+1,h_-1) is not differentiable where the two edges are equal, so we first need a lemma on the maximum of two functions. At contact, the edges contain d=ρ2−r2d= ρ^2-r^2, which is not differentiable at ρ=rρ=r, so there we work instead with −rΔv∥-r v_ , which equals h at contact. Lemma 4.1 Let f1,f2:[0,T]→ℝf_1,f_2:[0,T] be absolutely continuous and F=max(f1,f2)F= (f_1,f_2). Then F is absolutely continuous, and at almost every t, F˙(t)=f˙i(t) F(t)= f_i(t) for every i with fi(t)=F(t)f_i(t)=F(t). Proof: We write F=12(f1+f2+|f1−f2|)F= 12(f_1+f_2+|f_1-f_2|). Sums and absolute values of absolutely continuous functions are absolutely continuous, so F is. Then f1,f2f_1,f_2 and F are differentiable at almost every t. Fix such a t. If f1(t)>f2(t)f_1(t)>f_2(t), then F=f1F=f_1 near t and the claim follows, and the same holds if f2(t)>f1(t)f_2(t)>f_1(t). If f1(t)=f2(t)f_1(t)=f_2(t), then F(s)−F(t)=maxifi(s)−fi(t)F(s)-F(t)= _i\f_i(s)-f_i(t)\ for every s. We divide by s−ts-t and let s↓ts t to get F˙(t)=max(f˙1(t),f˙2(t)) F(t)= ( f_1(t), f_2(t)). If we let s↑ts t instead, s−ts-t is negative, so dividing turns the maximum into a minimum, and we get F˙(t)=min(f˙1(t),f˙2(t)) F(t)= ( f_1(t), f_2(t)). Since F is differentiable at t, the two limits are equal, so f˙1(t)=f˙2(t)=F˙(t) f_1(t)= f_2(t)= F(t). Proof of the theorem. Let x(⋅)x(·), defined on [0,T][0,T], be such a trajectory of the dynamics of Sec. I-B, and write h(t)h(t) for h(x(t))h(x(t)). On every compact interval on which ρ>0ρ>0, ρ and Δv∥ v_ are absolutely continuous, with derivatives (14) and (15) at almost every time. Each hσh_σ is continuous on ρ≥r\ρ≥ r\, and at contact d=0d=0, so every edge equals −rΔv∥-r v_ and h=−rΔv∥wherever ρ=r.h=-r v_ ρ=r. (24) Step 1: ρ≥rρ≥ r. The distance ρ=‖Δ‖ρ=\| p\| is continuous, since x is. Suppose ρ(t∗)<rρ(t )<r for some t∗t . Since x(0)∈x(0) , ρ(0)≥rρ(0)≥ r, so tr:=supt≤t∗:ρ(t)≥rt_r:= \t≤ t :ρ(t)≥ r\ exists, and by continuity ρ(tr)=rρ(t_r)=r and ρ<rρ<r on (tr,t∗](t_r,t ]. Again by continuity, ρ>0ρ>0 on [tr,tr+δ][t_r,t_r+δ] for some δ>0δ>0. We replace t∗t by min(t∗,tr+δ) (t ,t_r+δ), which keeps ρ(t∗)<rρ(t )<r, so that 0<ρ≤r0<ρ≤ r on [tr,t∗][t_r,t ]. On this interval the input satisfies the contact constraints of (11), so ρ˙≥0 ρ≥ 0 at almost every time. Since ρ is absolutely continuous there, ρ(t∗)≥ρ(tr)=rρ(t )≥ρ(t_r)=r, which contradicts ρ(t∗)<rρ(t )<r. Step 2: h≥0h≥ 0. The robot may touch the obstacle and leave it many times, even infinitely often, so we argue by contradiction on an interval where h<0h<0, and show that h cannot decrease there, either away from contact or across contact. By Step 1, the times split into the closed contact set K:=t:ρ(t)=rK:=\t:ρ(t)=r\ and its complement, a union of disjoint open intervals on which ρ>rρ>r. Away from contact we use the barrier constraint. On every compact subinterval of an interval of the complement, x stays in a compact subset of ρ>r\ρ>r\, on which each hσh_σ is continuously differentiable. So each hσ∘xh_σ x is absolutely continuous there, and by Lemma 4.1 so is h∘xh x, with derivative h˙σ(t) h_σ(t), where σ(t)σ(t) is the edge whose constraint the input satisfies. That constraint gives dth≥−α(h) ddth≥-α(h) at almost every time of the interval. At contact we use the contact constraints. Define G(t):=−rΔv∥(t)G(t):=-r v_ (t) for all t. The function G is absolutely continuous, it equals h on K by (24), and at almost every t∈Kt∈ K the input satisfies the contact constraints, so dtΔv∥≤0 ddt v_ ≤ 0 and G˙≥0 G≥ 0. Now suppose h(t1)<0h(t_1)<0 for some t1t_1. Since h(0)≥0h(0)≥ 0, t0:=supt≤t1:h(t)≥0t_0:= \t≤ t_1:h(t)≥ 0\ exists, and by continuity h(t0)=0h(t_0)=0 and h<0h<0 on (t0,t1](t_0,t_1]. We show that h is nondecreasing on [t0,t1][t_0,t_1], which contradicts h(t1)<0h(t_1)<0. On the part in (t0,t1](t_0,t_1] of each interval of the complement of K, h<0h<0, so α(h)<0α(h)<0 and dth>0 ddth>0 at almost every time. Hence h is nondecreasing on that part, and by continuity on its closure. For s<ts<t in K∩[t0,t1]K∩[t_0,t_1], the set [s,t]∖K[s,t] K is a union of disjoint open intervals (a,b)(a,b) with a,b∈Ka,b∈ K, and the absolute continuity of G, with the countable additivity of the integral, gives G(t)−G(s)=∫K∩[s,t]G˙dt′+∑(a,b)(G(b)−G(a)).G(t)-G(s)= _K∩[s,t] G\,dt + _(a,b) (G(b)-G(a) ). The integral is nonnegative, and each G(b)−G(a)=h(b)−h(a)≥0G(b)-G(a)=h(b)-h(a)≥ 0, so h(t)≥h(s)h(t)≥ h(s). For general s<ts<t in [t0,t1][t_0,t_1], either [s,t][s,t] contains no point of K, and lies in the closure of one interval of the complement, or s′:=min(K∩[s,t])s := (K∩[s,t]) and t′:=max(K∩[s,t])t := (K∩[s,t]) exist, and h(s)≤h(s′)≤h(t′)≤h(t)h(s)≤ h(s )≤ h(t )≤ h(t). So h is nondecreasing on [t0,t1][t_0,t_1]. By Steps 1 and 2, ρ(t)≥rρ(t)≥ r and h(t)≥0h(t)≥ 0 for all t∈[0,T]t∈[0,T], which means x(t)∈x(t) . This holds for every T, which gives the theorem. ■ Appendix E Certification of the Gain The gain κ⋆κ of Appendix C-B is conservative, since (22) bounds the drift and the authority separately, allowing worst cases that need not occur at the same state. For a given pair (κ,p)(κ,p), and for p>1p>1 a range ρ≤ρmaxρ≤ _ , the following three steps verify (16) at every state of σC^σ with ρ>rρ>r in that range. Step 1: constants. At p=1p=1, D¯=1 D=1 and M1=2M_1=2. For p>1p>1 we take D¯=ρmaxp−1 D= _ ^\,p-1, and write dp−1(p+r2/ρ2)=pdp−1+dp−1r2/(d2+r2)d^\,p-1(p+r^2/ρ^2)=p\,d^\,p-1+d^\,p-1r^2/(d^2+r^2). The second term is largest at d=r(p−1)/(3−p)d=r (p-1)/(3-p) for 1<p<31<p<3, which gives Mp=pD¯+3−p2(r(p−1)/(3−p))p−1M_p=p D+ 3-p2 (r (p-1)/(3-p) )^p-1. Step 2: low speeds. The bounds of Appendix C-A use the speed only through v≤vmaxv≤ v_ , so on the states with v≤vcv≤ v_c, for any vc≤vmaxv_c≤ v_ , they hold with vcv_c in place of vmaxv_ , also in wmaxw_ . With this replacement, ν and ξ increase with vcv_c and Λ decreases, so if (22) holds at some vcv_c, it holds at every smaller one. We find the largest such vcv_c, up to a tolerance, by bisection on [0,vmax][0,v_ ], keeping the end of the interval at which (22) holds. Then (16) holds at all speeds v≤vcv≤ v_c. If (22) holds at no vc>0v_c>0, the pair is not verified. Step 3: remaining speeds. For vc≤v≤vmaxv_c≤ v≤ v_ we divide the states into boxes, with one interval for each of r/ρr/ρ, the heading, v and σΔv⟂σ v_ . For Δv∥ v_ we use the range allowed by hσ≥0h_σ≥ 0 and ‖o‖≤vo,max\| v_o\|≤ v_o, . On each box, we compute a lower bound on suph˙σ _ u h_σ, with BσB_σ as in (10), by replacing every quantity with the worst value its interval allows, even if these values never occur together at one state. We compute this bound in interval arithmetic and round each result outward, so the bound stays valid in floating point. If the bound on a box is nonnegative, every state in the box satisfies (16), and we remove the box from the list. We also remove any box that contains no state of σC^σ. If the bound is negative, we split the box in two and put both halves back on the list. When the list is empty, every state of the domain lies in a removed box, so (16) holds on the whole domain, and the pair is verified. If instead a box reaches a minimum width with a negative bound, or the list exceeds a size limit, the pair is not verified. A smaller vcv_c would only enlarge this domain.