PaperlayerView exact revision on arXiv

Source-linked AI summary

Adversarially Robust Geometric Safety Certificates for Nonholonomic Robots Against Maneuvering Obstacles

Chandan Kumar Sah, Bazeela Banday, Jishnu Keshavan

arXiv:2609.37126v1cs.ROcs.MA

TL;DR

Dynamic obstacles can maneuver in ways that invalidate nominal geometric safety certificates, while full differential-game computation is difficult for online navigation. The paper contracts a line-of-sight barrier’s geometry to account for worst-case obstacle actions and establishes safety conditions for the resulting certificate. Simulations report reductions in barrier violations and collisions, and show that pointwise derivative robustification does not substitute for geometric contraction.

  • Problem

    Maneuvering obstacles can invalidate geometric safety certificates based on their instantaneous velocity, while differential-game methods are computationally expensive for online navigation.

    Source: §I · p. 1

  • Method

    The method contracts line-of-sight barrier parameters to reserve worst-case margin, exploiting a shared geometric gain through which robot and obstacle actions affect the certificate.

    Source: §I · p. 2

  • Results

    Simulations across obstacle capabilities, densities, and capability mismatch report consistent elimination of nominal DPCBF’s silent-failure mode and substantial reductions in barrier violations and collisions.

    Source: §VII · pp. 14–15

  • Takeaways & Limitations

    For the studied setting, contracting barrier geometry is the essential mechanism for anticipatory safety against maneuvering obstacles, rather than robustifying only the instantaneous derivative.

    Source: §VII · p. 15

Abstract

from arXiv · show

Safe navigation against obstacles that can actively maneuver within bounded capabilities remains challenging: robust control barrier function methods typically treat obstacle actions as generic disturbances, while differential-game approaches are computationally expensive for online navigation. We propose an adversarially robust geometric certificate that accounts for the worst-case effect of admissible obstacle maneuvers directly in the safe-set geometry through a closed-form contraction of the certificate parameters. The construction exploits a structural property of line-of-sight (LoS) certificates: the robot and obstacle actions enter the certificate through a common state-dependent geometric gain. This gain cancels in the worst-case comparison, reducing the differential game to a direct comparison between obstacle maneuvering capability and the weaker of the robot's longitudinal and steering authorities. Instantiated on the parabolic certificate, the construction yields Adversarially Robust Dynamic Parabolic Control Barrier Functions (AR-DPCBF), for which we establish sufficient conditions for forward invariance of the contracted safe set against all admissible obstacle maneuvers under kinematic bicycle dynamics with bounded inputs. When the obstacle capability is unknown, a sliding-window estimator supplies a high-probability upper bound, allowing the guarantee to be retained with the corresponding coverage probability. We further formulate soft and buffered variants to recover feasibility in dense environments. Simulations across obstacle capabilities, densities, and capability mismatch show substantial reductions in barrier violations and collisions and demonstrate that pointwise robustification of the barrier derivative cannot substitute for contraction of its geometry.

I. INTRODUCTION

Dynamic safety certificates can become unsound when obstacles maneuver, while nonholonomic robots must avoid collisions with limited steering authority. The paper develops a geometric adversarial certificate, establishes conditions for its safety, and adds estimation and feasibility variants.

A. Control Barrier Functions

  • Control barrier functions enforce forward-invariance requirements through a safe-input constraint that minimally deviates from a reference control.For nonholonomic systems, position inputs act through vehicle heading, which can raise the relative degree of distance-based constraints.Source: §I · p. 1, A. Control Barrier Functions · p. 2

I. INTRODUCTION

  • Maneuvering obstacles can invalidate a certificate that remains satisfied and feasible under the constant-velocity premise, causing a silent loss of soundness.The paper contrasts this gap with robust CBF margins on barrier derivatives and the online computational cost of HJI methods.Source: §I · pp. 1–2
  • The proposed certificate contracts the barrier geometry to reserve the worst-case margin, yielding sufficient conditions for forward invariance against admissible obstacle maneuvers.For LoS certificates, robot and obstacle actions share a geometric gain, reducing the worst-case comparison to obstacle capability versus robot authority.Source: §I · p. 2
  • A sliding-window estimator provides a high-probability upper bound on unknown obstacle capability, while soft and buffered variants trade safety conditions against feasibility in dense environments.The variants retain the nominal DPCBF constraint while penalizing violations of the adversarial condition.Source: §I · p. 2

