Star

Star{N, VN<:AbstractVector{N}, MN<:AbstractMatrix{N}, PT<:AbstractPolyhedron{N}} <: AbstractPolyhedron{N}

Generalized star set with a polyhedral predicate, i.e.

\[X = \{x ∈ ℝ^n : x = x₀ + ∑_{i=1}^m α_i v_i,~~\textrm{s.t. } P(α) = ⊤ \},\]

where $x₀ ∈ ℝ^n$ is the center, the $m$ vectors $v₁, …, vₘ$ form the basis of the star set, and the combination factors $α = (α₁, …, αₘ) ∈ ℝ^m$ are the predicate's decision variables, i.e., $P : α ∈ ℝ^m → \{⊤, ⊥\}$ where the polyhedral predicate satisfies $P(α) = ⊤$ if and only if $A·α ≤ b$ for some fixed $A ∈ ℝ^{p × m}$ and $b ∈ ℝ^p$.

Fields

• c – vector that represents the center
• V – matrix where each column corresponds to a basis vector
• P – polyhedral set that represents the predicate

Notes

The predicate function is implemented as a conjunction of linear constraints, i.e., a subtype of AbstractPolyhedron. By a slight abuse of notation, the predicate is also used to denote the subset of $ℝ^n$ such that $P(α) = ⊤$ holds.

The $m$ basis vectors (each one $n$-dimensional) are stored as the columns of an $n × m$ matrix.

We remark that a Star is mathematically equivalent to the affine map of the polyhedral set P, with the transformation matrix and translation vector being V and c, respectively.

Examples

This example is drawn from Example 1 in [2]. Consider the two-dimensional plane $ℝ^2$. Let

julia> V = [[1.0, 0.0], [0.0, 1.0]];

be the basis vectors and take

julia> c = [3.0, 3.0];

as the center of the star set. Let the predicate be the infinity-norm ball of radius 1,

julia> P = BallInf(zeros(2), 1.0);

We construct the star set $X = ⟨c, V, P⟩$ as follows:

julia> S = Star(c, V, P)
Star{Float64, Vector{Float64}, Matrix{Float64}, BallInf{Float64, Vector{Float64}}}([3.0, 3.0], [1.0 0.0; 0.0 1.0], BallInf{Float64, Vector{Float64}}([0.0, 0.0], 1.0))

We can use getter functions for each component field:

julia> center(S)
2-element Vector{Float64}:
 3.0
 3.0

julia> basis(S)
2×2 Matrix{Float64}:
 1.0  0.0
 0.0  1.0

julia> predicate(S)
BallInf{Float64, Vector{Float64}}([0.0, 0.0], 1.0)

In this case, the generalized star $S$ above is equivalent to the rectangle $T$ below.

\[ T = \{(x, y) ∈ ℝ^2 : (2 ≤ x ≤ 4) ∧ (2 ≤ y ≤ 4) \}\]

References

Star sets as defined here were introduced in [1]; see also [2] for a preliminary definition. For applications in reachability analysis of neural networks, see [3].

• [1] Duggirala, P. S., and Mahesh V. Parsimonious, simulation based verification of linear systems. International Conference on Computer Aided Verification. Springer, Cham, 2016.

• [2] Bak S, Duggirala PS. Simulation-equivalent reachability of large linear systems with inputs. In International Conference on Computer Aided Verification 2017 Jul 24 (pp. 401-420). Springer, Cham.

• [3] Tran, H. D., Lopez, D. M., Musau, P., Yang, X., Nguyen, L. V., Xiang, W., & Johnson, T. T. (2019, October). Star-based reachability analysis of deep neural networks. In International Symposium on Formal Methods (pp. 670-686). Springer, Cham.

an_element(X::LazySet)

Return some element of a nonempty set.

Input

• X – set

Output

An element of X unless X is empty.

Extended help

an_element(X::Star)

Algorithm

We apply the affine map to the result of an_element on the predicate.

basis(X::Star)

Return the basis vectors of a star.

Input

• X – star

Output

A matrix where each column is a basis vector of the star.

constraints_list(X::LazySet)

Compute a list of linear constraints of a polyhedral set.

Input

• X – polyhedral set

Output

A list of the linear constraints of X.

Extended help

constraints_list(X::Star)

Algorithm

See constraints_list(::LazySets.AbstractAffineMap).

isbounded(X::LazySet)

Check whether a set is bounded.

Input

• X – set

Output

true iff the set is bounded.

Notes

See also isboundedtype(::Type{<:LazySet}).

Extended help

isbounded(X::Star; cond_tol::Number=DEFAULT_COND_TOL)

Algorithm

See isbounded(::LazySets.AbstractAffineMap).

predicate(X::Star)

Return the predicate of a star.

Input

• X – star

Output

A polyhedral set representing the predicate of the star.

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

Create a random set of the given set type.

Input

• T – set type
• 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 set of the given set type.

Extended help

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

Algorithm

A predicate P can be passed directly. If P is nothing (default), we generate a random HPolytope of dimension dim.

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

∈(x::AbstractVector, X::LazySet)

Check whether a point lies in a set.

Input

• x – point/vector
• X – set

Output

true iff $x ∈ X$.

Extended help

∈(v::AbstractVector, X::Star)

Algorithm

See ∈(::AbstractVector, ::LazySets.AbstractAffineMap).