Zonotope
LazySets.Zonotope
— TypeZonotope{N, VN<:AbstractVector{N}, MN<:AbstractMatrix{N}} <: AbstractZonotope{N}
Type that represents a zonotope.
Fields
center
– center of the zonotopegenerators
– matrix; each column is a generator of the zonotope
Notes
Mathematically, a zonotope is defined as the set
\[Z = \left\{ x ∈ \mathbb{R}^n : x = c + ∑_{i=1}^p ξ_i g_i,~~ ξ_i \in [-1, 1]~~ ∀ i = 1,…, p \right\},\]
where $c \in \mathbb{R}^n$ is its center and $\{g_i\}_{i=1}^p$, $g_i \in \mathbb{R}^n$, is the set of generators. This characterization defines a zonotope as the finite Minkowski sum of line segments. Zonotopes can be equivalently described as the image of a unit infinity-norm ball in $\mathbb{R}^n$ by an affine transformation.
Zonotopes can be constructed in two different ways: either passing the generators as a matrix, where each column represents a generator, or passing a list of vectors where each vector represents a generator. Below we illustrate both ways.
Examples
A two-dimensional zonotope with given center and set of generators:
julia> Z = Zonotope([1.0, 0.0], [0.1 0.0; 0.0 0.1])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.0, 0.0], [0.1 0.0; 0.0 0.1])
julia> dim(Z)
2
julia> center(Z)
2-element Array{Float64,1}:
1.0
0.0
julia> genmat(Z)
2×2 Array{Float64,2}:
0.1 0.0
0.0 0.1
Here, the first vector in the Zonotope
constructor corresponds to the zonotope's center, and each column of the second argument corresponds to a generator. The functions center
and genmat
return the center and the generator matrix of this zonotope respectively.
We can collect its vertices using vertices_list
:
julia> vertices_list(Z)
4-element Array{Array{Float64,1},1}:
[1.1, 0.1]
[0.9, 0.1]
[0.9, -0.1]
[1.1, -0.1]
The support vector along a given direction can be computed using σ
(resp. the support function can be computed using ρ
):
julia> σ([1., 1.], Z)
2-element Array{Float64,1}:
1.1
0.1
Zonotopes admit an alternative constructor that receives a list of vectors, each vector representing a generator:
julia> Z = Zonotope(ones(2), [[1., 0.], [0., 1.], [1., 1.]])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.0, 1.0], [1.0 0.0 1.0; 0.0 1.0 1.0])
julia> genmat(Z)
2×3 Array{Float64,2}:
1.0 0.0 1.0
0.0 1.0 1.0
LazySets.center
— Methodcenter(Z::Zonotope)
Return the center of a zonotope.
Input
Z
– zonotope
Output
The center of the zonotope.
Base.rand
— Methodrand(::Type{Zonotope}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
[rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)
Create a random zonotope.
Input
Zonotope
– type for dispatchN
– (optional, default:Float64
) numeric typedim
– (optional, default: 2) dimensionrng
– (optional, default:GLOBAL_RNG
) random number generatorseed
– (optional, default:nothing
) seed for reseedingnum_generators
– (optional, default:-1
) number of generators of the zonotope (see comment below)
Output
A random zonotope.
Algorithm
All numbers are normally distributed with mean 0 and standard deviation 1.
The number of generators can be controlled with the argument num_generators
. For a negative value we choose a random number in the range dim:2*dim
(except if dim == 1
, in which case we only create a single generator).
LazySets.generators
— Methodgenerators(Z::Zonotope)
Return an iterator over the generators of a zonotope.
Input
Z
– zonotope
Output
An iterator over the generators of Z
.
LazySets.genmat
— Methodgenmat(Z::Zonotope)
Return the generator matrix of a zonotope.
Input
Z
– zonotope
Output
A matrix where each column represents one generator of the zonotope Z
.
LazySets.scale
— Methodscale(α::Real, Z::Zonotope)
Concrete scaling of a zonotope.
Input
α
– scalarZ
– zonotope
Output
The zonotope obtained by applying the numerical scale to the center and generators of $Z$.
LazySets.scale!
— Methodscale!(α::Real, Z::Zonotope)
Concrete scaling of a zonotope modifing Z
in-place
Input
α
– scalarZ
– zonotope
Output
The zonotope Z
after applying the numerical scale α
to its center and generators.
LazySets.ngens
— Methodngens(Z::Zonotope)
Return the number of generators of a zonotope.
Input
Z
– zonotope
Output
Integer representing the number of generators.
LazySets.togrep
— Methodtogrep(Z::Zonotope)
Return a generator representation of a zonotope.
Input
Z
– zonotopic set
Output
The same set Z
.
LazySets.reduce_order
— Methodreduce_order(Z::Zonotope, r::Union{Integer, Rational})
Reduce the order of a zonotope by overapproximating with a zonotope with fewer generators.
Input
Z
– zonotoper
– desired order
Output
A new zonotope with fewer generators, if possible.
Algorithm
See overapproximate(Z::Zonotope, ::Type{<:Zonotope}, r::Union{Integer, Rational})
for details.
Base.split
— Methodsplit(Z::AbstractZonotope, j::Int)
Return two zonotopes obtained by splitting the given zonotope.
Input
Z
– zonotopej
– index of the generator to be split
Output
The zonotope obtained by splitting Z
into two zonotopes such that their union is Z
and their intersection is possibly non-empty.
Algorithm
This function implements [Prop. 3, 1], that we state next. The zonotope $Z = ⟨c, g^{(1, …, p)}⟩$ is split into:
\[Z₁ = ⟨c - \frac{1}{2}g^{(j)}, (g^{(1, …,j-1)}, \frac{1}{2}g^{(j)}, g^{(j+1, …, p)})⟩ \\ Z₂ = ⟨c + \frac{1}{2}g^{(j)}, (g^{(1, …,j-1)}, \frac{1}{2}g^{(j)}, g^{(j+1, …, p)})⟩,\]
such that $Z₁ ∪ Z₂ = Z$ and $Z₁ ∩ Z₂ = Z^*$, where
\[Z^* = ⟨c, (g^{(1,…,j-1)}, g^{(j+1,…, p)})⟩.\]
[1] Althoff, M., Stursberg, O., & Buss, M. (2008). Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization. In Proc. of the 47th IEEE Conference on Decision and Control.
Base.split
— Methodsplit(Z::AbstractZonotope, gens::AbstractVector{Int}, nparts::AbstractVector{Int})
Split a zonotope along the given generators into a vector of zonotopes.
Input
Z
– zonotopegens
– vector of indices of the generators to be splitn
– vector of integers describing the number of partitions in the corresponding generator
Output
The zonotopes obtained by splitting Z
into 2^{n_i}
zonotopes for each generator i
such that their union is Z
and their intersection is possibly non-empty.
Examples
Splitting of a two-dimensional zonotope along its first generator:
julia> Z = Zonotope([1.0, 0.0], [0.1 0.0; 0.0 0.1])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.0, 0.0], [0.1 0.0; 0.0 0.1])
julia> split(Z, [1], [1])
2-element Array{Zonotope{Float64,Array{Float64,1},Array{Float64,2}},1}:
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([0.95, 0.0], [0.05 0.0; 0.0 0.1])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.05, 0.0], [0.05 0.0; 0.0 0.1])
Here, the first vector in the arguments corresponds to the zonotope's generator to be split, and the second vector corresponds to the exponent of 2^n
parts that the zonotope will be split into along the corresponding generator.
Splitting of a two-dimensional zonotope along its generators:
julia> Z = Zonotope([1.0, 0.0], [0.1 0.0; 0.0 0.1])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.0, 0.0], [0.1 0.0; 0.0 0.1])
julia> split(Z, [1, 2], [2, 2])
16-element Array{Zonotope{Float64,Array{Float64,1},Array{Float64,2}},1}:
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([0.925, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([0.925, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([0.925, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([0.925, 0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([0.975, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([0.975, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([0.975, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([0.975, 0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.025, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.025, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.025, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.025, 0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.075, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.075, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.075, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.075, 0.075], [0.025 0.0; 0.0 0.025])
Here the zonotope is split along both of its generators, each time into four parts.
LazySets.remove_zero_generators
— Methodremove_zero_generators(Z::Zonotope)
Return a new zonotope removing the generators which are zero of the given zonotope.
Input
Z
– zonotope
Output
If there are no zero generators, the result is the original zonotope Z
. Otherwise the result is a new zonotope that has the center and generators as Z
except for those generators that are zero.
LazySets.linear_map!
— Methodlinear_map!(Zout::Zonotope, M::AbstractMatrix, Z::Zonotope)
Compute the concrete linear map of a zonotope storing the result in Zout
.
Input
Zout
– zonotope (output)M
– matrixZ
– zonotope
Output
The zonotope Zout
, which is modified in-place.
LazySets.quadratic_map
— Methodquadratic_map(Q::Vector{MT}, Z::Zonotope{N}) where {N, MT<:AbstractMatrix{N}}
Return an overapproximation of the quadratic map of the given zonotope.
Input
Z
– zonotopeQ
– array of square matrices
Output
An overapproximation of the quadratic map of the given zonotope.
Notes
Mathematically, a quadratic map of a zonotope is defined as:
\[Z_Q = \right\{ \lambda | \lambda_i = x^T Q\^{(i)} x,~i = 1, \ldots, n,~x \in Z \left\}\]
such that each coordinate $i$ of the resulting zonotope is influenced by $Q\^{(i)}$
Algorithm
This function implements [Lemma 1, 1].
[1] Matthias Althoff and Bruce H. Krogh. 2012. Avoiding geometric intersection operations in reachability analysis of hybrid systems. In Proceedings of the 15th ACM international conference on Hybrid Systems: Computation and Control (HSCC ’12). Association for Computing Machinery, New York, NY, USA, 45–54.
LazySets._bound_intersect_2D
— Method_bound_intersect_2D(Z::Zonotope, L::Line2D)
Return the support function in the direction [0, 1] of the intersection between the given zonotope and line.
Input
Z
– zonotopeL
– vertical line 2D
Output
The support function in the direction [0, 1] of the intersection between the given zonotope and line.
Notes
The algorithm assumes that the given line is vertical and that the intersection between the given sets is not empty.
Algorithm
This function implements [Algorithm 8.2, 1].
[1] Colas Le Guernic. Reachability Analysis of Hybrid Systems with Linear Continuous Dynamics. Computer Science [cs]. Université Joseph-Fourier - Grenoble I, 2009. English. fftel-00422569v2f
LazySets.remove_redundant_generators
— Methodremove_redundant_generators(Z::Zonotope{N}) where {N}
Remove all redundant (pairwise linearly dependent) generators of a zonotope.
Input
Z
– zonotope
Output
A new zonotope with fewer generators, or the same zonotope if no generator could be removed.
Algorithm
For each generator $g_j$ that has not been checked yet, we find all other generators that are linearly dependent with $g_j$. Then we combine those generators into a single generator.
For one-dimensional zonotopes we use a more efficient implementation where we just take the absolute sum of all generators.
Inherited from LazySet
:
Inherited from AbstractPolytope
:
Inherited from AbstractCentrallySymmetricPolytope
:
Inherited from AbstractZonotope
: