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

📙 Documentation << WORK-IN-PROGRESS

🎨 Features

🏁 Quickstart

🐾 Examples Gallery

📘 Publications

📜 Citation

💾 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 email to the developers.

🎨 Features

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

🏁 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.