Zonotopes (AbstractZonotope)

AbstractZonotope{N} <: AbstractCentrallySymmetricPolytope{N}

Abstract type for zonotopic sets.

Notes

Mathematically, a zonotope is defined as the set

\[Z = \left\{ c + ∑_{i=1}^p ξ_i g_i,~~ ξ_i ∈ [-1, 1]~~ ∀ i = 1,…, p \right\},\]

where $c ∈ ℝ^n$ is its center and $\{g_i\}_{i=1}^p$, $g_i ∈ ℝ^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 $ℝ^n$ by an affine transformation.

See Zonotope for a standard implementation of this interface.

Every concrete AbstractZonotope must define the following functions:

• genmat(::AbstractZonotope) – return the generator matrix

• generators(::AbstractZonotope) – return an iterator over the generators

Since the functions genmat and generators can be defined in terms of each other, it is sufficient to only genuinely implement one of them and let the implementation of the other function call the fallback implementation genmat_fallback resp. generators_fallback.

The subtypes of AbstractZonotope (including abstract interfaces):

julia> subtypes(AbstractZonotope)
5-element Vector{Any}:
 AbstractHyperrectangle
 HParallelotope
 LineSegment
 RotatedHyperrectangle
 Zonotope

ngens(Z::AbstractZonotope)

Return the number of generators of a zonotopic set.

Input

• Z – zonotopic set

Output

An integer representing the number of generators.

genmat_fallback(Z::AbstractZonotope{N};
                [gens]=generators(Z), [ngens]=nothing) where {N}

Fallback definition of genmat for zonotopic sets.

Input

• Z – zonotopic set
• gens – (optional; default: generators(Z)) iterator over generators
• ngens – (optional; default: nothing) number of generators or nothing if unknown

Output

A matrix where each column represents one generator of Z.

Notes

Passing the number of generators (ngens) is more efficient, since otherwise the generators have to be obtained from the iterator (gens) and stored in an intermediate vector until the final result matrix can be allocated.

generators_fallback(Z::AbstractZonotope)

Fallback definition of generators for zonotopic sets.

Input

• Z – zonotopic set

Output

An iterator over the generators of Z.

ρ(d::AbstractVector, Z::AbstractZonotope)

Evaluate the support function of a zonotopic set in a given direction.

Input

• d – direction
• Z – zonotopic set

Output

The evaluation of the support function in the given direction.

Algorithm

The support value is $cᵀ d + ‖Gᵀ d‖₁$, where $c$ is the center and $G$ is the generator matrix of Z.

σ(d::AbstractVector, Z::AbstractZonotope)

Return a support vector of a zonotopic set in a given direction.

Input

• d – direction
• Z – zonotopic set

Output

A support vector in the given direction. If the direction has norm zero, the vertex with $ξ_i = 1 \ \ ∀ i = 1,…, p$ is returned.

∈(x::AbstractVector, Z::AbstractZonotope; solver=nothing)

Check whether a given point is contained in a zonotopic set.

Input

• x – point/vector
• Z – zonotopic set
• solver – (optional, default: nothing) the backend used to solve the linear program

Output

true iff $x ∈ Z$.

Examples

julia> Z = Zonotope([1.0, 0.0], [0.1 0.0; 0.0 0.1]);

julia> [1.0, 0.2] ∈ Z
false
julia> [1.0, 0.1] ∈ Z
true

Notes

If solver == nothing, we fall back to default_lp_solver(N).

Algorithm

The membership problem is reduced to the following linear program. Let $p$ and $n$ be the number of generators and ambient dimension, respectively. We consider the $p$-dimensional space of elements $(ξ_1, …, ξ_p)$ constrained to $ξ_i ∈ [-1, 1]$ for all $i = 1, …, p$ such that $x-c = Gξ$ holds.

linear_map(M::AbstractMatrix, Z::AbstractZonotope)

Concrete linear map of a zonotopic set.

Input

• M – matrix
• Z – zonotopic set

Output

The zonotope obtained by applying the linear map.

Algorithm

We apply the linear map to the center and the generators.

translate(Z::AbstractZonotope, v::AbstractVector)