B. Kinematic Bicycle Model

  • The robot is modeled as a kinematic bicycle with position, heading, and speed state, and longitudinal acceleration and slip-angle inputs.Under the small-slip approximation, the center-of-mass velocity has a no-slip component and a lateral component generated by slip.Source: B. Kinematic Bicycle Model · pp. 2–3

C. DPCBF Review

The DPCBF represents dynamic-obstacle safety with a parabolic boundary in line-of-sight relative-velocity coordinates. The paper extends this geometry to bounded obstacle maneuvers and formulates the resulting adversarial safety condition.

C. DPCBF Review

  • The DPCBF defines a parabolic safety boundary in the line-of-sight relative-velocity frame using relative velocity and clearance.States on or above the zero level set are safe under the nominal certificate.Source: C. DPCBF Review · p. 3

D. Obstacle Capability Set and Adversarial CBF

  • The obstacle is modeled with bounded acceleration and turning rate, and an adversarial safe set is constructed as a conservative inner approximation that excludes inevitable-collision states.The rectangular capability set separates the two authority axes for closed-form bounds; a Kamm-circle constraint would require a trust-region problem.Source: D. Obstacle Capability Set and… · p. 3
  • The adversarial CBF condition requires some admissible robot input to satisfy the barrier inequality for every admissible obstacle input.The obstacle’s open-loop ICS definition gives it at least as much power as nonanticipative strategies in differential games.Source: D. Obstacle Capability Set and… · pp. 3–4

E. LoS-Frame Relative Dynamics

  • The line-of-sight relative dynamics account for frame rotation and give its rotation terms in closed form.Those terms vanish as robot-obstacle separation tends to infinity; the residual bound depends on relative speed and clearance.Source: E. LoS-Frame Relative Dynamics · p. 4

III. ADVERSARIALLY ROBUST BARRIER PARAMETERS

The section constructs an adversarial barrier whose safe set lies within the nominal DPCBF safe set. It begins by relating clearance change to longitudinal line-of-sight velocity, then uses contraction to account for maneuvering obstacles.

III. ADVERSARIALLY ROBUST BARRIER PARAMETERS

  • The adversarial barrier’s safe set is a subset of the nominal DPCBF safe set, inheriting its collision-avoidance guarantee.Source: §III · p. 4

A. Setup and the maneuver gap

  • With zero slip, the clearance rate and longitudinal line-of-sight relative velocity have the same sign.Source: A. Setup and the maneuver gap · p. 4
  • The nominal DPCBF barrier is contracted to reserve a margin against worst-case admissible obstacle maneuvers.The following development derives this contraction from obstacle capability and establishes its safety guarantee.Source: A. Setup and the maneuver gap · p. 4

B. Standing assumptions

The certificate is defined over a bounded engagement envelope with positive relative speed, while adversarial robustness contracts its parameters according to obstacle capability. The resulting safe set shrinks with greater obstacle capability and recovers the nominal DPCBF when capability is zero.

B. Standing assumptions

  • The robot has bounded acceleration and steering inputs and must maintain positive forward speed because steering authority vanishes at rest.The engagement assumptions also impose positive minimum relative speed and a maximum clearance.Source: B. Standing assumptions · p. 5
  • On the certified boundary, relative speed and separation are bounded away from zero, keeping the certificate’s denominators well-defined.The engagement envelope is not enforced by the QP, and the certificate does not apply below the minimum relative speed.Source: B. Standing assumptions · p. 5

C. The contracted parameters

  • The adversarial construction contracts the nominal barrier parameters, enlarging the excluded set as obstacle capability κ increases and exactly recovering DPCBF at κ = 0.The contraction reserves part of the nominal certificate as a margin against worst-case admissible maneuvers.Source: C. The contracted parameters · p. 5

D. Sizing the buffer

  • The figure shows greater contraction for larger κ, lower relative speed, and smaller clearance; the safe set remains inside the nominal set.The lower-speed effect follows the 1/∥vrel∥ reaction-time scaling.Source: C. The contracted parameters · p. 5, Figure 2 · p. 6

