`CRULS`: Computing Reachable Sets of Uncertain Linear System

Given an uncertain linear system $x[t+1] = (A+ \Lambda) x[t]$, where $A \in \mathbb{R}^{n \times n}$ and $\Lambda \subset \mathbb{R}^{n \times n}$, this Python based prototype tool computes reachable sets of such system with various other functionalities.

The basic idea is given in the following figure:

Where:

$\theta_0$ is the initial set.
$ORS_t$ denotes the overapproximate reachable set at time step $t$.
$S_1 \oplus S_2$ denotes minkowski sum of sets $S_1$ and $S_2$.
$u_t \subseteq \Lambda \cdot ORS_t$ (computed using our technique from the paper)

Please email Bineet Ghosh at bineet@cs.unc.edu to get a preprint of the paper.

Installation

Dependencies

Python 3.9.x
NumPy
SciPy
mpmath
Gurobi Python Interface:
- Please obtain appropriate Gurobi License from here. Please note that if you are using Academic License, you should be in your University network (VPN should work fine too) while installing the license. Please refer to this link for details. After the license is installed properly, Gurobi can be used from home network.
- Install Gurobi. Please note that we will need Gurobi Python Interface. On-line documentation on installation can be found here.
- Gurobi Python Interface can also be installed through Anaconda. Details on installing Gurobi Python Interface through conda can be found here.
[Optional: Only needed to run the Mars Rover case study] Dependencies for Python Robotics need to be installed. Note that one doesn't need to download the Python Robotics repository — that is provided native with our code. Just installing the dependencies for Python Robotics is required. If one does not wish to run the Mars Rover case study, they can ignore this step.

Downloading the tool

Once the dependencies are installed:

Download the repository to your desired location /my/location/:

git clone https://github.com/bineet-coderep/Uncertain-Linear-System.git

Once the repository is downloaded, please open ~/.bashrc, and add the line export ULS_ROOT_DIR=/my/location/Uncertain-Linear-System/, mentioned in the following steps:
1. ```
vi ~/.baschrc
```
2. Once .bashrc is opened, please add the location, where the tool was downloaded, to a path variable ULS_ROOT_DIR (This step is crucial to run the tool):
  1. ```
  export ULS_ROOT_DIR=/my/location/Uncertain-Linear-System/
```

Running the tool

Once the dependencies are installed properly, and the path variable is set, following steps should run without any error.

Following are some of the crucial functionalities offered by this prototype tool:

Reachable set computation of linear uncertain systems.
Ordering cells in a given dynamics matrix w.r.t to its effect on the reachable set.
Robustness Metric: Amount uncertainties that can introduced to the dynamics, without violating the safety.

Case studies

We offer to case studies:

Anesthesia.
Mars Rover.

Here, we illustrate the Anesthesia case study, as the other one can be run in similar fashion.

```
cd src/
```
```
python Anasthesia.py
```

One should see the following plot in /my/location/Uncertain-Linear-System/output/pkpd_results:

The above plot shows the effect of perturbation in lower ranked cells (cyan), vs. higher ranked cells (high).

Other benchmark

We offer a plethora of benchmarks, here we show result for one:

```
cd src/
```
```
python DriverSplitAll.py
```

This should show the the following output in the terminal

======= ACC =======

ACC
-----------------

----Timining Details for ACC----
Without Reduction:  0.23662304878234863
With Reduction (Interval):  0.06682276725769043
Total Time:  0.35596227645874023
-
Kagstrom 1:  0.07081341743469238
Kagstrom 2:  0.2314913272857666
Loan:  0.02236771583557129
----- Sensitivity of the cells in decreasing order -----
(1, 1)
(1, 2)
(2, 1)
(0, 0)
(2, 2)
... 11  more ...
Time Taken:  0.00362396240234375
Case: Zero
Singular Values:  [1.41421452e+00 1.31441296e+00 2.46736800e-04 0.00000000e+00]
---------------------<END>--------------------
-------------------------

One should also see the following plot in /my/location/Uncertain-Linear-System/output/BloatPlot/

Along with the above plot, /my/location/Uncertain-Linear-System/output/Plot/ should show:

Contact

If you have any questions, or report a bug, please contact Bineet Ghosh at bineet@cs.unc.edu.

bineet-coderep/Uncertain-Linear-System

CRULS: Computing Reachable Sets of Uncertain Linear System