#  Characterization of a high bandwidth readout chain for the CMS Phase-2
pixel upgrade

C. Smith

###### Abstract

The CMS collaboration is building a new inner tracking pixel detector for the
High-Luminosity LHC. Each pixel readout chip will be controlled with a single
serial input stream at 160 $\mathrm{Mb}/\mathrm{s}$ and will send out data via
four current mode logic (CML) 1.28 $\mathrm{Gb}/\mathrm{s}$ outputs. The
readout chips will be grouped in modules and connected with up to 1.6 meters
long low-mass electrical links to Low-Power Gigabit Transceivers (lpGBT) and
Versatile Link PLUS Transceiver (VTRx+) modules that send the data optically
to off-detector electronics at 10 $\mathrm{Gb}/\mathrm{s}$. The
characterization of these components and system tests of the readout chain are
presented.

##  1 Introduction

In preparation for the High-Luminosity LHC (HL-LHC) [1], the CMS Tracker will
be fully replaced in the Phase-2 upgrade [2, 3, 4]. The new inner tracker will
have about two billion silicon pixels installed, and hybrid pixel modules will
process sensor data using a custom readout chip initially developed by the
RD53 collaboration [5]. Each readout chip on the detector needs a control link
to receive trigger, clock, commands, and settings from off-detector
electronics as well as data links to send pixel data to off-detector
electronics. The high bandwidth control and data links are split into two
stages: electrical links and optical links. System tests of these electrical
and optical links are presented.

##  2 Data Readout Chain

An overview of the data readout chain for the inner tracker is shown in Figure
1. High bandwidth electrical and optical links are used to establish control
and data links between pixel modules on the CMS detector and Data Trigger
Control (DTC) boards in the counting room. Low-mass electronic links (e-links)
up to 1.6 meters long provide 160 $\mathrm{Mb}/\mathrm{s}$ control links
(downlinks) and 1.28 $\mathrm{Gb}/\mathrm{s}$ data links (uplinks) between
pixel modules and portcards. Optical fibers connect portcards, which are
mounted on the support structure inside the detector, to DTC boards in the
counting room to establish 2.5 $\mathrm{Gb}/\mathrm{s}$ control links
(downlinks) and 10 $\mathrm{Gb}/\mathrm{s}$ data links (uplinks). The
portcards each carry three Low-Power Gigabit Transceivers (lpGBT) [6] and
three Versatile Link PLUS Transceiver (VTRx+) modules [7]. The lpGBTs
communicate with the pixel modules via electrical links, and the VTRx+ modules
establish optical links with the DTC boards.

Figure 1:  System readout architecture for the inner tracker [4]. Pixel
modules communicate with portcards through e-links. Portcards communicate with
Data Trigger Control (DTC) boards through optical links.

##  3 Electrical Links

The electrical link (e-link) bundles are created using low mass, small
diameter twisted pair cables. One end of a twisted pair electrical link bundle
is shown in Figure 2. E-link bundles are made to connect to modules and
provide each module with one control link twisted pair and multiple data link
twisted pairs. Each twisted pair is produced using two 36 American Wire Gauge
(AWG) copper core (127 $\upmu\mathrm{m}$ in diameter) wires surrounded by
polyimide insulation (45 $\upmu\mathrm{m}$ thick) that are twisted together
with 4 twists per inch. The pairs are soldered to small, 20 $\upmu\mathrm{m}$
thick PCBs that can plug into Molex connectors with 300 $\upmu\mathrm{m}$
pitch [8]. To improve durability and handling, the soldered wires are secured
with a non-conductive epoxy, and then the bundle is lashed together using
polyimide braiding.

Figure 2:  One end of an electrical link (e-link) bundle that has five twisted
pair channels: one channel for a control link and four channels for data
readout.

Prototype low-mass electrical links are characterized using a series of
measurements. The signal quality is assessed using eye diagrams, which overlay
transitions between binary states from repeated measurements of the signal
over a time interval. Bit error rate scans are used to characterize signal
integrity across e-links. To reliably readout pixel detector data, the e-links
need to support error rates of less than $10^{-13}$ for signals at 1.28
$\mathrm{Gb}/\mathrm{s}$. Cross talk effects from channels within an e-link
bundle (internal) and from multiple bundles (external) are studied.

To test error rates over e-links, an RD53 chip on a Single Chip Card (SCC) is
read out over e-links using an FC7 mezzanine card [9], as shown in Figure 3.
E-links of two gauges (34 and 36 AWG) and different lengths (from 0.35 to 2.0
meters) are used in the readout chain. Bit error rates are determined using a
pseudorandom binary sequence (PRBS) that is sent at 1.28
$\mathrm{Gb}/\mathrm{s}$ from the RD53 chip to the FC7 mezzanine card. The
amplitude of the PRBS signal is varied using the 10-bit “TAP0” pre-emphasis
setting, which controls the amplitude of the signal output by the current mode
logic (CML) driver on the RD53 chip. For this test, the amplitude is increased
until the bit error rate of $10^{-11}$ is reached. Longer e-links require a
larger signal amplitude to maintain a given bit error rate. Good performance
is seen for e-links up to 2.0 meters. A different hardware setup with a KC705
has been used to demonstrate bit error rates of less than $10^{-13}$, but
longer tests using the RD53 chip are needed to reach this same target.

Figure 3:  Measurement of signal amplitudes (set by TAP0) on e-links for a
fixed bit error rate. In the hardware setup (left), an FC7 mezzanine card is
connected to an SCC through two commercial display port cables, an adapter
board, and an e-link bundle for control and readout of an RD53 chip. The
measurements (right) show the TAP0 setting to achieve a bit error rate of
$10^{-11}$ for e-links of different lengths and gauges.

Furthermore, an external crosstalk measurement for e-link bundles was
performed, and the results are shown in Figure 4. To mitigate the effect of
external crosstalk from a large aggressor amplitude, the victim amplitude set
by TAP0 only requires a small increase. Thus, external crosstalk from the
single aggressor e-link bundle has a small effect on readout over the victim
e-link bundle.

Figure 4:  Measurement of the effect of external crosstalk on data
transmission across e-link bundles. Two e-link bundles (1.4 meters, 36 AWG)
are twisted together (left), with a victim e-link bundle connected between an
FC7 mezzanine card and SCC to read from an RD53 chip, and an aggressor e-link
bundle connected to a KC705. The KC705 sends PRBS signals on four e-link
channels on the aggressor at different amplitudes.

Radiation testing was performed to determine if e-links can maintain
performance up to the design specification of 1500 Mrad. Two different
epoxies, Araldite 2011 (Ref. [10]) and UR6060 (Ref. [11]), were used for
e-links that underwent radiation testing. After 1300 Mrad, the Araldite 2011
epoxy showed significant darkening, while the UR6060 epoxy remained
transparent. The signal integrity on e-links remained good after radiation.
The polyimide braiding used for lashing becomes brittle after 1900 Mrad, but
this should not affect the electrical readout.

##  4 Portcards

The portcards convert electrical signals from on-detector readout chips to
optical signals for off-detector DTC boards (see Figure 1). Dedicated setups
with the portcards reading out SCCs with short coaxial cables have been used
to test the prototype portcards and validate the optical part of the readout
chain. A measurement of the optical links using the lpGBT eye opening monitor
[6] was performed in which the high-speed input to the lpGBT is compared to an
adjustable threshold voltage by a comparator sampled with a phase interpolated
clock. Transitions of the comparator are counted, giving a “toggle count.”
Within the eye, a large number of transitions are expected, and outside of the
eye, approximately half as many transitions are expected. Data from this
measurement are shown in Figure 5. The vertical axis is scaled such that
regions with no transitions are not shown. The high toggle count region is
large and corresponds to a large eye diagram and a strong optical signal.

Figure 5:  Eye opening monitor from an lpGBT for the 2.56
$\mathrm{Gb}/\mathrm{s}$ optical down link with equalization parameters at
default settings. The vertical axis is an encoded voltage threshold, and the
horizontal axis is an encoded sampling phase. The color scale shows the number
of transitions (toggle count). The plot is scaled vertically to show the eye
opening region, and the regions without transitions are not shown. The regions
with high toggle count correspond to the eye opening.

In addition, the electrical link receivers on the lpGBT are being studied. In
one measurement, the signal source is a PRBS7 generator in the RD53 readout
chip. This signal is sent over a commercial display port cable, an adapter
board, and a commercial Molex FPC cable (Ref. [12]) to be received by an
lpGBT. The signal is compared to an internal error checker on the lpGBT. The
bit error rate is measured as a function of clock sampling phase and
equalization setting, and the results are provided in Figure 6. The region
with a bit error rate of $9.3*10^{-10}$ corresponds to zero errors for the
total number of bits checked ($1.07*10^{9}$). Low error rates on the lpGBT
electrical link receivers are achieved by tuning the sampling phase, and
changing the equalization setting has only a small effect on the timing.

Figure 6:  Scan of bit error rate vs. clock sampling phase and equalization
setting for electrical port receivers on the lpGBT driven by the RD53 pixel
readout chip. The number of bits checked at each setting is $1.07*10^{9}$.
Points in green have zero observed errors and report $9.3*10^{-10}$, which is
the reciprocal of the number of bits checked.