E. Safety inheritance

The contracted barrier’s safe set is contained within the nominal safe set, allowing its invariance to transfer to collision avoidance. The adversarial certificate is established through its derivative along the bicycle dynamics, including state-dependent parameter effects.

E. Safety inheritance

  • Because h∗ = h − b with b ≥ 0, maintaining h∗ ≥ 0 keeps the trajectory inside the nominal safe set and, under Assumption 4, guarantees clearance d ≥ r.This is the safety-inheritance step from the contracted certificate to collision avoidance.Source: E. Safety inheritance · p. 6

IV. VALIDITY OF THE ADVERSARIAL CERTIFICATE

  • The adversarial barrier satisfies the adversarial CBF condition throughout the engagement envelope, making the contracted set forward invariant and guaranteeing collision avoidance.The argument is for the kinematic bicycle model and uses a standard first-violation argument.Source: §IV · p. 6

A. The exact derivative

  • The exact derivative separates relative-velocity dynamics from a parameter channel, whose acceleration dependence enters through the scalar σ(x).The state-dependent parameters λ∗ and µ∗ depend on clearance and relative speed.Source: A. The exact derivative · pp. 6–7

B. Grouping the derivative by source

The derivative is organized by the sources of its terms, separating obstacle actions, robot control, drift, and slip. The obstacle’s worst-case effect is bounded by its scalar capability times a geometry-dependent gain.

B. Grouping the derivative by source

  • Grouping the derivative by source separates obstacle inputs, robot inputs, drift, and slip contributions to the barrier rate.The robot’s steering-slip correction is treated as a disturbance, conservatively discarding control authority.Source: B. Grouping the derivative by source · p. 7

C. Worst-Case Obstacle Contribution

  • The obstacle’s acceleration and turning inputs combine into sinusoidal functions of its line-of-sight heading, enabling a worst-case bound over the rectangular capability set.The rectangular set lets the worst-case choices for acceleration and turning separate.Source: C. Worst-Case Obstacle Contribution · p. 7
  • The obstacle’s effect is bounded by κΛ(x), where Λ is a geometry-dependent gain that is bounded away from zero on B.Λ is large where the barrier is sensitive to relative velocity and small where it is nearly flat.Source: C. Worst-Case Obstacle Contribution · p. 7

D. Control Authority

The robot’s control authority and the obstacle’s maneuvering effect share the same geometric gain, which cancels in their worst-case comparison. A finite drift bound on the certified boundary supports the resulting safety condition.

D. Control Authority

  • The robot’s and obstacle’s contributions share gain Λ, reducing the adversarial comparison to the weaker of the robot’s longitudinal and steering authorities versus κ.The cancellation also applies to certificates affine in longitudinal and quadratic in lateral relative velocity, with parameters depending on clearance and relative speed.Source: D. Control Authority · pp. 7–8
  • The steering contribution to control authority vanishes at zero speed, motivating the assumption that the robot maintains positive forward speed.The minimum authority is based on longitudinal acceleration and steering authority.Source: D. Control Authority · p. 8

E. Establishing a Positive Drift Margin

  • On the compact certified boundary B, the autonomous drift has a finite infimum and is bounded below by −D̄.The bound follows from the relative-speed and separation limits in the engagement envelope.Source: E. Establishing a Positive Drift Margin · p. 8

F. Bounding the Slip Residual

The safety guarantee is conditional on the robot out-authorizing the obstacle and the runtime constraint remaining feasible along the trajectory. The slip-model residual contributes a fixed overhead that vanishes as the slip limit goes to zero.

F. Bounding the Slip Residual

  • The slip residual is a fixed overhead proportional to vmaxβmax and vanishes as the slip limit goes to zero.Under the stated bounds, the residual components are bounded by vmaxβmaxpmax/dmin and vmaxβmax/pmin, respectively.Source: F. Bounding the Slip Residual · p. 8

