What is Reachability Decomposition?

Hamilton Jacobi (HJ) reachability allows us to take the physical dynamics of a system and construct a set that describes all all initial states from which the system can achieve a goal (or avoid an unsafe area), even in worst case scenarios.  For more background on HJ reachability analysis see the reachability page.

However, computing what is essentially all possible optimal trajectories of a system in order to perform this analysis is extremely computationally intensive; generally we can only use this method for very simplistic dynamics of 4 states or less.  In our lab we work on developing creative ways to split complex dynamics into multiple subsystems, allowing us to compute these goal-based path-planning sets in lower dimensions that can then be reconstructed.  

We can compute exact solutions for decoupled dynamics and dynamics that are coupled in a specific way that results in what we call "self-contained subsystems."  For dynamics that don't fall into this form we can compute approximate solutions.  These advancements allow us to look into many new applications, from multi-vehicle avoidance to safety boundaries for the movement of elderly people as they transition from sitting to standing.

Part 1: Exact Decomposition

We can decompose high-dimensional systems of a specific form into multiple lower-dimensional subsystems that are more computationally tractable to analyze.  Once these subsystems are processed, we can recompose the high-dimensional analysis in a way that preserves the exact solution.  This section will discuss the form needed to perform this exact decomposition by showing a simple example, a discussion of how to deal with coupled control variables, and the general form needed.  For a quick overview, see the video below from our 2016 ICRA paper:

Example:

Now, let's say we have a 3D system where two of the dimensions are dependent on the third.  A good example is the classic dubins car, where velocity in x and y depend on the speed and angle of the car, and the angle depends on the rotational velocity (which in this case is the input):

 We can split this system into two separate subsystems as shown below.  Note that each subsystem is completely self-contained; the dynamics only depend on the states in that particular subsystem.

We can now do reachability analysis on both of these smaller subsystems.  Once completed, we find the value of the full system by performing the following calculation:

In words what we are doing is saying that the value at a particular point in the 3D system is the max, or worst case, value between the two 2D systems.   A visualization of the solution can be seen in the ICRA video above.  

Dealing with Coupled Controls

Note that in this case the subsystems are coupled through the control variable, u.  This complicates the situation a bit.  If there is no coupling of the control, this process holds for all problems.  If there is coupling between the controls then this problem is only guaranteed to be exact for situations in which it is acceptable to use the optimal control for either subsystem 1 or subsystem 2.  Let's review when this is and is not true.

First, consider the case below where you want to reach a box in (x,y) space (shown in gray).  When we decompose the the system into subsystems 1 and 2, we also must decompose this target box as the intersection of the "back projection" between the two subsystem's goal sets--in other words, the intersection between the red and the blue sets shown in the figure.  After analysis, subsystem 1 will tell you to turn right to enter the red area, where it perceives to be the goal.  Subsystem 2 will tell you to turn left to enter the blue area, which is its goal.  Following either control in this case would be wrong.  However, if instead your target was the union of these two sets (the entire cross shown in the picture), following the orders from either subsystem would in fact get you to the goal.

Now let's consider the case when the gray box is an unsafe area that you want to avoid.  In this case, subsystem 1 will tell you to turn left to avoid the red area.  Subsystem 2 will tell you to turn right to avoid the blue area.  Obeying either control will work and keep you out of the gray box (i.e. the intersection of the two unsafe areas).  But if instead you wanted to avoid the union of the sets, neither control will prevent you from entering the unsafe area. 

Let's summarize the cases when this will and will not work:

Remember that is is only for the case where we have coupled control variables across multiple subsystems.  In the case where the controls are decoupled, every case works.  We are currently working on finding new ways to handle the coupled control cases that currently do not work.  If you have any thoughts or suggestions, please reach out to us!

General Form for Self-Contained Subsystems

The general form that a system must be in to use our self-contained subsystem method is as follows.  Note that we are only breaking the system into two subsystems for ease of notation, but in practice this can be done for many subsystems.

The full system can be broken into 3 components:

Where the derivatives of the first set of states depend only on themselves and the coupled states (like the angle in the example).  Likewise, the derivatives of the second set of states depend only on themselves and the coupled states.  The coupled states depend only on themselves.  Note that each component can also depend on shared control (like the rotational velocity in the example), and shared disturbance.  Here is what we just stated put mathematically:

If our system can be put in this form, then we can decompose it in the same way that we decomposed the example:

For more details on this form and the proofs behind our claims, please see [2] (conference paper) and [3] (journal paper) of the related papers below.

Part 2: Approximate Decomposition

There are situations where our system cannot be put into the self-contained subsystem form for exact decomposition.  In these cases we can consider approximate decomposition.  We can compute under-approximations of reachable sets for systems of a general form.

Let's reconsider the dubins car example, only this time we will add in speed as a state whose derivative is acceleration:

Now we know that we can decompose this using self-contained subsystems, but for now let's assume we weren't aware of that method.  Even though these dynamics are nonlinear and coupled, let's just pretend that we can decouple them as follows:

Subsystem 1 depends on the speed v, but it has no information about this state.  Similarly, subsystem 2 depends on the angle theta, but it has no information about that state.  To compensate for this, as we perform reachability analysis we will assume that the missing states are unknown "virtual disturbances" that are actively choosing to be whatever is most inconvenient value possible.

If we solve our example blindly we find that we get an extreme under-approximation.  This is because we are allowing our virtual disturbances to span a wide range of values.  If instead we solve each subsystem multiple times over smaller sections of the disturbance bounds, we find that we can reconstruct more of the full reachable set. 

If we split the angle into 16 sections and the speed into 2 sections we can reconstruct 21.7% of the volume in 86 seconds, compared to 12.7 hours to compute the full reachable set.  Below is a graph showing the computation time vs. how fine the state space grid is.  The full formulation quickly becomes intractable, whereas the decoupled approximation can be computed for much finer grids.

Related Papers

[1] Mo Chen*, Sylvia Herbert*, Claire J. Tomlin, "Fast Reachable Set Approximations via State Decoupling Disturbances," IEEE Conference on Decision and Control, 2016. cite

[2] Mo Chen, Sylvia Herbert, Claire J. Tomlin, "Exact and Efficient Hamilton-Jacobi-based Guaranteed Safety Analysis via System Decomposition," IEEE International Conference on Robotics and Automation, 2017. cite

[3] Mo Chen, Sylvia Herbert, Mahesh S. Vashishtha, Somil Bansal, Claire J. Tomlin, “A General System Decomposition Method for Computing Reachable Sets and Tubes,” IEEE Transactions on Automatic Control (submitted). cite