heirung/pytope

Minimal package for operations on polytopes, zonotopes, and invariant sets.

pytope

Package with a limited set of operations for polytopes, zonotopes, and invariant sets.

The currently implemented features include

• constructing polytopes from inequalities (halfspace representation), vertices, and upper and lower bounds,
• linear mapping (multiplying a matrix M and a polytope P: M P),
• the Minkowski sum and Pontryagin difference of polytopes,
• the intersection of polytopes, and
• simple plotting.

The figures below are generated with pytope. The first two illustrate some of the currently implemented operations (see demo.py); the third uses pytope to plot a robust MPC trajectory (obtained with CasADi), combining Figures 1 and 2 from Mayne et al. (2005) with a rough approximation of the disturbance sequence; the fourth shows an outer ε-approximation of a minimal robust positively invariant, or MRPI, set computed with pytope, reproducing the example from Raković et al. (2005).

pytope is experimental, fragile, largely untested, and probably buggy.

Figure: Illustration of various polytope operations.

Figure: The Minkowski sum of two polytopes.

Figure: Robust MPC trajectory from Mayne et al. (2005), combining Figures 1 and 2.

Figure: Outer ε-approximation of a minimal robust positively invariant (MRPI) set – a reproduction of the example in Raković et al. (2005).

References

• Mayne, D.Q., Seron, M.M., & Raković, S.V. (2005). Robust model predictive control of constrained linear systems with bounded disturbances. Automatica, 41(2), 219–224.
• Raković, S.V., Kerrigan, E.C., Kouramas, K.I., & Mayne, D.Q. (2005). Invariant approximations of the minimal robust positively invariant set. IEEE Transactions on Automatic Control, 50(3), 406–410.

pytope's Issues

Error in determine_H_rep

pytope/pytope/polytope.py

Line 366 in ebd8540

i_ineq_rows = list(set(range(H_cdd.col_size)) - H_cdd.lin_set)

Shouldn't this be H_cdd.row_size instead of H_cdd.col_size?

Obtaining H representation from vertices flips the vertices in the one dimensional case

Hi,

I realized that when defining a one-dimensional polytope via its vertices and obtaining the H representation from its V representation, the vertices will be flipped.
For example, we want to define the polytope given by the inverval $[-a,b]$, where $a,b>0$, and define a polytope based on $a$ and $b$.
Then the H representation of this polytope actually describes the polytope $[-b, a]$ and not $[-a, b]$.
Furthermore, when determining the V representation after determining the H representation, the V representation will also contain the flipped vertices.

Below I provide a code snippet to reproduce the issue, where $a=0.5$ and $b=1$.

import numpy as np
import pytope as pt # tested version 0.0.5

# define vertices for the polytope [-0.5, 1]
V= np.array([[-0.5], [1]])

# define polytope by vertices
poly = pt.Polytope(V=V)
print('Vertices describing poly before determining H rep:')
print(poly._get_V().T)
poly.determine_H_rep()
# Check if vertices are in the H representation
for i in range(len(V)):
    vertex = V[i]   
    print(f"Is vertex = {vertex[0]} in the H representation of the polytope defined by [-0.5, 1]?")
    if sum(poly.A*vertex-poly.b>0)>0:
        print("No")
# check vertices after determining the H rep
print('Vertices describing poly after determining H rep:')
print(poly._get_V().T)
# check vertices after determining both the H and V rep
poly.determine_V_rep()
print('Vertices describing poly after determining H rep and V rep:')
print(poly._get_V().T)

This code will print out "No", when we check if the vertex $1$ is in the H representation of the polytope and show that the vertices are flipped when determining the V representation after the H representation.

Pip version

Hello Tor,

We've been using your library in safe-control-gym for implementing robust tube MPC among other things.
Would you mind updating the pipy package to be version 0.0.5?
We would greatly appreciate it!
There's a couple features that you added in your latest release that we need and we'd like to avoid having to git clone and pip install from source.