LazySets: overapproximate sum of two HPolyhedron in 3D (or n-D)

General Usage
1

I am using the package LazySets to compute the Minkowsky sum of two HPolyhedron and then extract the resulting constraints to feed them into my JuMP model.
For the 2D case, I can approximate the exact Polyhedron with overapproximate, like this:

n = 2
A = [Matrix{Float64}(I, n,n); -Matrix{Float64}(I, n,n)]
b = 0.1*ones(size(A,1))
hPoly = HPolyhedron(A, b)
minkowSum = hPoly ⊕ hPoly 
overapproximate(minkowSum , 1e-3)

However, for higher dimensional Polyhedron (e.g. n=3) overapproximate throws an error. Is there a way to approximate the HPolyhedron resulting from the Minkowsky addition for n=3 with LazySets or Polyhedra?

1 Like
2

For anybody having similar issues, here is a short update:

Overapproximating an AbstractPolytope with n\ge4 is not implemented yet. For any updates on that topic, consider:
https://github.com/JuliaReach/LazySets.jl/issues/969

If you want to overapproximate an AbstractPolytope with n=3, the following code can be used

using LazySets
using Polyhedra
P = rand(HPolytope, dim=n)
A = rand(n,n)
minkowSum= A*P + P
dirs = SphericalDirections(10, 10)
oa = overapproximate(minkowSum, dirs)

The link below refers to the GitHub issue, where additional references can be found.
https://github.com/JuliaReach/LazySets.jl/issues/1476

1 Like