##  5 Conclusion

Various system tests have been performed for the new pixel readout chain.
Electrical links provide stable connectivity at the required lengths, and
crosstalk has a small effect on signal quality. Low bit error rates
($10^{-11}$) over e-links are observed, but longer tests with the RD53 chip
are needed to achieve the target error rate ($10^{-13}$). Conversion from
electrical to optical links is working well, and the optical links have good
performance. These results form an important input to the final design,
production, and testing of components for the pixel detector readout chain.

## Acknowledgments

The authors would like to thank the National Science Foundation for funding
this research.

## References

  * [1] G. Apollinari, O. Brüning, T. Nakamoto and L. Rossi, _Chapter 1: High Luminosity Large Hadron Collider HL-LHC_ , _CERN Yellow Report_ (2017) 1 [1705.08830].
  * [2] CMS collaboration, _The CMS experiment at the CERN LHC_ , _Journal of Instrumentation_ 3 (2008) S08004.
  * [3] CMS collaboration, _The Phase-2 Upgrade of the CMS Tracker_ , Tech. Rep. CERN-LHCC-2017-009, CMS-TDR-014, CERN, Geneva (Jun, 2017).
  * [4] S. Orfanelli, _The phase 2 upgrade of the CMS inner tracker_ , _Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment_ 980 (2020) 164396.
  * [5] RD53 collaboration, _The RD53A Integrated Circuit_ , Tech. Rep. CERN-RD53-PUB-17-001, CERN, Geneva (Oct, 2017).
  * [6] lpGBT collaboration, _lpGBT Manual_ , 2021.  https://lpgbt.web.cern.ch/lpgbt.
  * [7] C. Soós, S. Détraz, L. Olanterä, C. Sigaud, J. Troska, F. Vasey et al., _Versatile link PLUS transceiver development_ , _Journal of Instrumentation_ 12 (2017) C03068.
  * [8] Molex, “0.30mm pitch easy-on back flip FPC connector, part 5025984593.”  https://www.molex.com/molex/products/part-detail/ffc_fpc_connectors/5025984593.
  * [9] CERN, “FC7.”  https://espace.cern.ch/project-FC7/SitePages/Home.aspx.
  * [10] Huntsman, “Araldite 2011.”  https://www.huntsman.com/products/araldite2000/araldite-2011.
  * [11] E. Adhesives, “UR6060.”  https://www.ellsworth.com/products/encapsulants/polyurethane/resinlab-ur6060-polyurethane-encapsulant-clear-50-ml-cartridge.
  * [12] Molex, “Molex FPC cable jumper.”  https://www.molex.com/molex/products/family/premoflex?parentKey=ffc_fpc_connectors.


# Verification and Synthesis of Control Barrier Functions

Andrew Clark The author is with the Department of Electrical and Computer
Engineering, Worcester Polytechnic Institute, 100 Institute Road, Worcester,
MA, USA 01609. Email<EMAIL_ADDRESS>
###### Abstract

Control systems often must satisfy strict safety requirements over an extended
operating lifetime. Control Barrier Functions (CBFs) are a promising recent
approach to constructing simple and safe control policies. This paper proposes
a framework for verifying that a CBF guarantees safety for all time and
synthesizing CBFs with verifiable safety in polynomial control systems. Our
approach is to show that safety of CBFs is equivalent to the non-existence of
solutions to a family of polynomial equations, and then prove that this non-
existence is equivalent to a pair of sum-of-squares constraints via the
Positivstellensatz of algebraic geometry. We develop this Positivstellensatz
to verify CBFs, as well as generalization to high-degree systems and multiple
CBF constraints. We then propose a set of heuristics for CBF synthesis,
including a general alternating-descent heuristic, a specialized approach for
compact safe regions, and an approach for convex unsafe regions. Our approach
is illustrated on two numerical examples.

##  I Introduction

Safety is a critical property of cyber-physical systems in applications
including autonomous vehicles [1], energy [2], and medicine [3]. In the
control-theoretic context, safety is typically defined as ensuring that the
state trajectory remains within a given safe region (or, equivalently, avoids
a given unsafe region) for all time. It is not always possible, however, to
guarantee safety by introducing a control input, even for controllable systems
without actuation constraints. This has motivated substantial research into
characterizing the set of states from which safety can be guaranteed, and
constructing controllers that ensure safety from those states [4].

Control Barrier Functions (CBFs) are a promising recent approach to safe
control. CBFs are functions of the system state that are negative outside the
safe region, so that safety can be guaranteed by ensuring that the CBF remains
nonnegative. In particular, it has been shown that, if the control input
satisfies a particular linear constraint induced by the CBF for all time, then
safety is ensured [5]. CBFs have been generalized to high-degree [6],
stochastic [7, 8], and uncertain [9, 10] systems, and applied in diverse
domains such as bipedal locomotion [11], automotive control [12, 13], and UAVs
[14, 15].

While there is a large body of work on proving safety given CBF-induced linear
control constraints, the problem of verifying whether such constraints can
always be satisfied has received less attention. While constraint satisfaction
is guaranteed for fully-actuated systems, the more general case remains open.
Recent approaches have been proposed that consider finite time horizons [8,
16] or assume that the control input is a “backup controller”, however, such
methods may be conservative. A systematic approach to verification of CBFs, as
well as synthesizing CBFs with provable guarantees on safety, would enable
broader adoption of CBFs as well as construction of CBFs with minimal
performance trade-off.

In this paper, we develop a framework for verification and synthesis of CBFs
for polynomial control systems. Our approach is based on the fact that the
safety guarantees rely on two properties. First, there should be no point on
the boundary of the CBF for which the Lie derivative of the CBF is always
negative. Second, the safe region of the CBF should be contained within the
overall safe region. We show that both conditions can be expressed as the non-
existence of solutions to polynomial equations, which can then be mapped to a
set of sum-of-squares inequalities via the Positivstellensatz [17]. This
Positivstellensatz mapping allows verification of CBFs via semidefinite
programming and construction of CBFs. Our specific contributions are as
follows:

  * •

We develop a SOS program for verifying that a given CBF construction ensures
safety. We extend this approach to high-order CBFs and systems with multiple
CBF constraints.

  * •

We propose an alternating-descent heuristic for synthesizing CBFs using the
proposed conditions.

  * •

We consider special cases of our approach, including compact safe regions, and
constraints where the unsafe region is a union of non-overlapping convex sets.

  * •

We evaluate our approach through a numerical study.

This paper is organized as follows. Section II presents related work. Section
III gives preliminary results. Section IV gives our problem formulation and
CBF verification approach. Section V presents our approach to CBF synthesis.
Section VI contains numerical results. Section VII concludes the paper.

##  II Related Work

CBFs were initially proposed in [12] and further developed in [11]. Extensions
of CBFs to high-degree [18, 6], stochastic [7], Euler-Lagrange [19, 20],
uncertain [21], and hybrid [22] systems have been proposed. Minimal CBFs were
proposed in [23]. CBFs with actuation constraints were investigated in [15].
Most of these works provide safety guarantees under the assumption that a CBF
satisfying given safety and reachability properties exists, or derive CBFs
from a priori known backup controllers. Hence, they are complementary to the
present paper, which investigates synthesis and verification of CBFs.

Some recent works have investigated the problem of constructing CBFs from the
point of view of _abstraction-free synthesis_ , in which a higher-level
specification (e.g., a temporal logic formula) is implemented by a sequence of
control actions, each represented by one or more CBFs [24, 8, 16, 25, 26].
These approaches are distinct from this paper; in particular, they focus on
safety over finite time horizons, as opposed to the positive set invariance
guarantees provided in this paper. Sum-of-squares optimization techniques for
safety verification, including SOS methods for barrier certificate
construction, have been proposed [27].

The problem of identifying positive invariant sets and characterizing states
from which safety can be guaranteed has received extensive interest [4, 28].
Other related methods include HJB equations [29] and Lyapunov analysis [30].
The results presented in this paper on verification of safety and synthesis of
safe control policies, however, have not appeared in the existing literature.
The problem of avoiding convex obstacles (considered in Section V-C of this
paper) has been studied, e.g., in [31], where it was shown that the obstacles
can be avoided through a separating hyperplane construction. CBF-based
policies for guaranteed convex obstacle avoidance, however, have not been
proposed.

##  III Preliminaries and Background

In this section, we define sum-of-squares polynomials and provide background
on the Positivstellensatz. A sum-of-squares (SOS) polynomial is a polynomial
$f(x)$ such that

$f(x)=\sum_{i=1}^{m}{g_{i}(x)^{2}}$

for some polynomials $g_{1}(x),\ldots,g_{m}(x)$. Selecting coefficients of
$f(x)$ to ensure that $f(x)$ is a sum-of-squares can be formulated as a
semidefinite program, a procedure known as sum-of-squares optimization [32].

The Positivstellensatz gives necessary and sufficient conditions for a set of
polynomial constraints to have a real solution. It is stated as follows.

######  Theorem 1 (Positivstellensatz [17])

Consider a collection of polynomials $\\{f_{j}:j=1,\ldots,r\\}$,
$\\{g_{i}:i=1,\ldots,m\\}$, and $\\{h_{k}:k=1,\ldots,s\\}$. Then the set

