What is Hamilton-Jacobi (HJ) Reachability Analysis?

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

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

The Brief Explanation

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

Coming soon!  For now, please see Prof. Ian Mitchell's PhD thesis: Application of Level Set Methods to Control and Reachability Problems in Continuous and Hybrid Systems.

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 become completely infeasible to solve.  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.  We are working on a new project called 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.  For example, right now we are working with the HART lab to analyze safety guarantees for the elderly when transitioning from a sitting to a standing position.  We are also looking into using reachability for freshwater containment systems and watershed analysis.