An Efficient Reachability-Based Framework for
Provably Safe Autonomous Navigation in Unknown Environments

Andrea Bajcsy*
Somil Bansal*
Eli Bronstein
Varun Tolani
Claire Tomlin

University of California, Berkeley


Real-world autonomous vehicles often operate in a priori unknown environments. Since most of these systems are safety-critical, it is important to ensure they operate safely in the face of environment uncertainty, such as unseen obstacles. Current safety analysis tools enable autonomous systems to reason about safety given full information about the state of the environment a priori. However, these tools do not scale well to scenarios where the environment is being sensed in real time, such as during navigation tasks. In this work, we propose a novel, real-time safety analysis method based on Hamilton- Jacobi reachability that provides strong safety guarantees despite environment uncertainty. Our safety method is planner- agnostic and provides guarantees for a variety of mapping sensors. We demonstrate the proposed approach in simulation and on a hardware test-bed to provide safety guarantees around a state-of-the-art vision-based, learning-based planner.


Bajcsy, Bansal, Bronstein, Tolani, Tomlin

An Efficient Reachability-Based Framework for
Provably Safe Autonomous Navigation in Unknown Environments



Local Update Method. Visualization of local update method updating the value function from the warm-started function (orange) to the final converged value function (red). The states considered by the local update method are depicted by the dashed blue regions.

 [Coming Soon!]

Simulation Results

Simulated Sensors and Planners. The vehicle trajectories for the problem setting for both planners (RRT and Spline planners) and both sensors (LiDAR and Camerasensors) with the safety controller computed from each of the three candidate safety approaches. The proposed framework is able to safely navigate the vehicle to the goal in all cases. When the planner makes unsafe decisions,the safety controller intervenes (the states marked in red) to ensure safety.
Simulated Camera Results
Metric Planner HJI-VI Warm Local

Average Compute Time (s)
RRT 45.688 26.290 0.596
Spline 51.723 12.489 0.898

% Over-conservative States
RRT 0.0 1.112 0.517
Spline 0.0 0.474 0.506
Simulated LiDAR Results
Metric Planner HJI-VI Warm Local

Average Compute Time (s)
RRT 21.145 6.075 1.108
Spline 25.318 3.789 1.158

% Over-conservative States
RRT 0.0 0.032 0.290
Spline 0.0 0.024 0.240
Computational Results. Numerical comparison of average compute time and relative volume of over-conservative states for each planner and sensor across different BRS update methods. Local updates compute an almost exact BRS in approximately 1 second, and are significantly faster than both HJI-VI and warm-start.

Experiment Videos

We test the proposed approach in hardware using a TurtleBot 2 with a mounted stereo RGB camera. For planning, we use a state-of-the-art neural-network-based planner that uses the current RGB image to determine a candidate next state. We ran the experiment with and without the safety controller and show corresponding videos below. Without the safety controller, the learning-based planner struggles with making sharp turns near the corner, and eventually collides into the obstacle (the chair, in this case). However, when the learning-based planner is used within the proposed safety framework, the safety controller is able to account for this unsafe situation and safely steer the vehicle away from the obstacle.

Experiment 1: No safety. When the learning-based planner is deployed, it makes goal-directed decisions but does not guaruntee that these decisions will not result in collisions. Here we see one such scenario.

Experiment 2: Safety. When the learning-based planner is used with the proposed safety framework, the robot is able to make goal-directed decisions while being collision-free.


This research is supported in part by the DARPA Assured Autonomy program under agreement number FA8750-18-C-0101, by NSF under the CPS Frontier project VeHICaL project (1545126), and by SRC under the CONIX Center.

This webpage template was borrowed from some colorful folks.