Nicolas Binaud
email: binaud@irccyn.ec-nantes.fr

Philippe Cardou ⋆

St Éphane Caro

Philippe Wenger
email: wenger@irccyn.ec-nantes.fr

DETC2010/28635 THE KINEMATIC SENSITIVITY OF ROBOTIC MANIPULATORS TO JOINT CLEARANCES

The paper deals with the kinematic sensitivity of robotic manipulators to joint clearances. First, an error prediction model applicable to both serial and parallel manipulators is developed. A clearance model associated with axisymmetrical joints, which are widely used in robotic manipulators, is also proposed. Then, two nonconvex quadratically constrained quadratic programs (QCQPs) are formulated in order to find the maximum reference-point position error and the maximum orientation error of the moving-platform for given joint clearances. Finally, the contributions of the paper are highlighted by means of two illustrative examples.

INTRODUCTION

Accuracy is one of the key features that favor robotic manipulators for many industrial applications. Superior levels of accuracy are achieved by controlling or measuring all possible sources of errors on the pose of the moving platform 1 of a robotic manipulator. Among the most important sources of errors, we find manufacturing errors, assembly errors, compliance in the mechanical architecture, resolution of the servoactuators, backlash in the reductors, and clearances in the joints. As indicated in refs. [START_REF] Carusone | Tracking control for end-effector position and orientation of structurally flexible manipulators[END_REF][START_REF] Zhuang | Self-calibration of parallel mechanisms with a case study on stewart platforms[END_REF], the errors due to manufacturing, assembly and compliance can be compensated through calibration and model-based control. Joint clearances, on the contrary, exhibit low repeatability, which generally makes their compensation difficult. For this reason, the focus of this paper is the impact of joint clearances on the pose errors of serial and parallel-mechanism moving platforms.

Joint clearances introduce extraneous degrees of freedom between two connected links. When present, they generally contribute importantly to the degradation of the performance of a mechanism. Besides increasing the point-position and orientation errors of the end effector of a mechanism, they may cause impacts and faster wear of the joints. Because of these undesirable effects, machine designers can eliminate clearances by preloading the pairing elements. However, with preloaded joints, a parallel mechanism is difficult to assemble, as it requires high tolerances and manufacturing costs. When the parallel mechanism is overconstrained, it may even lose degrees of mobility or be impossible to assemble. As a result, joint clearances can be essential for proper functioning of certain mechanisms, but they cannot be neglected when evaluating their accuracy.

We may file the various approaches that have been proposed to compute and quantify the errors due to joint clearances into two categories: stochastic [START_REF] Ting | Uncertainty analysis of planar and spatial robots with joint clearances[END_REF] and deterministic [START_REF] Wang | Position errors due to clearances in journal bearings[END_REF][START_REF] Lin | Accuracy analysis of planar linkages by the matrix method[END_REF][START_REF] Innocenti | Kinematic clearance sensitivity analysis of spatial structures with revolute joints[END_REF][START_REF] Voglewede | Application of workspace generation techniques to determine the unconstrained motion of parallel manipulators[END_REF][START_REF] Venanzi | A new technique for clearance influence analysis in spatial mechanisms[END_REF][START_REF] Meng | Accuracy analysis of parallel manipulators with joint clearance[END_REF]. In this paper, we focus on deterministic methods, which generally allow to draw firm bounds on the pose errors given possible ranges for the clearances.

Wang and Roth [START_REF] Wang | Position errors due to clearances in journal bearings[END_REF] essentially proposed a model for clearances in revolute joints embodied as journal bearings. The effect of these clearances under a given wrench applied at the moving platform of a robotic manipulator was then computed by Innocenti [START_REF] Innocenti | Kinematic clearance sensitivity analysis of spatial structures with revolute joints[END_REF]. Other researchers attempted to decouple the effect of clearances from the wrench applied at the moving platform by computing all its possible displacements.

This is what was done by Voglewede and Ebert-Uphoff [START_REF] Voglewede | Application of workspace generation techniques to determine the unconstrained motion of parallel manipulators[END_REF], who used workspace generation techniques in order to compute the boundary of the set of moving-platform displacements allowed by clearances at the joints. The solution proposed in ref. [START_REF] Voglewede | Application of workspace generation techniques to determine the unconstrained motion of parallel manipulators[END_REF] is general and very attractive. However, it becomes computationally intensive when high numbers of joints are affected by clearances, and the moving-platform displacements occur in three-dimensional space.

In order to fill this gap, Venanzi and Parenti-Castelli [START_REF] Venanzi | A new technique for clearance influence analysis in spatial mechanisms[END_REF] took advantage of the generally small displacements allowed by clearances to treat them as small-displacement screws. The linearized loop-closure equations could then be used to evaluate the effects of clearances. A method for computing the maximum values of the moving-platform screw components due to clearances in a single open kinematic chain was devised. However, as these authors point out, their method does not apply to overconstrained parallel mechanisms, since they rely on the principle of virtual work in order to obtain the relationship between joint and moving-platform displacements.

Recently, Meng et al. [START_REF] Meng | Accuracy analysis of parallel manipulators with joint clearance[END_REF] modified the formulation proposed in ref. [START_REF] Venanzi | A new technique for clearance influence analysis in spatial mechanisms[END_REF] and approximated the clearance model proposed by Wang and Roth [START_REF] Wang | Position errors due to clearances in journal bearings[END_REF], which allowed them to formulate the problem of maximizing the components of the moving-platform small-displacement screw for any parallel mechanism. The problems obtained through this reformulation are convex, which guarantees that any local optimization method will converge to the global optimum. The results reported by Meng et al. [START_REF] Meng | Accuracy analysis of parallel manipulators with joint clearance[END_REF] are very complete, since they provide a fast and efficient method for computing the effect of clearances on the moving-platform pose of a robotic manipulator.

Nevertheless, we believe that it would be interesting to define a minimum number of metrics, in order to draw easily understandable, global pictures of the effect of clearances on the moving platform. In previous reports, the effect of joint clearances is measured sequentially over all the displacement directions of the moving platform. In space, this gives a total of six metrics, over which the designer is to base his design of a robotic manipulator. In this paper, we follow an idea proposed in ref. [START_REF] Cardou | Kinematic-sensitivity indices for dimensionally nonhomogeneous jacobian matrices[END_REF] and elsewhere for measuring the moving-platform sensitivity to actuator displacements. In clear, we define two indices: one for reference-point displacements of the moving platform, and one for its rotations.

The paper is divided as follows. We first recall the error prediction model proposed by [START_REF] Venanzi | A new technique for clearance influence analysis in spatial mechanisms[END_REF]. We then propose a model of clearances in axisymmetrical joints that is slightly different from those reported by [START_REF] Wang | Position errors due to clearances in journal bearings[END_REF][START_REF] Meng | Accuracy analysis of parallel manipulators with joint clearance[END_REF]. Having formally written all required models, we define the two proposed indices, which take the form of nonconvex optimization problems. We then explain the strategy adopted for solving this optimization problem. We finish with two examples, where we compute the indices for given poses of a spatial serial 3R manipulator and a planar parallel fivebar manipulator.

ERROR PREDICTION MODEL

A methodology is introduced is this section to obtain the variations in the moving platform pose as a function of joint clearances. In this vein, we consider serial and parallel robotic manipulators consisting of a fixed base and a moving-platform, which are mutually connected through m legs. Let us assume that the i th leg is a serial kinematic chain composed of n i links, the first being connected to the base and the n th i to the movingplatform. For a serial robotic manipulator m turns to be equal to 1. We mathematically describe these open kinematic chains using the Denavit-Hartenberg parameters.

Parameterization

Let us define frame F i, j , which is attached to the j th link of the i th leg. Moreover, F i,1 , i = 1, . . . , m, are the reference frames attached to the fixed base and have the same orientation. P i = F i,n i , i = 1, . . . , m, are attached to the moving-platform of the robotic manipulator. Each frame is related to the previous one by the screw

S i, j = R i, j t i, j 0 T 3 1 ∈ SE(3), (1)
which takes F i, j onto F i, j+1 , and where R i, j ∈ SO(3) is a 3 × 3 rotation matrix; t i, j ∈ R 3 points from the origin of F i, j to that of F i, j+1 , and 0 3 is the three-dimensional zero vector. Moreover, all frames follow the Denavit-Hartenberg convention [START_REF] Hartenberg | Kinematic Synthesis of Linkages[END_REF], so that S i, j may be expressed as

S i, j = S i, j,θ S i, j,b S i, j,a S i, j,α , (2)
where

S i, j,α ≡     1 0 0 0 0 cos α i, j sin α i, j 0 0 -sin α i, j cos α i, j 0 0 0 0 1     , (3)
S i, j,a ≡     1 0 0 a i, j 0 1 0 0 0 0 1 0 0 0 0 1     , (4)
S i, j,b ≡     1 0 0 0 0 1 0 0 0 0 1 b i, j 0 0 0 1     , (5)
S i, j,θ ≡     cos θ i, j sin θ i, j 0 0 -sin θ i, j cos θ i, j 0 0 0 0 1 0 0 0 0 1     , (6)
and where α i, j , a i, j , b i, j and θ i, j represent the link twist, the link length, the link offset, and the joint angle, respectively. In the case of a revolute joint, θ i, j is a variable, whereas in the case of a prismatic joint, b i, j is a variable.

The Moving-Platform Pose

Thence, the pose of the sixth link with respect to the fixed frame F i,1 may be expressed as

P i = n i ∏ j=1 S i, j , (7)
for a given leg i. Provided that the joints are perfectly rigid in all directions but one, that the links are perfectly rigid and that the geometry of the robotic manipulator is known exactly, we have

P = P 1 = P 2 = • • • = P m . (8)
However, if we consider small clearances in all the joints, we must include small errors in Eq. ( 7) of P i for Eq. ( 8) to hold true.

Joint-Clearance Errors

Taking into account clearances in the joints, the frame F i, j associated with link j of leg i is shifted to F ′ i, j . Provided it is small, this error on the pose of joint j + 1 with respect to joint j may be represented by the small-displacement screw

δ s i, j ≡ δ r i, j δ t i, j ∈ R 6 , (9)
where δ r i, j ∈ R 3 represents the small rotation taking frame F i, j onto F ′ i, j , while δ t i, j ∈ R 3 points from the origin of F i, j to that of F ′ i, j . δ s i, j can also represented as the 4 × 4 matrix

δ S i, j = δ R i, j δ t i, j 0 T 3 0 ∈ se(3), ( 10
)
where δ R i, j ≡ ∂ (δ r i, j × x)/∂ x is the cross-product matrix of δ r i, j .