Translate (i.e., shift) a zonotopic set by a given vector.

Input

• Z – zonotopic set
• v – translation vector

Output

A translated zonotopic set.

Notes

See also translate!(Z::AbstractZonotope, v::AbstractVector) for the in-place version.

translate!(Z::AbstractZonotope, v::AbstractVector)

Translate (i.e., shift) a zonotopic set by a given vector in-place.

Input

• Z – zonotopic set
• v – translation vector

Output

A translated zonotopic set.

Notes

See also translate(Z::AbstractZonotope, v::AbstractVector) for the out-of-place version.

Algorithm

We add the translation vector to the center of the zonotopic set.

split(Z::AbstractZonotope, j::Int)

Return two zonotopes obtained by splitting the given zonotopic set.

Input

• Z – zonotopic set
• j – 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], which we state next. The zonotopic set $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. Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization. CDC 2008.

split(Z::AbstractZonotope, gens::AbstractVector{Int},
      nparts::AbstractVector{Int})

Split a zonotopic set along the given generators into a vector of zonotopes.

Input

• Z – zonotopic set
• gens – vector of indices of the generators to be split
• n – 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 zonotopic set along its first generator:

julia> Z = Zonotope([1.0, 0.0], [0.1 0.0; 0.0 0.1])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.0, 0.0], [0.1 0.0; 0.0 0.1])

julia> split(Z, [1], [1])
2-element Vector{Zonotope{Float64, Vector{Float64}, Matrix{Float64}}}:
 Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.95, 0.0], [0.05 0.0; 0.0 0.1])
 Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.05, 0.0], [0.05 0.0; 0.0 0.1])

Here, the first vector in the arguments corresponds to the zonotopic set's generator to be split, and the second vector corresponds to the exponent of 2^n parts that the set will be split into along the corresponding generator.

As an example, below we split a two-dimensional zonotope along both of its generators, each time into four parts.

julia> Z = Zonotope([1.0, 0.0], [0.1 0.0; 0.0 0.1])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.0, 0.0], [0.1 0.0; 0.0 0.1])

julia> split(Z, [1, 2], [2, 2])
16-element Vector{Zonotope{Float64, Vector{Float64}, Matrix{Float64}}}:
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.925, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.925, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.925, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.925, 0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.975, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.975, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.975, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.975, 0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.025, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.025, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.025, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.025, 0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.075, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.075, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.075, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.075, 0.075], [0.025 0.0; 0.0 0.025])

constraints_list(P::AbstractZonotope)

Return a list of constraints defining a zonotopic set.

Input

• Z – zonotopic set

Output

A list of constraints of the zonotopic set.

Algorithm

This is the (inefficient) fallback implementation for rational numbers. It first computes the vertices and then converts the corresponding polytope to constraint representation.

constraints_list(Z::AbstractZonotope{N}) where {N<:AbstractFloat}

Return a list of constraints defining a zonotopic set.

Input

• Z – zonotopic set

Output

A list of constraints of the zonotopic set.

Notes

The main algorithm assumes that the generator matrix is full rank. The result has $2 \binom{p}{n-1}$ (with $p$ being the number of generators and $n$ being the ambient dimension) constraints, which is optimal under this assumption. If this assumption is not given, the implementation tries to work around.

Algorithm

We follow the algorithm presented in [1]. Three cases are not covered by that algorithm, so we handle them separately. The first case is zonotopes in one dimension. The second case is that there are fewer generators than dimensions, $p < n$, or the generator matrix is not full rank, in which case we fall back to the (slower) computation based on the vertex representation. The third case is that the zonotope is flat in some dimensions, in which case we project the zonotope to the non-flat dimensions and extend the result later.

[1] Althoff, Stursberg, Buss. Computing Reachable Sets of Hybrid Systems Using a Combination of Zonotopes and Polytopes. 2009.

vertices_list(Z::AbstractZonotope; [apply_convex_hull]::Bool=true)

Return a list of the vertices of a zonotopic set.

Input

• Z – zonotopic set
• apply_convex_hull – (optional, default: true) if true, post-process the computation with the convex hull of the points

