PaperlayerView exact revision on arXiv

Source-linked AI summary

Backup Control Barrier Functions: Formulation and Comparative Study

Yuxiao Chen, Mrdjan Jankovic, Mario Santillo, Aaron D. Ames

arXiv:2104.11332v1eess.SYcs.SYmath.OC

TL;DR

CBF-QP feasibility requires a control invariant set, while existing approaches face limitations in computation or rely on heuristics and tuning. This paper presents backup CBFs, which implicitly represent such sets using a fixed backup policy, and studies their relative degree and performance against benchmarks. It reports that the induced set can be close to the maximum control invariant set under a well-chosen policy in many practical problems.

  • Problem

    Computing control invariant sets is difficult, while existing CBF approaches lack a generic limited-input feasibility guarantee and face relative-degree challenges.

    Source: §I · p. 1

  • Method

    The paper presents backup CBFs, which implicitly represent a control invariant set induced by a fixed backup policy and evaluate it through online dynamics integration.

    Source: §I · p. 2, A. Control barrier functions · p. 2

  • Results

    The induced control invariant set is close to the maximum control invariant set under a properly chosen backup policy in many practical problems.

    Source: §V · p. 7

  • Takeaways & Limitations

    Backup CBFs are more scalable than benchmark methods with explicitly computed invariant sets, apply to general nonlinear dynamics, and have relative degree 1 under mild assumptions.

    Source: §V · p. 7

Abstract

from arXiv · show

The backup control barrier function (CBF) was recently proposed as a tractable formulation that guarantees the feasibility of the CBF quadratic programming (QP) via an implicitly defined control invariant set. The control invariant set is based on a fixed backup policy and evaluated online by forward integrating the dynamics under the backup policy. This paper is intended as a tutorial of the backup CBF approach and a comparative study to some benchmarks. First, the backup CBF approach is presented step by step with the underlying math explained in detail. Second, we prove that the backup CBF always has a relative degree 1 under mild assumptions. Third, the backup CBF approach is compared with benchmarks such as Hamilton Jacobi PDE and Sum-of-Squares on the computation of control invariant sets, which shows that one can obtain a control invariant set close to the maximum control invariant set under a good backup policy for many practical problems.

I. INTRODUCTION

CBF QPs need control invariant sets for guaranteed feasibility, but computing these sets is difficult, and existing workarounds may rely on unrealistic assumptions or tuning. Backup CBFs use a fixed backup policy to implicitly represent an invariant set, while the paper introduces the CBF conditions underlying that approach.

I. INTRODUCTION

  • Control invariant sets can guarantee CBF-QP feasibility, but their computation is difficult, with Hamilton–Jacobi PDE methods typically limited to systems of at most four state dimensions.Minkowski operations, robust linear programming, and Sum-of-Squares methods also do not scale well for even some linear or polynomial systems.Source: §I · p. 1
  • Without an invariant set, existing feasibility workarounds rely on assumptions such as infinite actuation or direct velocity control, and may fail in highly dynamic applications.The authors report no generic limited-input method guaranteeing CBF-QP feasibility without a control invariant set.Source: §I · p. 1
  • Backup CBFs extend a small known invariant set using a fixed backup policy, implicitly representing the resulting set while requiring online dynamics integration.The resulting set is typically not the maximum control invariant set.Source: §I · pp. 1–2

A. Control barrier functions

  • A valid CBF's nonnegative set is control invariant, and its invariance condition is what guarantees feasibility of the supervisory CBF QP.A CBF candidate satisfies the first two CBF conditions; a valid CBF satisfies all three.Source: A. Control barrier functions · p. 2

B. Double integrator example

In the double-integrator example, the position constraint alone gives a relative-degree-two candidate whose nonnegative set is not invariant under limited input. Combining the constraint with minimum stopping distance yields a backup CBF that supports a feasible online QP.