Error on the Moving-Platform Pose

Because of joint clearances, the frame P i is shifted to P ′ i . In SE(3), the displacement taking frame F i, j onto F ′ i, j is given by the matrix exponential of δ S i, j , e δ S i, j . As a result, the screw that represents the pose of the shifted moving-platform may be computed through the i th leg as

P ′ i = n i ∏ j=1 e δ S i, j S i, j , (11)
where screw P ′ i takes frame F i,1 onto P ′ i when taking errors into account.

In order to obtain the moving-platform pose error, the screw ∆P i |P i that takes the nominal moving-platform pose P i onto the shifted one P ′ i through the i th leg is expressed in frame P i as

∆P i |P i = P -1 i P ′ i , (12)
= 1 ∏ j=n i S -1 i, j n i ∏ j=1 e δ S i, j S i, j , (13)
= S -1 i,n i • • • S -1 i,1 e δ S i,1 S i,1 e δ S i,2 S i,2 • • • e δ S i,n i S i,n i , ≈ 1 ∏ j=n i S -1 i, j n i ∏ j=1 (1 4×4 + δ S i, j ) S i, j , (14)
= 1 ∏ j=n i S -1 i, j n i ∏ j=1 S i, j + δ S i, j S i, j , (15)
≈ 1 ∏ j=n i S -1 i, j n i ∏ j=1 S i, j + δ S i,1 S i,1 S i,2 • • • S i,n i + S i,1 δ S i,2 S i,2 • • • S i,n i + S i,1 S i,2 δ S i,3 S i,3 • • • S i,n i + • • • + S i,1 S i,2 • • • S i,n i -1 δ S i,n i S i,n i , (16)
= 1 4×4 + S -1 i,n i • • • S -1 i,1 δ S i,1 S i,1 S i,2 • • • S i,n i + S -1 i,n i • • • S -1 i,2 δ S i,2 S i,2 S i,3 • • • S i,n i + • • • + S -1 i,n i δ S i,n i S i,n i , (17)
= 1 4×4 + n i ∑ j=1 j ∏ k=n i S -1 i,k δ S i, j n i ∏ l= j S i,l . (18)
From Eq. ( 17), we see that end-effector displacement ∆P i |P i is small, since it is composed of the identity matrix plus a finite sum of small-displacement screws. Therefore, ∆P i |P i may be as well represented with the small displacement screw

δ P i |P i = n i ∑ j=1 j ∏ k=n i S -1 i,k δ S i, j n i ∏ l= j S i,l . (19)
Alternatively, the small-displacement screw taking frame P i onto frame P ′ i may be computed as a vector in R 6 , namely,

δ p i |P i
. To this end, let us recall that the adjoint map of screw S i, j is

adj(S i, j ) ≡ R i, j O 3×3 T i, j R i, j R i, j , (20)
where T i, j ≡ ∂ (t i, j × x)/∂ x is the cross-product matrix of t i, j . Then, we may express δ s i, j in frame F i, j+1 by simply computing adj(S -1 i, j )δ s i, j . As a result, δ s i, j may be expressed in frame P i through the product

j ∏ k=n i adj(S -1 i,k ) δ s i, j , (21)
and the small-displacement screw taking P i onto P ′ i simply becomes

δ p i |P i = n i ∑ j=1 j ∏ k=n i adj(S -1 i,k )δ s i, j (22)
≡ n i ∑ j=1 j ∏ k=n i (adj(S i,k )) -1 δ s i, j (23)
It is noteworthy that δ p i |P i is expressed in the frame attached to the moving platform, i.e., P i . For the evaluation of the pose errors on the moving-platform, the small-displacement screw taking P i onto P ′ i has to be expressed in the reference attached to the fixed base, i.e., F i,1 . Let δ p i |F i,1 be this smalldisplacement screw expressed in F i,1 :

δ p i |F i,1 = n i ∏ j=1 (N i, j )δ p i |P i , (24)
where

N i, j ≡ R i, j O 3×3 O 3×3 R i, j . ( 25
)
As a result,

δ p i |F i,1 = n i ∏ j=1 N i, j n i ∑ j=1 j ∏ k=n i adj(S i,k ) -1 δ s i, j (26)
= n i ∑ j=1 n i ∏ l=1 N i,l j ∏ k=n i (adj(S i,k )) -1 δ s i, j (27)
The following compact form may be used:

δ p i |F i,1 = M i δ s i , (28)
where

M i ≡ M i,1 M i,2 • • • M i,n i , (29)
M i, j ≡ n i ∏ l=1 (N i,l ) j ∏ k=n i (adj(S i,k )) -1 , (30)
δ s i ≡ δ s T i,1 δ s T i,2 • • • δ s T i,n i T . ( 31
)

MODELING THE CLEARANCES IN AN AXISYMMETRI-CAL JOINT

Intuitively, clearances in a joint are best modeled by bounding its associated errors below and above. Assuming that the lower and upper bounds are the same, this generally yields six parameters that bound the error screw δ s i, j . In the case of a revolute joint, however, we can take advantage of the axisymmetry to reduce the number of parameters. In the case of a prismatic joint, we assume that the prismatic joints are also axisymmetrical, which encompasses most hydraulic and pneumatic cylinders, as well as ball screws.

Recall that frame F i, j is attached to joint j of leg i according to the Denavit-Hartenberg convention. As a result, its Z-axis is aligned with the revolute-joint axis. Moreover, the origin of F i, j may be chosen to lie at the centroid of the revolute joint as shown in Fig. 1. In this case, the Z components of δ r i, j and δ t i, j -both defined in Eq. ( 9)-are axial components, while the X and Y components are radial. Accordingly, the error bounds are written as

δ r 2 i, j,X + δ r 2 i, j,Y ≤ ∆β 2 i, j,XY , (32) δ r 2 i, j,Z ≤ ∆β 2 i, j,Z , (33) δt 2 i, j,X + δt 2 i, j,Y ≤ ∆b 2 i, j,XY , (34) δt 2 i, j,Z ≤ ∆b 2 i, j,Z , (35)
where δ r i, j ≡ [δ r i, j,X δ r i, j,Y δ r i, j,Z ] T and δ t i, j ≡ [δt i, j,X δt i, j,Y δt i, j,Z ] T . Notice that previous works [START_REF] Wang | Position errors due to clearances in journal bearings[END_REF][START_REF] Venanzi | A new technique for clearance influence analysis in spatial mechanisms[END_REF][START_REF] Meng | Accuracy analysis of parallel manipulators with joint clearance[END_REF] have proposed geometric models of the embodiments and clearances of several types of revolute and prismatic joints based on bushings. Since many robotic mechanical systems rely on ball bearings, and not bushings, to allow motion of their joints, these geometrical analyzes are not always applicable. Therefore, we prefer using the generic mathematical inequalities (32-35), which are suitable for any axisymmetrical joint.

∆b i, j,Z ∆β i, j,XY ∆β i, j,Z ∆b i, j,XY x y z x y z x ′ y ′ z ′ F i, j F i, j F ′ i, j FIGURE 1. CLEARANCE-AFFECTED REVOLUTE JOINT

THE MAXIMUM MOVING-PLATFORM POSE ERRORS

This section aims at finding the maximum reference-point position error and the maximum orientation error of the movingplatform for given joint clearances and to identify the joints that need the tightest tolerances. Let us begin with the general case, where one seeks to identify the maximum errors due to joint clearances in the complete mechanism. For that matter, it would be interesting to compute the maximum rotation and maximum reference-point displacement due to joint clearances.

Formally, the maximum moving-platform rotation r max due to joint clearances is obtained by solving the problem

-r 2 max ≡ minimize -∑ k=1,2,3 (e T 6,k δ p) 2 , ( 36
) over δ p, δ s i, j , j = 1, . . . , n i , i = 1, . . . , m, subject to (e T 6,1 δ s i, j ) 2 + (e T 6,2 δ s i, j ) 2 -δ β 2 XY,i, j ≤ 0, (e T 6,3 δ s i, j ) 2 -δ β 2 Z,i, j ≤ 0, (e T 6,4 δ s i, j ) 2 + (e T 6,5 δ s i, j ) 2 -δ b 2 XY,i, j ≤ 0, (e T 6,6 δ s i, j ) 2 -δ b 2 Z,i, j ≤ 0, δ p = M i δ s i , j = 1, . . . , n i , i = 1, . . . , m, where e j,k ∈ R 6 is defined such that 1 j× j ≡ [e j,1 e j,2 • • • e j, j ].
Notice that r max is independent of δ t i, j , j = 1, . . . , n i , i = 1, . . . , m, i.e., the errors on the positions of the joint centroids. This may be verified by noticing that the point-displacement component of the errors on the joints in the i th leg, δ s i , always lies in the nullspace of the first three rows of M i . Accordingly, their contribution to the objective (through the equality of Eq. ( 36)) is null. Furthermore, for the proposed error model, the rotation and point-displacement errors, δ r i, j and δ t i, j , are completely decoupled in the inequality constraints. In conclusion, since δ t i, j does not affect the objective and is decoupled from the optimization variables that affect the objective, its associated constraints may be removed from Eq. (36). This leaves us with the simpler equivalent form

-r 2 max ≡ minimize -∑ k=1,2,3 (e T 6,k δ p) 2 , ( 37
) over δ p, δ s i, j , j = 1, . . . , n i , i = 1, . . . , m, subject to (e T 6,1 δ s i, j ) 2 + (e T 6,2 δ s i, j ) 2 -δ β 2 XY,i, j ≤ 0, (e T 6,3 δ s i, j ) 2 -δ β 2 Z,i, j ≤ 0, δ p = M i δ s i , j = 1, . . . , n i , i = 1, . . . , m.
The expression of the maximum point-displacement p max due to joint clearances is the same as that of r max , except for the objective function, namely,

-p 2 max ≡ minimize -∑ k=4,5,6 (e T 6,k δ p) 2 , ( 38
) over δ p, δ s i, j , j = 1, . . . , n i , i = 1, . . . , m, subject to (e T 6,1 δ s i, j ) 2 + (e T 6,2 δ s i, j ) 2 -δ β 2 XY,i, j ≤ 0, (e T 6,3 δ s i, j ) 2 -δ β 2 Z,i, j ≤ 0, (e T 6,4 δ s i, j ) 2 + (e T 6,5 δ s i, j ) 2 -δ b 2 XY,i, j ≤ 0, (e T 6,6 δ s i, j ) 2 -δ b 2 Z,i, j ≤ 0, δ p = M i δ s i , j = 1, . . . , n i , i = 1, . . . , m,
In the case of p max , the objective depends on both the rotation and the point-displacement errors. Therefore, Eq. ( 38) cannot be simplified as was Eq. ( 36).

