Barrier Certified Safety Learning Control:
When Sum-of-Square Programming Meets Reinforcement Learning

Hejun Huang¹, Zhenglong Li², Dongkun Han^1∗ ¹Hejun Huang and Dongkun Han are with the Department of Mechanical and Automation Engineering, The Chinese University of Hong Kong²Zhenglong Li is with the Department of Electrical and Electronic Engineering, The University of Hong Kong*Email: [email protected]

Abstract

Safety guarantee is essential in many engineering implementations. Reinforcement learning provides a useful way to strengthen safety. However, reinforcement learning algorithms cannot completely guarantee safety over realistic operations. To address this issue, this work adopts control barrier functions over reinforcement learning, and proposes a compensated algorithm to completely maintain safety. Specifically, a sum-of-squares programming has been exploited to search for the optimal controller, and tune the learning hyperparameters simultaneously. Thus, the control actions are pledged to be always within the safe region. The effectiveness of proposed method is demonstrated via an inverted pendulum model. Compared to quadratic programming based reinforcement learning methods, our sum-of-squares programming based reinforcement learning has shown its superiority.

I Introduction

Reinforcement learning (RL) is one of the most popular methods for accomplishing the long-term objective of a Markov-decision process [1, 2, 3, 4, 5, 6]. This learning method aims for an optimal policy that can maximize a long-term reward in a given environment recursively. For the case of RL policy gradient method [7, 8, 9], this reward-related learning problem is traditionally addressed using gradient descent to obtain superior control policies.

RL algorithms might generate desired results in some academic trials, e.g., robotic experiments [10, 11] and autonomous driving contexts [12, 13]. But for realistic situations, how to completely guarantee the safety based on these RL policies is still a problem. The intermediate policies from the RL agent’s exploration and exploitation processes may sometimes ruin the environment or the agent itself, which is unacceptable for safety-critical systems. Moreover, disturbances around the system would confuse the agent over learning process, which make the control tasks more complex and challenging.

To cope with the issues above, various methods are proposed to specify dynamical safety during the learning process. Initially, the region of attraction (ROA) from control Lyapunov functions or Lyapunov-like function work [14, 15] are used to certify the dynamical safety. Related and useful work of ROA estimation are introduced in [16, 17, 18, 19]. In 2017, [20] started to execute the RL’s exploration and exploitation in ROA to maintain safety. Different from region constraint, in 2018 [21, 22] proposed a shield framework to select safe actions repeatedly. Inspired by this work, [23, 24] further combined the control barrier function (CBF) to synthesis the RL-based controller. Note that, the CBF is not new to identify safe regions in control theory, [25, 26] are representative work to combine CBF in biped robot and [27] explored its implementation of quadrotors, etc. Appropriate region constraint for RL is important for building safe RL. Hence, a reliable learning method is expected to construct a controller inside the safe region over the process.

In this paper, we will consider a state-space model in the polynomial form, including an unknown term that estimated by Gaussian process. Then, we will apply Deep Deterministic Policy Gradient (DDPG) algorithm to design a controller. The generated control action will impact system dynamics and further influence the sum-of-squares programming (SOSP) solution of control barrier functions.

The main contributions of this work are: (1) Formulate the framework to embed SOSP-based CBF into DDPG algorithm; (2) compare the performance of quadratic programming (QP)-based and SOSP-based controller with DDPG algorithm; and (3) demonstrate the safety and efficiency of DDPG-SOSP algorithm via an inverted pendulum model.

This paper is organized as follows, we first present some preliminaries about reinforcement learning, Gaussian process and control barrier function in Section II. Then, in Section III, we formulate the steps to compute an SOSP-based controller and introduce a corresponding DDPG-SOSP algorithm. Numerical examples are given for these cases in Section IV, then we discuss the learning efficiency and safety performance of QP-based and SOSP-based strategies, before concluding this paper.

II Preliminary

A discrete-time nonlinear control-affine system with state $s_{t},s_{t+1}\in S$ and control action $a_{t}\in A$ is considered as:

s_{t+1}=f(s_{t})+g(s_{t})a_{t}+d(s_{t}),\forall t\in[\underline{t},\overline{t}],

(1)

where $s_{t},s_{t+1}$ are finished within a bounded time $t$ , while $\underline{t}$ and $\overline{t}$ are constants.

Notation: From the infinite-horizon discounted Markov decision process (MDP) theory [28], let $r:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{R}$ denote the reward of the current state-action pair $(s_{t},a_{t})$ in (1), let $P(s_{t},s_{t+1},a_{t})=p(s_{t+1}|s_{t},a_{t})$ denote the probability distribution to next state $s_{t+1}$ , and let $\gamma\in(0,1)$ denote a discount factor. Thus, a MDP tuple $\tau=(s_{t},s_{t+1},a_{t},r_{t},P_{t},\gamma)$ establishes at each state $t$ .

