Reset map (ResetMap)

ResetMap{N, S<:LazySet{N}} <: AbstractAffineMap{N, S}

Type that represents a lazy reset map. A reset map is a special case of an affine map $A x + b, x ∈ X$ where the linear map $A$ is the identity matrix with zero entries in all reset dimensions, and the translation vector $b$ is zero in all other dimensions.

Fields

• X – set
• resets – resets (a mapping from an index to a new value)

Notes

The reset map preserves convexity: if X is convex, then any reset map of X is convex as well.

Examples

julia> X = BallInf([2.0, 2.0, 2.0], 1.0);

julia> r = Dict(1 => 4.0, 3 => 0.0);

julia> rm = ResetMap(X, r);

Here rm modifies the set X such that x1 is reset to 4 and x3 is reset to 0, while x2 is not modified. Hence rm is equivalent to the set Hyperrectangle([4.0, 2.0, 0.0], [0.0, 1.0, 0.0]), i.e., an axis-aligned line segment embedded in 3D.

The corresponding affine map $A x + b$ would be:

\[ egin{pmatrix} 0 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 0 nd{pmatrix} x + egin{pmatrix} 4 & 0 & 0 nd{pmatrix}\]

Use the function matrix (resp. vector) to create the matrix A (resp. vector b) corresponding to a given reset map.

julia> matrix(rm)
3×3 LinearAlgebra.Diagonal{Float64,Array{Float64,1}}:
 0.0   ⋅    ⋅
  ⋅   1.0   ⋅
  ⋅    ⋅   0.0

julia> vector(rm)
3-element SparseArrays.SparseVector{Float64,Int64} with 1 stored entry:
  [1]  =  4.0

The application of a ResetMap to a ZeroSet or an EmptySet is simplified automatically.

julia> ResetMap(ZeroSet(3), r)
Singleton{Float64,SparseArrays.SparseVector{Float64,Int64}}(  [1]  =  4.0)

julia> ResetMap(EmptySet(3), r)
EmptySet{Float64}(3)

The (in this case unique) support vector of rm in direction ones(3) is:

julia> σ(ones(3), rm)
3-element Array{Float64,1}:
 4.0
 3.0
 0.0

dim(rm::ResetMap)

Return the dimension of a reset map.

Input

• rm – reset map

Output

The dimension of a reset map.

ρ(d::AbstractVector, rm::ResetMap)

Return the support function of a reset map.

Input

• d – direction
• rm – reset map

Output

The support function in the given direction.

Notes

We use the usual dot-product definition, but for unbounded sets we redefine the product between $0$ and $±∞$ as $0$; Julia returns NaN here.

julia> Inf * 0.0
NaN

See the discussion here.

σ(d::AbstractVector, rm::ResetMap)

Return the support vector of a reset map.

Input

• d – direction
• rm – reset map

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

an_element(rm::ResetMap)

Return some element of a reset map.

Input

• rm – reset map

Output

An element in the reset map. It relies on the an_element function of the wrapped set.

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

Return the $A$ matrix of the affine map $A x + b, x ∈ X$ represented by a reset map.

Input

• rm – reset map

Output

The (diagonal) matrix for the affine map $A x + b, x ∈ X$ represented by the reset map.

Algorithm

We construct the identity matrix and set all entries in the reset dimensions to zero.

vector(rm::ResetMap)

Return the $b$ vector of the affine map $A x + b, x ∈ X$ represented by a reset map.

Input

• rm – reset map

Output

The (sparse) vector for the affine map $A x + b, x ∈ X$ represented by the reset map. The vector contains the reset value for all reset dimensions, and is zero for all other dimensions.

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.

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.