$\left(\bigcap_{j=1}^{r}{\\{x:f_{j}(x)\geq
0\\}}\right)\cap\left(\bigcap_{i=1}^{m}{\\{x:g_{i}(x)=0\\}}\right)\\\
\cap\left(\bigcap_{k=1}^{s}{\\{x:h_{k}(x)\neq 0\\}}\right)$

is empty if and only if there exist polynomials $f$, $g$, and $h$ satisfying
(i) $f(x)=\sum_{j=1}^{r}{\alpha_{j}(x)f_{j}(x)}$, where $\alpha_{j}(x)$ is a
sum-of-squares; (ii) $g(x)=\sum_{i=1}^{m}{\eta_{i}(x)g_{i}(x)}$ for some
polynomials $\eta_{1},\ldots,\eta_{m}$, (iii) $h$ is a product of powers of
the $h_{k}$’s, and (iv) $f(x)+g(x)+h(x)^{2}=0$ for all $x$.

We note that we can verify that there does not exist a solution to
$f_{j}(x)\geq 0$, $j=1,\ldots,r$ and $g_{i}(x)=0$, $i=1,\ldots,m$ by choosing
$\\{h_{k}\\}$ as the singleton set $h=1$. The constraint then becomes
$f(x)+g(x)+1=0$ for all $x$.

##  IV Problem Formulation: CBF Verification

This section presents the problem of verifying a safe control policy. We first
state the problem and then give our verification framework.

###  IV-A Problem Statement and Background on CBFs

We consider nonlinear control systems with dynamics

$\dot{x}(t)=f(x(t))+g(x(t))u(t)$ (1)

where $x(t)\in\mathbb{R}^{n}$ denotes the state, $u(t)\in\mathbb{R}^{m}$ is a
control input, and $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ and
$g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ are polynomials. The _safe region_
is defined as $\mathcal{C}=\\{x:h(x)\geq 0\\}$, where
$h:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a polynomial. The boundary of the
safe region, denoted $\partial\mathcal{C}$, is defined by
$\partial\mathcal{C}=\\{x:h(x)=0\\}$. The _viability kernel_ is defined as
follows [33].

###### Definition 1

The viability kernel is a set $\Omega\subseteq\mathcal{C}$ such that, for any
$x_{0}\in\Omega$, there is a control input signal $\\{u(t):t\in[0,\infty)\\}$
that guarantees $x(t)\in\Omega$ for all time $t$ when the initial state is
$x(0)=x_{0}$.

The problem studied in this section is as follows.

###### Problem 1

Given a system (1) and a safety constraint set $\mathcal{C}$, (i) verify
whether a set $\tilde{\Omega}$ is contained in the viability kernel, and (ii)
verify that a given control policy ensures that the system state remains in
the viability kernel.

Note that we do not consider any constraints on the control input $u(t)$
(e.g., limits on actuation). As a first step to our approach, we define
control barrier functions and high-order control barrier functions as follows.

###### Definition 2

A function $b$ is a control barrier function for system (1) if there is a
class-K function $\alpha$ such that, for all $x$ with $b(x)\geq 0$, there
exists $u$ satisfying

$\frac{\partial b}{\partial x}(f(x)+g(x)u)\geq-\alpha(b(x))$ (2)

The following result establishes the safety guarantees provided by CBFs.

######  Theorem 2 ([12])

Suppose that $b$ is a CBF, $b(x(0))\geq 0$, and $u(t)$ satisfies (2) for all
$t$. Then the set $\\{x:b(x)\geq 0\\}$ is positive invariant.

A potential drawback of CBFs occurs in high-degree systems when
$\frac{\partial b}{\partial x}g(x)=0$. High-order CBFs (HOCBFs), defined as
follows, address this weakness.

######  Definition 3 ([6])

For a function $b$, define functions $\psi_{0},\ldots,\psi_{r}$ by

$\displaystyle\psi_{0}(x)$ $\displaystyle=$ $\displaystyle b(x)$
$\displaystyle\psi_{1}(x)$ $\displaystyle=$
$\displaystyle\dot{\psi}_{0}(x)+\alpha_{1}(\psi_{0}(x))$ $\displaystyle\vdots$
$\displaystyle\psi_{r}(x)$ $\displaystyle=$
$\displaystyle\dot{\psi}_{r-1}(x)+\alpha_{r}(\psi_{r-1}(x))$

where $\alpha_{1},\ldots,\alpha_{r}$ are class-K functions. Define set $C_{i}$
by $C_{i}=\\{x:\psi_{i}(x)\geq 0\\}$ for $i=0,\ldots,r$. The functions
$b,\psi_{1},\ldots,\psi_{r}$ define a HOCBF if
$\frac{\partial\psi_{i}}{\partial x}g(x)=0$ for $i<r$ and, for all
$x\in\bigcap_{i=0}^{r}{C_{i}}$, there exists $u$ satisfying

$L_{f}^{r}b(x)+L_{g}L_{f}^{r-1}b(x)u+O(b(x))+\alpha_{m}(\psi_{r-1}(x))\geq 0$
(3)

where $O(b(x))$ denotes lower-order Lie derivatives of $b(x)$.

Throughout the paper, we let $L$ denote the Lie derivative of a function. The
following result establishes the positive invariance of HOCBFs.

######  Theorem 3 ([6])

If $b$ is a HOCBF, then the set $\bigcap_{i=0}^{r}{C_{i}}$ is positive
invariant.

While these results lead to safety guarantees for CBFs and HOCBFs, they do not
provide a procedure for verifying that such an input $u(t)$ exists for all $t$
(Problem 1). We derive such an approach in the next section.

###  IV-B Verification of CBFs

In what follows, we present an SOS-based approach to verifying a CBF and
approximating the viability kernel. We have the following initial result.

###### Proposition 1

The function $b(x)$ is a CBF iff there is no $x$ satisfying $b(x)=0$,
$\frac{\partial b}{\partial x}g(x)=0$, and $\frac{\partial b}{\partial
x}f(x)<0$.

###### Proof:

By Nagumo’s Theorem [4], we have that $b(x(t))\geq 0$ for all $t\geq 0$ iff
$\dot{b}(x(t))\geq 0$ at the boundary, i.e., when $b(x)=0$. Suppose that
$b(x)=0$. If $\frac{\partial b}{\partial x}g(x)\neq 0$, then $u(t)$ can be
chosen to satisfy (2). One feasible choice is to select $i$ with
$\left[\frac{\partial b}{\partial x}g(x)\right]_{i}\neq 0$ and choose

$u_{i}(t)=-\left(\left[\frac{\partial b}{\partial
x}g(x)\right]_{i}\right)^{-1}(\frac{\partial b}{\partial x}f(x)+\alpha(b(x)))$

and $u_{j}(t)=0$ for $j\neq i$. Otherwise, if $\frac{\partial b}{\partial
x}g(x)=0$ and $\frac{\partial b}{\partial x}f(x)\geq 0$, then $\dot{b}(t)\geq
0$. Conversely, if $\frac{\partial b}{\partial x}g(x_{0})=0$, $\frac{\partial
b}{\partial x}f(x_{0})<0$, and $b(x_{0})=0$ for some $x_{0}$, then the set
$\\{b(x)\geq 0\\}$ will not be positive invariant, since $x(t)$ will leave the
set if $x(0)=x_{0}$. ∎

Based on this proposition, we can formulate the following conditions via the
Positivstellensatz.

###### Theorem 4

A polynomial $b(x)$ is a CBF for (1) if and only if there exist polynomials
$\eta(x)$, $\theta_{1}(x),\ldots,\theta_{m}(x)$, SOS polynomials
$\alpha_{0}(x)$ and $\alpha_{1}(x)$, and an integer $r$ such that

$\eta(x)b(x)+\sum_{i=1}^{m}{\theta_{i}(x)\left[\frac{\partial b}{\partial
x}g(x)\right]_{i}}\\\ -\alpha_{0}(x)-\alpha_{1}(x)\frac{\partial b}{\partial
x}f(x)\\\ +\left(\frac{\partial b}{\partial x}f(x)\right)^{2r}=0$ (4)

Moreover, the set $\\{b(x)\geq 0\\}$ is a subset of the viability kernel of
$\mathcal{C}$ if (4) holds and there exist SOS polynomials $\beta_{0}(x)$ and
$\beta_{1}(x)$ and a polynomial $\omega(x)$ such that

$\beta_{0}(x)+\beta_{1}(x)b(x)+w(x)h(x)+1=0$ (5)

###### Proof:

By Proposition 1, we have that $b(x)$ is a CBF iff there is no $x$ satisfying
$b(x)=0$, $\frac{\partial b}{\partial x}g(x)=0$, and $\frac{\partial
b}{\partial x}f(x)<0$. The latter condition is equivalent to $-\frac{\partial
b}{\partial x}f(x)\geq 0$ and $\frac{\partial b}{\partial x}f(x)\neq 0$. These
conditions are equivalent to (4) by Theorem 1.

