Polytope evaluation algorithms

There are three methods implemented in this paper to resolve all the polytope calculations:

• Hyper-plane shifting method (HPSM)

• Iterative convex hull method (ICHM)

• Vertex enumeration (VEPOLI²)

All of the methods are implemented in the module pycapacity.algorithms and can be used as standalone functions. See in [docs for more info](pycapacity.algorithms.html).

Hyper-plane shifting method (HPSM)

Based on the paper:

Characterization of Parallel Manipulator Available Wrench Set Facets

by Gouttefarde M., Krut S.

In: Lenarcic J., Stanisic M. Advances in Robot Kinematics: Motion in Man and Machine. Springer, Dordrecht (2010)

This method finds the half-space representation of the polytope of a class:

\[P = \{ x ~|~ x = By, \quad y_{min}\leq y \leq y_{max} \}\]

To find the vertices of the polytope after finding the half-space representation \(Hx \leq d\) an convex-hull algorithm is used.

The method is a part of the pycapacity.algorithms` module hyper_plane_shift_method, See in docs for more info

Iterative convex-hull method (ICHM)

Based on the paper:

On-line feasible wrench polytope evaluation based on human musculoskeletal models: an iterative convex hull method

by A.Skuric, V.Padois, N.Rezzoug and D.Daney

Published in RAL & ICRA2022

This method finds both vertex and half-space representation of the class of polytopes:

\[P = \{ x ~|~ Ax = By, \quad y_{min}\leq y \leq y_{max} \}\]

And it can be additionally extended to the case where there is an additional projection matrix $P$ making a class of problems:

\[P = \{ x ~|~ x= Pz, Az = By, \quad y_{min}\leq y \leq y_{max} \}\]

The method is a part of the pycapacity.algorithms module iterative_convex_hull_method. See the docs for more info

Vertex enumeration algorithm (VEPOLI²)

Based on the paper:

On-line force capability evaluation based on efficient polytope vertex search

by A.Skuric, V.Padois and D.Daney

Published on ICRA2021

This method finds vertex representation of the class of polytopes:

\[P = \{ x ~|~ Ax = y, \quad y_{min}\leq y \leq y_{max} \}\]

To find the half-space representation (faces) of the polytope after finding the vertex representation an convex-hull algorithm is used.

The method is a part of the pycapacity.algorithms module vertex_enumeration_vepoli2. See the docs for more info

Performance evaluation of polytope metrics

The applicable methods to evaluate different polytope based metrics depend on the family of problems they correspond to. Therefore this section brings the information about which algorithm is used for which polytope metric and provides a brief performance evaluation their execution times.

Polytope algorithms used for different robot polytope metrics and their performance evaluation

Polytope Metric	Algorithm	Problem type	Execution time [ms] mean \(\pm\) std. (max)
Velocity	HPSM	\(x=By,~ y \in [y_{min}, y_{max}]\)	3.6 \(\pm\) 0.21 (5.7)
Acceleration	HPSM	\(x=By,~ y \in [y_{min}, y_{max}]\)	6.6 \(\pm\) 1.4 (14.2)
Force	VEPOLI \(\!^2\)	\(Ax=b, ~ b \in [b_{min}, b_{max}]\)	6.8 \(\pm\) 0.88 (16.4)
Force intersection	VEPOLI \(\!^2\)	\(Ax=b,~ b \in [b_{min}, b_{max}]\)	98.2 \(\pm\) 29.33 (165.8)
Force sum	VEPOLI \(\!^2\)	\(Ax=b,~ b \in [b_{min}, b_{max}]\)	17.1 \(\pm\) 3.4 (44.9)
Reachable space	ICHM	\(x=By,~ y \in P_{y}\)	30.5 \(\pm\) 6.6 (76.7)

The average execution time is calculated using 7 dof Franka Emika panda robot, the model was used with pinocchio software. All the experiments are run on a computer equipped with 1.90GHz Intel i7-8650U processor. The results are obtained using the benchmarking script provided in the examples folder, script link.

In case of human musculoskeletal models the methods used are given in the table below.

Polytope algorithms used for different human polytope metrics and their performance evaluation

Polytope Metric	Algorithm	Problem type	Execution time [ms] mean \(\pm\) std. (max)
Force	ICHM	\(Ax=By,~ y \in [y_{min}, y_{max}]\)	186.8 \(\pm\) 45.6 (281.6)
Acceleration	HPSM or ICHM	\(x=By,~ y \in [y_{min}, y_{max}]\)	378.8 \(\pm\) 62.3 (643.7)
Velocity	ICHM	\(x=By,~ y \in P_{y}\)	223.1 \(\pm\) 60.4 (389.1)

The average execution time was calculated using 50 muscle 7 dof musculoskeletal model introduced by Holzbaur, the model was used with biorbd biomechanics software. The experiments are run on a computer equipped with 1.90GHz Intel i7-8650U processor. The results are obtained using the benchmarking script provided in the examples folder, script link.

As these times can vary significantly depending on the complexity of the model used and the hardware it is run on, the users are encouraged to run the benchmark scripts themselves to get the most accurate results. This package provides several benchmarking scripts in the examples folder, see link for more details: link.