Code and algorithms for computing online guaranteed inner- and outer-approximations of reachable sets.
The main idea behind our method is that we know what states our system can nominally reach starting from a particular initial state after a given amount of time; this is known as the nominal reachable set. We then consider the case of our system dynamics changing (thus becoming off-nominal), in addition to our control authority changing (i.e., the allowable control inputs we can apply changes).
Naturally, one may ask what the reachable set will be for this off-nominal case. In some applications, computation from scratch is intractable, say, if the system that would compute the reachable set has limited resources (e.g., memory), or the exact change in dynamics is not clearly known (say, we only have a worst-case norm bound on some parameters). In either case, one wishes to use the nominal reachable set, and modify it to be either an inner- or outer-approximation of the off-nominal reachable set, without explicitly recomputing the exact shape of the set from scratch. This is exactly what our method allows for; given some rudimentary bounds on the change in dynamics, we can directly compute how to reshape the nominal reachable set to approximate the (unknown) off-nominal reachable set.
More information on these ideas can be found in a talk I gave on the topic.
The theoretical underpinnings for this work are currently under submission under the title 'Online Guaranteed Reachable Set Approximation for Systems with Changed Dynamics and Control Authority.' A preprint version can be found on ArXiV.
Consider the nominal dynamics
where ,
, and the off-nominal dynamics
Let us first assume . Define
,
, and
.
A running assumption in our work, namely a nonlinear growth condition, reads
Assumption 2
For all
where are continuous and positive and
is continuous, monotonic, nondecreasing and positive. In addition,
is uniformly monotonically nondecreasing in
.
For the off-nominal dynamics , we assume the following:
Assumption 3
For all ,
,
, we have
where is a positive, continuous function on
.
Equipped with this information, we present a ball-based version of the Bihari inequality:
Lemma 1 (Modified Bihari Inequality)
Assume Assumptions 2 and 3 hold. Let there be and
, such that
,
, and
.
Then, satisfies
for all , where
for arbitrary and for all
for which it holds that
We are mostly interested in the function . Let
denote the known nominal reachable set, and let
denote the unknown off-nominal reachable set. We note to define one more operation before we can state one of our main results.
Given a set and a scalar
, let the ball-based fattening of
by
be defined as:
where is a closed ball of radius
.
Given the assumptions of Lemma 1, as well as some additional mild technical assumptions, our theory proves:
- Inner-approximation:
- Outer-approximation
We also provide tighter bounds by consider hyperrectangular fattenings, which consider each dimension separately; details can be found here.
While the slimming and fattening operations are quite straightforward, obtaining is the hardest step.
In our implementation, we use trapezoidal integration to obtain and the integrals of
. To compute
, we use the secant method with tight tolerances.
For a Python implementation, see `python/bihari.py as well as the inline documentation.
This demo should work on Python 3.6 or greater, with the same dependencies as outlined in python/requirements.txt:
- numpy
- scipy
- shapely
- matplotlib
In addition, the *.m scripts require MATLAB (or GNU Octave, though only tested on MATLAB R2019b) to run, with CORA Toolbox R2020 installed. We have provided precomputed outputs for all Matlab scripts, so this is not necessary per se. Raw output data can be found in the raw/ folder.
You can simply run the python/example.py file to run a demo that uses the provided python/example*.txt files to show the theory in action. Both the inner approximation and the off-nominal reachable set are plotted.
We consider the following dynamics, which describe the heading of a ship cruising at fixed speed, controlled by a changing rudder angle. This model is due to Norrbin1:
We consider changes in the velocity, as well as the rudder effectiveness (maximum rudder movement). The code can be found in the various python/norrbin*.py files, with the nominal and off-nominal reachable sets being produced in the python/norrbin*.txt files.
A small demo video can be found here.
Inner approximation of the off-nominal reachable set of the Norrbin model in the case of diminished control authority, as obtained using a ball-based slimming operation. The cross-hatched areas each denote an interval on the
$i$ -th Cartesian dimension in which it is guaranteed that there exists at least one state$y$ in the off-nominal reachable set such that$y_i = x_i$ , where$x_i$ lies on the interval.
| 0.5 s | 1 s | 3 s |
|---|---|---|
 |
 |
 |
| Decreased speed | Increased speed |
|---|---|
 |
 |
These latter two examples are concerned with showcasing the scalability of our approach. Details are and results are omitted here, but we invite the interested reader to study the results and the code (in python/utri*.py and python/iconn*.py, respectively). The goals of these examples is also to show how our hyperrectangular slimming/fattening approach is much tighter than classical ball-based results.
Projected length ratios of the lower triangular system example by dimension using hyperrectangular and ball-based slimming operations.
| Dimension | Hyperrect. inner-approx./Off-nominal length | Ball-based inner-approx./Off-nominal length |
|---|---|---|
| 1 | 88.3% | 29.8% |
| 2 | 87.7% | 41.7% |
| 3 | 87.0% | 52.8% |
| 4 | 63.8% | 18.8% |
| 5 | 58.0% | 30.3% |
Projected length ratios of the interconnected system example by dimension using hyperrectangular and ball-based slimming operations.
| Dimension | Hyperrect. inner-approx./Off-nominal length | Ball-based inner-approx./Off-nominal length |
|---|---|---|
| 1 | 61.0% | 34.3% |
| 2 | 95.5% | 89.7% |
| 3 | 67.4% | 0% |
| 4 | 71.7% | 0% |
| 5 | 80.4% | 13.6% |
Footnotes
-
T. Fossen and M. Paulsen, "Adaptive feedback linearization applied to steering of ships," in The First IEEE Conference on Control Applications. Dayton, USA: IEEE, 1992, pp. 1088-1093. ↩