An Ellipsoidal Calculus
Based on Propagation and Fusion
- MAPLE code freely available for academic purposes -

The grey ellipsoid transforms to the gold cylinder by propagation through an affine relationFusion (gold) of two ellipsoids (grey)
Joint work by
Assumpta Sabater (1),
Federico Thomas (2), and Lluís Ros (2)

(1) Applied Mathematics Department - UPC
(2) Institut de Robòtica i Informàtica Industrial - CSIC / UPC

electronic mail addresses are:
assumpta dot sabater-pruna followed by at upc dot es
fthomas followed by at iri dot upc dot es
llros followed by at ir dot upc dot es

Introduction  |  SnapshotsRelated papersMaple code


This work develops an Ellipsoidal Calculus based on two operations: propagation and fusion. Propagation refers to obtaining an ellipsoid that must satisfy an affine relation with another ellipsoid, and fusion to that of computing the ellipsoid that tightly bounds the intersection of two other ellipsoids. These two operations supersede the Minkowski sum and difference, affine transformation and intersection tight bounding of ellipsoids on which other Ellipsoidal Calculi are based. Actually, a Minkowski operation can be seen as a fusion followed by a propagation, and an affine transformation as a particular case of propagation. Moreover, the presented formulation is robust in the sense that it is inmune to degeneracies of the involved ellipsoids (they may extend infinetely in any direction) and/or of the affine relations.

Altogether, these tools permit a set-membership approach to dealing with uncertainty in many contexts. We here illustrate how they can be used in two specific domains:
the spatial interpretation of line drawings and the computation of force/manipulability ellipsoids for parallel manipulators. Other possible applications are to estimation theory, and to robot self-localization and map building (SLAM). 

The calculus has been implemented in MAPLE, and is distributed here under the name  ECT - Ellipsoidal Calculus Toolbox. Most of the routines are general, in the sense that they work for n-dimensional ellipsoids. ECT is accompanied with several MAPLE worksheets examplifying its use, and with several routines to plot the results. 


Example of propagation: Computing the uncertainty of the imaginary apex, taking into account the green uncertainties for the vertices


This sequence shows one application of the propagation and fusion operators to line drawing interpretation. The figure in red is a projection of a truncated tetrahedron. Note that it is only correct when the three edges joining the two red triangles intersect at a common point, the imaginary apex of such a tetrahedron. Since the apex must lie on any pair of two such edges, we can use the propagation operator to derive the yellow elliptical bounds for the apex, given the green elliptic uncertainties for the vertices.

Next, the three yellow ellipses are intersected by repeatedly using the fusion operator. The resulting elliptical envelope of such intersection is shown in yellow, in the second figure.

Related papers

L. Ros, A. Sabater, and F. Thomas. "An Ellipsoidal Calculus based on Propagation and Fusion." IEEE Transactions on Systems Man and Cybernetics, Part B. Vol. 32, n. 4, pp. 430-442. August 2002. IEEE Press. ISSN 1083-4419.

A. Sabater and F. Thomas, "Set Membership Approach to the Propagation of Uncertain Geometric Information," Proceedings of the 1991 IEEE International Conference on Robotics and Automation, Vol. III, pp. 2718-2723, abril 9-11, 1991, Sacramento, USA.

Maple code
(For MAPLE 8.0 or higher)

This code is freely distributed only for academic purposes.
Please contact the authors for permission to use it commercially.

The Ellipsoidal Calculus Toolbox is distributed as a single file, ect-1.0.txt, included below. There is no written manual for ECT 1.0 yet. However, all functions of the library are extensively documented inside ect-1.0.txt. These comments, together with the papers above, and the example worksheets below, should suffice to develop your own application of ECT. If you have troubles using ECT, you can also e-mail us, we'll be glad to help you.

So where do you start? We recommend that you first read the first paper above (which explains the the calculus in the form implemented in ECT), then download all files below, and try the execution of the example worksheets in MAPLE 8.0 or higher. HTML versions of these files are also available, to browse their contents without executing them.  If you prefer, you can download all files below collected in a zip file (2.6 Mb).

- ECT's primary library file:
- Simple examples of propagation:
Maple worksheet - Html version
- Simple examples of fusion:
Maple worksheet - Html version
- Simple examples of Minkowski sums:
Maple worksheet - Html version

Two applications of ECT are included, related to dealing with uncertainty in line drawing interpretation and isotropy analysis of parallel manipulators:

- Application to line drawing interpretation:
Tools ascii file - Maple worksheet - Html version
- Application to isotropy analysis:
Tools ascii file - Maple worksheet - Html version