G. Sufficient Condition for Safety

  • κ < cmin, together with the stated boundary bounds and runtime feasibility, yields conditional forward invariance against every admissible obstacle strategy while the trajectory remains in the engagement envelope.For initial states in int C* with d(0) > r, the trajectory cannot cross ∂C* while it remains in Ω.Source: G. Sufficient Condition for Safety · pp. 8–9
  • The feasibility guarantee applies on the boundary for a single obstacle; interior feasibility and feasibility for multiple obstacles are not implied and must hold along the closed loop.The theorem’s invariance conclusion is therefore conditional on runtime feasibility.Source: G. Sufficient Condition for Safety · p. 9

H. Sliding-Window Estimator

The sliding-window estimator uses observed obstacle motion to construct capability bounds, with an exposure assumption linking windowed observations to the obstacle’s capabilities. Under the stated noise and exposure assumptions, those bounds preserve the safety guarantee with probability at least 1 − δ.

H. Sliding-Window Estimator

  • The estimator’s capability bounds require the obstacle to realize its acceleration, turning-rate, and speed capabilities at the sampling resolution within each window.Maneuvers shorter than one sampling interval are certified only through their interval averages.Source: H. Sliding-Window Estimator · p. 9

I. Robustness Guarantee

  • With probability at least 1 − δ, the inflated estimated capability bounds dominate the true bounds, so the resulting conservative AR-DPCBF retains the stated safety guarantee.This guarantee applies when the inflated capability satisfies Theorem 10’s hypotheses.Source: §I · p. 10

V. CONTROLLER FORMULATION AND VARIANTS

  • The controller combines a certified hard AR-DPCBF QP with soft and buffered variants that trade formal guarantees for feasibility.The base formulation is a convex QP with two decision variables and Nobs linear constraints.Source: §V · p. 10, A. Base AR-DPCBF Quadratic Program · p. 10

A. Base AR-DPCBF Quadratic Program

  • The control cycle updates capability estimates and contracted barriers before solving the selected variant’s QP.Its total per-cycle cost is O(NobsNw), the same order as the DPCBF controller.Source: A. Base AR-DPCBF Quadratic Program · p. 10

B. Conservatism of Hard AR-DPCBF

Hard AR-DPCBF contracts the safe set against obstacle maneuvers but can become infeasible in dense multi-obstacle scenes. Soft and buffered variants retain nominal DPCBF constraints while relaxing or proactively penalizing the adversarial condition.

B. Conservatism of Hard AR-DPCBF

  • For κj > 0, the contracted adversarial safe set is a strict subset of the nominal DPCBF safe set, and hard constraints can become infeasible in dense multi-obstacle environments.The soft formulations preserve adversarial awareness while recovering feasibility when the hard formulation is infeasible.Source: B. Conservatism of Hard AR-DPCBF · pp. 10–11

C. Soft AR-DPCBF

  • Soft AR-DPCBF keeps the nominal DPCBF constraint hard and penalizes adversarial residuals, but permits adversarial-constraint violations and adds no incentive to build margin while the penalty is inactive.The penalty is inactive whenever gj(x, u) > 0.Source: C. Soft AR-DPCBF · p. 11

D. Buffer Soft AR-DPCBF

  • Buffer Soft AR-DPCBF activates a Huber penalty before the adversarial margin is exhausted, while retaining the nominal DPCBF feasible set.Within the buffer, a quadratic branch encourages proactive margin recovery; for gj ≤ 0, a linear branch limits restoring effort, and both soft variants remain feasible whenever the nominal QP is feasible.Source: D. Buffer Soft AR-DPCBF · p. 11

VI. RESULTS

Simulations show that maneuvering obstacles can silently invalidate nominal DPCBF certificates, while AR-DPCBF variants reduce violations and collisions across adversarial fractions and capabilities. The results also expose trade-offs in feasibility and path length, and show that online capability estimation retains strong safety performance under measurement noise.

B. Breakdown of the Nominal Safety Certificate

  • In the illustrative scenario, DPCBF collides after losing its certificate despite satisfying its nominal constraint on 92% of cycles; Buffer AR-DPCBF keeps both barriers positive.Buffer maintains a minimum clearance of 0.93 m; its minimum h is 0.64 and minimum h* is 0.18.Source: B. Breakdown of the Nominal Safety… · p. 12, Figure 3 · p. 12
  • Across adversarial fractions, AR-DPCBF variants reduce violations and collisions; Buffer performs best, and no AR variant violates the barrier on a trial where DPCBF stays safe.Across 600 paired trials, all pairwise differences are significant (p < 10^-3), except Hard versus R-DPCBF on violations (p = 0.041).Source: B. Breakdown of the Nominal Safety… · pp. 12–13, Figure 5 · p. 13

