GSOC Ideas

Computational methods using zonotopes

Zonotopes are representations of extended use in set-based analysis, since linear transformations and Minkowski sums can be computed efficiently. However, they are are not closed under intersections. In the literature there exist different alternatives for overapproximation of zonotope intersections with other set types. The package LazySets.jl already offers support for zonotopes but lacks some of the state-of-the-art methods.

Zonotopes provide a very good middle ground between hyperrectangular approximations and general polyhedral approximations in terms of performance and accuracy. Applications of this project are the verification of hybrid dynamical systems (see juliareach.org) and in neural network verification (see AI2 and NeuralVerification.jl project).

Recommended Skills: Basic knowledge on convex geometry and polyhedral computations is preferred but can be learned along the way. A taste for writing efficient code.

Expected Results: Some possibilities are: overapproximation of zonotopes with polytopes, zonotope-polytope intersections, order reduction metods, Minkowski difference of zonotopes.

Mentors: Marcelo Forets and Christian Schilling.

References: See Reachability.jl#Publications and references therein, or contact us in the gitter channel.