ReachabilityAnalysis.jl
ReachabilityAnalysis.jl copied to clipboard
Implement GLGM06 scheme without order reduction
see http://ljk.imag.fr/membres/Antoine.Girard/Publications/hscc2006a.pdf Algorithm 1.
I just read the paper again. Here are some more comments:
- The algorithm is general in a set representation that is closed under linear map and Minkowski sum (e.g., polytopes). So the method should not be restricted to
Zonotope
s. And for homogeneous systems, you only need closure under linear map, so you can also use, e.g., ellipsoids. - Even the algorithm with approximation (e.g., order reduction) is general in the set representation. For example, the paper only presents an algorithm with box approximation and not with order reduction (Algorithm 2). I suggest that there should be a parameter
approximation
that is a function that takes a set and returns a new set. This function can then be instantiated withreduce_order
orbox_approximation
. This is also discussed in Remark 1, so the algorithm with approximation could for instance also be instantiated with ellipsoids and boxes. - The implementation here looks actually different from the pseudocode to me. It would be interesting to implement the exact same algorithm as a comparison.
- In particular, the algorithm in the paper suggests to share the generators of the zonotopes in the sequence. This might be much better than creating copies for each
ReachSet
.
Thanks for the heads up! Let me CC @asarvind with whom we discussed about this method recently.
The implementation here looks actually different from the pseudocode to me. It would be interesting to implement the exact same algorithm as a comparison.
True. I look forward to adding one or two new variations of GLGM06 for comparison. A good candidate test is the helicopter model.
It would be interesting to try this method in connection to https://github.com/JuliaReach/LazySets.jl/pull/2288 (efficient 2D zonotope vertex enumeration algorithm).