Now, suppose that (4) holds, and hence $b(x(t))\geq 0$ for all $t$ under any
control policy satisfying (2) for all $t$. It therefore suffices to show that
$b(x(t))\geq 0$ for all $t$ implies that $h(x(t))\geq 0$ for all $t$. If this
is not the case, then there exists a point satisfying $h(x)=0$ and $b(x)\geq
0$. This, however, contradicts (5) by Theorem 1. ∎

Next, we derive equivalent conditions for $\psi_{0}(x),\ldots,\psi_{r}(x)$ to
define a HOCBF.

###### Theorem 5

If $b(x)$ is a polynomial with relative degree $r$ with respect to (1), then
$b(x)$ and $\psi_{0},\ldots,\psi_{r}$ define a HOCBF if and only if there
exist polynomials $\eta(x),\theta_{1}(x),\ldots,\theta_{r}(x)$, SOS
polynomials $\alpha_{0}(x),\alpha_{1}(x)$, and
$\gamma_{0}(x),\ldots,\gamma_{r-1}(x)$, and an integer $s$ such that

$\eta(x)b(x)+\sum_{i=1}^{r}{\theta_{i}(x)L_{g}L_{f}^{r-1}b(x)}\\\
-\alpha_{0}(x)-\alpha_{1}(x)(L_{f}^{r}b(x)+O(b(x)))+\left(L_{f}^{r}b(x)+O(b(x))\right)^{2s}\\\
+\sum_{i=0}^{r-1}{\gamma_{i}(x)\psi_{i}(x)}=0$ (6)

Moreover, the set $\bigcap_{i=0}^{r}{C_{i}}$ is a subset of the viability
kernel if there exist SOS polynomials $\beta_{0}(x),\ldots,\beta_{r+1}(x)$ and
a polynomial $w(x)$ such that

$\sum_{i=0}^{r}{\psi_{i}(x)\beta_{i}(x)}+\beta_{r+1}(x)+w(x)h(x)+1=0.$ (7)

###### Proof:

By Theorem 3, positive invariance of $\\{b(x)\geq 0\\}$ is guaranteed if (6)
holds for some $u$ at each $x\in\bigcap_{i=0}^{r}{C_{i}}$. Such a $u$ exists
if there is no $x$ with $x\in C_{i}$ for all $i=0,\ldots,r$, $\psi_{r}(x)=0$,
$L_{f}^{r-1}L_{g}b=0$, and $L_{f}^{r}b+O(b(x))<0$. This is equivalent to (6)
by Theorem 1.

Now, we want to show that if $x(t)\in C_{i}$ for $i=0,\ldots,r$ and
$h(x(0))\geq 0$, then $h(x(t))\geq 0$ for all $t$ if (7) holds. If (7) holds,
then there is no $x$ satisfying $x\in C_{i}$ for $i=0,\ldots,r$ and $h(x)=0$.
Since $x(t)\in C_{i}$ for all $t$ and $i=0,\ldots,r$, $x(t)$ never reaches the
boundary of $\mathcal{C}$, and hence remains in $\mathcal{C}$ for all time
$t$. ∎

We next consider intersections of CBFs. Such constructions may be useful when
a single CBF is not sufficient to characterize the viability kernel. An
example where such constraints are relevant is when the safe region consists
of the complement of a set of disjoint compact sets, e.g., in an obstacle
avoidance problem where each of the sets represents an obstacle.

###### Theorem 6

Let $b_{1}(x),\ldots,b_{k}(x)$ be a collection of polynomials. There is a
control policy that renders the set $\bigcap_{i=1}^{k}{\\{x:b_{i}(x)\geq
0\\}}$ positive invariant if the following conditions hold:

  1. 1.

For each $i=1,\ldots,k$, there exist polynomials $\eta_{i}(x)$,
$\theta_{i,1}(x),\ldots,\theta_{i,m}(x)$, and SOS polynomials
$\alpha_{i,0}(x)$, $\alpha_{i,1}(x)$,
$\\{\lambda_{ij}(x):j\in\\{1,\ldots,k\\}\setminus\\{i\\}\\}$ such that

$\eta_{i}(x)b_{i}(x)+\sum_{j=1}^{m}{\theta_{i,j}(x)\left[\frac{\partial
b_{i}}{\partial x}g(x)\right]_{j}}+\alpha_{i,0}(x)\\\
-\alpha_{i,1}(x)\frac{\partial b_{i}}{\partial x}f(x)+\sum_{j\neq
i}{\lambda_{ij}(x)b_{j}(x)}+1=0$ (8)

  2. 2.

For each $i,j\in\\{1,\ldots,k\\}$ with $i\neq j$, there exist polynomials
$w_{ij}^{i}(x)$ and $w_{ij}^{j}(x)$ and SOS polynomials $\alpha_{i,j,l}(x)$
for $l=1,\ldots,m$, such that

$-\sum_{l=1}^{m}{\left(\alpha_{i,j,l}(x)\left[\frac{\partial b_{i}}{\partial
x}g(x)\right]_{l}\left[\frac{\partial b_{j}}{\partial
x}g(x)\right]_{l}\right)}\\\
+\alpha_{i,j,0}(x)+w_{ij}^{i}(x)h_{i}(x)+w_{ij}^{j}(x)h_{j}(x)+1=0$ (9)

###### Proof:

We consider a control policy in which the control $u$ is chosen to satisfy (2)
for each of the functions $b_{i}$. Suppose the conditions of the theorem hold.
For each $x(t)$ at the boundary of $\bigcap_{i=1}^{k}{\\{b_{i}(x)\geq 0\\}}$,
define $Z(x)=\\{i:b_{i}(x)=0\\}$. We have the following cases.

_Case I – $Z(x)=\\{i\\}$:_ In this case, Condition (8) implies that there is
no $x\in\bigcap_{j=1}^{k}{\\{b_{j}(x)\geq 0\\}}$ with $b_{i}(x)=0$,
$\frac{\partial b_{i}}{\partial x}g(x)=0$, and $\frac{\partial b_{i}}{\partial
x}f(x)<0$. Hence we can select a $u(t)$ satisfying (2), ensuring that the
state does not leave $\bigcap_{i=1}^{m}{\\{b_{i}(x)\geq 0\\}}$.

_Case II - $|Z(x)|>1$:_ We claim that, if Condition (9) holds, then for all
$i,j\in Z(x)$ and $l=1,\ldots,m$, either $\left[\frac{\partial b_{i}}{\partial
x}g(x)\right]_{l}$ and $\left[\frac{\partial b_{j}}{\partial
x}g(x)\right]_{l}$ have the same sign, or one of them is zero. Indeed,
Condition (9) and the Positivstellensatz imply that there is no point $x$
satisfying $h_{i}(x)=h_{j}(x)=0$ and

$\left[\frac{\partial b_{i}}{\partial x}g(x)\right]_{l}\left[\frac{\partial
b_{j}}{\partial x}g(x)\right]_{l},\ l=1,\ldots,m.$

Hence, for each $i\in Z(x)$, we can select $u$ of sufficient magnitude to
ensure that constraint (2) is satisfied. ∎

Finally, we note that, given multiple CBFs $b_{1}(x),\ldots,b_{k}(x)$ for a
safe region $\mathcal{C}$, the set $\bigcup_{i=1}^{k}{\\{x:b_{i}(x)\geq 0\\}}$
is contained in the viability kernel.

##  V Control Barrier Function Construction

This section gives techniques for constructing control barrier functions. The
problem studied in this section is formulated as follows.

###### Problem 2

Given a system (1) and a safety constraint set $\mathcal{C}$, construct a CBF
(or HOCBF) $b$ that verifiably guarantees positive invariance of
$\mathcal{C}$.

We first present a general heuristic based on sum-of-squares optimization,
followed by approaches for linear systems and compact safe regions, as well as
convex unsafe regions.

###  V-A General Heuristic

Our approach is based on the observation that the CBF conditions of Theorems
4–6 are polynomial constraints, enabling efficient verification when the
candidate CBF $b(x)$ is given. If $b(x)$ is unknown, however, the constraints
are nonlinear and cannot be converted to linear matrix inequalities as in sum-
of-squares optimization. We therefore propose an alternating-descent heuristic
which is described as follows.

We initialize $b^{0}(x)$ arbitrarily, and initialize parameters $\rho_{0}$ and
$\rho^{\prime}$ to be infinite. At step $k$, we solve the following SOS
program with variables $\rho$, $\alpha^{k}(x)$, $\eta^{k}(x)$,
$\theta_{1}^{k}(x),\ldots,\theta_{m}^{k}(x)$, $w(x)$, and $\beta^{k}(x)$

$\begin{array}[]{ll}\mbox{minimize}&\rho\\\
\mbox{s.t.}&\alpha^{k}(x)\frac{\partial b^{k-1}}{\partial
x}f(x)+\sum_{i=1}^{m}{\theta_{i}^{k}(x)\left[\frac{\partial b^{k-1}}{\partial
x}g(x)\right]_{i}}\\\ &+\eta^{k}(x)b^{k-1}(x)+\rho\Lambda(x)-1\in SOS\\\
&-\beta^{k}(x)b^{k-1}(x)+w(x)h(x)-1\in SOS\\\ &\beta^{k}(x),\alpha^{k}(x)\in
SOS\end{array}$ (10)

