# ReachabilityAnalysis.jl

β¨ What is Reachability Analysis?

Reachability analysis is concerned with computing rigorous approximations of the set
of states reachable by a dynamical system. In the scope of this package are systems
modeled by **continuous** or **hybrid** dynamical systems, where the dynamics changes with discrete events.
Systems are modelled by ordinary differential equations (ODEs) or semi-discrete partial differential equations (PDEs),
with uncertain initial states, uncertain parameters or non-deterministic inputs.

The library is oriented towards a class of numerical methods known as **set propagation techniques:**
to compute the set of states reachable by continuous or hybrid systems, such methods iteratively
propagate a sequence of sets starting from the set of initial states, according to the systems' dynamics.

See our Commonly asked questions (FAQ) section for pointers to the relevant literature, related tools and more.

π― Table of Contents

πΎ Installation

Open a Julia session and activate the
`pkg`

mode (to activate the `pkg`

mode in Julia's REPL, type `]`

,
and to leave it, type `<backspace>`

), and enter:

`pkg> add ReachabilityAnalysis`

π Documentation

See the Reference Manual for introductory material, examples and API reference.

**Need help?** Have any question, or wish to suggest or ask for a missing feature?
Do not hesitate to open a **issue** or join the JuliaReach gitter chat: , or send an email to the developers.

π¨ Features

The following types of systems are supported (click on the left arrow to display a list of examples):

## Hybrid systems with piecewise-affine dynamics βοΈ

## Hybrid systems with non-linear dynamics βοΈ

π Quickstart

In less than 15 lines of code, we can formulate, solve and visualize the set of states reachable by the Duffing oscillator starting from any initial condition
with position in the interval `0.9 .. 1.1`

and velocity in `-0.1 .. 0.1`

.

```
using ReachabilityAnalysis, Plots
const Ο = 1.2
const T = 2*pi / Ο
@taylorize function duffing!(du, u, p, t)
local Ξ± = -1.0
local Ξ² = 1.0
local Ξ΄ = 0.3
local Ξ³ = 0.37
x, v = u
f = Ξ³ * cos(Ο * t)
# write the nonlinear differential equations defining the model
du[1] = u[2]
du[2] = -Ξ±*x - Ξ΄*v - Ξ²*x^3 + f
end
# set of initial states
X0 = Hyperrectangle(low=[0.9, -0.1], high=[1.1, 0.1])
# formulate the initial-value problem
prob = @ivp(x' = duffing!(x), x(0) β X0, dim=2)
# solve using a Taylor model set representation
sol = solve(prob, tspan=(0.0, 20*T), alg=TMJets())
# plot the flowpipe in state-space
plot(sol, vars=(1, 2), xlab="x", ylab="v", lw=0.5, color=:red)
```

πΎ Examples

Quadrotor altitude control | Lotka-Volterra with tangential guard crossing |

Laub-Loomis model | Production-Destruction model |

Coupled van der pol oscillator model | Spacecraft rendez-vous model |

π Publications

This library has been applied in a number of scientic works. We list them in reverse chronological order.

[10] **Efficient reachability analysis of parametric linear hybrid systems with time-triggered transitions.** Marcelo Forets, Daniel Freire, Christian Schilling, 2020. arXiv: 2006.12325. In 18th ACM-IEEE International Conference on Formal Methods and Models for System Design
.

[9] **ARCH-COMP20 Category Report: Continuous and Hybrid Systems with Linear Continuous Dynamics.** Matthias Althoff, Stanley Bak, Zongnan Bao, Marcelo Forets, Daniel Freire, Goran Frehse, Niklas Kochdumper, Yangge Li, Sayan Mitra, Rajarshi Ray, Christian Schilling, Stefan Schupp, and Mark Wetzlinger (2020) ARCH20. 7th International Workshop on Applied Verification of Continuous and Hybrid Systems. 7th International Workshop on Applied Verification of Continuous and Hybrid Systems (ARCH20), vol 74, pages 16--48. 10.29007/7dt2.