C. Robustness Across Adversary Capability

  • As obstacle capability increases, the ordering is Buffer < Soft < {Hard ≈ R-DPCBF} < DPCBF, while Hard AR-DPCBF loses feasible QP solutions as κ rises.Soft variants retain near-nominal feasibility and robustness gains beyond those of R-DPCBF.Source: C. Robustness Across Adversary… · pp. 13–14, Figure 6 · p. 15
  • With κasm = 0.98, Buffer AR-DPCBF degrades gradually when κtrue exceeds the assumed capability and outperforms DPCBF even when true capability is more than twice the assumed value.Soft AR-DPCBF follows the same trend but loses robustness more rapidly.Source: C. Robustness Across Adversary… · p. 14, Figure 7 · p. 15
  • Theorem 10’s condition cmin > κ is sound but conservative: sampled boundary states within the certified region were maintainable, while empirical maintainability extended beyond it.The sampled transition to roughly half of boundary states becoming unmaintainable occurred near cmin ≈ 0.4–0.9, even for κ up to 2.5.Source: C. Robustness Across Adversary… · p. 14, Figure 8 · p. 15

D. Mechanistic and Practical Validation

  • Pointwise robustification improves on DPCBF but remains less robust than soft contracted barriers; it preserves a larger feasible control set and lower computational overhead than Hard AR-DPCBF.The stated distinction is that contraction reserves margin over the engagement, whereas pointwise guarantees apply only at the current state.Source: D. Mechanistic and Practical Validation · p. 14
  • Greater robustness adds path length, but the increase is modest relative to collision reduction; Buffer provides the best safety-efficiency trade-off.Increasing adversarial fraction primarily shifts the frontier toward higher path overhead, with collision rates largely unchanged.Source: D. Mechanistic and Practical Validation · p. 14, Figure 9 · p. 15
  • With online capability estimation, violations stay below 17% and collisions below 7% across noise levels, versus 93% and 43% for DPCBF; the estimator’s empirical coverage is 0.95–0.99.The estimated-capability controller matches or exceeds the oracle; as noise decreases, its margin vanishes and it approaches the oracle.Source: D. Mechanistic and Practical Validation · p. 14, Figure 10 · p. 15

APPENDIX A POINTWISE ROBUSTIFICATION BASELINE (R-DPCBF)

The appendix gives a sufficient condition for a positive lower bound on Λ and describes a pointwise robustified DPCBF baseline that retains the nominal quadratic-program structure.

APPENDIX A POINTWISE ROBUSTIFICATION BASELINE (R-DPCBF)

  • The R-DPCBF baseline treats obstacle inputs in capability set F as disturbances acting on the DPCBF barrier rate.Because the barrier depends on relative velocity, it has relative degree one with respect to obstacle inputs.Source: Appendix A · p. 16
  • Bounding the obstacle disturbance below by −m(x) yields a robust barrier-rate constraint that remains affine in control and preserves the DPCBF quadratic-program structure.Here m(x) = a_obs,max∥∇_v_o h∥ + ω_obs,max|∂h/∂θ_o|.Source: Appendix A · p. 16

APPENDIX B ADDITIONAL THEORETICAL PROOFS

  • When k_μd_max < 2v_rel,min, Λ_min is bounded below by 1 − Σ+ > 0, with Σ+ = (k_μd_max)^2/(4v_rel,min^2).The result assumes λ* and μ* are nonnegative on B, as specified under condition (28).Source: Appendix B · p. 16
  • The proof uses the boundary condition h*=0 to show relative longitudinal velocity is nonpositive, then bounds a concave quadratic using k_μd_max < 2v_rel,min.The quadratic’s maximum occurs at χ* = −k_μd/(2∥v_rel∥), yielding the bound used for Λ.Source: Appendix B · p. 16
Loading 2609.37126v1…