B. Double integrator example

  • The position-only candidate h0 has relative degree 2 and is not control invariant: at the boundary with positive velocity, limited input cannot prevent crossing into the danger set.This failure occurs because inertia can carry the state across the safety boundary before the input stops it.Source: B. Double integrator example · p. 2
  • The valid CBF combines the safety constraint with minimum stopping distance, so maximum deceleration can bring any state with h(x) ≥0 to rest without violating the constraint.The backup policy takes the system to the small invariant set S0 = {x|v = 0}.Source: B. Double integrator example · p. 2
  • For more complicated dynamics, a backup-policy-induced CBF can be obtained without a closed form, and its online CBF QP is guaranteed feasible.The guarantee follows from the valid CBF construction described for the approach.Source: B. Double integrator example · pp. 2–3

C. Notation and preliminaries

The preliminaries define the closed-loop flow map under a policy and establish how it changes with time and initial state. These flow properties support the later backup-CBF derivation.

C. Notation and preliminaries

  • For policy π, the closed-loop dynamics are fπ(x) = f(x) + g(x)π(x), and Φfπ(x0,t) denotes the state reached after time t from x0 under those dynamics.Because the system is time invariant, the initial time does not affect the flow map, which is additive in time.Source: C. Notation and preliminaries · p. 3
  • The flow map's time derivative is the closed-loop vector field evaluated at the flowed state: ∂tΦfπ(x0,t) = fπ(Φfπ(x0,t)).This is the derivative along the backup-policy dynamics.Source: C. Notation and preliminaries · p. 3
  • Differentiating the flow map with respect to its initial state and then time yields a relation used in deriving the CBF condition.The paper identifies this derivative fact as key to the derivation.Source: C. Notation and preliminaries · p. 3
  • Following the backup policy leaves the flow unchanged over time when the current state itself follows that policy.This is the stated physical interpretation of the flow-map proposition.Source: C. Notation and preliminaries · p. 3

III. BACKUP CBF

The section presents the backup CBF approach step by step, with Fig. 2 illustrating how a backup policy can enlarge a known invariant set.

III. BACKUP CBF

  • The section presents the backup CBF approach step by step.Source: §III · p. 3
  • Fig. 2 depicts enlargement of a known control invariant set S0 using backup policy π.The figure caption identifies the set and policy involved in the enlargement.Source: Figure 2 · p. 3

A. Definition and CBF QP

The backup policy defines a constrained reachable set that enlarges a known invariant set while keeping trajectories inside the safe region. Its minimum-based barrier supports a sufficient QP condition that is feasible for states in the set under the stated assumption.

A. Definition and CBF QP

  • For any T > 0, states whose backup-policy trajectories stay in C and reach S0 form an invariant set S with S0 ⊆ S ⊆ C.The set is constructed by extending a known invariant set under the backup controller.Source: A. Definition and CBF QP · p. 3
  • Increasing the horizon T monotonically enlarges the constrained reachable set in the set-inclusion sense.Applying the reachability construction for successive durations is equivalent to using their summed duration.Source: A. Definition and CBF QP · pp. 3–4
  • The barrier h represents S through its zero-level set, taking the minimum of safe-region constraints along the backup trajectory and the terminal-set constraint.Membership requires satisfying the safe-region condition throughout the horizon and reaching S0 at its end.Source: A. Definition and CBF QP · p. 4
  • Because h may be nondifferentiable and its CBF condition may be nonconvex in the input, the paper enforces the condition at every time τ as a sufficient alternative.Proposition 2 establishes that these constraints imply the original condition ˙h + α(h) ≥ 0.Source: A. Definition and CBF QP · p. 4
  • When the continuous-time minimum is difficult to evaluate, a finite set of times can approximate it, with error bounded using flow-map Lipschitz constants.The sampled times span the interval from t to t + T.Source: A. Definition and CBF QP · p. 4
  • Under Assumption 1, the backup CBF QP is always feasible for states with h ≥ 0.The backup policy supplies a feasible input for the constraints at those states.Source: A. Definition and CBF QP · pp. 3–4

B. Relative degree of backup CBFs

The backup CBF has relative degree one under local weak controllability and a nonconstant-function condition, apart from singular points. This avoids requiring high-order extensions or backstepping.