[8] **ARCH-COMP20 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics.** Luca Geretti, Julien Alexandre dit Sandretto, Matthias Althoff, Luis Benet, Alexandre Chapoutot, Xin Chen, Pieter Collins, Marcelo Forets, Daniel Freire, Fabian Immler, Niklas Kochdumper, David P. Sanders and Christian
Schilling (2020) ARCH20. To appear in 7th International Workshop on Applied Verification of Continuous and Hybrid Systems. 7th International Workshop on Applied Verification of Continuous and Hybrid Systems (ARCH20), vol 74, pages 49--75. 10.29007/zkf6.

[7] **Case Study: Reachability Analysis of a unified Combat-Command-and-Control Model.** Sergiy Bogomolov, Marcelo Forets, Kostiantyn Potomkin. *International Conference on Reachability Problems (2020). Lecture Notes in Computer Science, vol 12448.* (2020) doi: 10.1007/978-3-030-61739-4_4. Presented in the 14th International Conference on Reachability Problems 2020. article

[6] **Reachability analysis of linear hybrid systems via block decomposition.** Sergiy Bogomolov, Marcelo Forets, Goran Frehse, Kostiantyn Potomkin, Christian Schilling. *IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 39:11 (2020).* doi: 10.1109/TCAD.2020.3012859. Presented in Embedded Systems Week 2020. Get pdf from arXiv: 1905.02458.

[5] **ARCH-COMP19 Category Report: Continuous and Hybrid Systems with Linear Continuous Dynamics.** Matthias Althoff, Stanley Bak, Marcelo Forets, Goran Frehse, Niklas Kochdumper, Rajarshi Ray, Christian Schilling and Stefan Schupp (2019) ARCH19. 6th International Workshop on Applied Verification of Continuous and Hybrid Systems, vol 61, pages 14--40 doi: 10.29007/bj1w.

[4] **ARCH-COMP19 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics.** Fabian Immler, Matthias Althoff, Luis Benet, Alexandre Chapoutot, Xin Chen, Marcelo Forets, Luca Geretti, Niklas Kochdumper, David P. Sanders and Christian Schilling (2019) ARCH19. 6th International Workshop on Applied Verification of Continuous and Hybrid Systems, vol 61, pages 41--61 doi: 10.29007/bj1w.

[3] **JuliaReach: a Toolbox for Set-Based Reachability.** Sergiy Bogomolov, Marcelo Forets, Goran Frehse, Kostiantyn Potomkin, Christian Schilling. Published in Proceedings of HSCC'19: 22nd ACM International Conference on Hybrid Systems: Computation and Control (HSCC'19), see ACM link here. Get pdf from arXiv: 1901.10736.

[2] **ARCH-COMP18 Category Report: Continuous and Hybrid Systems with Linear Continuous Dynamics.** Matthias Althoff, Stanley Bak, Xin Chen, Chuchu Fan, Marcelo Forets, Goran Frehse, Niklas Kochdumper, Yangge Li, Sayan Mitra, Rajarshi Ray, Christian Schilling and Stefan Schupp (2018) ARCH18. 5th International Workshop on Applied Verification of Continuous and Hybrid Systems, 54: 23β52. doi: 10.29007/73mb.

[1] **Reach Set Approximation through Decomposition with Low-dimensional Sets and High-dimensional Matrices.** Sergiy Bogomolov, Marcelo Forets, Goran Frehse, FrΓ©dΓ©ric Viry, Andreas Podelski and Christian Schilling (2018) HSCC'18 Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control: 41β50. See the ACM Digital Library link, or the arXiv: 1801.09526.

*Note:* Articles [1-7] use the former codebase `Reachability.jl`

.

π Citation

Research credit and full references to the scientific papers presenting the algorithms implemented in this package can be found in the source code for each algorithm and in the References section of the online documentation.

If you use this package for your research, we kindly ask you to cite the following paper, see CITATION.bib. Moreover, please **also cite the appropriate original references to the algorithms used.**