Here $\Lambda(x)$ is a fixed SOS polynomial of sufficiently large degree to
ensure that the first constraint is SOS for sufficiently large $\rho$. We let
$\rho_{k}$ denote the value of $\rho$ returned by the optimization. The
procedure terminates if $\rho\leq 0$ or if
$|\rho_{k}-\rho_{k-1}^{\prime}|<\epsilon$. Otherwise, we solve the SOS problem
with variables $\rho$ and $b^{k}$ given by

$\begin{array}[]{ll}\mbox{minimize}&\rho\\\
\mbox{s.t.}&\alpha^{k}(x)\frac{\partial b^{k}}{\partial
x}f(x)+\sum_{i=1}^{m}{\theta_{i}^{k}(x)\left[\frac{\partial b^{k}}{\partial
x}g(x)\right]_{i}}\\\ &+\eta^{k}(x)b^{k}(x)+\rho\Lambda(x)-1\in SOS\\\
&-\beta^{k}(x)b^{k}(x)+w(x)h(x)-1\in SOS\\\ &\beta^{k}(x),\alpha^{k}(x)\in
SOS\end{array}$ (11)

We let $\rho_{k}^{\prime}$ denote the value of $\rho$ returned by the
optimization. The procedure terminates if $\rho\leq 0$ or if
$|\rho_{k}-\rho_{k}^{\prime}|<\epsilon$. The following theorem establishes the
correctness and convergence of this approach.

###### Theorem 7

If the procedure described above terminates at stage $k$ with $\rho_{k}\leq
0$, then $b^{k-1}(x)$ is a CBF and $\\{b^{k-1}(x)\geq 0\\}$ is a subset of the
viability kernel. If the procedure terminates at stage $k$ with
$\rho_{k}^{\prime}\leq 0$, then $b^{k}(x)$ is a CBF and $\\{b^{k}(x)\geq 0\\}$
is a subset of the viability kernel. The procedure converges in a finite
number of iterations $k$.

###### Proof:

We prove that if $\rho_{k}\leq 0$, then $b^{k-1}(x)$ is a CBF and
$\\{b^{k-1}(x)\geq 0\\}$ is a subset of the viability kernel. The case of
$\rho_{k}^{\prime}\leq 0$ is similar. If $\rho_{k}\leq 0$, then by
construction of (10) there exist SOS polynomials $\overline{\alpha}(x)$ and
$\overline{\beta}(x)$ such that

$\displaystyle\overline{\alpha}(x)$ $\displaystyle=$
$\displaystyle\alpha^{k}(x)\frac{\partial b^{k-1}}{\partial
x}f(x)+\sum_{i=1}^{m}{\theta_{i}^{k}(x)\left[\frac{\partial b^{k-1}}{\partial
x}g(x)\right]_{i}}$ (13)
$\displaystyle+\eta^{k}(x)b^{k-1}(x)+\rho_{i}\Lambda(x)-1$
$\displaystyle\overline{\beta}(x)$ $\displaystyle=$
$\displaystyle-\beta^{k}(x)b^{k-1}(x)+w(x)h(x)-1$ (14)

Rearranging (13) and setting $\overline{\theta}=-\theta_{i}^{k}$ and
$\overline{\eta}=-\eta^{k}$ yields

$\sum_{i=1}^{m}{\overline{\theta}_{i}(x)\left[\frac{\partial b^{k-1}}{\partial
x}g(x)\right]_{i}}+\overline{\eta}(x)b^{k-1}(x)\\\
+\overline{\alpha}(x)-\rho_{k}\Lambda(x)-\alpha^{k}(x)\frac{\partial
b^{k-1}}{\partial x}f(x)+1=0$

Since $\rho_{k}\leq 0$ and $\Lambda(x)$ is SOS,
$\overline{\alpha}(x)-\rho_{k}\Lambda(x)$ is SOS. Hence, by Theorem 1, there
does not exist any $x$ satisfying

$\frac{\partial b^{k-1}}{\partial x}f(x)\leq 0,\ b^{k-1}(x)=0,\ \frac{\partial
b^{k-1}}{\partial x}g(x)=0$

and $b^{k-1}(x)$ is a CBF by Proposition 1.

Similarly, setting $\overline{w}(x)=-w(x)$, we have

$\overline{\beta}(x)+\beta^{k}(x)b^{k-1}(x)+\overline{w}(x)h(x)+1=0,$

implying that $\\{b^{k-1}(x)\geq 0\\}\subseteq\mathcal{C}$ by Theorem 4.

Finally, to prove convergence, we observe that $\rho_{k-1}^{\prime}$,
$\alpha^{k-1}(x)$, $\eta^{k-1}(x)$,
$\theta_{1}^{k-1}(x),\ldots,\theta_{m}^{k-1}(x)$, and $\beta^{k-1}(x)$
comprise a feasible solution to (10) and $\rho_{k}$, $b^{k-1}(x)$ are feasible
solutions to (11). Hence
$\rho_{1}\geq\rho_{1}^{\prime}\geq\cdots\geq\rho_{k}\geq\rho_{k}^{\prime}\geq\cdots$,
i.e., the sequence is monotone nonincreasing. If the sequence is unbounded,
then there exists $K$ such that $\rho_{k},\rho_{k}^{\prime}\leq 0$ for all
$k>K$, and hence the algorithm terminates after $K$ iterations. If the
sequence is bounded below by zero, then it converges by the monotone
convergence theorem and hence $|\rho_{k}-\rho_{k}^{\prime}|<\epsilon$ and
$|\rho_{k}-\rho_{k-1}^{\prime}|<\epsilon$ for $k$ sufficiently large, implying
termination of the procedure. ∎

We next consider the problem of constructing HOCBFs. We observe that, in
addition to the same non-convexity as the CBF, HOCBFs have an additional
degree of freedom, namely, the selection of the class-K functions $\alpha_{i}$
in Definition 3. To mitigate this complexity, we present the following.

###### Proposition 2

Let $\psi_{0}(x),\ldots,\psi_{r}(x)$ be a collection of polynomials such that
the following hold: (i) for all $i=1,\ldots,r$, there is no $x$ satisfying
$\psi_{i}(x)\geq 0$, $\psi_{i-1}(x)=0$, and
$\frac{\partial\psi_{i-1}}{\partial x}f(x)<0$, and (ii)
$\frac{\partial\psi_{i}}{\partial x}g(x)=0$ for all $i<r$. If (3) holds for
all $t$, then $\bigcap_{i=0}^{r}{\\{\psi_{i}(x)\geq 0\\}}$ is positive
invariant.

###### Proof:

The proof is by backwards induction. By (3), $\psi_{r}(x(t))\geq 0$ for all
$t$. By Nagumo’s Theorem, we have that $L\psi_{i-1}(x)\geq 0$ at the boundary
points where $\psi_{i-1}(x)=0$ and $\psi_{i}\geq 0$, and hence
$\\{\psi_{i-1}\geq 0\\}$ is positive invariant if $\\{\psi_{i}(x)\geq 0\\}$ is
positive invariant, completing the proof. ∎

We then adopt the following alternating-descent procedure analogous to the CBF
case. We initialize $\psi_{0}$ arbitrarily and choose
$\psi_{1},\ldots,\psi_{r}$ according to Definition 3. We then solve the SOS
problem with variables $\rho$, $\alpha^{k}(x)$, $\eta^{k}(x)$,
$\theta_{1}^{k}(x),\ldots,\theta_{m}^{k}(x)$, $w(x)$, $\beta^{k}(x)$,
$\lambda_{0}^{k}(x),\ldots,\lambda_{r-1}^{k}(x)$,
$\zeta_{0}^{k}(x),\ldots,\zeta_{r-1}^{k}(x)$,
$\gamma_{0}^{k}(x),\ldots,\gamma_{r-1}^{k}(x)$, and
$\phi_{0}(x),\ldots,\phi_{r-1}(x)$

$\begin{array}[]{ll}\mbox{min}&\rho_{k}\\\
\mbox{s.t.}&\eta^{k}(x)\psi_{r}^{k-1}(x)+\sum_{i=1}^{m}{\theta_{i}^{k}(x)L_{g}L_{f}^{r-1}\psi_{r-1}^{k-1}(x)}\\\
&+\alpha^{k}(x)(L_{f}^{r}\psi_{r-1}^{k-1}(x)+O(b(x)))\\\
&-\sum_{i=0}^{r-1}{\gamma_{i}^{k}(x)\psi_{i}^{k-1}(x)}+\rho_{k}\Lambda(x)-1\in
SOS\\\ &-\sum_{i=0}^{r-1}{\psi_{i}^{k-1}(x)\beta_{i}^{k}(x)}+w(x)h(x)-1\in
SOS\\\
&-\lambda_{i}^{k}\psi_{i}^{k-1}(x)+\zeta_{i-1}^{k}(x)\psi_{i-1}^{k-1}\\\
&+\phi_{i}^{k}(x)L\psi_{i-1}^{k-1}(x)-1\in SOS,\quad i=1,\ldots,r\\\
&\lambda_{i}^{k}(x),\phi_{i}^{k}(x),\beta_{i}^{k}(x),\alpha^{k}(x),\gamma_{i}^{k}(x)\in
SOS\end{array}$ (15)