Computing the Maximum Moving-Platform Pose Errors

The problems of Eqs. (37) and ( 38) are nonconvex quadratically constrained quadratic programs (QCQPs). Although their feasible sets are convex-all the constraints of both problems are convex-their objectives are concave, making the computation of their global minima -r 2 max and -p 2 max non-trivial, at least in general. Notice that some specific instances of nonconvex QCQPs were proven to have equivalent convex formulations [START_REF] Anstreicher | On lagrangian relaxation of quadratic matrix constraints[END_REF][START_REF] Ye | New results on quadratic minimization[END_REF][START_REF] Beck | Quadratic matrix programming[END_REF], and hence, allow for the computation of solutions in polynomial time. However, the problems of Eqs. (37) and (38) do not correspond to any of these classes of QCQPs. This calls for an additional effort in order to reliably and efficiently compute the global optima r max and p max .

We begin by rewriting Eq. ( 38) in a form that is similar to the original problem in ref. [START_REF] Hoffman | A method for globally minimizing concave functions over convex sets[END_REF]. This requires the elimination of the equality constraints, which may be achieved through a change of variables. To this end, let us resort to QR factorizations of M T i , 6) , and U i,1 ∈ R 6×6 is an upper-triangular matrix. This QR factorization may be computed using the Householder method. Notice that, from its structure, M i is bound to bear its full row rank of six. As a result, U i,1

M T i = V i U i , (39)
= V i,1 V i,2 U i,1 0 (6n-6)×6 , = V i,1 U i,1 , (40
) i = 1, . . . , m, where V i ∈ R 6n i ×6n i is orthogonal, U i ∈ R 6n i ×6 i is upper-triangular, V i,1 ∈ R 6×6 , V i,2 ∈ R 6×(6n i -
is also of full rank, i.e., it is invertible. Moreover, we define

δ q i ≡ δ q i,1 δ q i,2 = V T i δ s i , (41)
where δ q i,1 ∈ R 6 and δ q i,2 ∈ R 6n i -6 , so that

δ s i = V i,1 δ q i,1 + V i,2 δ q i,2 . ( 42
)
This allows us to rewrite the equality constraints as

δ p = M i δ s i = U T i,1 V T i,1 δ s i = U T i,1 δ q i,1 , (43)
or,

δ q i,1 = U -T i,1 δ p, (44)
where U -T i,1 is the inverse of the transpose of U i,1 . Upon substituting Eq. (44) into Eq. ( 42), we obtain

δ s i = V i,1 U -T i,1 δ p + V i,2 δ q i,2 . (45)
Let us regroup all remaining optimization variables into the array

δ u ≡ δ p T δ q T 1,2 δ q T 2,2 • • • δ q T m,2 T ∈ R ν ,
where ν = 6 + 6 ∑ m k=1 (n k -1), so that δ s i may be expressed as

δ s i ≡ ϒ i δ u, (46)
where

ϒ i ≡ V i,1 U -T i,1 V i,2 0 6n i ×6 ∑ m k=i+1 (n k -1) ∈ R 6n i ×ν , ( 47
) for i = 1 ϒ i ≡ V i,1 U -T i,1 0 6n i ×6 ∑ i-1 k=1 (n k -1) V i,2 0 6n i ×6 ∑ m k=i+1 (n k -1) ∈ R 6n i ×ν , (48)
for i = 2, . . . , m -1 and

ϒ i ≡ V i,1 U -T i,1 0 6n i ×6 ∑ i-1 k=1 (n k -1) V i,2 ∈ R 6n i ×ν (49)
for i = m.

Finally, we substitute Eq. ( 46) into Eq. ( 38) in order to come up with an optimization problem that contains only inequality constraints, namely,

-p 2 max ≡ minimize f 0 ≡ -δ u T F 0 δ u, ( 50
) over δ u, subject to f i, j,k (δ u) ≡ δ u T F i, j,k δ u -1 ≤ 0, k = 1, . . . , 4, j = 1, . . . , n i , i = 1, . . . , m,
where

F 0 ≡ ∑ l=4,5,6 e ν,l e T ν,l , (51)
F i, j,1 ≡ (1/δ β 2 XY,i, j )ϒ T i e 6n i ,6 j-5 e T 6n i ,6 j-5

+e 6n i ,6 j-4 e T 6n i ,6 j-4 ϒ i , (52)
F i, j,2 ≡ (1/δ β 2 Z,i, j )ϒ T i e 6n i ,6 j-3 e T 6n i ,6 j-3 ϒ i , (53)
F i, j,3 ≡ (1/δ b 2 XY,i, j )ϒ T i e 6n i ,6 j-2 e T 6n i ,6 j-2 +e 6n i ,6 j-1 e T 6n i ,6 j-1 ϒ i , (54)
F i, j,4 ≡ (1/δ b 2 Z,i, j )ϒ T i e 6n i ,6 j e T 6n i ,6 j ϒ i . (55)
In the scope of this paper, optimization problem (50) is solved with ModeFrontier software [START_REF] Esteco | modefrontier[END_REF] in order to find the maximum reference-point position error and the maximum orientation error of the moving-platform for given joint clearances and for any robot configuration. This optimization problem could be also solved by means of Interval Analysis [START_REF] Berger | Finding the maximal pose error in robotic mechanical systems using constraint programming[END_REF] or with the algorithm proposed in [START_REF] Hoffman | A method for globally minimizing concave functions over convex sets[END_REF].

ILLUSTRATIVE EXAMPLES

The kinematic sensitivities of a 3R serial manipulator and a five-bar parallel manipulator to joint clearances are analyzed in this section in order to highlight the contributions of the paper. The lengths are expressed in meter, while the angles are given in radian in these examples.

3R Serial Manipulator

Figure 2 illustrates the 3R serial manipulator under study. It is composed of one leg, i.e., m = 1, that contains three revolute joints, i.e., n 1 = 3. The first and the second joints axes are orthogonal, while the second and the third ones are parallel. As a consequence, the Denavit-Hartenberg parameters of the manipulator take the form:

{α 1,1 , a 1,1 , b 1,1 , θ 1,1 } = -π/2, 0, 10, θ 1,1 (56) {α 1,2 , a 1,2 , b 1,2 , θ 1,2 } = 0, 5, 0, θ 1,2 (57) {α 1,3 , a 1,3 , b 1,3 , θ 1,3 } = 0, 5, 0, θ 1,3 (58)
θ 1, j , j = 1, . . . , 3 being the revolute joint angles. The er-

b 1,1 a 1,2 a 1,3 X 1,1 Y 1,1 Z 1,1 F 1,1 X 1,2 Y 1,2 Z 1,2 X 1,3 Y 1,3 Z 1,3 X p Y p Z p P 1 P FIGURE 2. 3R SERIAL MANIPULATOR
ror bounds characterizing the joint clearances and defined in Eqs.(32-35) are assumed to be: Figure 4 shows the isocontours of the maximum pointdisplacement p max throughout the manipulator workspace W s , which is defined with respect to ρ and p z , ρ ≡ p 2

x + p 2 y . p max is evaluated at each grid-point by means of optimization problem (50). It appears that p max varies between 0.2 and 0.54 throughout W s . Notice that the maximum orientation error on the endeffector is constant throughout W s and is equal to 0.043 rad.

Figures 5(a)-(b) show the trend in the maximum pointdisplacement p max of the end-effector as a function of the Zcoordinate of the end-effector in frame F 1,1 and ρ, respectively. From Fig. 5(a), p max is a minimum when p z is equal to 5.8. From Fig. 5(b), the higher ρ, the higher p max .

Five-bar Parallel Manipulator

Figure 6 illustrates the five-bar parallel manipulator under study. It is composed of two legs, i.e., m = 2, that contain two revolute joints, i.e., n 1 = n 2 = 2. All revolute joints axes are parallel. As a consequence, the Denavit-Hartenberg parameters of the manipulator take the form:

{α 1,1 , a 1,1 , b 1,1 , θ 1,1 } = 0, 5, 0, θ 1,1 (64) {α 1,2 , a 1,2 , b 1,2 , θ 1,2 } = 0, 10, 0, θ 1,2 (65) {α 2,1 , a 2,1 , b 2,1 , θ 2,1 } = 0, 5, 0, θ 2,1 (66) {α 2,2 , a 2,2 , b 2,2 , θ 2,2 } = 0, 10, 0, θ 2,2 (67)
θ i, j , i = 1, . . . , 2, j = 1, . . . , 2, is the angle of the jth revolute joint of the ith leg. The distance c between the axes of the revolute joints attached to the base is equal to 5. The error bounds characterizing the joint clearances and defined in Eqs.(32-35) are assumed to be:

∆β i, j,XY = 0.01 (68) ∆β i, j,Z = 0.01 (69) ∆b i, j,XY = 0.1 (70) ∆b i, j,Z = 0.1 (71)
Notice that the revolute joint connecting the two legs is supposed to be perfect, i.e., without any clearance. Figure 7 illustrates the workspace of the five-bar parallel manipulator under study and its regular workspace RW . The regular workspace of a manipulator is a regular-shaped part of its workspace. The regular workspace shape is up to the designer. It may be a cube, a parallelepiped, a cylinder or another regular shape [START_REF] Caro | Sensitivity analysis of 3-rpr planar parallel manipulators[END_REF]. A reasonable choice is a shape that "fits well" the one of the singular surfaces. It turns out that a rectangle suits well for the five-bar parallel manipulator. The regular workspace RW of the manipulator under study is obtained by means of a Tabu search Hooke and Jeeves algorithm [START_REF] Al-Sultan | A tabu search hooke and jeeves algorithm for unconstrained optimization[END_REF].

a 1,1 a 1,2 a 2,1 a 2,2 c X 1,1 Y 1,1 Z 1,1 X 2,1 Y 2,1 Z 2,1 X 2,2 Y 2,2 Z 2,2 X 1,2 Y 1,2 Z 1,2 Z 1,p , Z 2,p X 1,p Y 1,p X 2,p Y 2,p P FIGURE 6. FIVE-BAR PARALLEL MANIPULATOR a 1,1 a 1,2 a 2,1
Figure 8 shows the isocontours of the maximum pointdisplacement, p max , of point P throughout RW . Likewise, Fig. 9 shows the isocontours of the maximum orientation error, r max , of the moving-platform throughout RW . Notice that p max and r max are evaluated at each grid-point of RW by means of optimization problem (50 11 shows the isocontours of the maximum point-displacement, p max , of its end-effector P throughout RW . It appears that p max varies between 3.58 × 10 -1 and 5.19 × 10 -1 . Moreover, the maximum orientation error of its moving-platform is constant throughout RW and is equal 2.28 × 10 -2 rad.

It is noteworthy the maximum orientation error of the endeffector of any serial manipulator due to joint clearances is constant throughout its workspace. As a result, the maximum point-displacement of the movingplatform of the serial manipulator is about five times larger than the one of its parallel counterpart. Similarly, the maximum orientation error of the moving-platform of the serial manipulator is about fifty times larger than the one of the parallel manipulator. As a matter fact, the parallel manipulator turns to be quite more accurate than its serial counterpart as the revolute joint that connects the legs is assumed to be perfect and the link lengths are relatively large in comparison with joint clearances.

CONCLUSIONS

The paper dealt with the kinematic sensitivity of robotic manipulators to joint clearances. First, an error prediction model applicable to both serial and parallel manipulators was developed. A clearance model associated with axisymmetrical joints, which are widely used in robotic manipulators, was also proposed. Then, two nonconvex quadratically constrained quadratic programs (QCQPs) were formulated in order to find the maximum reference-point position error and the maximum orientation error of the moving-platform for given joint clearances. Finally, the contributions of the paper were highlighted by means of serial and parallel manipulators. It turns out that 2R serial manipulators are more sensitive to joint clearances than five-bar parallel manipulators. This result makes sense as joint clearances are compensated in parallel manipulators.

∆β 1 ,Figure 3 6 T

 136 Figure3shows the end-effector reference-point position error due to the joint clearances, the nominal Cartesian coordinates of the end-effector P in base frame F 1,1 being equal to

FIGURE 3 .

 3 FIGURE 3. THE RANGE OF END-EFFECTOR REFERENCE-POINT POSITION ERRORS IN FRAME P 1 FOR THE NOMINAL END-EFFECTOR POSITION DEFINED WITH EQ. (63)

FIGURE 4 .

 4 FIGURE 4. ISOCONTOURS OF p max THROUGHOUT W s

FIGURE 5 .

 5 FIGURE 5. THE MAXIMUM POINT-DISPLACEMENT p max OF THE END-EFFECTOR AS A FUNCTION OF: (a) p z ; (b) ρ

16 RWFIGURE 7 .

 167 FIGURE 7. THE WORKSPACE AND REGULAR WORKSPACE RW OF THE FIVE-BAR PARALLEL MANIPULATOR UNDER STUDY

FIGURE 11 .

 11 FIGURE 11. ISOCONTOURS OF p max THROUGHOUT RW

  ). It is apparent that p max varies between ISOCONTOURS OF r max THROUGHOUT RW 7.15 × 10 -2 and 9.12 × 10 -2 , while r max varies 3.49 × 10 -4 rad and 4.41 × 10 -4 rad throughout RW . FIGURE 10. 2R SERIAL MANIPULATOR Figure 10 depicts one leg of the five-bar parallel manipulator under study, namely, a 2R serial manipulator.Figure

	×10 -2
	9.1 10.1		8.13		7.82	8.45	8.76 9.07
	p y	6.1 7.1 8.1				7.22 7.52
	-8 5.1	-6	-4	-2	0 p x	2	4	6	8
		FIGURE 8. ISOCONTOURS OF p max THROUGHOUT RW
	×10 -4
	9.1 10.1	4.06 3.83		4.18	4.30		3.94 3.71
	-8 -6 -4 5.1 6.1 7.1 8.1 3.83 4.30 p y	-2 3.71 4.06	0 p x 4.18	2 3.58 3.94	4	6	8
		FIGURE 9. a 1,1 Z 1,1		Z 1,2
							Y 1,1			X 1,2
				X 1,1				Y 1,2		a 1,2
										Z 1,p
										Y 1,p
									P
									X 1,p

In this paper, the end effector of a serial manipulator is referred to as its moving platform.


domain: info math math.math-lo

text:
Luca Amarù

Eleonora Testa

Miguel Couceiro

Odysseas Zografos

Giovanni De Micheli

Mathias Soeken

Majority logic synthesis

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

The majority function [START_REF] Wigington | A new concept in computing[END_REF] of three Boolean variables x, y, and z, denoted xyz , evaluates to true if and only if at least two of the three variables are true. The majority function is self-dual [START_REF] Knuth | The Art of Computer Programming[END_REF] and can be expressed in disjunctive and conjunctive normal form as xyz = xy ∨ xz ∨ yz = (x ∨ y)(x ∨ z)(y ∨ z).

(

) 1
Setting any variable to 0 gives the conjunction of the other two variables, and analogously one obtains the disjunction by setting any variable to 1, i.e., 0xy = x ∧ y and 1xy = x ∨ y.

The majority function can be generalized to n variables

x 1 x 2 . . . x n = x 1 + x 2 + • • • + x n > n-1 2 , ( 3
)
where n is odd as a special case of the threshold function [START_REF] Elgot | Truth functions realizable by single threshold organs[END_REF], [START_REF] Winder | More about threshold logic[END_REF]. The function evaluates to true if at least n 2 variables are true. We refer to a majority expression as a multi-level expression that consists of majority functions with different number of inputs (fan-in), Boolean variables, and constants. If all majority functions in a majority expression have n inputs, we call the expression a majority-n expression.

Majority expressions can be represented as a graph, in which nodes represent constants, variables, and majority operations and edges connect operations to their arguments. Edges can be regular or complemented depending on whether the respective argument is complemented or not. We call such graphs Majority-Inverter Graphs (MIGs, [START_REF] Amarù | Majority-inverter graph: A novel data-structure and algorithms for efficient logic optimization[END_REF]) following the a c in b c out s Fig. 1. MIG of a full adder nomenclature of And-Inverter Graphs (AIGs, [START_REF] Hellerman | A catalog of three-variable Or-invert and Andinvert logical circuits[END_REF], [START_REF] Kuehlmann | Robust Boolean reasoning for equivalence checking and functional property verification[END_REF]). Fig. 1 shows the MIG of a full adder with s = a ābc in abc in = a ⊕ b ⊕ c in and c out = abc in . [START_REF] Winder | More about threshold logic[END_REF] Note that the expression of the carry-out c out is shared in the expression for the sum s. In the MIG, input nodes are drawn as rectangles, majority operations as circles, regular edges as solid strokes, and complemented edges as dashed strokes.

The explicit consideration of the majority function in Boolean equations has first been suggested by Lindaman [START_REF] Lindaman | A theorem for deriving majority-logic networks within an augmented Boolean algebra[END_REF]. He proposes an algebraic expansion to translate expressions for n-variable Boolean functions of the form

x n-1 i=1 f i ∨ x 2(n-1) i=n f i (5)
into majority-3 expressions. In [START_REF] Amarù | Majority-inverter graph: A novel data-structure and algorithms for efficient logic optimization[END_REF], the f i are Boolean functions that do not depend on x. It is exemplarily shown in [START_REF] Lindaman | A theorem for deriving majority-logic networks within an augmented Boolean algebra[END_REF] that this expansion can lead to much smaller expressions when compared to directly replacing AND and OR gates using the equations given in [START_REF] Knuth | The Art of Computer Programming[END_REF]. Miiller and Winder [START_REF] Miller | Majority-logic synthesis by geometric methods[END_REF] presented a synthesis algorithm based on Karnaugh-Veigh diagrams similar to the algorithms used to derive sum-of-product expressions. To synthesize a function f , the algorithm first tries to express f as f 1 f 2 f 3 by heuristically selecting a majority operation to express f 1 that minimizes |f ⊕ f 1 |, i.e., it agrees closest with the function values of f . This choice implies constraints on function values of f 2 and f 3 , on which the algorithm recurs. The algorithm may backtrack if subexpressions result which cannot be realized by a majority function. The algorithm already becomes cumbersome for moderate n but offers a convenient pen-and-paper approach for small functions (see also [START_REF] Horna | A geometric synthesis method of three-input majority logic networks[END_REF]).

Akers [START_REF] Akers | Synthesis of combinational logic using threeinput majority gates[END_REF] presented an embedding of incompletely specified Boolean functions, represented as truth tables, into monotone self-dual functions [START_REF]A truth table method for the synthesis of combinational logic[END_REF], [START_REF] De | Minimal sets of distinct literals for a logically passive function[END_REF]. These functions can then be reduced into what he calls a reduced unitized table. This is used as a starting point to derive various different majority expressions: i) canonical majority expressions, ii) canonical majority-3 expressions, and iii) possibly small (but not guaranteed optimal) majority-3 expressions.

