Control Barrier Function Based Quadratic Programs for Safety Critical Systems

Aaron D. Ames, Xiangru Xu, Jessy W. Grizzle, Paulo Tabuada

Seminal September 2016

TL;DR Turns barrier-function safety conditions into constraints that are linear in the control input and solves them together with a relaxed control Lyapunov function in a quadratic program, so safety is a hard constraint and performance a soft one. In simulated lane keeping the car stays within 0.9 m of the lane center at no more than 0.3 g lateral acceleration.

What they do

The paper defines two barrier-function conditions that certify forward invariance of a safe set, turns them into control barrier functions (CBFs) that are affine constraints on the input, and combines them with control Lyapunov functions (CLFs) in a quadratic program (QP) solved at each state. Safety is a hard constraint and the CLF is relaxed, so safety and performance need not be satisfiable at the same time. Demonstrated in simulation on adaptive cruise control (ACC) and lane keeping.

How it works

Two barrier types. A reciprocal barrier B grows to infinity at the boundary and must satisfy dB/dt ≤ α(1/B); a zeroing barrier h vanishes there and must satisfy dh/dt ≥ −α(h). Unlike the earlier dB/dt ≤ 0 or dh/dt ≥ 0, these leave the barrier free far from the boundary. For a compact set, admitting a zeroing barrier is necessary and sufficient for invariance.
CBF-CLF QP. For control-affine dynamics both conditions are linear in u. The QP minimizes a quadratic cost over u and a CLF slack under the relaxed CLF constraint, the hard CBF constraint and input bounds. Without input bounds and with a relative-degree-one barrier, the solution is locally Lipschitz, in closed form.
Force-aware barriers. For ACC, the safe set contains only states from which the car can keep its time headway while braking at no more than 0.25 g, even if the lead car brakes at its maximum. Lane keeping uses a similar barrier on lateral position and velocity with a 0.3 g limit.

Results

ACC with a 22 m/s desired speed: the QP without force limits keeps the headway but exceeds the comfort acceleration bounds. The force-limited QP satisfies both for all time, braking earlier; the optimal barrier allows closer following than the conservative one.
Zeroing CBFs also satisfy all constraints and, in the authors’ limited experience, give a smoother input than reciprocal ones.
Lane keeping on a curved road at 27.7 m/s: displacement stays within 0.9 m and lateral acceleration within 0.3 g.

Limitations

Simulation only, on a point-mass car-following model and a linear lateral model at constant speed. Lipschitz continuity is not guaranteed once input bounds enter the QP, the higher-relative-degree construction fails under input constraints, and the force-aware barriers are derived by hand for each problem.

Figures

From Figure 2: Adaptive cruise control with the QP that has no force limits. Left, speeds of the lead and controlled ... — From Figure 2: Adaptive cruise control with the QP that has no force limits. Left, speeds of the lead and controlled car with the desired speed dashed; middle, acceleration as a fraction of g, which leaves the dashed comfort bounds; right, the headway constraint, positive when satisfied.

From Figure 3: The lane-keeping safe set projected onto lateral position and lateral velocity lies between the upper ... — From Figure 3: The lane-keeping safe set projected onto lateral position and lateral velocity lies between the upper and lower curves; the in-lane subset is bounded by the dotted lines at plus and minus y_max. On those edges the car always moves back toward the center, so keeping the larger set invariant keeps the car in its lane.

From Figure 4: Speed of the lead car (red) and of the controlled car under the QP without force limits (blue) and the... — From Figure 4: Speed of the lead car (red) and of the controlled car under the QP without force limits (blue) and the force-limited QP with the conservative (black) or optimal (cyan) barrier; the dashed line is the desired speed.

From Figure 6: Lane keeping with the QP controller: lateral displacement stays within 0.9 m (left), lateral accelerat... — From Figure 6: Lane keeping with the QP controller: lateral displacement stays within 0.9 m (left), lateral acceleration within 0.3 g (middle), and the barrier function stays positive (right).

Abstract

Safety critical systems involve the tight coupling between potentially conflicting control objectives and safety constraints. As a means of creating a formal framework for controlling systems of this form, and with a view toward automotive applications, this paper develops a methodology that allows safety conditions -- expressed as control barrier functions -- to be unified with performance objectives -- expressed as control Lyapunov functions -- in the context of real-time optimization-based controllers. Safety conditions are specified in terms of forward invariance of a set, and are verified via two novel generalizations of barrier functions; in each case, the existence of a barrier function satisfying Lyapunov-like conditions implies forward invariance of the set, and the relationship between these two classes of barrier functions is characterized. In addition, each of these formulations yields a notion of control barrier function (CBF), providing inequality constraints in the control input that, when satisfied, again imply forward invariance of the set. Through these constructions, CBFs can naturally be unified with control Lyapunov functions (CLFs) in the context of a quadratic program (QP); this allows for the achievement of control objectives (represented by CLFs) subject to conditions on the admissible states of the system (represented by CBFs). The mediation of safety and performance through a QP is demonstrated on adaptive cruise control and lane keeping, two automotive control problems that present both safety and performance considerations coupled with actuator bounds.

Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.

Matt Strong