As above, $\Lambda(x)$ is a suitably-chosen SOS polynomial. If the solution
$\rho_{k}\leq 0$ or $|\rho_{k}-\rho_{k-1}^{\prime}|<\epsilon$, the algorithm
terminates. Else, we solve the SOS program with variables
$\psi_{0}^{k}(x),\ldots,\psi_{r}^{k}(x),\rho_{k}^{\prime}$ given by

$\begin{array}[]{ll}\mbox{min}&\rho_{k}^{\prime}\\\
\mbox{s.t.}&\eta^{k}(x)\psi_{r-1}^{k}(x)+\sum_{i=1}^{m}{\theta_{i}^{k}(x)L_{g}L_{f}^{r-1}\psi_{r-1}^{k}(x)}\\\
&+\alpha^{k}(x)(L_{f}^{r}\psi_{r-1}^{k}(x)+O(b(x)))-\sum_{i=0}^{r-1}{\gamma_{i}^{k}(x)\psi_{i}^{k}(x)}\\\
&+\rho_{k}^{\prime}\Lambda(x)-1\in SOS\\\
&-\sum_{i=0}^{r}{\psi_{i}^{k}(x)\beta_{i}^{k}(x)}+w(x)h(x)-1\in SOS\\\
&-\lambda_{i}^{k}\psi_{i}^{k}(x)+\zeta_{i-1}^{k}(x)\psi_{i-1}^{k}\\\
&\frac{\partial\psi_{i}^{k}}{\partial x}g(x)=0,\ i=0,\ldots,(r-1)\\\
&+\phi_{i}^{k}(x)L\psi_{i-1}^{k}(x)-1\in SOS,\qquad i=1,\ldots,r\\\
\end{array}$ (16)

If $\rho_{k}^{\prime}\leq 0$ or $|\rho_{k}-\rho_{k}^{\prime}|<\epsilon$, the
algorithm terminates. We have the following result.

###### Theorem 8

If $\rho_{k}\leq 0$, then $\psi_{0}^{k-1}(x),\ldots,\psi_{r}^{k-1}(x)$ define
a HOCBF and $\bigcap_{i=0}^{r}{\\{\psi_{i}^{k-1}(x)\\}}\subseteq\mathcal{C}$.
If $\rho_{k}^{\prime}\leq 0$, then $\psi_{0}^{k},\ldots,\psi_{r}^{k}(x)$
define HOCBF and
$\bigcap_{i=0}^{r}{\\{\psi_{i}^{k}(x)\\}}\subseteq\mathcal{C}$. The procedure
terminates in finite time.

###### Proof:

We prove that if $\rho_{k}\leq 0$, then
$\psi_{0}^{k-1}(x),\ldots,\psi_{r}^{k-1}(x)$ defines a HOCBF and
$\bigcap_{i=0}^{r}{\\{\psi_{i}^{k-1}(x)\\}}\subseteq\mathcal{C}$. The case of
$\rho_{k}^{\prime}\leq 0$ is similar. If $\rho_{k}\leq 0$, then

$\overline{\eta}(x)\psi_{r}^{k-1}(x)-\alpha^{k}(x)(L_{f}^{r}\psi_{r}^{k-1}(x)+O(b(x)))+\overline{\alpha}(x)\\\
+\sum_{i=1}^{m}{\overline{\theta}_{i}(x)L_{g}L_{f}^{r-1}\psi_{r}^{k-1}(x)}+\sum_{i=0}^{r-}{\gamma_{i}^{k}(x)\psi_{i}^{k-1}(x)}+1=0$

for some SOS polynomial $\overline{\alpha}(x)$, where
$\overline{\eta}(x)=-\eta^{k}(x)$ and
$\overline{\theta}_{i}(x)=-\theta_{i}^{k}(x)$. Hence Eq. (3) is feasible for
all $x\in\bigcap_{i=0}^{r}{\\{\psi_{i}^{k-1}(x)\geq 0\\}}$ by the
Positivstellensatz. Similarly, we have that

$\overline{\beta}(x)+\sum_{i=0}^{r}{\psi_{i}^{k-1}(x)\beta_{i}^{k}(x)}+w(x)h(x),$

and hence $\bigcap_{i=0}^{r}{\\{\psi_{i}^{k-1}(x)\geq 0\\}}$ is in the
viability kernel. Finally, we have

$\lambda_{i}^{k}\psi_{i}^{k-1}(x)-\zeta_{i-1}(x)\psi_{i}^{k-1}(x)-\phi_{i}^{k}(x)L\psi_{i-1}^{k-1}(x)\\\
+\overline{\lambda}_{i}(x)+1=0$

for some SOS polynomial $\overline{\lambda}_{i}(x)$ for all $i$, and thus the
conditions of Proposition 2 hold and the set is a subset of the viability
kernel. The termination proof is similar to Theorem 7. ∎

The preceding results provide heuristics for constructing CBFs and HOCBFs.
However, we observe several limitations of this approach. First, there is no
guarantee that the algorithm will terminate when $\rho_{k}\leq 0$, and hence
no guarantee that a CBF or HOCBF will be returned. Second, the approach
involves solving $2k$ SOS programs, each of which includes multiple linear
matrix inequalities, and hence is computationally challenging for high-
dimensional systems. In the following, we present more efficient approaches
with provable guarantees for special cases of compact safe regions, as well as
convex unsafe regions.

###  V-B Compact Safe Region

In what follows, we consider the case where $\mathcal{C}$ is compact. Our
approach is motivated by the following preliminary result.

######  Proposition 3 ([34])

Suppose that $\dot{x}(t)=f(x(t))$ is a dynamical system that remains in a
compact region. Then $f(x)$ has a fixed point.

We observe that, if a given feedback control policy ensures that $x(t)$
remains within the safe region, then the control policy results in a fixed
point. Based on this preliminary result, our approach is to identify fixed
points of (1), and then construct barrier functions in the neighborhoods of
those points.

###### Lemma 1

Let $(x^{\ast},u^{\ast})$ satisfy $f(x^{\ast})+g(x^{\ast})u^{\ast}=0$ and
$x^{\ast}\in\mbox{int}(\mathcal{C})$. Then there exists a positive definite
matrix $P$ and $\delta>0$ such that the function

$b_{0}(x;x^{\ast})=\delta-(x-x^{\ast})^{T}P(x-x^{\ast})$

is a CBF with $\\{b_{0}(x;x^{\ast})\geq 0\\}\subseteq\mathcal{C}$.

###### Proof:

Let $\dot{x}(t)=Fx(t)+Gu(t)$ be the linearization of (1) in a neighborhood of
$(x^{\ast},u^{\ast})$. Let $\tilde{u}(t)={u}^{\ast}-K(x-x^{\ast})$ be a
stabilizing controller of the linearized system. Hence, there is a quadratic
Lyapunov function $V(x)=(x-x^{\ast})^{T}P(x-x^{\ast})$ such that (1) is
asymptotically stable in a neighborhood of $x^{\ast}$, i.e.,

$\frac{\partial V}{\partial x}(f(x)+g(x)\tilde{u}(t))\leq 0.$

By construction of $b_{0}(x;x^{\ast})$, this is equivalent to

$\frac{\partial b_{0}(x;x^{\ast})}{\partial x}(f(x)+g(x)\tilde{u})\geq 0$

for $(x-x^{\ast})$ sufficiently small. Furthermore, since $x^{\ast}$ is an
interior point, $b_{0}(x;x^{\ast})\geq 0$ is contained in $\mathcal{C}$ for
$\delta$ sufficiently small. ∎

The preceding lemma implies that we can construct a CBF by identifying a fixed
point $(x^{\ast},u^{\ast})$, constructing a stabilizing linear controller
$\overline{u}=-K\overline{x}$ of the linearized system, and solving the
Lyapunov equation

$\overline{F}^{T}P+P\overline{F}+N=0,$

where $\overline{F}=(F-GK)$ and $N$ is a positive definite matrix. We can then
to find a value of $\delta$ such that $b_{0}(x;x^{\ast})$ is a CBF by solving
a sequence of SOS verification problems of the form (4) and (5). We have the
following result.

###### Theorem 9

Suppose that $(x^{\ast},u^{\ast})$ is a fixed point of (1), $P$ is a solution
to the Lyapunov equation corresponding to a stabilizing controller of the
linearized system, and the SOS constraints

$\alpha(x)(-2(x-x^{\ast})^{T}Pf(x))+\sum_{i=1}^{m}{\theta_{i}(x)\left[-2(x-x^{\ast})^{T}Pg(x)\right]_{i}}\\\
+\eta(x)(\delta-(x-x^{\ast})^{T}P(x-x^{\ast}))\in SOS$ (17)

and

$h(x)-\beta(x)(\delta-(x-x^{\ast})^{T}P(x-x^{\ast}))\in SOS$ (18)

hold for some polynomials $\theta_{1},\ldots,\theta_{m},\eta(x)$ and SOS
polynomials $\alpha(x)$ and $\beta(x)$. Then
$b_{0}(x;x^{\ast})=\delta-(x-x^{\ast})^{T}P(x-x^{\ast})$ is a CBF and
$\\{b_{0}(x;x^{\ast})\geq 0\\}$ is in the viability kernel.

