stephane-caron/pyfme

Symbolic (analytical) polyhedron projection by Fourier-Motzkin elimination using SymPy

Symbolic Fourier-Motzkin elimination

This library can be used to project a polyhedron using Fourier-Motzkin elimination with the two Imbert acceleration theorems. It is implemented in Python using SymPy for symbolic computations and multiprocessing to leverage the high degree of parallelization achievable with this method.

Trying out variable eliminations

This library is mainly a graphical tool to help a human user explore various variable-elimination schemes to project a polyhedral cone given in symbolic form. The user can explore the directed acyclic graph of variable-elimination sequences, adding if-then-else nodes to the graph when desired.

Example

We used Fourier-Motzkin elimination to derive the frictional wrench cone of surface contacts used in robotics to alleviate computations caused by redundant contact-point models. The step-by-step example wrench_cone.py derives automatically the calculations from the Appendix of this paper. You can start from there for a first contact with the GUI.

Related libraries

For better performance on numerical rather than symbolic systems, you can use the double description method. A number of libraries implement this algorithm, or similarly vertex enumeration or convex hull algorithms:

• cdd (C) or pycddlib (Python)
• lrs
• panda
• pypoman
• ppl (C++) or pyparma (Python)
• qhull