A lot of synthesis algorithms for majority expressions have been presented in the field of quantum-dot cellular automata (QCA, [START_REF] Tougaw | Logical devices implemented using quantum cellular automata[END_REF], [START_REF] Amlani | Digital logic gate using quantum-dot cellular automata[END_REF]). The basic blocks in QCA are the identity, negation, and majority-3, and therefore QCA circuits inherently realize majority-3 expressions [START_REF] Snider | Quantum-dot cellular automata: line and majority logic gate[END_REF]. Initial research [START_REF] Zhang | A method for majority logic reduction for quantum cellular automata[END_REF], [START_REF] Walus | Circuit design based on majority gates for applications with quantum-dot cellular automata[END_REF], [START_REF] Rai | Majority gate based design for combinational quantum cellular automata (QCA) circuits[END_REF] targeted the realization of 3-variable functions as majority-3 expressions based on the methods from Miiller and Winder [START_REF] Miller | Majority-logic synthesis by geometric methods[END_REF] and Akers [START_REF] Akers | Synthesis of combinational logic using threeinput majority gates[END_REF]. Several groups [START_REF] Zhang | Synthesis of majority and minority networks and its application to QCA, TPL and SET based nanotechnologies[END_REF], [START_REF] Huo | Logic optimization for majority gate-based nanoelectronic circuits[END_REF], [START_REF] Zhang | Majority and minority network synthesis with application to QCA-, SET-, and TPL-Based nanotechnologies[END_REF] have then extended this method to synthesize multilevel multi-output Boolean functions. Their techniques start from a minimized algebraically factored circuit [START_REF] Micheli | Synthesis and Optimization of Digital Circuits[END_REF]. The circuit is then decomposed into nodes that have at most three inputs; if a node represents the majority function it is directly mapped, otherwise the previous mentioned techniques are used to find a good majority-3 expression. The various algorithms differ mainly in how the initial circuit is preprocessed and decomposed and in how nodes are translated into majority expressions. The algorithms have been further extended [START_REF] Vemry | Majority logic gate synthesis approaches for post-cmos logic circuits: A review[END_REF] to consider technology-aware cost metrics [START_REF] Kong | An optimized majority logic synthesis methodology for quantum-dot cellular automata[END_REF], [START_REF] Martins | Majority-based logic synthesis for nanometric technologies[END_REF] or to consider four inputs in the decomposed nodes [START_REF] Wang | Synthesis of majority/minority logic networks[END_REF] and have been optimized using genetic algorithms [START_REF] Bonyadi | Logic optimization for majority gate-based nanoelectronic circuits based on genetic algorithm[END_REF], [START_REF] Tehrani | Multi-output majority gatebased design optimization by using evolutionary algorithm[END_REF].

