HParallelotope

HParallelotope{N, VN<:AbstractVector{N}, MN<:AbstractMatrix{N}} <: AbstractZonotope{N}

Type that represents a parallelotope in constraint form.

Fields

• directions – square matrix where each row is the direction of two parallel constraints
• offset – vector where each element is the offset of the corresponding constraint

Notes

Parallelotopes are centrally symmetric convex polytopes in $\mathbb{R}^n$ having $2n$ pairwise parallel constraints. Every parallelotope is a zonotope. As such, parallelotopes can be represented in constraint form or in generator form. The HParallelotope type represents parallelotopes in constraint form.

Let $D ∈ \mathbb{R}^{n × n}$ be a matrix and let $c ∈ \mathbb{R}^{2n}$ be a vector. The parallelotope $P ⊂ \mathbb{R}^n$ generated by the directions matrix $D$ and the offset vector $c$ is given by the set of points $x ∈ \mathbb{R}^$ such that:

\[ D_i ⋅ x ≤ c_{i},\text{ and } -D_i ⋅ x ≤ c_{n+i}\]

for $i = 1, …, n$. Here $D_i$ represents the $i$-th row of $D$ and $c_i$ the $i$-th component of $c$.

Note that, although representing a zonotopic set, an HParallelotope can be empty or unbounded if the constraints are unsuitably chosen. This may cause problems with default methods because the library assumes that zonotopic sets are non-empty and bounded. Thus such instances are considered illegal. The default constructor thus checks these conditions, which can be deactivated by passing the argument check_consistency=false.

For details as well as applications of parallelotopes in reachability analysis we refer to [1] and [2]. For conversions between set representations we refer to [3].

References

[1] Tommaso Dreossi, Thao Dang, and Carla Piazza. Reachability computation for polynomial dynamical systems. Formal Methods in System Design 50.1 (2017): 1-38.

[2] Tommaso Dreossi, Thao Dang, and Carla Piazza. Parallelotope bundles for polynomial reachability. Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control. ACM, 2016.

[3] Matthias Althoff, Olaf Stursberg, and Martin Buss. Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes. Nonlinear analysis: hybrid systems 4.2 (2010): 233-249.

directions(P::HParallelotope)

Return the directions matrix of a parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

A matrix where each row represents a direction of the parallelotope. The negated directions -D_i are implicit (see HParallelotope for details).

offset(P::HParallelotope)

Return the offsets of a parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

A vector with the $2n$ offsets of the parallelotope, where $n$ is the dimension of P.

dim(P::HParallelotope)

Return the dimension of a parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

The ambient dimension of the parallelotope.

base_vertex(P::HParallelotope)

Compute the base vertex of a parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

The base vertex of P.

Algorithm

Intuitively, the base vertex is the point from which we get the relative positions of all the other points. The base vertex can be computed as the solution of the $n$-dimensional linear system $D_i x = c_{n+i}$ for $i = 1, \ldots, n$, see [1, Section 3.2.1].

[1] Dreossi, Tommaso, Thao Dang, and Carla Piazza. Reachability computation for polynomial dynamical systems. Formal Methods in System Design 50.1 (2017): 1-38.

extremal_vertices(P::HParallelotope{N, VN}) where {N, VN}

Compute the extremal vertices with respect to the base vertex of a parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

The list of vertices connected to the base vertex of $P$.

Notes

Let $P$ be a parallelotope in constraint representation with directions matrix $D$ and offset vector $c$. The extremal vertices of $P$ with respect to its base vertex $q$ are those vertices of $P$ that have an edge in common with $q$.

Algorithm

The extremal vertices can be computed as the solution of the $n$-dimensional linear systems of equations $D x = v_i$ where for each $i = 1, \ldots, n$, $v_i = [-c_{n+1}, \ldots, c_i, \ldots, -c_{2n}]$.

We refer to [1, Section 3.2.1] for details.

[1] Tommaso Dreossi, Thao Dang, and Carla Piazza. Reachability computation for polynomial dynamical systems. Formal Methods in System Design 50.1 (2017): 1-38.

center(P::HParallelotope)

Return the center of a parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

The center of the parallelotope.

Algorithm

Let $P$ be a parallelotope with base vertex $q$ and list of extremal vertices with respect to $q$ given by the set $\{v_i\}$ for $i = 1, \ldots, n$. Then the center is located at

\[ c = q + \sum_{i=1}^n \frac{v_i - q}{2} = q (1 - \frac{2}) + \frac{s}{2},\]

where $s := \sum_{i=1}^n v_i$ is the sum of extremal vertices.

genmat(P::HParallelotope)

Return the generator matrix of a parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

A matrix where each column represents one generator of the parallelotope P.

Algorithm

Let $P$ be a parallelotope with base vertex $q$ and list of extremal vertices with respect to $q$ given by the set $\{v_i\}$ for $i = 1, \ldots, n$. Then, the $i$-th generator of $P$, represented as the $i$-th column vector $G[:, i]$, is given by:

\[ G[:, i] = \frac{v_i - q}{2}\]

for $i = 1, \ldots, n$.

generators(P::HParallelotope)

Return an iterator over the generators of a parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

An iterator over the generators of P.

constraints_list(P::HParallelotope)

Return the list of constraints of a parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

The list of constraints of P.

rand(::Type{HParallelotope}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Create a random parallelotope in constraint representation.

Input

• HParallelotope – type for dispatch
• N – (optional, default: Float64) numeric type
• dim – (optional, default: 2) dimension
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

A random parallelotope.

Notes

All numbers are normally distributed with mean 0 and standard deviation 1.

Algorithm

The directions matrix and offset vector are created randomly. On average there is a good chance that this resulting set is empty. We then modify the offset to ensure non-emptiness.

There is a chance that the resulting set represents an unbounded set. This implementation checks for that case and then samples a new set.

volume(P::HParallelotope)

Return the volume of a parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

The volume.

Algorithm

The volume of an $n$-dimensional parallelotope P is $2^n · |\det(G)|$, where $G$ is the generator matrix of P. This can be seen as follows: The generator matrix transforms the $n$-dimensional hypercube $[0, 1]^n$ to a parallelotope of volume $|\det(G)|$. Since the representation of a parallelotope instead transforms the hypercube $[-1, 1]^n$, this result has to be doubled for each dimension.