###### Proof:

If (17) holds, then $b_{0}$ is a CBF by Theorem 4. To show (18) implies that
$\\{b_{0}\geq 0\\}$ is in the viability kernel, we use nonnegativity of SOS
polynomials to conclude that $\\{b_{0}(x)\geq 0\\}$ implies $\\{h(x)\geq 0\\}$
if

$h(x)=\beta(x)b_{0}(x)+\beta_{0}(x)$

for some SOS $\beta$ and $\beta_{0}$. Rearranging terms gives (18). ∎

The preceding theorem suggests that a binary search approach can be used to
find the maximum $\delta$ such that (17) and (18) hold, and choosing
$b_{0}(x;x^{\ast})$ as the CBF. Moreover, we can generalize this approach by
considering functions of the form

$b_{1}(x;x^{\ast})=b_{0}(x;x^{\ast})+\alpha(h(x)),$

where $\alpha(\cdot)$ is a class-K function. We have the following.

###### Lemma 2

If $b_{1}(x;x^{\ast})$ is a CBF, then the set

$\mathcal{V}(b_{0},b_{1})=\left(\\{b_{0}(x;x^{\ast})\geq
0\\}\cup\\{b_{1}(x;x^{\ast})\geq 0\\}\right)\cap\mathcal{C}$

is in the viability kernel.

###### Proof:

We construct a control policy that ensures positive invariance of
$\mathcal{V}(b_{0},b_{1})$ as follows. We select $\mu$ to satisfy (2) for
$b_{0}(x;x^{\ast})$ when $b_{0}(x(t);x^{\ast})\geq 0$ and to satisfy (2) for
$b_{1}(x;x^{\ast})\geq 0$ if $b_{1}(x(t);x^{\ast})\geq 0$ and
$b_{0}(x;x^{\ast})<0$.

First, suppose that $b_{0}(x(t^{\prime});x^{\ast})\geq 0$ for some
$t^{\prime}$. Since $b_{0}(x;x^{\ast})$ is a CBF, the set
$\\{b_{0}(x;x^{\ast})\geq 0\\}$ is positive invariant and is contained in
$\mathcal{C}$.

Next, suppose that
$x(t_{0})\in\mathcal{V}(b_{0},b_{1})\setminus\\{b_{0}(x)\geq 0\\}$ and yet
$x(t_{0})$ is not in the viability kernel. Let

$t^{\ast}=\inf{\\{t:h(x(t))=0\\}}.$

By the preceding discussion, we must have $b_{0}(x(t))<0$ for
$t\in[t_{0},t^{\ast}]$. We therefore have