In this tutorial we review the state-of-the-art in several topics of majority logic synthesis. The next section discusses how practical algorithms can be implemented for optimizing majority-inverter graphs based on majority-3 gates. Section III reviews the theory of decomposing majority-n gates into smaller ones and illustrates a practical algorithm based on binary decision diagrams. Section IV discusses the effect of the majority operation in normal forms to express Boolean functions. Finally, Section V concludes with showing applications in nanoemerging technologies using devices that operate based on the majority function.

II. PRACTICAL MAJORITY LOGIC SYNTHESIS

MIGs are a logic representation form based on majority and inverter operators [START_REF] Amarù | Majority-inverter graph: A novel data-structure and algorithms for efficient logic optimization[END_REF]. An MIG is a logic network consisting of 3-input majority nodes and regular/complemented edges. MIGs can emulate traditional And Or Inverter Graphs (AOIGs) by fixing to 0 (AND) or to 1 (OR) one input of the majority nodes. To natively operate on MIGs, a set of bidirectional transformations, named Ω, is introduced in [START_REF] Amarù | Majority-inverter graph: A novel data-structure and algorithms for efficient logic optimization[END_REF] and reported hereafter.

By using Ω, it is possible to optimize an MIG with respect to a desired metric. For example, majority Ω.M enables size and depth reduction when applied from left to right. Also, distributivity Ω.D enables depth reduction when applied from left to right and z is a critical variable. On the other hand, distributivity Ω.D applied from right to left enables size reduction. In a similar fashion, the remaining transformations in Ω are also useful in MIG optimization.

Several other complex rules are derivable from Ω. Among the ones we encountered, three rules derived from Ω are of particular interest to logic optimization. We refer to them as Ψ and are described hereafter. In the following, the symbol f x/y represents a replacement operation, i.e., it replaces x with y in all its appearence in f .

Ψ.R : Relevence xyz = xyz x/ȳ Ψ.C : Compl. assoc. xy y ūz = xu yxz Ψ.S : Substitution xyz = v v xyz v/u u v xyz v/ū ū , (7)
The first rule, relevance Ψ.R, replaces reconvergent variables with their neighbors. For example, consider the function f = xy wz xyz . Variables x and y are reconvergent because they appear in both the bottom and the top majority operators. In this case, relevance Ψ.R replaces x with ȳ in the bottom majority as f = xy wz ȳyz . This representation can be further reduced to f = xyw by using Ω.M.

The second rule, complementary associativity Ψ.C, deals with variables appearing in both polarities. Its rule of replacement is xu yūz = xu yxz as depicted by [START_REF] Kuehlmann | Robust Boolean reasoning for equivalence checking and functional property verification[END_REF].

The third rule, substitution Ψ.S, extends variable replacement to the non-reconvergent case. We refer the reader to Fig. 3 for an example about substitution Ψ.S applied to a 3-input parity function.

In an automated MIG optimization tool, Ω and Ψ transformations are iterated in sequence, with a sense (left-to-right or right-to-left) acting in accordance to the chosen target metric. We refer the reader to [START_REF] Amarù | Majority-inverter graph: A novel data-structure and algorithms for efficient logic optimization[END_REF] for more details on the use of Ω and Ψ in MIG optimization.

Fig. 3 shows how examples from Fig. 2 can be optimized using Ω and Ψ rules.

III. DECOMPOSING MAJORITY FUNCTIONS

In this part of the tutorial, we explore the functional decomposition of majority-n networks, which permits the use of majority primitives with n inputs (where n is odd). We particularly focus on the decomposition into majority-3 as this is the main building block of several emerging nanotechnologies. After reviewing the decomposition methods from the classic literature, we discuss a more recent techniques that exploit binary decision diagrams. We conclude with the challenge of finding minimum-size decompositions.

A. State-of-the-art

The problem of expressing majority-n using majority-ofthree has already been studied in the 1960s. In [START_REF] Amarel | Majority gate networks[END_REF], Amarel et al. investigated "how best can the 5-argument majority function be realized with a network of 3-input majority gates? ". The focus was on finding the minimum number of 3-input majorities to build majority-5, but larger n were also considered [START_REF] Amarel | Majority gate networks[END_REF]. In the remainder, we will refer to the minimum number of majority-of-three to build a majority-n as M (n). It is surprising that, as of today, M (n) is known only for 5-and 7input majorities, while the minimum realization of majority-9 (and larger n) in terms of majority-3 is still under investigation.

Other works have focused on M (n), but they have only considered its asymptotic bounds [START_REF] Kulikov | Computing majority by constant depth majority circuits with low fan-in gates[END_REF]. A quasi-linear construction follows from sorter networks [START_REF] Knuth | The Art of Computer Programming[END_REF]. We simply sort the n bits and pick the one that ends up in the middle position. Sorter networks consist of comparators, and each comparator can be composed with 2 majority-3 operations. Let S(n) be the optimum number of comparators in a sorter network that sorts n elements. Then an upper bound on the number of majority-3 operations is u S (n) ≤ 2S(n).

Dor and Zwick showed that less than 2.942n comparisons are necessary to select the median value from a set of n numbers, without the need to sort them [START_REF] Dor | Selecting the median[END_REF]. Applying it directly, it would lead to an upper bound of 5.884n majority-3 operations to decompose majority-n. However, this number needs to be treated more carefully, since their analysis is based on the comparison model in which only the number of comparators are counted and all other operations are considered free.

When applying the discussed constructions to small values for n, the resulting majority graphs are still very large. For example, the majority-7 function can be constructed using 42 majority-3 operations according to median selection construction, while it is known that M (7) = 7. Even if sorter networks provide an alternative construction that provides a quasi-linear bound [START_REF] Codish | Twentyfive comparators is optimal when sorting nine inputs (and twenty-nine for ten)[END_REF], for small n the construction can yield better results compared to median selection. To follow up with the previous example, the majority-7 function can be constructed using 32 majority-3 operations based on the sorter network construction.

In this tutorial, we discuss an alternative construction based on Binary Decision Diagrams (BDDs, [START_REF] Bryant | Graph-based algorithms for Boolean function manipulation[END_REF]) as first presented in [START_REF] Testa | Mapping monotone Boolean functions into majority[END_REF]. We show that for monotone Boolean functions the Shannon decomposition, which is used in the construction of BDDs, can be expressed using the majority function.

B. Transforming BDDs into Majority Graphs

Binary Decision Diagrams (BDDs, [START_REF] Bryant | Graph-based algorithms for Boolean function manipulation[END_REF]) are connected directed acyclic graphs, in which each node represents a Boolean function. Two terminal nodes labeled '⊥' and ' ' represent the constant functions 0 and 1, and all nonterminal nodes are labeled 'i' for some 1 ≤ i ≤ n and connect their two successor nodes f xi and f xi using Shannon's decomposition:

f = x i ? f xi : f xi = x i f xi ⊕ xi f xi (8)
Here, the cofactors f xi and f xi are the functions that are obtained by replacing x i with 1 and 0 in f , respectively. Each BDD has one node without parents representing the function, called the root. One can express any Boolean function f : B n → B in terms of its cofactors using [START_REF] Lindaman | A theorem for deriving majority-logic networks within an augmented Boolean algebra[END_REF]. If f is monotone, i.e., f xi fxi = 0 for all i, it is possible to use the majority function for decomposition [START_REF]A truth table method for the synthesis of combinational logic[END_REF]:

f = x i f xi f xi = x i f xi ⊕ x i f xi ⊕ f xi f xi (9)
The two cofactors f xi and f xi commute in ( 9), but they do not in [START_REF] Lindaman | A theorem for deriving majority-logic networks within an augmented Boolean algebra[END_REF]. Plus, the cofactor operation preserves monotonicity in [START_REF] Lindaman | A theorem for deriving majority-logic networks within an augmented Boolean algebra[END_REF]. Thus, (9) can iteratively be applied to the whole BDD.

The main idea presentd in [START_REF] Testa | Mapping monotone Boolean functions into majority[END_REF] is that, due to these properties,

f = x i ? f xi : f xi = x i f xi f xi ( 10
)
one can replace each "Shannon node" by a "majority node" in the BDD of monotone functions. The replacement allows us to generate majority graphs for monotone functions (c) optimum result Fig. 5. Majority-3 from its optimal BDD f (x 1 , . . . , x n ) directly from their BDDs using the discussed transformation rule.

Example 1: We show how to apply the transformation to the BDD in Fig. 4. By just translating every BDD node into a MAJ node as in [START_REF] Horna | A geometric synthesis method of three-input majority logic networks[END_REF], one obtains the majority graph depicted in Fig. 4(b) directly from its BDD (Fig. 4(a)).

C. Minimum-size Decomposition and Upper Bounds

The proposed approach can be used to map the majority-n function into MIGs with majority-3 operations. For example, for the majority-3 function x 1 x 2 x 3 , the BDD and its corresponding majority graph are shown in Fig. 5(a) and (b), respectively. Note that the majority expression that Fig. 5(b) represents is x 1 x 2 0x 3 x 2 1x 3 , which is of course far from optimal. The distributivity rule applies to this expression, giving x 1 01 x 2 x 3 = x 1 x 2 x 3 ; its diagrammatic notation is shown in Fig 5(c). This example was rather trivial. The same approach is applied in [START_REF] Testa | Mapping monotone Boolean functions into majority[END_REF] to rewrite majority-5 and majority-7 into their optimum MIGs using the identities presented in [START_REF] Amarù | Majority-inverter graph: A new paradigm for logic optimization[END_REF], [START_REF] Testa | Mapping monotone Boolean functions into majority[END_REF]. The majority-5 optimization is described in Fig. 6; all the details can be found in [START_REF] Testa | Mapping monotone Boolean functions into majority[END_REF].

