{'fraction_non_alphanumeric': 0.025902695372096964, 'fraction_numerical': 0.007560603492117308, 'mean_word_length': 4.3473531544597535, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Interval Analysis Based Study for the Design and the Comparison of 3-DOF Parallel Kinematic Machines

This paper addresses an interval analysis based study that is applied to the design and the comparison of 3-DOF parallel kinematic machines. Two design criteria are used, (i) a regular workspace shape and, (ii) a kinetostatic performance index that needs to be as homogeneous as possible throughout the workspace. The interval analysis based method takes these two criteria into account: on the basis of prescribed kinetostatic performances, the workspace is analysed to find out the largest regular dextrous workspace enclosed in the Cartesian workspace. An algorithm describing this method is introduced. Two 3-DOF translational parallel mechanisms designed for machining applications are compared using this method. The first machine features three fixed linear joints which are mounted orthogonally and the second one features three linear joints which are mounted in parallel. In both cases, the mobile platform moves in the Cartesian x-y-z space with fixed orientation.

Parallel kinematic machines (PKM) are known for their high dynamic performances and low positioning errors.
The kinematic design of PKM has drawn the interest of several researchers. The workspace is usually considered as a relevant design criterion [1,2,3]. Parallel singularities [4] occur in the workspace where the moving platform cannot resist any effort. Thus are very undesirable and generally eliminated by design. The Jacobian matrix, which relates the joint rates to the output velocities is generally not constant and not isotropic. Consequently, the performances (e.g. maximum speeds, forces, accuracy and stiffness) vary considerably for different points in the Cartesian workspace and for different directions at one given point. This is a serious drawback for machining applications [5,6,7]. Few parallel mechanisms are isotropic throughout the workspace [8,9]. But their low structural stiffness make them inadequate for machining applications because their legs are subject to bending.
To be of interest for machining applications, a PKM should preserve good workspace properties, that is, regular workspace shape and acceptable kinetostatic performances throughout. For example in milling applications, the machining conditions must remain constant along the whole tool path [10,11]. In many research papers, this criterion is not taken into account in the algorithmic methods used to compute the workspace volume [12,13]. Other papers present methods that compute the well-conditioned workspace using discretization [14,15]. Thus, the results they provide cannot be proved formally. Conversely, interval analysis methods applied to well-conditioned workspace computation provide guaranteed results [16,17].
The comparison of PKM architectures is a difficult but relevant challenge [7,18]. Providing tools to allow designers or end-users to rigorously compare PKM is indeed necessary since the variety of existing PKM makes it hard to choose which one is best-suited for a specific task.
In this paper, an interval analysis based method is addressed for the design and comparison of 3-DOF PKM. This method takes into account two criteria, (i) a regular workspace shape and, (ii) a kinetostatic performance index that needs to be as homogeneous as possible throughout the workspace. Two basic tools and an algorithm that considers these two criteria are introduced: on the basis of prescribed kinetostatic performances, the workspace is analyzed to find out the largest regular dextrous workspace (square, cube, cylinder, etc...) enclosed in the Cartesian workspace.
Two translational parallel mechanisms derived from the Delta robot [2] are compared using this method.
The first machine, called Orthoglide [19], features three fixed linear joints which are mounted orthogonally and the second one, called UraneSX (Renault Automation) [20], features three linear joints which are mounted in parallel. In both cases, the mobile platform moves in the Cartesian x − y − z space with fixed orientation.
Next section presents the interval analysis based method for 3-DOF PKM design. Section 3 presents the Orthoglide and UraneSX mechanisms, their kinematic equations and singularity analysis. Section 4 reports the comparison between the two mechanisms through the determination of the largest dextrous cube for the Orthoglide and the largest dextrous square for the UraneSX enclosed in the workspace. For a 3-axis serial machine-tool, a parallelepiped-shaped Cartesian workspace allows the end-user to visualize easily where to place cutting paths. This consideration should also hold for PKM. However the workspace shape is often geometrically complex and thus hard to visualize. Therefore, a regular-shaped workspace is needed for PKM. Thus, we need to define a regular dextrous workspace which is a regular-shaped workspace included in the machine Cartesian workspace. Throughout the dextrous workspace, a kinetostatic performance index (that is chosen beforehand) remains as homogeneous as possible. This index can be the local or global conditioning [3] of the Jacobian matrix J (that maps the actuated joint rates of the manipulator into the velocity of the mobile platform), the force or velocity transmission factors. These last two indices make sense for 3-DOF translational PKM with identical actuated joints.
The method presented in this paper aims at designing such 3-DOF PKM. The velocity transmission factors are the ratio between the actuated joints velocities and the velocity of the mobile platform. They are the square roots ψ 1 , ψ 2 and ψ 3 of the real eigenvalues σ 1 , σ 2 and σ 3 of (JJ T ) −1 . In order to keep homogeneous kinetostatic properties, these factors are bounded inside the dextrous workspace. The regular dextrous Cartesian workspace can be defined as a set of points P in the workspace such that ψ 1 , ψ 2 and ψ 3 are bounded, that is, Points P in W Dextrous are called dextrous points.
The values of ψ min and ψ max (resp. σ min and σ max ) depend on given performance requirements. The method described further aims at computing the largest dextrous Cartesian workspace included in the Cartesian workspace, so that its ratio to the Cartesian workspace is the best one. To be of real interest for milling applications, a PKM must indeed include a large regular dextrous workspace in its Cartesian workspace.

Introduction to ALIAS library
An algorithm for the definition of the largest dextrous workspace included in the Cartesian workspace is described in the following sections. This algorithm uses the ALIAS library [16], which is a C++ library of algorithms based on interval analysis. These algorithms deal with systems of equations and inequalities whose expressions are an arbitrary combination of the most classical mathematical functions (algebraic terms, sine, cosine, log etc..) and whose coefficients are real numbers or, in some cases, intervals. An interface exists with Maple that allows the automatic generation of C++ codes being given the Maple description of the system and then to compile and run the generated code in order to get the result within the Maple session. Without being exhaustive, ALIAS library provides algorithms that enable one to, (i) find an approximation of the real roots of n-dimensional systems, (ii) find an approximation of the variety defined by n-dimensional systems, (iii) find an approximation of the global minimum or maximum of a function (eventually under equations and/or inequalities constraints) up to an accuracy provided by the user, (iv) analyze a system of algebraic equations to determine bounds for its real roots.

Geometric constraints
The dextrous workspace W Dextrous is defined in Eq. 1 as a function of the eigenvalues of (JJ T ) −1 . These eigenvalues are determined by solving the third degree characteristic polynomial P of (JJ T ) −1 . To decrease the computing time and to avoid numerical problems on singularities, it is recommended to add geometrical constraints. These constraints naturally depend on the mechanism architecture (see §4.2).

A first basic tool: Box verification
Our purpose is to determine the largest regular dextrous workspace that is enclosed in the Cartesian workspace.
For a given point, we note valid point if it is a dextrous point and invalid point otherwise. For that purpose we need to design first a procedure, called M(B), that takes as input a Cartesian box B and returns: • 0: if neither of the other two conditions could be verified.
The first step of this procedure consists in considering an arbitrary point of the box (e.g. its center) and to compute the eigenvalues at this point: either all of them lie in the range [σ min , σ max ] in which case the center is called valid or at least one of them lie outside this range and the center point is denoted invalid.

Valid center point
In that case if we are able to check that there is no point in B such that one of the eigenvalues at this point is equal to σ min or σ max , then we can guarantee that every point in B is valid. Indeed assume that at a given point B the lowest eigenvalue is lower than σ min : this implies that somewhere along the line joining this point to the center of the box the lowest eigenvalue is exactly σ min .
To perform this check we set the unknown in the characteristic polynomial P of (JJ T ) −1 to σ min (and then to σ max ) and we get a polynomial in x, y, z only. We now have to determine if there exists some values for these three Cartesian coordinates that cancel the polynomial, being understood that these values have to define a point belonging to B. This is done by using an interval analysis algorithm from the ALIAS library [16]. The principle of this algorithm is to calculate first the polynomial value for the center point C B of B. Without lack of generality we may assume that this value is positive. If we are able to determine a point S B in B such that the polynomial value at this point is negative, then we can guarantee that there exists a point on the line joining C B to S B such that the polynomial is exactly 0.  [21,22,23]).
Hence we have the following properties: The algorithm may indeed return 0 for a box that includes only valid points. But the width of this box will be lower than α/2 (where α is an accuracy threshold fixed in advance for the computation) and hence the final result will be within the tolerance margin of the calculation. The only case in which the calculation will be not guaranteed will occur only when α is lower than the machine accuracy. But we may determine that we are in such configuration as the width of the box from the machine viewpoint will be 0: if a box of width 0 is processed and the algorithm returns 0, then a warning message will be issued indicating that the calculation is no more guaranteed. Note, however, that we may still use the algorithm by using a multi-precision package such as MPFR that will allow to get a guaranteed result. Furthermore it is doubtful that computing the result with an accuracy better than the machine precision makes sense.