B. Relative degree of backup CBFs

  • Under local weak controllability, h composed with the backup-policy flow has relative degree 1, apart from singular points, for all t > 0.The result assumes h is not constant on any subset with non-empty interior.Source: B. Relative degree of backup CBFs · p. 5
  • The proof argues that a neighborhood where the input Lie derivative vanishes would contradict local weak controllability and the assumption that h is nonconstant on every set with non-empty interior.It uses the flow map to carry an accessible set with non-empty interior into such a contradiction.Source: B. Relative degree of backup CBFs · p. 5
  • The paper cannot establish relative degree one for the min-based CBF in (10), but says its QP can be solved as if it has that degree when hS and hC meet the nonconstancy condition.The QP constraints apply to the flow-composed hC terms and the terminal hS term.Source: B. Relative degree of backup CBFs · p. 5
  • The relative-degree-one property applies to the backup-flow composition, which bridges potentially high-relative-degree hC and hS with the input dynamics.The paper states this avoids high-order extension or backstepping.Source: B. Relative degree of backup CBFs · p. 5

IV. COMPARATIVE STUDY

The comparative study assesses how conservative the backup CBF’s induced control invariant set is against Hamilton–Jacobi and Sum-of-Squares benchmarks. It uses the HJ result as a close approximation of the maximum control invariant set and matches the backup controller for SOS.

IV. COMPARATIVE STUDY

  • The study measures backup CBF conservatism by the size of its induced control invariant set and compares it with HJ and SOS results.The HJ result is described as a close approximation of the maximum control invariant set.Source: §IV · p. 5
  • For sufficiently large t, the limit of the HJ value function is an inner approximation of the maximum control invariant set.At time t, the nonnegative set of h(x,t) is the backward reachable set.Source: §IV · p. 6
  • The SOS benchmark computes a valid CBF under a fixed controller, using the same backup controller as the backup CBF for fairness.The HJ formulation follows and is computed with the level-set toolbox; SOS follows,.Source: §IV · pp. 5–6

A. Lane keeping with Dubin’s car model

The lane-keeping comparison evaluates the backup CBF and SOS under a Dubin’s car model, then compares their invariant sets with the HJ result. The backup set is smaller than HJ but can become almost identical with a more aggressive backup policy.

A. Lane keeping with Dubin’s car model

B. Aeroplane avoidance

The aeroplane-avoidance example assumes plane b maintains a fixed orientation and compares danger sets for HJ PDE and a simple backup policy. The two sets are almost identical.

B. Aeroplane avoidance

C. Computation

The computation-time comparison spans backup CBF, HJ-based CBF, and SOS-based CBF, but the paper says the comparison is not strictly fair because offline and online costs differ. In backup CBF, QP solving dominates its online computation, and the approach is demonstrated on a 16-dimensional quadrotor model.

C. Computation

  • The computation-time comparison is not strictly fair: backup CBF avoids offline computation but has more complicated online computation than normal CBF QP.Source: C. Computation · p. 6
  • Backup CBF's QP time is 1 magnitude larger than solving the CBF QP with explicit form; integration time is relatively small.The backup QP enforces its condition over every τ in [t, t + T], using a sequence of τi in practice, which increases the number of constraints.Source: C. Computation · p. 6
  • Table I compares computation time for backup CBF, HJ-based CBF, and SOS-based CBF.Source: Table I · p. 7
  • The backup CBF was implemented on a 16-dimensional quadrotor model with a reasonable loop rate, beyond the stated dimensional limits of HJ and SOS.Source: C. Computation · p. 7

V. CONCLUSION

The conclusion presents backup CBF as a tutorial approach compared with HJ PDE and SOS benchmarks. It reports near-maximum control-invariant sets under suitable backup policies, greater scalability, and relative degree 1 under mild assumptions.

V. CONCLUSION

  • The implicit control-invariant set can be close to the maximum under a properly chosen backup policy in many practical problems; backup CBF is more scalable than explicit-set benchmarks and applies to general nonlinear dynamics.Source: §V · p. 7
  • Backup CBF has relative degree 1 under mild assumptions, making it a better choice than high-order CBFs that lack a feasibility guarantee.Source: §V · p. 7
Loading 2104.11332v1…