The proposed synthesis method from a BDD suggests an upper bound u B (n) for the majority-n function. The majorityn function x 1 . . . x n can be realized using a majority graph with at most u B (n) ≤ n 2 2 -1 majority operations. Both the construction on sorter networks and median selection have asymptotically better upper bounds compared to the quadradic bound from the BDD construction. However, when actually calculating the numbers for small instances with n ≤ 17, the [START_REF] Dor | Selecting the median[END_REF], but do not take other operations into account.

BDD approach yields the smallest values (see Table I, which also shows the known optimum results up to n = 7 that were confirmed using exhaustive enumeration [START_REF] Soeken | Exact synthesis of majority-inverter graphs and its applications[END_REF]). The approach is therefore a good starting point for finding compact majorityn realizations for small n. The results obtained using BDD + optimization rules are listed in Table I as "Optimized BDD". The method in [START_REF] Testa | Mapping monotone Boolean functions into majority[END_REF] is able to obtain (i) the optimum known results for majority-5 and majority-7, and (ii) the best result for majority-9. One may be able to derive a general derivation procedure to obtain optimum or close to optimum majority-n realizations for n ≥ 9.

IV. EFFICIENT NORMAL FORM SYSTEMS

We focus on the efficient representation of Boolean functions. We consider Normal Form Systems (NFSs) as our representation of choice. These induce sets of terms that have a certain form: i.e., certain connectives occur before others. See, e.g., the Disjunctive Normal Form (DNF), Conjunctive Normal Form (CNF), or median NFS (MNF) that has as nontrivial connective the median, that is the ternary generator of the clone SM of self-dual monotone Boolean functions. It was proven in [START_REF] Couceiro | Composition of Post classes and normal forms of Boolean functions[END_REF] that the median normal form system is polynomially more efficient than the DNF, CNF, polynomial and dual polynomial normal form systems, associated with the generators of the clones Λ of all conjunctions, the clone V of all disjunctions, and the clone L of all linear functions (∧, ∨, and ⊕, respectively). However, these results were obtained for certain generators of these clones. A natural question to ask is whether these results still hold for arbitrary generators.

It is known that clones are finitely generated; however, and as it is the case for the clone SM of monotone self-dual functions, several generators (or sets of generators) may exist.

For instance, SM is generated by the 5-ary median (and, in fact, by any 2n + 1-ary median). Are the NFSs associated with the ternary majority and the 5-ary majority equivalently efficient? In fact, it can be shown that they are. Remark, for instance, that

xyz = xyz01 , xyztu = xyz t xyu uz .
Both equalities allow the efficient conversion from terms involving majority-5 into terms involving majority-3, and reciprocally. Furthermore, in general, it can be shown that the choice of generator for SM does not impact the efficiency of the NFS associated with it. These results motivate the study of other efficient NFS, that is, NFS that are equivalent to the median normal form systems. These include, for instance, the Sheffer NF that is generated by the Sheffer function x ↑ y ≡ ¬(x∧y), one of the two generators of minimal arity of the clone Ω of all Boolean functions, the other being Peirce's arrow, x ↓ y ≡ ¬(x ∨ y) (see, e.g., [START_REF] Żyliński | Some remarks concerning the theory of deduction[END_REF]).

In [START_REF] Couceiro | Comparing the efficiency of normal form systems to represent Boolean functions[END_REF] such efficient NFSs were studied and were proven to be equivalent for generators of minimal arity. A natural question to ask, just as for the MNF, is whether these results still hold for arbitrary generators. In fact, it can be shown that any generator of Ω yields an efficient NFS, and similarly for other clones associated with non-associative connectives. Furthermore, the choice of generator for the clones associated with non-efficient NFSs, namely, the clones of disjunctions, conjunctions, and linear functions, does not impact the efficiency results.

V. EMERGING NON-CHARGE-BASED MAJORITY LOGIC TECHNOLOGIES

In this section we describe QCA and STMG. Both technologies use the 3-input majority gate as their main building block. QCA technology is based on the interaction of QCA cells: each cell consists of four quantum dots and two free electrons. The free electrons can tunnel between the dots, which are coupled by tunnel barriers. Coulomb repulsion forces the electrons in opposite corners of the cell, thus producing two energetically equivalent polarizations, i.e., P = 1 and P = -1. The two polarizations represent the logic values 1 and 0, respectively. QCA technology is functionally complete, and the fundamental logic element of QCA is the three-inputs majority gate [START_REF] Tougaw | Logical devices implemented using quantum cellular automata[END_REF]. Figs. 7a and7b show the layout of a QCA majority gate and inverter, respectively. For the majority gate the polarization of the central logic cell, called device cell, is the majority of the three inputs; the output cell follows the polarization of the device cell. In the inverter case, the input wire is first branched in two offset wires; both will have the same polarization as the input due to aligning effects. Antialigning effects at the second joint control the polarization of the next cell, causing an inversion of the input signal.

STMG is a three-input majority gate that can ensure small area, low power, non-volatility, reconfigurability, and radiation hardness [START_REF] Nikonov | Proposal of a spin torque majority gate logic[END_REF]. STMG is driven by spin transfer torque (STT, [START_REF] Berger | Emission of spin waves by a magnetic multilayer traversed by a current[END_REF]); its schematic is shown in Fig. 8. Four magnetic tunnel junctions (MTJ) share one cross-shaped free layer. Three MTJs (yellow) write the input states via STT, while the forth MTJ (orange) reads the output state via tunnel magnetoresistance. The magnetic domains are mainly driven by domain wall automotion [START_REF] Nikonov | Automotion of domain walls for spintronic interconnects[END_REF], and the magnetization orientation (up/down) in the free layer carries the bit information (0 or 1). Despite of potential advantages as small area and low power, there is a lack of an efficient spin torque inverter (STI) concept which would be necessary to implement circuits. An STI implementation has been proposed in [START_REF] Nikonov | Nanomagnetic circuits with spin torque majority gates[END_REF], but it cannot be realized with the state-of-the-art technology for magnetic materials. In [START_REF] Testa | Inverter propagation and fanout constraints for beyond-CMOS majority-based technologies[END_REF], the lack of STI has been overcome by demonstrating inverter-free circuits, obtained using MIGs as intermediate data structure.

Fig. 2

 2 depicts two logic representation examples for MIGs. They are obtained by translating their And Or Inverter Graphs (AOIGs) representations into MIGs, using the aforementioned strategy.

Fig. 2 .

 2 Fig. 2. Examples of MIG representations (right) for (a) f = x ⊕ y ⊕ z and (b) g = x(y ∨ uv) derived by transposing their AOIG representations (left). Complement attributes are represented by bubbles on the edges.

Fig. 3 .

 3 Fig. 3. Examples of optimized MIG representations (right) for (a) f = x ⊕ y ⊕ z and (b) g = x(y ∨ uv).

Fig. 4 . 4

 44 Fig. 4. Diagrammatic notation of a BDD (a) and majority graph (b) for the function clique 4,3

Fig. 6 .

 6 Fig. 6. Decomposing majority-5 into majority-3

Fig. 7 .

 7 Fig. 7. (a) QCA layout for majority, (b) inverter

Fig. 8 .

 8 Fig.8. Schematic of STMG[START_REF] Nikonov | Proposal of a spin torque majority gate logic[END_REF]. The three MTJ inputs are visible in yellow, while the output is the orange block.

TABLE I

 I

	UPPER BOUNDS ON THE NUMBER OF MAJORITY-3 OPERATIONS TO
		REALIZE MAJORITY-n
	n	3 5 7 9 11 13 15 17
	Optimum (M (n))	1 4 7
	Optimized BDDs	1 4 7 15
	BDDs	3 8 15 24 35 48 63 80
	Sorter networks	6 18 32 50 70 90 112 142
	Median selection *	18 30 42 53 65 77 89 101

* These numbers are based on the number of comparators in the construction of

Acknowledgments: The authors like to thank Pierre-Emmanuel Gaillardon, Winston Haaswijk, Alan Mishchenko, and Heinz Riener, who conitributed to various works reviewed in this tutorial. This research was supported by the Swiss National Science Foundation (200021-169084 MAJesty) and by the European Research Council in the project H2020-ERC-2014-ADG 669354 CyberCare.


Ana Lucia

Cruz Ruiz

Stéphane Caro
email: stephane.caro@irccyn.ec-nantes.fr

Philippe Cardou
email: pcardou@gmc.ulaval.ca

François Guay
email: francois.guay.2@ulaval.ca

Franc ¸ois Guay

ARACHNIS: Analysis of Robots Actuated by Cables with Handy and Neat Interface Software

Keywords: workspace, wrench-feasible workspace, interference, graphical user interface, capacity margin, static equilibrium, cable-driven robot, wire-driven robot 1

come   L'archive ouverte pluridisciplinaire

Introduction

Cable-Driven Parallel Robots (CDPRs) may be seen as Gough-Stewart platforms in which the prismatic actuators are replaced with cables. Hence, the cables are connected between the moving platform and fixed eyelets. The platform moves around by increasing or decreasing the lengths of the different cables in concert while preventing any cable from becoming slack [START_REF] Roberts | On the inverse kinematics, statics, and fault tolerance of cable-suspended robots[END_REF]. This architecture allows for marked advantages over conventional robots, such as the possibility of a larger workspace and higher accelerations, thanks to lighter mechanical components. CPDRs also suffer from important drawbacks, however. First, there is the possibility of interferences among the cables or between a cable and the moving platform. Furthermore, the non-rigid nature of the CPDR links further restrict its workspace, and requires a rigorous study of its force transmission characteristics.

Nevertheless, CDPRs have been used, often with success, in many areas such as robotic cranes, cable-driven cameras, medicine, automatic painting and rescue operations, to name but a few. The reader is referred to a recent literature survey on the topic [START_REF] Gosselin | Cable-driven parallel mechanisms: State of the art and perspectives[END_REF] for a more thorough account of these applications. These CDPRs and others were developed independently, in most cases, meaning that their designers usually started the analysis and design process development "from scratch". As CDPRs become more popular, there is an obvious need to automate their design and analysis, to accelerate their development and to provide a common working ground to the engineers involved.