II-A Reinforcement Learning

RL focuses on training an agent to map various situations to the most valuable actions in a long-term process. During the process, the agent will be inspired by a cumulative reward $r$ to find the best policy $\pi(a|s)$ . Various novel RL algorithms are proposed to select optimal $\pi(a|s)$ . For more details of selecting $\pi$ , we kindly refer interested readers to [1].

Given MDP tuple $\tau$ , the RL agent is selecting an optimal policy $\pi^{*}$ by maximizing the expected reward $J(\pi)$

J(\pi)=\mathbb{E}_{\tau}[\sum^{\infty}_{t=0}\gamma^{t}r(s_{t},a_{t})].

(2)

Furthermore, the action value function $Q_{\pi}$ can be generated from $\tau$ and satisfies the Bellman equation as follows,

	$\displaystyle Q_{\pi}(s_{t},a_{t})$	$\displaystyle=\mathbb{E}_{s_{t},a_{t}}[r_{t}+\gamma\mathbb{E}_{a_{t+1}}[Q_{\pi}(s_{t+1},a_{t+1})]]$		(3)
		$\displaystyle=\mathbb{E}_{s_{t+1},a_{t+1},\dots}[\sum^{\infty}_{l=0}\gamma^{l}r(s_{t+l},a_{t+l})].$		(3)