$\displaystyle b_{1}(x(t^{\ast});x^{\ast})$ $\displaystyle=$ $\displaystyle
b_{0}(x(t^{\ast});x^{\ast})+\alpha(h(x(t^{\ast}))$ $\displaystyle=$
$\displaystyle b_{0}(x(t^{\ast}))<0$

contradicting Theorem 2. ∎

One candidate for $\alpha$ is the function $\alpha(h(x))=kh(x)$, where $k$ is
a positive real number. We observe that, for $k$ sufficiently small,
$b_{0}(x;x^{\ast})+kh(x)$ is a CBF. We can therefore select such a $k$ by
solving the feasibility problem (4)–(5) and approximate the viability kernel
as

$\bigcup_{x^{\ast}\in FP}{\left(\left(\\{b_{0}(x;x^{\ast})\geq
0\\}\cup\\{b_{0}(x;x^{\ast})+kh(x)\geq 0\\}\right)\cap\mathcal{C}\right)}$

where FP denotes the set of fixed points of (1).

We observe that, while this approach is valid for general unsafe regions,
there may be safe trajectories that do not contain fixed points when the safe
region is not compact.

$\begin{array}[]{cc}\includegraphics[width=216.81pt]{Figures/numerical-
example}&\includegraphics[width=216.81pt]{Figures/inverted-pendulum}\\\
\mbox{(a)}&\mbox{(b)}\end{array}$

Figure 1: Illustration of our CBF framework. (a) Numerical example showed in
(19). A trajectory originating inside the shaded viability kernel remains
inside the safe region (outer blue circle), while a trajectory originating
outside the viability kernel but inside the safe region exits the safe region.
(b) Inverted pendulum with dynamics (20). The trajectory originating inside
the viability kernel remains safe, while the trajectory originating outside
the viability kernel exits the safe region.

###  V-C Convex Unsafe Region

In what follows, we consider a special case where the viability kernel and
$\mathcal{C}$ are identical. This is the case of controllable linear systems
$\dot{x}(t)=Fx(t)+Gu(t)$ where the safe region is given by
$\mathcal{C}=\mathbb{R}^{n}\setminus\bigcup_{i=1}^{m}{\\{h_{i}(x)\leq 0\\}}$,
where each $h_{i}$ is a convex function, and the distance $d(\\{h_{i}(x)\leq
0\\},\\{h_{j}\leq 0\\})>\delta$ for all $i,j$ and some $\delta>0$. We observe
that this problem formulation has been considered, e.g., in [31], and safe
control strategies have been proposed. This section presents a CBF-based
framework for convex obstacle avoidance.

###### Theorem 10

Under the conditions described above, the viability kernel is equal to
$\mathcal{C}$, and there exists a CBF-based policy that ensures safety.

###### Proof:

We will prove that, for any $\epsilon>0$, there exists a control policy such
that $\bigcap_{i=1}^{m}{\\{h_{i}(x)>\epsilon\\}}$ is in the viability kernel.
The proof is by construction. We assume that $\epsilon<\delta$. As a first
step, for each $i$, we cover the set
$\\{x:h_{i}(x)\in(\epsilon/2,\epsilon)\\}$ with a collection of balls denoted
$\\{U_{ij}:j\in\mathcal{I}_{i}\\}$ where $\mathcal{I}_{i}$ is an index set.
For each $U_{ij}$, we let $\overline{h}_{ij}(x)=a_{ij}^{T}x-b_{i}$ be such
that $\\{\overline{h}_{ij}(x)\geq 0\\}$ is a separating hyperplane between
$U_{ij}$ and $\\{h_{i}(x)<\epsilon/2\\}$.

We consider each set $U_{ij}$. In the case where $a_{ij}^{T}G\neq 0$, our
control policy follows the CBF constraint (2) whenever $x\in U_{ij}$. When
$a_{ij}^{T}G=0$, we have that $a_{ij}^{T}F^{r}G\neq 0$ for some
$r\in\\{1,\ldots,n-1\\}$ since $(F,G)$ is controllable. We then define an
HOCBF as

$\displaystyle\overline{h}_{ij}^{0}(x)$ $\displaystyle=$
$\displaystyle\overline{h}_{ij}(x)$ $\displaystyle\overline{h}_{ij}^{1}(x)$
$\displaystyle=$ $\displaystyle a_{ij}^{T}Fx+k_{0}\overline{h}_{ij}^{0}(x)$
$\displaystyle\vdots$ $\displaystyle\overline{h}_{ij}^{r-1}(x)$
$\displaystyle=$ $\displaystyle
a_{ij}^{T}F^{r-1}x+\sum_{l=1}^{r-2}{\left(\prod_{s=l}^{r-2}{k_{s}}\right)a_{ij}^{T}F^{l}x}$
$\displaystyle+\left(\prod_{s=0}^{r-2}{k_{s}}\right)\overline{h}_{ij}^{0}(x)$

for $k_{0},\ldots,k_{r-2}>0$. In the limit as $k_{l}\rightarrow 0$ (for $l>0$)
and $k_{0}\rightarrow\infty$, the set

$C_{ij}=\bigcap_{l=0}^{r-1}{\\{\overline{h}_{ij}^{l}(x)\geq 0\\}}$

approaches $\\{\overline{h}_{ij}(x)\geq 0\\}$.

Hence, by following this control policy, the set
$\bigcap_{i=1}^{m}{\\{h_{i}(x)>\epsilon\\}}$ is positive invariant, implying
the viability kernel is equal to $\mathcal{C}$. ∎

##  VI Simulation

We evaluated our approach through simulation of two example systems. First, we
examined an unstable linear system with dynamics

$\dot{x}(t)=\left(\begin{array}[]{cc}1&0\\\
-1&4\end{array}\right)x(t)+\left(\begin{array}[]{c}1\\\
0\end{array}\right)u(t)$ (19)

As the safe region, we chose $\\{h(x)\geq 0\\}$ where $h(x)=1-x^{T}x$, i.e.,
the unit disc. We first approximated the viability kernel using the approach
of Section V-B, using the stabilizing feedback controller $u(t)=-Kx(t)$ where
$K=(8\ -30)$. The approximate viability kernel is shown as the red shaded in
region in Fig. 1(a). To evaluate our approximation of the viability kernel, we
simulated trajectories beginning inside and outside the kernel at the points
$(-0.75\ -0.15)^{T}$ and $(-0.4\ -0.4)^{T}$, respectively. For both points, we
used a CBF-based control policy with CBF
$\overline{h}=k-(x-x_{0})^{T}P(x-x_{0})$, where $k=1.1575$, $x_{0}=(0.1378\
0)$, and

$P=\left(\begin{array}[]{cc}6.23&-26.7\\\ -26.7&146.7\end{array}\right)$

As shown in Fig. 1(a), the trajectory originating inside the viability kernel
remains safe, whereas the trajectory originating at the point outside the
viability kernel leaves the safe region.

We next evaluated our approach on an inverted pendulum with dynamics

$\dot{x}(t)=\left(\begin{array}[]{cc}0&1\\\
1&0\end{array}\right)x(t)+\left(\begin{array}[]{c}0\\\
1\end{array}\right)u(t)$ (20)

and the safe region is defined by $[-0.1,0.15]\times[-0.3,0.25]$. This region
can be viewed as the intersection of four half-plane constraints. We
approximated the viability kernel of Section V-B with feedback controller
$u(t)=-Kx(t)$ where $K=(3\ 3)$. We simulated trajectories beginning inside and
outside the kernel at the points $(0.1\ -0.1)^{T}$ and $(0.13\ 0.25)^{T}$,
respectively. For both initial conditions, we used a CBF-based control policy
with CBF $\overline{h}=k-(x-x_{0})^{T}P(x-x_{0})$, where $k=0.01$, $x_{0}=0$,
and

$P=\left(\begin{array}[]{cc}1.25&0.25\\\ 0.25&0.25\end{array}\right)$

The trajectory originating within the viability kernel remains in the safe
region for all time, while the trajectory originating outside the viability
kernel leaves the safe region returning to the origin.

##  VII Conclusions and Future Work

This paper presented a framework for verification and synthesis of control
barrier functions for safe control. We mapped the conditions for safe CBFs and
HOCBFs to the existence of solutions to a system of polynomial equations.
Using the Positivstellensatz, we proved that these conditions are equivalent
to sum-of-squares optimization problems, which can be solved via semidefinite
programming. We proposed CBF construction heuristics, including an
alternating-descent semidefinite programming approach, a Lyapunov function-
based method, and a CBF construction for convex unsafe regions. Our results
were verified via numerical study, which showed that our approach
distinguished between safe and unsafe states of an unstable linear system.

## References

  * [1] P. Koopman and M. Wagner, “Autonomous vehicle safety: An interdisciplinary challenge,” _IEEE Intelligent Transportation Systems Magazine_ , vol. 9, no. 1, pp. 90–96, 2017.
  * [2] K. Morison, L. Wang, and P. Kundur, “Power system security assessment,” _IEEE power and energy magazine_ , vol. 2, no. 5, pp. 30–39, 2004.
  * [3] A. Rovetta, “Telerobotic surgery control and safety,” in _Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065)_ , vol. 3. IEEE, 2000, pp. 2895–2900.
  * [4] J.-P. Aubin, A. M. Bayen, and P. Saint-Pierre, _Viability theory: new directions_. Springer Science & Business Media, 2011.
  * [5] A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada, “Control barrier function based quadratic programs for safety critical systems,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 8, pp. 3861–3876, 2016.
  * [6] W. Xiao and C. Belta, “Control barrier functions for systems with high relative degree,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_. IEEE, 2019, pp. 474–479.
  * [7] A. Clark, “Control barrier functions for complete and incomplete information stochastic systems,” in _2019 American Control Conference (ACC)_. IEEE, 2019, pp. 2928–2935.
  * [8] P. Jagtap, S. Soudjani, and M. Zamani, “Formal synthesis of stochastic systems via control barrier certificates,” _IEEE Transactions on Automatic Control_ , 2020.
  * [9] W. Xiao, C. Belta, and C. G. Cassandras, “Adaptive control barrier functions for safety-critical systems,” _arXiv preprint arXiv:2002.04577_ , 2020.
  * [10] R. Cheng, G. Orosz, R. M. Murray, and J. W. Burdick, “End-to-end safe reinforcement learning through barrier functions for safety-critical continuous control tasks,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, no. 01, 2019, pp. 3387–3395.
  * [11] S.-C. Hsu, X. Xu, and A. D. Ames, “Control barrier function based quadratic programs with application to bipedal robotic walking,” in _2015 American Control Conference (ACC)_. IEEE, 2015, pp. 4542–4548.
  * [12] A. D. Ames, J. W. Grizzle, and P. Tabuada, “Control barrier function based quadratic programs with application to adaptive cruise control,” in _53rd IEEE Conference on Decision and Control_. IEEE, 2014, pp. 6271–6278.
  * [13] W. Xiao, C. G. Cassandras, and C. A. Belta, “Bridging the gap between optimal trajectory planning and safety-critical control with applications to autonomous vehicles,” _arXiv preprint arXiv:2008.07632_ , 2020.
  * [14] B. Xu and K. Sreenath, “Safe teleoperation of dynamic uavs through control barrier functions,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 7848–7855.
  * [15] Y. Chen, A. Singletary, and A. D. Ames, “Guaranteed obstacle avoidance for multi-robot operations with limited actuation: a control barrier function approach,” _IEEE Control Systems Letters_ , vol. 5, no. 1, pp. 127–132, 2020\.
  * [16] C. Santoyo, M. Dutreix, and S. Coogan, “A barrier function approach to finite-time stochastic system verification and control,” _Automatica_ , p. 109439, 2021.
  * [17] G. Stengle, “A nullstellensatz and a positivstellensatz in semialgebraic geometry,” _Mathematische Annalen_ , vol. 207, no. 2, pp. 87–97, 1974.
  * [18] Q. Nguyen and K. Sreenath, “Exponential control barrier functions for enforcing high relative-degree safety-critical constraints,” in _2016 American Control Conference (ACC)_. IEEE, 2016, pp. 322–328.
  * [19] F. S. Barbosa, L. Lindemann, D. V. Dimarogonas, and J. Tumova, “Provably safe control of lagrangian systems in obstacle-scattered environments,” in _2020 59th IEEE Conference on Decision and Control (CDC)_. IEEE, 2020, pp. 2056–2061.
  * [20] W. S. Cortez and D. V. Dimarogonas, “Correct-by-design control barrier functions for euler-lagrange systems with input constraints,” in _2020 American Control Conference (ACC)_. IEEE, 2020, pp. 950–955.
  * [21] C. Folkestad, Y. Chen, A. D. Ames, and J. W. Burdick, “Data-driven safety-critical control: Synthesizing control barrier functions with koopman operators,” _IEEE Control Systems Letters_ , 2020.
  * [22] N. Jahanshahi, P. Jagtap, and M. Zamani, “Synthesis of partially observed jump-diffusion systems via control barrier functions,” _IEEE Control Systems Letters_ , vol. 5, no. 1, pp. 253–258, 2020.
  * [23] R. Konda, A. D. Ames, and S. Coogan, “Characterizing safety: Minimal control barrier functions from scalar comparison systems,” _IEEE Control Systems Letters_ , vol. 5, no. 2, pp. 523–528, 2020.
  * [24] G. Yang, B. Vang, Z. Serlin, C. Belta, and R. Tron, “Sampling-based motion planning via control barrier functions,” in _Proceedings of the 2019 3rd International Conference on Automation, Control and Robots_ , 2019, pp. 22–29.
  * [25] M. Anand, A. Lavaei, and M. Zamani, “Compositional synthesis of control barrier certificates for networks of stochastic systems against omega-regular specifications,” _arXiv preprint arXiv:2103.02226_ , 2021.
  * [26] L. Niu and A. Clark, “Control barrier functions for abstraction-free control synthesis under temporal logic constraints,” in _2020 59th IEEE Conference on Decision and Control (CDC)_. IEEE, 2020, pp. 816–823.
  * [27] S. Prajna, A. Jadbabaie, and G. J. Pappas, “A framework for worst-case and stochastic safety verification using barrier certificates,” _IEEE Transactions on Automatic Control_ , vol. 52, no. 8, pp. 1415–1428, 2007.
  * [28] F. Blanchini, “Set invariance in control,” _Automatica_ , vol. 35, no. 11, pp. 1747–1767, 1999.
  * [29] J. F. Fisac, N. F. Lugovoy, V. Rubies-Royo, S. Ghosh, and C. J. Tomlin, “Bridging hamilton-jacobi safety analysis and reinforcement learning,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 8550–8556.
  * [30] M. Z. Romdlony and B. Jayawardhana, “Uniting control lyapunov and control barrier functions,” in _53rd IEEE Conference on Decision and Control_. IEEE, 2014, pp. 2293–2298.
  * [31] S. M. Khansari-Zadeh and A. Billard, “A dynamical system approach to realtime obstacle avoidance,” _Autonomous Robots_ , vol. 32, no. 4, pp. 433–454, 2012\.
  * [32] P. A. Parrilo, “Semidefinite programming relaxations for semialgebraic problems,” _Mathematical programming_ , vol. 96, no. 2, pp. 293–320, 2003\.
  * [33] T. Gurriet, M. Mote, A. D. Ames, and E. Feron, “An online approach to active set invariance,” in _2018 IEEE Conference on Decision and Control (CDC)_. IEEE, 2018, pp. 3592–3599.
  * [34] D. Richeson, J. Wiseman _et al._ , “A fixed point theorem for bounded dynamical systems,” _Illinois Journal of Mathematics_ , vol. 46, no. 2, pp. 491–495, 2002.