To partly answer this need, we propose the graphical user interface ARACHNIS, or Analysis of Robots Actuated by Cables with Handy and Neat Interface Software. In short, ARACHNIS is dedicated to the parameter-based analysis and design of CDPRs. It allows the designer to enter the design parameters of the robot, to specify the task that the robot should perform in terms of force and moment ranges, and to assess the performance of the robot through the visualization of its Wrench-Feasible Workspace (WFW) [START_REF] Bouchard | On the ability of a cable-driven robot to generate a prescribed set of wrenches[END_REF][START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF] and its Interference-Free Constant Orientation Workspace (IFCOW) [START_REF] Merlet | Analysis of the influence of wires interference on the workspace of wire robots[END_REF]. ARACHNIS seems to be similar in its functions to a previously developed interface named WireCenter [START_REF] Pott | Large-scale assembly of solar power plants with parallel cable robots[END_REF]. From the little information we could gather on WireCenter, it seems that the two interfaces differ mainly in that WireCenter allows to trace the wrench-closure workspace (WCW), while ARACH-NIS allows to trace the WFW.

This workspace was chosen to analyze the static-equilibrium of the robot because it applies to a wider range of tasks than the WCW [START_REF] Gouttefarde | Analysis of the wrench-closure workspace of planar parallel cable-driven mechanisms[END_REF] or the Static Workspace (SW) [START_REF] Stump | Workspaces of Cable-Actuated Parallel Manipulators[END_REF]. In fact, the WCW and the SW can be shown to be special cases of the WFW. To the knowledge of the author, two methods have been reported to trace the WFW of a spatial parallel robot driven by m cables. Both of these methods are purely numerical, since, as was pointed out in [START_REF] Bosscher | Wrench-feasible workspace generation for cabledriven robots[END_REF], computing symbolic expressions of the WFW-boundaries is too complex to be practical in the general case. This spurred other researchers to simply use a brute-force method [START_REF] Azizian | The dimensional synthesis of spatial cable-driven parallel mechanisms[END_REF] to trace the WFW as a cloud of points. Others resorted to interval arithmetics to trace the WFW as a set of boxes that are either completely inside the workspace or not completely outside of it [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF]. Both of these methods are relatively slow and generally yield poor renderings of the workspace boundary. In ARACHNIS, we resort to an alternative method that was recently proposed by the authors [START_REF] Guay | Measuring how well a structure supports varying external wrenches[END_REF], and which, if far from perfect, appears be somewhat faster and to yield smoother estimates of the WFW than the two existing ones. The IFCOW, on the other hand, is determined according to the method proposed in [START_REF] Perreault | Geometric determination of the interferencefree constant-orientation workspace of parallel cable-driven mechanisms[END_REF].

The paper is organized as follows: Section 2 describes the kinetostatic model of a cable-driven parallel mechanism. Section 3 introduces the capacity margin as a measure of the robustness of CDPR equilibrium. Section 4 explains how the capacity margin is used to trace the WFW. Section 5 presents the polygons of the IFCOW where interferences occur between the cables and the moving platform. Section 6 describes the ARACHNIS interface. A planar cable-driven parallel mechanism and a spatial cable-driven parallel mechanism are studied in Secs. 7 and 8, respectively. Finally, we present our conclusions and future work in Sec. 9.

Kinetostatic Model of a Cable-Driven Parallel Robot

Formally, a cable-driven parallel robot consists of a moving platform connected to a fixed base by a set of m cables acting in parallel. The winding and unwinding of these cables on fixed spools controls the platform motion in space.

To mathematically model this mechanism, let us attach frame P to the moving platform, and frame F to the fixed frame, as shown in Fig. 1. The origins of these frames are P and O, respectively. The platform pose may thus be represented by the vector p pointing from O to P, and by the rotation matrix Q rotating F onto P. 1 The kinetostatic model of a cable-driven parallel mechanism

c i F O P P R i A i p r i a i Q Fig.
The i th cable is modeled as a straight-line segment from the attachment point onto the moving platform, R i , to the attachment point onto the fixed frame, A i . The positions of these attachment points are respectively given by r i , expressed in frame P, and a i , expressed in frame F . The i th cable may thus be represented by the vector

c i ≡ a i -p -Qr i , (1)
and the corresponding cable length is

c i ≡ c i 2 , i = 1, . . . , m. (2)
Let us now assume that external forces are applied on the moving platform. These forces are equivalent to the resultant force-moment system w e ≡ [f T e (1/r)n T e ] T , the force f e ∈ R 3 being applied at P, the moment being n e ∈ R 3 , and r being a positive length used to render w e dimensionally homogeneous. Here, we define this length quite arbitrarily as

r 2 = (1/m) ∑ m i=1 r i 2 2 .
For the moving platform to remain in equilibrium, there must be a combination of cable tensions t ≡ [t 1 • • • t m ] T that balances the system of external forces. By the application of the Newton-Euler equations to the moving platform, we obtain

Wt + w e = 0 6 , (3)
where 0 6 is the six-dimensional null vector and W is the Jacobian matrix of the mechanism at this particular pose. This matrix may be computed as

W = c 1 /c 1 • • • c m /c m (Qr 1 ) × c 1 /(r c 1 ) • • • (Qr m ) × c m /(r c m ) . (4)
To this standard kinetostatic model of a cable-driven parallel robot, let us add limits to the involved forces and moments. Indeed, for a given application, we may safely assume that the designer of a cable-driven parallel mechanism can define a set of external force-moment systems w e that can be applied on the mobile platform. We further assume that this set is a box W e in R 6 . For reasons that will later become apparent, let us give the vertex representation of this box, namely,

W e = {w e ∈ R 6 : w e = n ∑ j=1 α j w e, j , n ∑ j=1 α j = 1, α j ≥ 0, j = 1, . . . , n}, (5)
where w e, j , j = 1, . . . , 64 are the vertices of W e . The cable tensions t i , i = 1, . . . , m, are also limited by the load capacities of the motors and by the strengths of the cables and spool transmission elements. From the components he/she selected, the designer should thus be able to assess the lower and upper tension bounds, respectively t and t. Formally, these define the m-dimensional box of feasible tensions

T = {t ∈ R m : t ≤ t ≤ t}. ( 6
)
3 The Capacity Margin as a Measure of the Robustness of Equilibrium

According to the model of a cable-driven parallel robot presented above, the moving platform is in equilibrium for every possible external force-moment system w e if and only if, in every case, the Newton-Euler equilibrium, eq. ( 3), can be satisfied by a set of feasible cable tensions t. Such a pose of "complete" equilibrium of the moving platform is often called a "feasible pose" in the scientific literature. The set of all feasible poses is called the "wrench-feasible workspace" (WFW), and is formally expressed in Definition 1.

Definition 1. The wrench-feasible wokspace F is defined as

F = {(p, Q) ∈ R 3 × SO(3) : ∀w e ∈ W e , ∃t ∈ T , Wt + w e = 0 6 }, (7)
where SO(3) is the group of proper rotation matrices, W e is defined in eq. ( 5), T is defined in eq. ( 6), and W is defined in eq. ( 4).

The capacity margin was recently introduced by the same authors in [START_REF] Guay | Measuring how well a structure supports varying external wrenches[END_REF] under the name minimum degree of constraint satisfaction. We believe that the name capacity margin describes better this index, if only for the sake of brevity, but for other reasons that will be made apparent from its definition.

This definition stems from the geometric interpretation of the wrench-feasible workspace, which is represented in Fig. 2. The two sets involved in the definition of F , W e and T , live in different spaces and have different numbers of dimensions. In this paper, we assume the number of dimensions of W e to be six, although the proposed method applies equally well to lower dimensional cases. The number of cables m corresponds to the number of dimensions of T . For the sake of illustration, the dimensions of W e and T in Fig. 2 were chosen to be two and three, respectively. The two sets are connected by eq. ( 3), by which the tensions, t, are linearly mapped onto the wrench space via the transformation -W. Hence, the box T of feasible tensions becomes the zonotope W t in the wrench space.

T W t W e -W w 1 w 2 γ t 1 t 2 t 3
Fig. 2 An analog geometric representation of the capacity margin γ

From the definition of the wrench-feasible workspace, this zonotope should include the set W e of external wrenches. Indeed, for an external wrench w e to be sustained by the moving platform, there must exist a set of tensions in T such that w e = -Wt. Geometrically, this means that the point w e should be contained in W t . Therefore, for any external wrench to be sustained, we should have

W e ⊆ W t , (8)
which gives us a necessary and sufficient condition for a pose (p, Q) to be wrenchfeasible. This binary condition does not tell us how far is a feasible pose from being unfeasible. Such a question is important to the designer, as an answer would indicate the robustness of the equilibrium. This is precisely what the capacity margin represents.

In Fig. 2, the capacity margin is geometrically represented by γ, the signed width of the margin between the boundary of W t and W e . This width is taken positive when the margin is inside W t , and negative when it is outside. It may thus be seen as the degree of inclusion of W e within W t .

Mathematically, we compute γ as follows:

1. Compute the facet representation of W t using the hyperplane shifting method [START_REF] Bouchard | On the ability of a cable-driven robot to generate a prescribed set of wrenches[END_REF].

We thus obtain a l and b l , l = 1, . . . , p in the equation W t = {w ∈ R 6 : a T l w ≤ b l , l = 1, . . . , p}. 2. Compute the coordinate γ j,l of each vertex w e, j of W e with each facet (a l , b l ) of W t . This coordinate is taken from the facet in its normal direction a l , which gives γ i, j = (b l -w T e, j a l )/ a l 2 , j = 1, . . . , n, l = 1, . . . , p. 3. Keep the minimum of all coordinates as a worst case scenario: γ = min j=1,...,n min l=1,...,p γ j,l .

Tracing the Wrench-Feasible Workspace Using the Capacity Margin

The capacity margin γ indicates the degree of inclusion of the set W e of external wrenches into the set W t of feasible wrenches. γ is a greater positive scalar as W e is further inside W t opposed to being a greater negative scalar as at least a part of W e is further outside W t . Consequently, γ is zero when W e ⊆ W t and a point of W e is on the boundary of W t . From definition 1, this latter case corresponds to a pose that is on the limit of feasibility. Hence, the boundary of the wrench-feasible workspace may simply be expressed as

γ(p, Q) = 0. (9)
In this paper, we use this fact to trace the boundary of the wrench-feasible workspace as the zero isosurface or isocontour of the capacity margin. To compute the zero isocontour of a function, one first needs to evaluate it at a grid of points covering its domain. The next step consists in interpolating the between adjacent points of the grid in search of roots of the function. This process is readily implemented in virtually all scientific computation packages. In Matlab, for instance, the functions isosurface and contour can be used to trace the isosurface and isocontour of a function, respectively. In Maple, the analogous functions are implicitplot3d and implicitplot.

