GLGM06{N, AM, S, D, NG, P, RM} <: AbstractContinuousPost

Implementation of Girard - Le Guernic - Maler algorithm for reachability of linear systems using zonotopes.

Fields

• δ – step-size of the discretization
• approx_model – (optional, default: FirstOrderZonotope) approximation model; see Notes below for possible options
• max_order – (optional, default: 5) maximum zonotope order
• static – (optional, default: false) if true, convert the problem data to statically sized arrays
• dim – (optional default: missing) ambient dimension
• ngens – (optional, default: missing) number of generators
• preallocate – (optional, default: true) if true, use the implementation which preallocates the zonotopes prior to applying the update rule
• reduction_method – (optional, default: GIR05()) zonotope order reduction method used
• disjointness_method – (optional, default: NoEnclosure()) method to check disjointness between the reach-set and the invariant

Notes

The type fields are:

• N – number type of the step-size
• AM – approximation model
• S – value type associated to the static option
• D – value type associated to the dimension of the system
• NG – value type associated to the number of generators
• P – value type associated to the preallocate option
• RM – type associated to the reduction method

The sole parameter which doesn't have a default value is the step-size, associated to the type parameter N. Parameters D and NG are optionally specified (default to Missing). These parameters are needed for implementations that require the size of the zonotopes to be known (fixed) at compile time, namely the static=true version of this algorithm. Otherwise, the number of generators is not necessarily fixed.

The default approximation model is

approx_model=FirstOrderZonotope()

Here, FirstOrderZonotope refers to the forward-time adaptation of the approximation model from Lemma 3 in [FRE11]. Some of the options to compute this approximation can be specified, see the documentation of FirstOrderZonotope for details.

References

The main ideas behind this algorithm can be found in [GIR05] and [GLGM06]. These methods are discussed at length in the dissertation [LG09].

Regarding the zonotope order reduction methods, we refer to [COMB03], [GIR05] and the review article [YS18].

Regarding the approximation model, we use an adaptation of a result in [FRE11].