Zonotopes (AbstractZonotope)

A zonotope is a specific centrally symmetric polytope characterized by a center and a collection of generators.

LazySets.AbstractZonotopeType
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:

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

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

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)
4-element Vector{Any}:
 AbstractHyperrectangle
 HParallelotope
 LineSegment
 Zonotope
source

This interface requires to implement the following functions:

LazySets.generatorsMethod
generators(Z::AbstractZonotope)

Return an iterator over the generators of a zonotopic set.

Input

  • Z – zonotopic set

Output

An iterator over the generators of Z.

source
LazySets.genmatMethod
genmat(Z::AbstractZonotope)

Return a generator matrix of a zonotopic set.

Input

  • Z – zonotopic set

Output

A generator matrix of Z.

source

This interface defines the following functions:

LazySets.API.constraints_listMethod
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.

source
LazySets.API.constraints_listMethod
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.

source
LazySets.generators_fallbackMethod
generators_fallback(Z::AbstractZonotope)

Fallback definition of generators for zonotopic sets.

Input

  • Z – zonotopic set

Output

An iterator over the generators of Z.

source
LazySets.genmat_fallbackMethod
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.

source
LazySets.ngensMethod
ngens(Z::AbstractZonotope)

Return the number of generators of a zonotopic set.

Input

  • Z – zonotopic set

Output

An integer representing the number of generators.

source
LazySets.orderMethod
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.

source
LazySets.API.reflectMethod
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.

source
LazySets.remove_redundant_generatorsMethod
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.

source
LazySets.togrepMethod
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.

source
LazySets.API.vertices_listMethod
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.

source
Base.:∈Method
∈(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.

source
LazySets.API.linear_mapMethod
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.

source
LazySets.reduce_orderFunction
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.

source
Base.splitMethod
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.

source
Base.splitMethod
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])
source
LazySets.API.ρMethod
ρ(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.

source
LazySets.API.σMethod
σ(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.

source

Order-reduction methods

LazySets.ASB10Type
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.

source
LazySets.COMB03Type
COMB03 <: AbstractReductionMethod

Zonotope order-reduction method from [1].

  • [1] C. Combastel. A state bounding observer based on zonotopes. ECC 2003.
source
LazySets.GIR05Type
GIR05 <: AbstractReductionMethod

Zonotope order-reduction method from [1].

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

HSCC 2005.

source

Implementations