Tracing the Interference Polygons

The wrench-feasible workspace alone is not sufficient to design a cable-driven parallel robot. Interferences between the moving parts must also be considered, either by shear intuition or by systematic analysis. A technique for such analysis of the interference-free workspace was proposed in [START_REF] Perreault | Geometric determination of the interferencefree constant-orientation workspace of parallel cable-driven mechanisms[END_REF], and was implemented in ARACH-NIS. Let us note, however, that the technique only applies to a constant orientation of the moving platform. Moreover, it is developed under the assumptions that the cables are line segments and that the moving platform is a convex polyhedron represented by its edges.

In [START_REF] Perreault | Geometric determination of the interferencefree constant-orientation workspace of parallel cable-driven mechanisms[END_REF], it was shown that the region of the Cartesian space where a pair of cables collide is composed of two disjoint polygons in space. Mathematically, the two polygons corresponding to an interference between the i th and j th cables may be expressed as

C i, j = {p ∈ R 3 : p = a j -Qr i + α(a j -a i ) + β Q(r j -r i ), α, β ≥ 0}, (10a)
C j,i = {p ∈ R 3 : p = a i -Qr j + α(a i -a j ) + β Q(r i -r j ), α, β ≥ 0}. ( 10b
)
Interferences can also occur between a cable and the moving platform. The associated interference regions are computed in [START_REF] Perreault | Geometric determination of the interferencefree constant-orientation workspace of parallel cable-driven mechanisms[END_REF]. This is done by tracing the interference region between the i th cable and the edge connecting the j th and k th vertices of the polyhedron-shaped moving-platform. Let the positions of these vertices be represented by v j and v k , respectively, in the mobile frame P. In this case, the interference region E i, j,k takes the form of a polygon in space, that is, [START_REF] Roberts | On the inverse kinematics, statics, and fault tolerance of cable-suspended robots[END_REF] Notice that the regions C i, j and E i, j,k are unbounded in some directions. In ARACHNIS, we assume that the portion of interest of the Cartesian workspace is a box containing all the fixed points A i , i = 1, . . . , m. In the proposed interface, we thus trace the intersections of this box with the interference regions C i, j , i, j = 1, . . . , m, and E i, j,k , i = 1, . . . , m, j, k = 1, . . . , q, where q is the number of vertices of the moving platform.

E i, j,k = {p ∈ R 3 : p = a i -Qr i + ν j Q(v j -b i ) + ν k Q(v k -b i ), ν j , ν k ≤ 0, ν j + ν k ≤ -1}.
6 The ARACHNIS Interface ARACHNIS, or "Analysis of Robots Actuated by Cables with Handy and Neat Interface Software", is a graphical user interface developed in MATLAB to automate the design and the analysis of CDPRs. At the conceptual design stage, this tool aids the designer in choosing the design that best meets two requirements: equilibrium throughout the workspace and interference avoidance.

The interface provides the degree to which these requirements are satisfied for a particular design through the generation of the WFW and the IFCOW. As shown in Fig. 3, it is divided into four main areas: Robot Parameters, Robot Posture, Robot Task and Robot Visualization. The section Robot Parameters is dedicated to the specification of the geometry of the platform and base, cable tension limits and cable arrangement. The geometry of the platform is described through the Cartesian coordinates of the cable anchor points Section specific help data Checkboxes for choosing plot type Fig. 3 ARACHNIS and its main features on the platform (rx, ry and rz) expressed in the platform frame and the geometry of the base is described through the Cartesian coordinates of the cable anchor points on the base (ax, ay and az) expressed in the base frame. The tension limits are specified via the minimum and maximum tensions allowed in each cable.

In the section Robot Posture, the poses required from the platform during a specific task are specified through positions and orientations with respect to the X, Y and Z axes (px, py, pz, phi, theta, psi). The angles phi, theta and psi are the Euler angles specifying the attitude of the platform frame with respect to the fixed frame according to the XY Z convention. Fixed positions and orientations are specified by single numbers, while parameters that vary are specified by intervals and resolutions. Each varying parameter is then assigned to a workspace axis through the pop-up menus.

By allowing any combination and assignation of parameters to the workspace axes, ARACHNIS is able to generate any WFW from two to six dimensions. The WFW above three dimensions cannot be traced in three-dimensional space, of course. In such cases, three of the axes are selected to trace the workspace. The poses contained in the WFW are then the poses for which the full range of poses in the remaining axes are wrench-feasible poses.

The section Robot Task consists in describing the prescribed robot task by specifying intervals of forces and moments along each dimension (Fx, Fy, Fz, Mx, My, Mz) . The forces are assumed to be applied at the origin of the moving-platform frame, but the components of the forces and moments are parallel to the axes of the fixed frame.

The section Robot Visualization consists of a graphical area to visualize the CDPR geometry, its WFW and its IFCOW. This information can be hidden or shown by first clicking the corresponding checkboxes and then clicking the plot button. This section also contains a data button, which generates an Excel spreadsheet containing the information on the interface and the simulation data, a cancel button to stop the workspace computation, and a progress bar to indicate the simulation progress. ARACHNIS also contains Help buttons and error messages customized for each section to guide the user as he or she inputs the parameters.

Case Study 1: A Planar Cable-Driven Parallel Mechanism

This case study demonstrates the capacity of ARACHNIS to generate the wrench feasible workspace (WFW) of planar cable-driven mechanisms. The mechanism under study is the eight-cable robot shown in Fig. 4, which has previously been analyzed in [START_REF] Verhoeven | Analysis of the workspace of tendon-based stewart platforms[END_REF]. As in [START_REF] Verhoeven | Analysis of the workspace of tendon-based stewart platforms[END_REF], the tension limits were set to 10 N and 1000 N and no external wrench was applied. The total orientation workspace in Fig. 4 was computed by displacing the robot in a 1.2 m × 1.2 m × 120 • grid using a resolution of 80 points per axis. The green iso-surface corresponding to γ = 0 represents the frontier of the WFW. Inside this boundary the robot can safely perform the task. We can acquire a more quantitative view of the stability of the robot by slicing the total orientation workspace and generating the constant orientation workspace shown in Fig. 4. Each contour in the figure represents a value of γ. Again, the contour where γ = 0 defines the stability frontier. The higher this value, the greater the robustness of the moving-platform equilibrium. Notice that these results match those obtained in [START_REF] Verhoeven | Analysis of the workspace of tendon-based stewart platforms[END_REF]. Other examples of the workspaces generated by ARACHNIS were done by the same authors in [START_REF] Guay | Measuring how well a structure supports varying external wrenches[END_REF], which match the workspaces in ref. [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF]. The computation time reported in [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF] was 51 s, while that obtained with ARACHNIS was 6 s. This time difference is significant, and cannot be attributed only to the different personal computers that were used in the two studies. Notice that all the simulations were done on a Dell Inspiron 15r laptop (Intel Core i7-3537U 2.50 GHz).

Case Study 2: A Spatial Cable-Driven Parallel Mechanism

This case study demonstrates the capacity of ARACHNIS to generate workspaces of spatial cable-driven mechanisms. The mechanism under study is the spatial robot with eight cables displayed in Fig. 5, which has also been previously analyzed in [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF]. The tension limits for all cables were set to 1 N and 540 N. The externally applied forces along each dimension varied from -10 N to 10 N, while the moments varied from -0.5 N m to 0.5 N m.

The 5D WFW workspace of this robot was generated by translating it along a 1 m×1 m×1 m grid. At each point on this grid, the robot was rotated around the X and Y axes through orientations ranging from -15 • to 15 • , while retaining a fixed orientation with respect to the Z-axis. The capacity margin was then evaluated at each of these poses. A set of values γ was thus obtained for every position on a 3D grid. The minimum value from each set was selected and assigned to its corresponding position on the grid. Finally, the values were interpolated, creating the boundary shown Fig. 5. As in the previous section, we computed the 2D slices of this higher dimensional workspace to assess quantitatively the performance of the robot. A slice along the XZ plane is also shown in Fig. 5. These results also match those obtained in [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF] by means of interval arithmetics. An argument often made in favor of interval arithmetics is the guarantee of exactness that comes with its results. In the example shown in [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF], however, the volume occupied by the uncertainty boxes-boxes that have not been determined to be fully inside or outside the WFW-amounts to 60 % of the total workspace volume. In these conditions, there is no guarantee on the boxes of interest, i.e., those that are close to the boundary of the WFW. Hence, for this example, interval arithmetics offers no more guarantee than any other method. This case study also evidences the computational efficiency of ARACHNIS. The workspace was computed in 225 s, outperforming the algorithm presented in [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF] whose computation time was 1567 s. The interference-free constant orientation workspace was also computed through 6 Interference-Free Constant Orientation Workspace (IFCOW) of a spatial robot the method described in Sec. 5 and is displayed in Fig. 6. The green polygons symbolize the interference regions between cables, while the blue ones represent the interference regions between a cable and a moving-platform edge. The results show that this robot has an interference free workspace within a box of 1 m × 1 m × 1 m.

Conclusions

In this paper, we presented a graphical user interface named ARACHNIS, or Analysis of Robots Actuated by Cables with Handy and Neat Interface Software. ARACHNIS allows the design and analysis of Cable Driven Parallel Robots (CD-PRs). It requires the designer to enter the parameters of the robot, to specify the loads involved in the robot task, and to assess the performance of the robot through the visualization of its Wrench Feasible Workspace (WFW) and its Interference-Free Constant Orientation Workspace (IFCOW). The capacity margin was first defined as a measure of the robustness of the moving-platform equilibrium and was used to trace the wrench-feasible workspace of the CDPRs. Interferences between the moving parts have also been considered. An existing technique for tracing the interference-free workspace of CDPRs was summarized and implemented in ARACHNIS. The WFW and the IFCOW of a planar cable-driven parallel mechanism and of a spatial cable-driven parallel mechanism have been plotted with ARACHNIS. It turns out that ARACHNIS is very competitive in terms of computation time for tracing the WFW and the IFCOW of CDPRs. The use of the proposed capacity margin to compute the wrench-closure workspace, the static workspace and the dynamic workspace of CDPRs and the conversion of ARACHNIS into a stand-alone interface are the subjects of future work.

Fig. 4

 4 Fig. 4 Wrench Feasible Workspace (WFW) of a planar robot

Fig. 5

 5 Fig. 5 Wrench Feasible Workspace (WFW) of a spatial robot

Fig.

  Fig. 6 Interference-Free Constant Orientation Workspace (IFCOW) of a spatial robot