Output

A list of the vertices.

Algorithm

Two-dimensional case

We use a trick to speed up enumerating vertices of 2-dimensional zonotopic sets with all generators in the first quadrant or third quadrant (same sign). Namely, sort the generators by angle and add them clockwise in increasing order and counterclockwise in decreasing order. A more detailed explanation can be found here.

To avoid the cumulative sum from both directions separately, we build a 2D index matrix to sum generators for both directions in one matrix-vector product.

General case

If the zonotopic set has $p$ generators, each vertex is the result of summing the center with some linear combination of generators, where the combination factors are $ξ_i ∈ \{-1, 1\}$.

There are at most $2^p$ distinct vertices. Use the flag apply_convex_hull to control whether a convex-hull algorithm is applied to the vertices computed by this method; otherwise, redundant vertices may be present.

order(Z::AbstractZonotope)

Return the order of a zonotopic set.

Input

• Z – zonotopic set

Output

A rational number representing the order of the zonotopic set.

Notes

The order of a zonotopic set is defined as the quotient of its number of generators and its dimension.

togrep(Z::AbstractZonotope)

Return a generator representation of a zonotopic set.

Input

• Z – zonotopic set

Output

The same set in generator representation. This fallback implementation returns a Zonotope; however, more specific implementations may return other generator representations.

remove_redundant_generators(Z::AbstractZonotope)

Remove all redundant (pairwise linearly dependent) generators of a zonotopic set.

Input

• Z – zonotopic set

Output

A new zonotope with fewer generators, or the same zonotopic set if no generator could be removed.

Algorithm

By default this implementation returns the input zonotopic set. Subtypes of AbstractZonotope whose generators can be removed have to define a new method.

reduce_order(Z::AbstractZonotope, r::Real,
             [method]::AbstractReductionMethod=GIR05())

Reduce the order of a zonotopic set by overapproximating with a zonotope with fewer generators.

Input

• Z – zonotopic set
• r – desired order
• method – (optional, default: GIR05()) the reduction method used

Output

A new zonotope with fewer generators, if possible.

Algorithm

The available algorithms are:

julia> subtypes(AbstractReductionMethod)
3-element Vector{Any}:
 LazySets.ASB10
 LazySets.COMB03
 LazySets.GIR05

See the documentation of each algorithm for references. These methods split the given zonotopic set Z into two zonotopes, K and L, where K contains the most "representative" generators and L contains the generators that are reduced, Lred, using a box overapproximation. We follow the notation from [1]. See also [2].

• [1] Yang, X., & Scott, J. K. *A comparison of zonotope order reduction

techniques*. Automatica 2018.

• [2] Kopetzki, A. K., Schürmann, B., & Althoff, M. *Methods for order reduction

of zonotopes*. CDC 2017.

• [3] Althoff, M., Stursberg, O., & Buss, M. *Computing reachable sets of hybrid

systems using a combination of zonotopes and polytopes*. Nonlinear analysis: hybrid systems 2010.

reflect(Z::AbstractZonotope)

Concrete reflection of a zonotopic set Z, resulting in the reflected set -Z.

Input

• Z – zonotopic set

Output

A Zonotope representing -Z.

Algorithm

If $Z$ has center $c$ and generator matrix $G$, then $-Z$ has center $-c$ and generator matrix $G$. For the latter, observe that $G$ and $-G$ behave the same way.

AbstractReductionMethod

Abstract supertype for order-reduction methods of a zonotopic set.

ASB10 <: AbstractReductionMethod

Zonotope order-reduction method from [1].

• [1] Althoff, M., Stursberg, O., & Buss, M. *Computing reachable sets of hybrid

systems using a combination of zonotopes and polytopes*. Nonlinear analysis: hybrid systems 2010.

COMB03 <: AbstractReductionMethod

Zonotope order-reduction method from [1].

• [1] C. Combastel. A state bounding observer based on zonotopes. ECC 2003.

GIR05 <: AbstractReductionMethod

Zonotope order-reduction method from [1].

• [1] A. Girard. Reachability of Uncertain Linear Systems Using Zonotopes.

HSCC 2005.