In this paper, we will use DDPG algorithm, a typical actor-critic and off-policy method, to handle the concerned dynamics of (1). Let parameters $\theta^{\pi}$ and $\theta^{Q}$ denote the neural network of actor and critic, respectively. By interacting with the environment repeatedly, the actor will generate an actor policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$ and be evaluated by the critic via $Q_{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{R}$ . These actions will be stored in replay buffer to update the policy gradient w.r.t $\theta^{\pi}$ , and the loss function w.r.t $\theta^{Q}$ , once if the replay buffer is fulfilled.

However, the state-action of DDPG algorithm generates without a complete safety guarantee, which is unacceptable in safety critical situations. Inspired by the work of [23], we propose a programming assist method to maintain safety over the learning process in Section III.

II-B Gaussian Process

Gaussian processes (GP) estimate the system and further predict dynamics based on the prior data. A GP is a stochastic process that construct a joint Gaussian distribution with concerned states $\{s_{1},s_{2},\dots\}\subset S$ . We use GP to estimate the unknown term $d$ in (1) during the system implementation. Mixed with an independent Gaussian noise $(0,\sigma_{n}^{2})$ , the GP model’s prior data $\{d_{0},d_{1},\dots,d_{k}\}$ can be computed from $d_{k}=s_{k+1}-f-g\cdot a_{k}$ indirectly. Then, a high probability statement of the posterior output $\hat{d}:S\rightarrow\mathbb{R}$ generates as

\displaystyle d(s)\sim\mathcal{N}(m_{d}(s),\sigma_{d}(s)),

(4)

where the mean function $m_{d}(s)$ and the variance function $\sigma_{d}(s)$ can describe the posterior distribution as

\displaystyle m_{d}(s)-k_{\delta}\sigma_{d}(s)\leq d(s)\leq m_{d}(s)+k_{\delta}\sigma_{d}(s),

(5)

with probability greater or equal to $(1-\delta)^{k}$ , $\delta\in(0,1)$ [29], where $k_{\delta}$ is a parameter to design interval $[(1-\delta)^{k},1]$ . Therefore, by learning a finite number of data points, we can estimate the unknown term $d(s_{*})$ of any query state $s_{*}\in\mathcal{S}$ .

As the following lemma declaims in [30, 31], there exists a polynomial mean function to approximate the term $d$ via GP, which can predict the output of state $s_{*}$ straightly here.

Lemma 1.

Suppose we have access to $k$ measurements of $d(s)$ in (1) that corrupted with Gaussian noise $(0,\sigma_{n}^{2})$ . If the norm unknown term $d(s)$ bounded, the following GP model of $d(s)$ can be established with polynomial mean function $m_{d}(s_{*})$ and covariance function $\sigma_{d}^{2}(s_{*})$ ,

	$\displaystyle m_{d}(s_{*})$	$\displaystyle=\varphi(s_{*})^{\mathrm{T}}w,$		(6)
	$\displaystyle\sigma_{d}^{2}(s_{*})$	$\displaystyle=k(s_{},s_{})-k_{}^{\mathrm{T}}(K+\sigma_{n}^{2}I)^{-1}k_{},$		(6)

within probability bounds $[(1-\delta)^{k},1]$ , where $\delta\in(0,1)$ , $s_{*}$ is a query state, $\varphi(s_{*})$ is a monomial vector, $w$ is a coefficient vector, $[K]_{(i,j)}=k(s_{i},s_{j})$ is a kernel Gramian matrix and $k_{*}=[k(s_{1},s_{*}),k(s_{2},s_{*}),\dots,k(s_{k},s_{*})]^{\mathrm{T}}$ .

Lemma 1 generates a polynomial expression of $d(s)$ within probabilistic range $[(1-\delta)^{k},1]$ . Meanwhile, the nonlinear term $f(s)$ in (1) can be approximated by Chebyshev interpolants $P_{k}(s)$ and bounded remainder $\xi(s)$ in certain domain as $f(s)=P_{k}(s)+\xi(s)$ [32], where $k$ is the degree of the polynomial $P_{k}(x)$ [32]. Now we convert (1) as

\displaystyle s_{t+1}=P_{k}(s_{t})+g(s_{t})a_{t}+d_{\xi}(s_{t}).

(7)

The polynomial (7) is equal to (1) with a new term $d_{\xi}(s_{t})=d(s_{t})+\xi(s_{t})$ . Consequently, we can obtain a polynomial system within a probability range by learning $d_{\xi}(s_{t})$ ,

\displaystyle s_{t+1}=P_{k}(s_{t})+g(s_{t})a_{t}+m_{d_{\xi}}(s_{t}),

(8)

which will be used to synthesis the controller in Section III.

II-C Control Barrier Function

The super-level set of the control barrier function (CBF) $h:\mathcal{S}\rightarrow\mathcal{R}$ could validate an safety set $\mathcal{C}$ as

\displaystyle\mathcal{C}=\{{s_{t}\in\mathcal{S}:h(s_{t})\geq 0}\}.

(9)

Throughout this paper, we refer to $\mathcal{C}$ as a safe region and

\displaystyle\mathcal{U}=\mathcal{S}-\mathcal{C}=\{s_{t}\in\mathcal{S}:h(s_{t})<0\},

(10)

as unsafe regions of the dynamical system (8). Then, the state $s_{t}\in\mathcal{C}$ will not enter into $\mathcal{U}$ by satisfying the forward invariant constraint below,

\forall s_{t}\in\mathcal{C}:h(s_{t})\geq 0,\,\Delta{h}(s_{t},a_{t})\geq 0,

(11)

where $\Delta{h(s_{t},a_{t})}=h(s_{t+1})-h(s_{t})$ . Before we demonstrate the computation of $h$ of the system (8), the Positivestellensatz (P-satz) needs to be introduced first [33].

Let $\mathcal{P}$ be the set of polynomials and $\mathcal{P}^{\text{SOS}}$ be the set of sum of squares polynomials, e.g., $P(x)=\sum_{i=1}^{k}p_{i}^{2}(x),$ where $p_{i}(x)\in\mathcal{P}$ and $P(x)\in\mathcal{P}^{SOS}$ .

Lemma 2.

For polynomials $\{a_{i}\}_{i=1}^{m}$ , $\{b_{j}\}_{j=1}^{n}$ and $p$ , define a set $\mathcal{B}=\{s\in\mathcal{S}:\{a_{i}(s)\}_{i=1}^{m}=0,\{b_{j}(s)\}_{j=1}^{n}\geq 0\}$ . Let $\mathcal{B}$ be compact. The condition $\forall x\in\mathcal{S},p(s)\geq 0$ holds if the following condition is satisfied,

$\left\{\begin{array}[]{l}\exists r_{1},\dots,r_{m}\in\mathcal{P},~{}s_{1},\dots,s_{n}\in\mathcal{P}^{\text{SOS}},\\ p-\sum^{m}_{i=1}r_{i}a_{i}-\sum^{n}_{j=1}s_{j}b_{j}\in\mathcal{P}^{\text{SOS}}.\end{array}\right.$ $\square$

Lemma 2 points out that any strictly positive polynomial $p$ lies in the cone that generated by non-negative polynomials $\{b_{j}\}_{j=1}^{n}$ in the set of $\mathcal{B}$ . Based on the definition of $\mathcal{C}$ and $\mathcal{U}$ , P-satz will be adequately used in the safety verification.

Refer to caption — Figure 1: Workflow of the safe RL control with SOS program

The sufficient condition to establish a CBF is the existence of a deterministic controller $a^{CBF}\colon\mathcal{S}\rightarrow\mathcal{A}$ . Based on Lemma 2, we can compute a polynomial controller $a^{CBF}$ through SOS program to avoid entering into unsafe regions $\mu_{i}(s)\in\mathcal{U},i=1,2,\dots,n$ at each step $t$ .

Lemma 3.

Provided a safe region $\mathcal{C}$ certified by the polynomial barrier function $h$ and some unsafe regions $\mu_{i}\in\mathcal{U},i\in\mathbb{Z}^{+}$ , in a polynomial system (8), if there exists a controller $a^{CBF}$ that satisfies

$\displaystyle\qquad\underset{s_{t}\in\mathcal{S},a^{CBF}\in\mathcal{A};L(s_{t}),M_{i}(s_{t})\in\mathcal{P}^{SOS};\;\;}{a^{*}\quad=\quad\arg\min\;{\\|a^{CBF}\\|_{2}}}$		(12)
s.t.	$\displaystyle\;\quad\Delta{h}(s_{t},a^{CBF})-L(s_{t})h(s_{t})\in\mathcal{P}^{SOS},$
$\displaystyle-\Delta{h}(s_{t},a^{CBF})-M_{i}(s_{t})\mu_{i}(s_{t})\in\mathcal{P}^{\text{SOS}},$

where $L(s_{t})$ and $M_{i}(s_{t})$ are SOS polynomials for $i=1,2,\dots,n$ . Then, action $a^{*}$ is a minimum polynomial controller that regulates the system (8) safely.

Proof.

Let us suppose that there exists a CBF $h$ that certified a safe region $\mathcal{C}$ . Then, a deterministic input $a_{t}=a^{CBF}(s_{t})$ is needed to establish the necessary condition $\Delta{h(s_{t},a^{CBF})}\geq 0$ in (11) of the system (8).

Since $h$ is a polynomial function, if $a^{CBF}$ is also a polynomial, $\Delta h$ will maintain in the polynomial form. According to Lemma 2, we can formulate this non-negative condition of $\Delta h$ as part of SOS constraint in the cone of $h$ as

\displaystyle\Delta h(s_{t},a^{CBF})-L(s_{t})h(s_{t})\in\mathcal{P}^{SOS},

(13)

where the auxiliary SOS polynomials $L(s_{t})$ is used to project the related term into an non-negative compact domain $\mathcal{C}$ that certified by the superlevel set of $h(s_{t})$ .

We continue to leverage the P-satz again to drive the dynamics of (8) far from unsafe areas $\mu_{i}(s_{t})$ as follows,

\displaystyle-\Delta h(s_{t},a^{CBF})-\mu_{i}(s_{t})M_{i}(s_{t})\in\mathcal{P}^{SOS},

(14)

where $M_{i}(s_{t})$ denote the corresponding SOS polynomials. Guided by the optimization (LABEL:eq:CLF-CBF-discrete), we can solve a minimal cost control to maintain system safety with (LABEL:eq:text1) and (14), which completes the proof. ∎

This lemma maintains the safety of polynomial system (8) and minimizes the current control $a^{CBF}$ with a SOS program. Multiple unsafe regions $\mu_{i}(s_{t})$ are also considered in solving the target input $a^{*}$ in (LABEL:eq:CLF-CBF-discrete). Since Lemma 1 discussed the probabilistic relationship of (8) and (1), the computed result of (LABEL:eq:CLF-CBF-discrete) of (1) can also be a feasible control to regulate the true dynamics safely.

III CBF Guiding Control with Reinforcement Learning

In the first part of this section, we will further express the computation steps of (LABEL:eq:CLF-CBF-discrete). In the second part, we will go through the details about the SOSP-based CBF guiding control with DDPG algorithm.

III-A SOS Program Based CBF

Different from [23], our control $a^{CBF}$ is solved by SOS program with polynomial barrier functions, rather than the QP and linear barrier functions. In [23], they initially constructed QP with monotonous linear barrier constraints to cope with RL. Obviously, a safe but more relaxed searching area will enhance the RL training performance. We propose a SOS program to compute a minimal control with polynomial barrier function based on Lemma 3.

Lemma 3 declared that we can compute a minimal control $a^{CBF}$ from an approximated polynomial system (8) directly. However, it is hard to define the minimization of the convex function $a^{CBF}$ in (LABEL:eq:CLF-CBF-discrete). The optimal control can be searched by using the following 2 steps:

Step 1: Search an optimal auxiliary factor $L(s_{t})$ by maximizing the scalar $\epsilon_{1}$ ,

$\displaystyle\underset{\epsilon_{1}\in\mathcal{R}^{+},L(s_{t})\in\mathcal{P}^{\text{SOS}}}{L^{*}(s_{t})\quad=\quad\arg\max\quad\epsilon_{1}}$		(15)
s.t.	$\displaystyle\Delta h(s_{t},a^{CBF})-L(s_{t})h(s_{t})-\epsilon_{1}\in\mathcal{P}^{\text{SOS}}$
$\displaystyle-\Delta{h}(s_{t},a^{CBF})-M_{i}(s_{t})\mu_{i}(s_{t})\in\mathcal{P}^{\text{SOS}},$

where $L(s_{t})$ is an auxiliary factor to obtain a permissive constraint for the existing action $a^{CBF}$ .

Step 2: Given $L(s_{t})$ from last step, search an optimal control of $a^{CBF}$ with minimal control cost by minimizing the scalar $\epsilon_{2}$ ,

$\displaystyle\underset{\epsilon_{2}\in\mathcal{R}^{+}}{a^{*}_{t}\quad=\quad\arg\min\quad\epsilon_{2}}$		(16)
s.t.	$\displaystyle\Delta{h}(s_{t},a^{CBF})-L(s_{t})h(s_{t})-\epsilon_{2}\in\mathcal{P}^{\text{SOS}}$
$\displaystyle-\Delta{h}(s_{t},a^{CBF})-M_{i}(s_{t})\mu_{i}(s_{t})\in\mathcal{P}^{\text{SOS}}.$

Remark.

The scalars $\epsilon_{1}$ and $\epsilon_{2}$ in (15) and (16) are used to limit the magnitude of the coefficients’ optimization of $L(s_{t})$ and $a_{t}$ , respectively.

The SOS programs above demonstrate the details of a target controller computation of the system (8), and the solution of (16) regulates the dynamical safety via a control barrier function directly.

III-B SOS Program Based CBF with Reinforcement Learning

The workflow of the CBF guiding DDPG control algorithm is shown in Fig. 1, which is akin to the original idea in [23] to push the agent’s action into a safe training architecture. In Fig. 1, we list these flowing elements into brackets and highlight the corresponding input of each factor computation.

We illustrate the core idea of CBF guiding RL control as,

\displaystyle a_{t}=

\displaystyle a^{RL}_{\theta_{k}}+\bar{a}_{k}+a_{t}^{CBF},

(17)

where the final action $a_{t}$ consists of a RL-based controller $a^{RL}_{\theta_{k}}$ , a previous deployed CBF controller $\bar{a}_{\phi}$ and a SOS program based CBF controller $a_{t}^{CBF}$ . A clear distinction of the subscript $t$ and $k$ is stated here: $t$ denotes the step number of each policy iteration and $k$ denotes the policy iteration number over the learning process.

More specifically, the first term in (17) is an action generated from a standard DDPG algorithm with parameter $\theta$ . The second term $\bar{a}_{k}=\sum_{i=0}^{k-1}a_{i}^{CBF}$ demotes a global consideration of previous CBF controllers. Since it is impractical to compute the exact value of each CBF action $a_{i}^{CBF}$ at each step. Supported by the work of [23], we approximate this term as $\bar{a}_{\phi_{k}}\approx\bar{a}_{k}=\sum^{k-1}_{i=0}a_{i}^{CBF}$ , where $\bar{a}_{\phi_{k}}$ denotes an output from the multilayer perceptron (MLP) with hyperparameters $\phi$ . Then, we fit the MLP and update $\phi_{k}$ with $\sum^{k-1}_{i=0}a_{i}^{CBF}(s,a_{\theta_{0}}^{RL},\dots,a_{\theta_{i-1}}^{RL})$ at each episode.

The third term $a^{CBF}_{t}$ in (17) is a real-time value based on the deterministic value $s_{t}$ , $a^{RL}_{\theta_{k}}(s_{t})$ and $\bar{a}_{\phi_{k}}(s_{t})$ . Although there exists an unknown term $d$ in the system (1), we can still solve the dynamical safety in the approximated polynomial system (8). So, the optimal $a_{t}$ in (17) can be computed by the SOS program below with deterministic $a^{RL}_{\theta_{k}}$ and $\bar{a}_{\phi_{k}}$

$\displaystyle\qquad\underset{s_{t}\in\mathcal{S},a_{k}\in\mathcal{A};L(s_{t}),M_{i}(s_{t})\in\mathcal{P}^{SOS};\;\;}{a^{*}\quad=\quad\arg\min\;{\\|a_{k}\\|_{2}}}$		(18)
s.t.	$\displaystyle\;\quad\Delta{h}(s_{t},a_{k})-L(s_{t})h(s_{t})\in\mathcal{P}^{SOS},$
$\displaystyle-\Delta{h}(s_{t},a_{k})-M_{i}(s_{t})\mu_{i}(s_{t})\in\mathcal{P}^{\text{SOS}}.$

Thus, we can establish a controller by satisfying the solution of (LABEL:eq:sosclb) over the learning process.

Theorem 1.

Given a barrier function $h$ in (9), a partially unknown dynamical system (1) and a corresponding approximated system (8), while (8) is a stochastic statement of (1) within the probabilistic range $[(1-\delta)^{k},1]$ , suppose there exists an action $a_{t}$ satisfying (LABEL:eq:sosclb) in the following form:

	$\displaystyle a_{t}(s_{t})=$	$\displaystyle a^{RL}_{\theta_{k}}(s_{t},a_{t},s_{t+1},r_{t})+\bar{a}_{\phi_{k}}(s_{t},\sum_{i=0}^{k-1}(s_{t},a^{CBF}_{i}))$		(19)
		$\displaystyle+a^{CBF}_{t}(s_{t},a^{RL}_{\theta_{k}},\bar{a}_{\phi_{k}}).$		(19)

Then, the controller (19) guarantees the system (1) inside the safe region within the range of probability $[{(1-\delta)}^{n},1]$ .

Proof.

Regarding the system (8), this result follows directly from Lemma 3 by solving the SOS program (LABEL:eq:sosclb). The only different part of SOS program (LABEL:eq:sosclb) from the SOS program (LABEL:eq:CLF-CBF-discrete) in Lemma 3 is the action $a_{k}$ here contains additional deterministic value $a_{\theta_{k}}^{RL}(s_{t})$ and $\bar{a}_{\phi_{k}}(s_{t})$ .

Since the output of (LABEL:eq:sosclb) can regulate the dynamics of the model (8) in a safe region, while the approximated model (8) is a stochastic statement of the original system (1) with the probability greater or equal to $(1-\delta)^{k}$ . Then, the solution of (LABEL:eq:sosclb) can be regarded as a safe control to drive the system (1) far from dangerous, which ends the proof. ∎

We display an overview of the whole steps in the combination of the aforementioned factors over the learning process. The detailed workflow is outlined in Algorithm 1

Input: Origin system (1); barrier function

h

Output: RL optimal policy

\pi

1 Preprocess (1) into (8).

2 Create the tuple

\hat{D}

to store

\{s_{t},a_{t},s_{t+1},r_{t}\}

\hat{D}

3 for $k\in\{1,2,\dots,k\}$ do

4 Execute SOSP (LABEL:eq:sosclb) to obtain the real-time CBF controller

a^{CBF}_{k}

and store it to train previous CBF controller

\bar{a}_{\theta_{k}}^{CBF}

5 Actuate the agent with

a_{t}

in (19).

6 Construct

\hat{D}

and update

\theta_{k}

and

\phi_{k}

directly.

8return

\pi

Algorithm 1 DDPG-SOSP

IV Numerical Example

A swing-up pendulum model from OpenAI Gym environment (Pendulum-v1) is used to verify the above theorems,

\displaystyle ml^{2}\ddot{\theta}=mgl\sin(\theta)+a.

(20)

Let $s_{1}=\theta$ , $s_{2}=\dot{\theta}$ . The dynamics of (20) are defined as

\displaystyle\begin{aligned} \begin{bmatrix}\dot{s}_{1}\\ \dot{s}_{2}\end{bmatrix}=\begin{bmatrix}s_{2}\\ \;-\frac{g}{l}\sin{(s_{1})}+\frac{a}{ml^{2}}+d\;\end{bmatrix},\end{aligned}

(21)

where $d$ denotes unknown dynamics that generate by inaccurate parameters $\bar{m}=1.4$ , $\bar{l}=1.4$ , as [23] introduced. When we try to construct a polynomial system (8), the $\sin(s_{1})$ in (21) will be approximated by Chebyshev interpolants within $s_{1}\in[-3,3]$ . Then, with SOSOPT Toolbox [34], Mosek solver [35] and Tensorflow, we implement Algorithm 1 in the pendulum model.

The related model parameters are given in Table 1.

TABLE 1: Swing-up Pendulum Model Parameters

Model Parameter	Symbol	Value	Units
Pendulum mass	$m$	$1.0$	kg
Gravity	$g$	$10.0$	$\text{m}/\text{s}^{2}$
Pendulum length	$l$	$1.0$	m
Input torque	$a$	$[-15.0,15.0]$	N
Pendulum Angle	$\theta$	$[-1.00,1.00]$	rad
Angle velocity	$\dot{\theta}$	$[-60.0,60.0]$	$\text{rad}/\text{s}$
Angle acceleration	$\ddot{\theta}$	—	$\text{rad}/\text{s}^{2}$

We want to maintain the pendulum angle $\theta$ always in a safe range $[-1.0,1.0]$ during the learning process. Three RL algorithms are selected and compared in this example, including the DDPG-ONLY algorithm [5], CBF-based DDPG-QP algorithm [23] and CBF-based DDPG-SOSP algorithm (our work). The codes of CBF-based DDPG-SOSP can be found at the url: https://github.com/Wogwan/CCTA2022_SafeRL.

All of these algorithms are trained in $150$ episodes and each episode contains $200$ steps. Each step is around $0.05s$ . And the reward function $r=\theta^{2}+0.1\dot{\theta}^{2}+0.001a^{2}$ is defined such that the RL agent are expected to keep the pendulum upright with minimal $\theta$ , $\dot{\theta}$ and $\ddot{\theta}$ .

Fig. 2 compares the collected maximum $|\theta|$ at each episode by using different algorithms. As a baseline algorithm, DDPG-ONLY explored every state without any safety considerations, while DDPG-QP sometimes violated the safe state and DDPG-SOS completely kept in safe regions.

The historical maximum value of $|\dot{\theta}|$ of these algorithms is compared and shown in Fig. 3. It is found that DDPG-SOS is able to maintain the pendulum into a lower $\dot{\theta}$ easily than others over episodes.

In Fig. 4, from the reward curve of these algorithms, it is easy to observe the efficiency of different algorithms: DDPG-SOS obtains comparatively lower average reward and thus a better performance.

Fig. 5 shows the first ( $2^{nd}$ episode) and the final ( $150^{th}$ episode) policy guided control performance between DDPG-QP and DDPG-SOSP algorithm. We observed $50$ steps of the pendulum angle to highlight the superiority of these two algorithms. Both in Fig. 5(a) and (b), the final policy can reach a smoother control output with less time. Although DDPG-SOSP takes a quicker and smoother action to stabilize the pendulum than DDPG-QP, but the time consuming will increase due to the dynamics regression and optimization computation under uncertainty. Accordingly, the result of DDPG-SOSP algorithm of model (20) is not only obviously stabler than DDPG-QP, but also maintaining the RL algorithm action’s safety strictly.

V Conclusion

In this paper, we consider a novel approach to guarantee the safety of reinforcement learning (RL) with sum-of-squares programming (SOSP). The objective is to find a safe RL method toward a partial unknown nonlinear system such that the RL agent’s action is always safe. One of the typical RL algorithms, Deep Deterministic Policy Gradient (DDPG) algorithm, cooperates with control barrier function (CBF) in our work, where CBF is widely used to guarantee the dynamical safety in control theories. Therefore, we leverage the SOSP to compute an optimal controller based on CBF, and propose an algorithm to creatively embed this computation over DDPG. Our numerical example shows that SOSP in the inverted pendulum model obtains a better control performance than the quadratic program work. It also shows that the relaxations of SOSP can enable the agent to generate safe actions more permissively.

For the future work, we will investigate how to incorporate SOSP with other types of RL including value-based RL and policy-based RL. Meanwhile, we check the possibility to solve a SOSP-based RL that works in higher dimensional cases.

References

[1] R. S. Sutton, A. G. Barto, ”Reinforcement learning: An introduction,” MIT press, 2018.
[2] Y. Duan, X. Chen, R. Houthooft, J. Schulman, P. Abbeel, “Benchmarking deep reinforcement learning for continuous control,” in Proc. Int. Conf. on Machine Learning, pp. 1329–1338, PMLR, 2016.
[3] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al., “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015.
[4] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, et al., “Mastering the game of go with deep neural networks and tree search,” Nature, vol. 529, no. 7587, pp. 484–489, 2016.
[5] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, D. Wierstra, “Continuous control with deep reinforcement learning,” ArXiv:1509.02971, 2015.
[6] Li, Z., Cheng, X., Peng, X. B., Abbeel, P., Levine, S., Berseth, G., Sreenath, K., ”Reinforcement Learning for Robust Parameterized Locomotion Control of Bipedal Robots,” in Proc. Int. Conf. on Robotics and Automation, pp. 2811–2817, 2021.
[7] J. Peters, S. Schaal, “Reinforcement learning of motor skills with policy gradients,” Neural Networks, vol. 21, no. 4, pp. 682–697, 2008.
[8] R. S. Sutton, et al. ”Policy gradient methods for reinforcement learning with function approximation,” Advances in Neural Information Processing Systems, 1999.
[9] D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, M. Riedmiller, “Deterministic policy gradient algorithms,” in Proc. Int. Conf. on Machine Learning, pp. 387–395, PMLR, 2014.
[10] J. Kober, J. A. Bagnell, J. Peters, “Reinforcement learning in robotics: A survey,” Int. Journal of Robotics Research, vol. 32, no. 11, pp. 1238–1274, 2013.
[11] P. Kormushev, S. Calinon, D. G. Caldwell, “Reinforcement learning in robotics: Applications and real-world challenges,” Robotics, vol. 2, no. 3, pp. 122–148, 2013.
[12] J. Levinson, J. Askeland, J. Becker, J. Dolson, D. Held, S. Kammel, J. Z. Kolter, D. Langer, O. Pink, V. Pratt, et al., “Towards fully autonomous driving: Systems and algorithms,” IEEE Intelligent Vehicles Symposium, pp. 163–168, 2011.
[13] B. R. Kiran, I. Sobh, V. Talpaert, P. Mannion, A. A. Al Sallab, S. Yogamani, P. Pérez, “Deep reinforcement learning for autonomous driving: A survey,” IEEE Trans. on Intelligent Transportation Systems, 2021.
[14] L. Wang, D. Han, M. Egerstedt, “Permissive barrier certificates for safe stabilization using sum-of-squares,” in Proc. Amer. Control Conf., pp. 585–590, 2018.
[15] D. Han, D. Panagou, “Robust multitask formation control via parametric Lyapunov-like barrier functions,” IEEE Trans. on Automatic Control, vol. 64, no. 11, pp. 4439–4453, 2019.
[16] G. Chesi, ”Domain of attraction: analysis and control via SOS programming”, Springer Science & Business Media, vol. 415, 2011.
[17] D. Han, G. Chesi, Y. S. Hung, “Robust consensus for a class of uncertain multi-agent dynamical systems,” IEEE Trans. on Industrial Informatics, vol. 9, no. 1, pp. 306–312, 2012.
[18] D. Han, G. Chesi, “Robust synchronization via homogeneous
parameter-dependent polynomial contraction matrix,” IEEE Trans. on Circuits and Systems I: Regular Papers, vol. 61, no. 10, pp. 2931–2940, 2014.
[19] D. Han, M. Althoff, “On estimating the robust domain of attraction for uncertain non-polynomial systems: An LMI approach,” in Proc. Conf. on Decision and Control, pp. 2176–2183, 2016.
[20] B. Felix, M. Turchetta, A. Schoellig, A. Krause, ”A Safe model-based reinforcement learning with stability guarantees,” Advances in Neural Information Processing Systems, pp. 909–919, 2018.
[21] M. Alshiekh, R. Bloem, R. Ehlers, B. Könighofer, S. Niekum, U. Topcu, “Safe reinforcement learning via shielding,” in AAAI Conf. on Artificial Intelligence, vol. 32, no. 1, 2018.
[22] C. Steven, N. Jansen, S. Junges, U. Topcu, ”Safe Reinforcement Learning via Shielding for POMDPs,” ArXiv:2204.00755, 2022.
[23] R. Cheng, G. Orosz, R. M. Murray, J. W. Burdick, “End-to-end safe reinforcement learning through barrier functions for safety-critical continuous control tasks,” in AAAI Conf. on Artificial Intelligence, vol. 33, no. 1, 2019.
[24] R. Cheng, A. Verma, G. Orosz, S. Chaudhuri, Y. Yue, J. W. Burdick, ”Control Regularization for Reduced Variance Reinforcement Learning,” in Proc. Int. Conf. on Machine Learning. pp. 1141–1150, 2019.
[25] S. C. Hsu, X. Xu, A. D. Ames, “Control barrier function based quadratic programs with application to bipedal robotic walking,” in Proc. Amer. Control Conf., pp. 4542–4548, 2015.
[26] T. Akshay, Z. Jun, K. Sreenath. ”Safety-Critical Control and Planning for Obstacle Avoidance between Polytopes with Control Barrier Functions,” in Proc. Int. Conf. on Robotics And Automation, accepted, 2022.
[27] L. Wang, E. A. Theodorou, M. Egerstedt, “Safe learning of quadrotor dynamics using barrier certificates,” in Proc. Int. Conf. on Robotics And Automation, pp. 2460–2465, 2018.
[28] P. Martin, ”Markov decision processes: discrete stochastic dynamic programming”, John Wiley & Sons, 2014.
[29] A. Lederer, J. Umlauft, S. Hirche, “Uniform error bounds for Gaussian process regression with application to safe control,” Advances in Neural Information Processing Systems, pp. 659–669, 2019.
[30] H. Huang, D. Han, ”On Estimating the Probabilistic Region of Attraction for Partially Unknown Nonlinear Systems: An Sum-of-Squares Approach,” in Proc. Chinese Control and Decision Conf., accepted, 2022.
[31] D. Han, H. Huang, ”Sum-of-Squares Program and Safe Learning on Maximizing the Region of Attraction of Partially Unknown Systems,” in Proc. Asian Control Conf., 2022.
[32] L. N. Trefethen, ”Approximation Theory and Approximation Practice,” SIAM, 2019.
[33] M. Putinar, “Positive Polynomials on Compact Semi-algebraic Sets,” Indiana University Mathematics Journal, vol. 42, no. 3, pp. 969–984, 1993.
[34] P. Seiler, ”SOSOPT: A toolbox for polynomial optimization,”
ArXiv:1308.1889, 2013.
[35] M. ApS, ”Mosek optimization toolbox for Matlab,” User’s Guide And Reference Manual, Ver. 4, 2019.

Barrier Certified Safety Learning Control: When Sum-of-Square Programming Meets Reinforcement Learning

Abstract

I Introduction

II Preliminary

II-A Reinforcement Learning

II-B Gaussian Process

Lemma 1.

II-C Control Barrier Function

Lemma 2.

Lemma 3.

Proof.

III CBF Guiding Control with Reinforcement Learning

III-A SOS Program Based CBF

Remark.

III-B SOS Program Based CBF with Reinforcement Learning

Theorem 1.

Proof.

IV Numerical Example

V Conclusion

References

Barrier Certified Safety Learning Control:
When Sum-of-Square Programming Meets Reinforcement Learning