HParallelotope

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

Type that represents a parallelotope in constraint form.

Fields

• directions – square matrix such that each row is the direction of two parallel constraints
• offset – vector such that 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 either in constraint form or in generator form. The HParallelotope type represents parallelotopes in constraint form.

The constraint form of a parallelotope is described next. 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$.

For details on the notions given in these notes 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.

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.

Input

• P – parallelotope in constraint representation

Output

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

dim(P::HParallelotope)

Return the dimension of a parallelotope.

Input

• P – parallelotope in constraint representation

Output

An integer representing the dimension of the parallelotope

base_vertex(P::HParallelotope)

Compute the base vertex of the given 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 the given parallelotope in constraint representation.

Input

• P – parallelotope in constraint representation

Output

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

Algorithm

Let $P$ be a parallelotope in constraint representation with directions matrix $D$ and offset vector $c$. We denote the extremal vertices of $P$ with respect to its base vertex $q$ to be those vertices of $P$ which have an edge in common with $q$. 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.

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.

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.

Input

• P – parallelotope in constraint representation

Output

An iterator over the generators of P.

constraints_list(H::AbstractHyperrectangle{N}) where {N}

Return the list of constraints of an axis-aligned hyperrectangular set.

Input

• H – hyperrectangular set

Output

A list of linear constraints.

constraints_list(P::Ball1{N}) where {N}

Return the list of constraints defining a ball in the 1-norm.

Input

• B – ball in the 1-norm

Output

The list of constraints of the ball.

Algorithm

The constraints can be defined as $d_i^T (x-c) ≤ r$ for all $d_i$, where $d_i$ is a vector with elements $1$ or $-1$ in $n$ dimensions. To span all possible $d_i$, the function Iterators.product is used.

constraints_list(x::Interval{N}) where {N}

Return the list of constraints of the given interval.

Input

• x – interval

Output

The list of constraints of the interval represented as two one-dimensional half-spaces.

constraints_list(L::Line{N, VN}) where {N, VN}

Return the list of constraints of a line.

Input

• L – line

Output

A list containing 2n-2 half-spaces whose intersection is L, where n is the ambient dimension of L.

constraints_list(U::Universe{N}) where {N}

Return the list of constraints defining a universe.

Input

• U – universe

Output

The empty list of constraints, as the universe is unconstrained.

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

Return the list of constraints of the given parallelotope.

Input

• P – parallelotope in constraint representation

Output

The list of constraints of P.

constraints_list(cpa::CartesianProductArray{N}) where {N}

Return the list of constraints of a (polyhedral) Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product array

Output

A list of constraints.

constraints_list(ia::IntersectionArray{N}) where {N}

Return the list of constraints of an intersection of a finite number of (polyhedral) sets.

Input

• ia – intersection of a finite number of (polyhedral) sets

Output

The list of constraints of the intersection.

Notes

We assume that the underlying sets are polyhedral, i.e., offer a method constraints_list.

Algorithm

We create the polyhedron from the constraints_lists of the sets and remove redundant constraints.

constraints_list(rm::ResetMap{N}) where {N}

Return the list of constraints of a polytopic reset map.

Input

• rm – reset map of a polytope

Output

The list of constraints of the reset map.

Notes

We assume that the underlying set X is a polytope, i.e., is bounded and offers a method constraints_list(X).

Algorithm

We fall back to constraints_list of a LinearMap of the A-matrix in the affine-map view of a reset map. Each reset dimension $i$ is projected to zero, expressed by two constraints for each reset dimension. Then it remains to shift these constraints to the new value.

For instance, if the dimension $5$ was reset to $4$, then there will be constraints $x₅ ≤ 0$ and $-x₅ ≤ 0$. We then modify the right-hand side of these constraints to $x₅ ≤ 4$ and $-x₅ ≤ -4$, respectively.

constraints_list(rm::ResetMap{N, S}) where {N, S<:AbstractHyperrectangle}

Return the list of constraints of a hyperrectangular reset map.

Input

• rm – reset map of a hyperrectangular set

Output

The list of constraints of the reset map.

Algorithm

We iterate through all dimensions. If there is a reset, we construct the corresponding (flat) constraints. Otherwise, we construct the corresponding constraints of the underlying set.

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

Create a random parallelotope.

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.