What is Safety Analysis for Autonomous Systems?
You are in your car driving on the road. As you round a corner, you see a deer in the middle of the street. Will you be able to slam on your brakes and decelerate before you hit the deer? If not, will you be able to swerve out of the way safely? At what point are you doomed to crash? Could we make control systems in cars that ensure you will never be in a position where you are doomed to crash?
Safety analysis uses tools like Hamilton-Jacobi Reachability to find the mathematical answers to such questions. Let’s say I have some system that evolves over time (e.g. a car, a glucose monitor, an HVAC system in a house) and I can also define what would be unsafe for that system (e.g. hitting obstacles, allowing glucose to drop to dangerous levels, letting a house get too warm or too cold). Safety analysis claims to find the set of initial conditions from which your system will inevitably enter those unsafe conditions (e.g. when you are in a car at high speeds headed straight for an obstacle, and no matter how hard you brake or turn you are going too fast to prevent a crash). Once you know this reachable set of initial conditions that lead to unsafe states, you can work to ensure that your systems will never enter those inevitable conditions.
What is Hamilton-Jacobi (HJ) Reachability Analysis?
The Brief Explanation
An animation of how we produce a reachable set. First the goal (or unsafe set) is defined, shown here as the blue circle. We then create a level set function that is a signed distance function: negative inside the set and positive outside. We propagate this function using HJ reachability for the desired time horizon. Finally, we take the zero slice of this function to produce the reachable set
HJ reachability analysis is all about optimal control and guarantees for reaching goals and staying safe. When given a dynamic system and a goal, this method produces the set of initial states from which your system is guaranteed to reach that goal when using optimal control. What’s more, the method provides the optimal control to reach the goal. This can also be done for obstacles and unsafe states: HJ reachability will provide a set of initial states that your system must stay out of in order to remain safe, as well as the control to accomplish this. We can combine scenarios with both goals and obstacles, and we can even consider worst-case disturbances (e.g. wind).
The Thorough Explanation
Please see our tutorial paper for a more thorough introduction.
Available Toolboxes
helperOC (MATLAB) — Our public code for computing reachable sets can be cloned or downloaded at https://github.com/HJReachability/helperOC (note: this is essentially a user-friendly wrapper with extra functionality for Prof. Ian Mitchel’s level set toolbox). This MATLAB repository is the most user-friendly, and also contains a lot of visualization functionality. The downside is that it is not as efficient as the other toolboxes.
hj_reachability (Python) — this is the python implementation of the above toolboxes, lead by Edward Schmerling at Stanford. It is much more efficient than the MATLAB version and has an active group maintaining and updating it. It currently lacks some of the niche functionality of the helperOC toolbox, but is very good for most standard reachability applications and is adding new functionality rapidly.
BEACLS (C++) — BEACLS stands for Berkeley Efficient API in C++ for Level Set methods. It is essentially a reimplementation of the MATLAB toolboxes in C++ with tweaks to improve efficiency and compatibility with GPUs. It is quite a bit faster than the MATLAB implementation, but sacrifices readability for performance.
optimized_dp (Python/C++) — This toolbox was built by Prof. Mo Chen at Simon Fraser University, with the goal of having an easy python-based user interface to set up a reachability problem, and then conversion to fast C++ code via HeteroCL.
DeepReach (Python) — Toolbox from Prof. Somil Bansal at the University of Southern California for approximating high-dimensional value functions using sinusoidal neural networks. Paper here.
Flow* — Developed by Prof. Sriram Sankaranarayanan at CU Boulder. Good for computing safe sets for large numbers of states, and computing sets that do not have control/disturbance inputs (i.e. policy is already determined and plugged into dynamics). Uses scalability tools that lead to over-approximation of reachable sets.
Why Study HJ Reachability?
Reachability analysis is extremely useful in safety-critical scenarios. When flying a plane or administering anesthetics, accidental mistakes from less rigorous planning methods can result in disaster. Reachability is able to provide guarantees on what is safe, as well as how to implement controls to accomplish your goal. What’s more, HJ Reachability can handle nonlinear dynamics and worst-case external disturbances.
The challenges in HJ reachability lie in its expensive computational cost. Due to the nature of dynamic programming the computational complexity of solving a reachability problem rises exponentially with the number of dimensions in the system. This means that systems with more than ~4 dimensions are generally intractable to solve analyses for. We have been working on methods to circumvent this issue by splitting systems into separate sub-systems that can be solved independently and then recombined. Depending on the system and the decomposition we can acquire either exact or conservative results of the true reachable set or tube. Read more on our decomposition work here.
Another fun research direction is to merge the guarantees of reachability with the speed and convenience of other path planning methods. An example is the framework FaSTrack: Fast and Safe Tracking. In this project we developed a tool to precompute a maximum tracking error bound between a simple and a complicated model of an autonomous system. This allows us to plan trajectories through an environment using the simple model, while ensuring a maximum bound on the tracking error between this planned trajectory and the executed trajectory. More information on FaSTrack can be found here.
Finally, we are always looking for new and interesting applications of reachability. Our core application area has been both manned aerial systems and UAVs, but with the recent advances we have made in theory we are able to expand our reach in applications such as biological systems, environmental systems, and power systems.