Invalid center point
Without lack of generality, we may assume that at the center of the box the largest eigenvalue is greater than σ max . If there is no point in B such that one of the eigenvalues is equal to σ max , then we can guarantee that for any point in B the largest eigenvalue is always greater than σ max and consequently M(B) = −1. This check is performed by using the same method as in the previous case.

A second basic tool: Box workspace verification
During the calculation of the dextrous workspace, we consider a Cartesian box B and we have to examine if this box may contain a point that is the center of a Cartesian box B W with edge length w, which is fully enclosed in the robot workspace. We assume here that this workspace is defined by a set of m inequalities F j such All the boxes with edge length w that have as center a point As in the previous section we may use interval analysis to compute an interval evaluation belonging to the workspace whereas other ones do not, we may state that B contains both points that may be the center of a box B W and points that cannot. A similar situation is obtained if we have found at least a sub-box that satisfies property 1 and a sub-box that satisfies property 2.
At that point we may define a procedure G(B, w) that takes as input a box B and an edge length w and returns: • -1: there is no points in B that may be the center of a box B W • 1: all the points in B may be the center of a box B W • 0: B contains both points that may be the center of a box B W and points that cannot.

Algorithm for the determination of a cubic dextrous Cartesian workspace
An algorithm is now described for the determination of a cube that is enclosed in the Cartesian workspace and aligned with the coordinate axis, whose edge length is 2w and such that there is no other cube enclosed in the workspace with an edge length of 2(w + α). This algorithm can be applied to any 3-DOF manipulator. Other shapes for regular dextrous workspace is considered in section 2.5.
The first step is to determine the largest cube enclosed in the workspace with a center located at (0, 0, 0). This is done by using the M procedure on the Cartesian box where k is an integer initialized to 1. Each time the M procedure returns 1 for B init (which means that the cube with edge length 2kα is enclosed in the dextrous workspace) we double the value of k. If this procedure returns -1 for a value of k larger than 1 this implies that the cube with edge length kα/2 is in the dextrous workspace whereas the cube with edge length kα is not. Hence if k > 2 (otherwise no improvement is possible) we restart the process with k = (k/2 + k)/2. After a failure at k f ail the principle is to always choose a value of k which is the mid-point between the last value k s of k for which M = 1 and k f ail until k f ail = k s + 1. For example if M returns 1 for k=1, 2, 4 and returns -1 for k = 8 we set k to 6. Otherwise we have determined that the cube with edge length 2kα is enclosed in the dextrous workspace, whereas the cube with edge length 2(k + 1)α is not. The value 2kα is hence an initial value for w. Note that the above procedure may be used whatever the coordinates of the center: it is implemented as a general purpose procedure C(x M , y M , z M ) that takes as input the coordinates of a point M and returns the edge length of the largest cube centered at M , that is enclosed in the dextrous workspace.
In the algorithm for determining the largest cube enclosed in the dextrous workspace, we manage a list of Cartesian boxes L that are processed by the algorithm in sequence. During the processing, boxes may be added to a list. At one step of the algorithm we have n boxes in the list whereas processing box numbered i (which means that boxes numbered from 0 to i − 1 have already been processed and may be discarded whereas boxes If n < N/2, both boxes are stored at the end of the list (and we set i=i+1), otherwise Box B 1 i are stored in L in place of B i whereas box B 2 i is stored at location i + 1 after a shift of the boxes B i+1 , . . . , B n . Set n to n + 1 and go to 2.
Step 1 allows one to establish an initial value for the maximal edge length.
Step 3 eliminates boxes that cannot contain the center of the maximal cube due to the workspace limits. Boxes satisfying step 4 are candidate to include the center of the largest cube: hence we calculate the largest cube centered at the box that may allow to update the current value of the largest edge.
Step 6 is the bisection process that allows one to decrease the size of the box with the effect of a sharper calculation for the procedure G. Note also that two storage modes that are used for adding the boxes resulting from the bisection process. The second mode allows for a minimal memory storage but has the drawback of focusing on a given part of the workspace whereas the center of the largest cube may be located in another part. The first mode makes it possible to explore various parts of the workspace which may result in large improvement on the value of w but as the drawback of possibly creating a large number of boxes. The proposed storage mode allows one to mix the advantages of both storage modes.
This procedure ensures to determine a cube with edge length w that is enclosed in the workspace and in the dextrous workspace, whereas there is no such cube with edge length w + α.
Note that an incremental approach is possible. After having computed w = w 1 with a given accuracy α it is always possible to replace the initial value of w as calculated in step 1 of the algorithm by the value w 1 when computing the cube with a lower value for α. Computation times of the largest cube for various accuracies are given for a specific 3-DOF PKM in section 4.3.

Other regular dextrous workspace shapes
Clearly, considering the largest cube may not be appropriate if the studied PKM has a rectangular or a sphericalshaped workspace. The algorithm can thus be modified. Here are for example the necessary changes that must be taken into account to consider the largest sphere: the idea is to use spherical coordinates and hence x, y, z are substituted by x c + r sin ψ sin θ, y c + cos ψ sin θ, z c + r cos θ, with r in [0,R], ψ, θ in [0, 2π], x c , y c , z c being the coordinates of the center of the sphere and R its radius. Interval analysis allows to deal with expressions involving sine and cosine and hence procedures M, G can still be used with these new parameters. Similarly procedure C(x M , y M , z M ) can be used to determine the largest radius of the sphere centered at (x M , y M , z M ) for which the eigenvalues are valid. Hence, with this modification, the algorithm can calculate the largest sphere enclosed in the dextrous workspace.
Spheres and cubes are defined by their center and one additional parameter. But other shapes may involve more parameters: for example a cylinder needs a center but also a height and a radius. We can still perform a change in the variables so that procedures M, G can still be used. The key point is that procedure C(x M , y M , z M ) has to be modified as we have now two optimization parameters. But in that case volume optimization alone has less meaning: for example the optimization result for a cylinder may be a cylinder with a relatively small radius and a large height, which may be of no interest. A cylinder of identical radius and height with a lower volume may be the most interesting result. A possible way to manage this problem is to assign a range [a, b] for the ratio R/h where R is the cylinder radius and h its height. In that case the procedure C has to solve an optimization problem which is to maximize the volume of the cylinder under the constraints that the eigenvalues are valid and the ratio R/h satisfies a ≤ R/h ≤ b. ALIAS is still able to manage such an optimization procedure. Note that this procedure may be incremental if the boxes neglected at step 4-a are stored in a file F . Indeed a first run with a given ǫ allows to obtain initial values for V a , V e . If the quality of the approximation is not satisfactory, we may choose a smaller value of ǫ (e.g. ǫ/2). But instead of starting with the initial B 0 , we may use the boxes stored in F , thereby avoiding to repeat computation that has already been done during the initial run.

Description of the Orthoglide and the UraneSX
The previous interval analysis based design method is now applied to the comparison of two 3-DOF translational PKM. It is particularly interesting to compare these two mechanisms because they belong to the same architecture family.

Orthoglide and UraneSX architectures
x y z q 1 b 1 Figure 1: Orthoglide kinematic architecture The output body is connected to the linear joints through a set of three parallelograms of equal lengths For the Orthoglide mechanism, the first linear joint axis is parallel to the x-axis, the second one is parallel to the y-axis and the third one is parallel to the z-axis. When each vector e i is aligned with A i B i , the Orthoglide is in an isotropic configuration and the tool center point P is located at the intersection of the three linear joint axes.

Figure 2: UraneSX kinematic architecture
The linear joint axes of the UraneSX mechanism are parallel to the z-axis. In fig. 2, points A 1 , A 2 and A 3 are the vertices of an equilateral triangle whose geometric center is O and such that OA i = R. Thus, points B 1 , B 2 and B 3 are the vertices of an equilateral triangle whose geometric center is P , and such that OB i = r.

Kinematic equations and singularity analysis
We recall briefly here the kinematic equations and the singularities of the Orthoglide and of the UraneSX (See [20,19] for more details).
Let θ i and β i denote the joint angles of the parallelogram about axes i i and j i , respectively (Figs. 1 and 2).
Let ρ 1 , ρ 2 , ρ 3 denote the linear joint variables and L denote the length of the three legs, For the Orthoglide, the position vector p of the tool center point P is defined in a reference frame (O, x, y, z) centered at the intersection of the three linear joint axes (note that the reference frame has been translated in Fig. 1 for more legibility).
For the UraneSX, the position vector p of the tool center point P is defined in a reference frame (O, x, y, z) centered at the geometric center of the points A 1 , A 2 , and A 3 (same remark as above).
Letρ be referred to as the vector of actuated joint rates andṗ as the velocity vector of point P : p can be written in three different ways by traversing the three chains A i B i P : where a i and b i are the position vectors of the points A i and B i , respectively, and e i is the direction vector of the linear joints, for i = 1, 2,3.
We want to eliminate the three idle joint ratesθ i andβ i from Eqs. (3), which we do by dot-product of Equations (4) can now be cast in vector form, namely Aṗ = Bρ, where A and B are the parallel and serial Jacobian matrices, respectively: Parallel singularities occur when the determinant of the matrix A vanishes, i.e. when det(A) = 0. Eq. (5) shows that the parallel singularities occur when: that is when the points A 1 , B 1 , A 2 , B 2 , A 3 and B 3 lie in parallel planes. A particular case occurs when the links A i B i are parallel: Serial singularities arise when the serial Jacobian matrix B is no longer invertible i.e. when det(B) = 0. At a serial singularity a direction exists along which no Cartesian velocity can be produced. Equation (5) shows that det(B) = 0 when for one leg i, When B is not singular, we can write,ρ 4 Comparison of the Orthoglide and the UraneSX In this section, we calculate the edge length of the largest cube for the Orthoglide, the edge length of the largest square for the UraneSX, as well as the location of their respective centers. To simplify the problem, the bounds on the velocity transmission factors are such that ψ min = 1/ψ max .

Regular dextrous workspace shape
The Orthoglide and the UraneSX are compared according to the size of their largest regular dextrous Workspace.
Due to the symmetrical architecture of the Orthoglide, the Cartesian workspace has a fairly regular shape in which it is possible to include a cube whose sides are parallel to the planes xy, yz and xz respectively. The Cartesian workspace of the UraneSX is the intersection of three cylinders whose axes are parallel to the zaxis. Thus, the workspace is unlimited in the z-direction and the Jacobian matrix does not depend on the z coordinate. Only the limits on the linear joints define the limits of the Cartesian workspace in the z-direction.
However, it is possible to include a square in the plane xy. Regular dextrous workspaces are thus chosen to be a cube for the Orthoglide and a square for the UraneSX.

Geometric constraints
Section 2.1 is suggested to add geometrical constraints so as to decrease the computing time and to avoid numerical problems on singularities. Here, polynomial P is defined only for the points within the intersection I of the three cylinders defined by for the Orthoglide, and, for the UraneSX. With these constraints, matrix B is never singular and thus can be always inverted. To solve numerically the above equations and to compare the two mechanisms, the length of the legs is normalized, i.e.

Comparison results
To compare the two mechanisms studied, the leg length L is set to 1 and the bounds on the velocity factor amplification are set to ψ = [0. 5 2], with α = 0.001. For the UraneSX, it is necessary to define two additional lengths, r and R. However, the edge length of the workspace depends only on R − r.
For the Orthoglide, it is found that the largest cube has its center located at (0.086, 0.086, 0.086), and that the cube edge length is L W orkspace = 0.644. Also, using the incremental approach described in section 2.4, we get for the Orthoglide the computation time of    The optimal value of R ′ is obtained for λ = 0, i.e. for the design parameters defined in [20] for an industrial application (see table 2). To expand this square workspace in the z-direction, the range limits must be equal to the edge length of the square plus the range variations necessary to move throughout the square in the x − y plane.
The constraints on the velocity amplification factors used for the design of the Orthoglide are close to those used for the design of the UraneSX which is an industrial machine tool. For the same length of the legs, the size of the cubic workspace is larger for the Orthoglide than for the UraneSX.
For the Orthoglide, the optimization puts the serial and parallel singularities far away from the Cartesian workspace [19]. The UraneSX has no parallel singularities due to the design parameters (R − r < L), but serial singularities cannot be avoided with the previous optimization function. To produce the motion in the z-direction, the range limits of the linear joints are set such that the constraints on the velocity amplification factors are not satisfied throughout the Cartesian workspace.
The range limits ∆ρ i of each prismatic joint can be decomposed into two parts. For the Orthoglide (resp. for the UraneSX), the first part ∆f i makes it possible to move the mobile platform throughout the face of the prescribed cube that is perpendicular to the considered prismatic joint axis (resp. throughout the prescribed square). The second part is equal to the edge length of the cubic workspace L W orkspace . The equations of the inverse kinematic model allow us to compute ∆f i for the two mechanisms.
For the Orthoglide, the position and the size of the prescribed cube define three range limits for the x − y − z platform coordinates,  Table 3: Workspace volumes of the two mechanisms To help understand these results, Fig. 3 and 4 show the location of the largest cubic workspace inside the Cartesian workspace. As the Cartesian workspace of the Orthoglide is regular and admits a quasi-cubic shape, the ratio between the cubic workspace and the Cartesian workspace is better than for the UraneSX. In table 4, the design parameters are compared to achieve the same cubic dextrous workspace with L W orkspace = 1.
The legs length is directly connected to the dynamic properties of the mechanism. The range limits and the   Table 4: Synthesis of the comparative study for the same cubic Cartesian workspace These criteria allow us to optimize some geometric parameters to design a machine tool for milling applications. Although in this approach, the kinetostatic properties of the Orthoglide are better than the UraneSX ones, we cannot assert that the Orthoglide is better than the UraneSX. One reason is that these two PKM are not aimed at identical manufacturing tasks. The main applications of the UraneSX are drilling, facing and tapping whereas the Orthoglide is more universal.
Other shapes of regular dextrous workspaces can be computed for the Orthoglide and the UraneSX by using cylindrical or spherical coordinates to have the largest cylinder or sphere respectively, even if these shapes are generally less relevant for milling applications.

Conclusions
This paper introduces an interval analysis based study for the design and the comparison of 3-DOF PKM. Two basic tools and an algorithm are described to determine the largest regular dextrous workspace enclosed in the Cartesian workspace. The dextrous workspace is a part of the Cartesian workspace in which the velocity amplification factors remain within a predefined range. This means that throughout the dextrous workspace, milling tool paths are available because the variations of the kinematic performances index remain under reasonable values. The regular dextrous workspace shape is a cube for the Orthoglide and a square for the UraneSX.
This general method is coupled with geometric constraints associated with the mechanisms studied to avoid numerical problems at singular configurations. The shape of the dextrous workspace was chosen for milling applications but it can be different for other applications. The range limits and the volume of the Cartesian workspace were calculated to compare the two mechanisms.

Acknowledgments
This research was supported by the CNRS (Project ROBEA "Machine Architecture compleXe"). We would like to thank the anonymous reviewers for their very useful comments.