1 of 25

Refining Control Barrier Functions through Hamilton-Jacobi Reachability

Sander Tonkens and Sylvia Herbert

CBFs meet HJR

2022

2 of 25

A popular tool to ensure safety in critical control applications are value functions

2

The desired safety constraint

Long-term effect of the dynamics

A single scalar function

Level – measure of the safety margin

Gradient – unsafe / safe direction

CBFs meet HJR

2022

3 of 25

Unfortunately, synthesizing a safe CBF is notoriously difficult…

3

We update an approximate CBF leveraging dynamic programming to obtain a CBF that is guaranteed to be safe

CBFs meet HJR

2022

4 of 25

Outline

  • Control barrier functions meet HJ reachability

​

  • A simple idea: Dynamic programming with a candidate CBF

​

  • Theoretical guarantees

​

​

4

CBFs meet HJR

2022

5 of 25

Outline

  • Control barrier functions meet HJ reachability

​

  • A simple idea: Dynamic programming with a candidate CBF

​

  • Theoretical guarantees

​

​

5

CBFs meet HJR

2022

6 of 25

The value function is synthesized based on both the system’s dynamics and its environment

6

 

Desired safe region

 

 

state

 

 

CBFs meet HJR

2022

7 of 25

Control Barrier Functions have emerged as a popular tool for maintaining safety

7

 

Safety

Derivative of safety

CBFs meet HJR

2022

8 of 25

Any safe CBF’s 0-superlevel set is guaranteed to be a subset of the maximally safe set: the viability kernel

8

 

 

 

CBFs meet HJR

2022

9 of 25

The viability kernel can be described by an optimal control problem

9

 

System Dynamics

Cost function

Objective:

CBFs meet HJR

2022

10 of 25

Hamilton-Jacobi reachability analysis solves this optimal control problem using dynamic programming

​

​

​

​

​

​

10

Cost-to-go

Current cost

Worst-case cost over entire trajectory

We want to maximize the cost, i.e. be as safe as possible

Terminal cost: Distance to obstacle

CBFs meet HJR

2022

11 of 25

The viability kernel is computed backward in time and is the 0-superlevel set of the HJ value function

11

 

 

Desired safe region

 

 

 

Target set

Fisac et al., HSCC 2015

 

CBFs meet HJR

2022

12 of 25

How to refine CBFs using HJ reachability?

12

CBFs meet HJR

2022

13 of 25

Synthesizing an approximately correct CBF is usually easy!

Conservative

13

Unsafe

CBFs meet HJR

2022

14 of 25

Outline

  • Control barrier functions meet HJ reachability

​

  • A simple idea: Dynamic programming with a candidate CBF

​

  • Theoretical guarantees

​

​

14

CBFs meet HJR

2022

15 of 25

We revisit the classic Adaptive Cruise Control problem and consider a conservative CBF

15

ego vehicle

lead vehicle

 

 

 

 

 

 

 

Safety objective

 

 

CBFs meet HJR

2022

16 of 25

We initialize HJ reachability with a conservative CBF and recover a larger safe set!

16

 

 

Safety constraint

Bounded input

CBFs meet HJR

2022

17 of 25

The CBF is optimal when neglecting friction, whereas the CBVF adapts to incorporate friction

17

CBFs meet HJR

2022

18 of 25

This method can be used to improve both the performance and the safety of CBFs!

Our simple, intuitive, framework:

  • Enlarges the safe set of overly conservative CBFs, making them less invasive!
  • Refines unsafe CBFs to render them safe!
    • Becomes safer with every iteration, so can be used in-the-loop
  • Retains the principled online enforcement of safety through the CBF derivative constraint

​

…. All of this with theoretical guarantees!

18

CBFs meet HJR

2022

19 of 25

Outline

  • Control barrier functions meet HJ reachability

​

  • A simple idea: Dynamic programming with a candidate CBF

​

  • Theoretical guarantees

​

​

19

CBFs meet HJR

2022

20 of 25

Our method guarantees the value function does not become less safe throughout the DP iterations

20

  1. A state with a conservative value will always remain conservative
  2. A state with an unsafe value will never become more unsafe

​

CBFs meet HJR

2022

21 of 25

… And is additionally guaranteed to converge to a control invariant subset of the viability kernel

21

CBFs meet HJR

2022

22 of 25

Lastly, it will satisfy the CBF derivative constraint everywhere in the state space!

22

 

 

 

CBFs meet HJR

2022

23 of 25

Our method is applicable to a wide variety of CBF synthesis techniques

23

Refine CBF to circumvent

high-relative degree systems

Make candidate CBF safe

Reduce online computation of

backup CBF

Refine safe, yet conservative, CBF

CBFs meet HJR

2022

24 of 25

This method is a practical method to enhance the safety of deployed robotic systems

  • It can be used to locally refine or certify learned CBFs around the boundary of the safe set

​

  • We can implement it in-the-loop on robotic hardware when faced with modified disturbances (e.g., more wind)

​

  • Approximate dynamic programming may alleviate some of the computational complexity

​

​

24

CBFs meet HJR

2022

25 of 25

Contributions

A framework for value-function based safety that formally enforces AND encodes safety…

  1. Guarantees the CBVF becomes monotonically safer throughout the DP iterations and converges to a safe set
  2. Can be used to refine any type of synthesized CBF, improving safety and empirically improving performance

​

25

Tonkens and Herbert, IROS 2022 (Submitted)

arxiv.org/abs/2204.12507

github.com/UCSD-

SASLab/refineCBF

CBFs meet HJR

2022