Damien Chablat
email: chablat@irccyn.ec-nantes.fr

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

Raza Ur-Rehman
email: ur-rehman@irccyn.ec-nantes.fr

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

COMPARISON OF PLANAR PARALLEL MANIPULATOR ARCHITECTURES BASED ON A MULTI-OBJECTIVE DESIGN OPTIMIZATION APPROACH

This paper deals with the comparison of planar parallel manipulator architectures based on a multi-objective design optimization approach. The manipulator architectures are compared with regard to their mass in motion and their regular workspace size, i.e., the objective functions. The optimization problem is subject to constraints on the manipulator dexterity and stiffness. For a given external wrench, the displacements of the moving platform have to be smaller than given values throughout the obtained maximum regular dexterous workspace. The contributions of the paper are highlighted with the study of 3-PRR, 3-RPR and 3-RRR planar parallel manipulator architectures, which are compared by means of their Pareto frontiers obtained with a genetic algorithm.

INTRODUCTION

The design of parallel kinematics machines is a complex subject. The fundamental problem is that their performance heavily depends on their geometry [START_REF] Hay | Methodologies for the optimal design of parallel manipulators[END_REF] and the mutual dependency of almost all the performance measures. This makes the problem computationally complex and yields the traditional solution approaches inefficient. As reported in [START_REF] Merlet | Parallel Robots[END_REF], since the performance of a parallel manipulator depends on its dimensions, the latter depend on the manipulator application(s). Furthermore, numerous design aspects contribute to the Parallel Kinematics Machine (PKM) performance and an efficient design will be one that takes into account all or most of these design aspects. This is an iterative process and an efficient design requires a lot of computational efforts and capabilities for mapping design parameters into design criteria, and hence turning out with a multiobjective design optimization problem. Indeed, the optimal geometric parameters of a PKM can be determined by means of a the resolution of a multiobjective optimization problem. The solutions of such a problem are non-dominated solutions, also called Pareto-optimal solutions. Therefore, design optimization of parallel mechanisms is a key issue for their development.

Several researchers have focused on the optimization problem of parallel mechanisms the last few years. They have come up either with mono-or multi-objective design optimization problems. For instance, Lou et al. [START_REF] Lou | Optimal design of parallel manipulators for maximum effective regular workspace[END_REF][START_REF] Lou | Randomized optimal design of parallel manipulators[END_REF] presented a general approach for the optimal design of parallel manipulators to maximize the volume of an effective regular-shaped workspace while subject to constraints on their dexterity. Hay and Snyman [START_REF] Hay | Methodologies for the optimal design of parallel manipulators[END_REF] considered the optimal design of parallel manipulators to obtain a prescribed workspace, whereas Ottaviano and Ceccarelli [START_REF] Ottaviano | Workspace and optimal design of a pure translation parallel manipulator-tsai manipulator[END_REF][START_REF] Ottaviano | Optimal design of capaman (cassino parallel manipulator) with prescribed workspace[END_REF] proposed a formulation for the optimum design of 3-Degree-Of-Freedom (DOF) spatial parallel manipulators for given position and orientation workspaces. They based their study on the static analysis and the singularity loci of a manipulator in order to optimize the geometric design of the Tsai manipulator for a given free-singularity workspace. Hao and Merlet [START_REF] Hao | Multi-criteria optimal design of parallel manipulators based on interval analysis[END_REF] discussed a multi-criterion optimal design methodology based on interval analysis to determine the possible geometric parameters satisfying two compulsory requirements of the workspace and accuracy. Similarly, Ceccarelli et al. [START_REF] Ceccarelli | Multi criteria optimum design of manipulators[END_REF] dealt with the multi-criterion op-timum design of both parallel and serial manipulators with the focus on the workspace aspects, singularity and stiffness properties. Gosselin and Angeles [START_REF] Gosselin | The optimum kinematic design of a planar three-degree-of-freedom parallel manipulator[END_REF][START_REF] Gosselin | The optimum kinematic design of a spherical three-degree-of-freedom parallel manipulator[END_REF] analyzed the design of a 3-DOF planar and a 3-DOF spherical parallel manipulators by maximizing their workspace volume while paying attention to their dexterity. Pham and Chen [START_REF] Pham | Optimal synthesis for workspace and manipulability of parallel flexure mechanism[END_REF] suggested maximizing the workspace of a parallel flexible mechanism with the constraints on a global and uniformity measure of manipulability. Stamper et al.

[12] used the global conditioning index based on the integral of the inverse condition number of the kinematic Jacobian matrix over the workspace in order to optimize a spatial 3-DOF translational parallel manipulator. Stock and Miller [13] formulated a weighted sum multi-criterion optimization problem with manipulability and workspace as two objective functions. Menon et al. [14] used the maximization of the first natural frequency as an objective function for the geometrical optimization of the parallel mechanisms. Similarly, Li et al. [15] proposed dynamics and elastodynamics optimization of a 2-DOF planar parallel robot to improve the dynamic accuracy of the mechanism. They proposed a dynamic index to identify the range of natural frequency with different configurations. Krefft [START_REF] Krefft | Elastodynamic optimization of parallel kinematics[END_REF] also formulated a multi-criterion elastodynamic optimization problem for parallel mechanisms while considering workspace, velocity transmission, inertia, stiffness and the first natural frequency as optimization objectives. Chablat and Wenger [START_REF] Chablat | Architecture optimization of a 3-dof parallel mechanism for machining applications, the orthoglide[END_REF] proposed an analytical approach for the architectural optimization of a 3-DOF translational parallel mechanism, named Orthoglide 3-axis, based on prescribed kinetostatic performance to be satisfied in a given Cartesian workspace.

Most of the foregoing research works aimed to improve the performance of a given manipulator and the comparison of various architectures for a given application or performance has not been considered. In this paper, the mechanisms performance are improved over a regular shaped workspace for given specifications. As a result, we propose a methodology to deal with the multiobjective design optimization of PKMs. The size of the regular shaped workspace and the mass in motion of the mechanism are the objective functions of the optimization problem. Its constraints are determined based on the mechanism accuracy, assembly and the conditioning number of its kinematic Jacobian matrix. The proposed approach is applied to the optimal design of Planar Parallel Manipulators (PPMs) with the same mobility and set of design parameters. The non-dominated solutions, also called Pareto-optimal solutions, are obtained by means of a genetic algorithm for the three architectures and finally a comparison is made between them.

MANIPULATORS UNDER STUDY

Figure 1(a)-(c) illustrate the architectures of the planar parallel manipulators (PPMs) under study, which are named 3-PRR, 3-RPR and 3-RRR PPMs, respectively. Other families of PPMs are described in [START_REF] Merlet | Parallel Robots[END_REF]. Here and throughout this paper, R, P, R and P denote revolute, prismatic, actuated revolute and actuated prismatic joints, respectively. The manipulators under study are composed of a base and a moving platform (MP) connected by means of three legs. Points A 1 , A 2 and A 3 , (C 1 , C 2 and C 3 , respectively) lie at the corners of a triangle, of which point O (point P, resp.) is the circumcenter. Each leg of the 3-PRR PPM is composed of a P, a R and a R joint in sequence. Each leg of the 3-RPR PPM is composed of a R, a P and a R joint in sequence. Likewise, each leg of the 3-RRR PPM is composed of three R joints in sequence. The three P joints of the 3-PRR and the 3-RPR PPMs are actuated while the first R joint of each leg of the 3-RRR PPM is actuated.

F b and F p are the base and the moving platform frames of the manipulator. In the scope of this paper, F b and F p are supposed to be orthogonal. F b is defined with the orthogonal dihedron ( Ox, Oy), point O being its center and Ox parallel to segment A 1 A 2 . Likewise, F p is defined with the orthogonal dihedron ( PX, PY ), point C being its center and PX parallel to segment C 1 C 2 . The manipulator MP pose, i.e., its position and its orientation, is determined by means of the Cartesian coordinates vector p = [p x , p y ] T of operation point P expressed in frame F b and angle φ , namely, the angle between frames F b and F p .

The geometric parameters of the manipulators are defined as follows: (i) R is the circumradius of triangle A 1 A 2 A 3 of circumcenter O, i.e., R = OA i ; (ii) r is the circumradius of triangle C 1 C 2 C 3 of circumcenter P, i.e., r = PC i , i = 1, . . . , 3; (iii) L b is the length of the intermediate links, i.e., L b = B i C i for the 3-PRR PPM. L b is also the maximum displacement of the prismatic joints of the 3-RPR PPM. Similarly, L b is the length of the two intermediate links of the 3-RRR PPM, i.e., L b = A i B i = B i C i ; (iv) r j is the cross-section radius of the intermediate links; (v) r p : the cross-section radius of links of the moving platform, the latter being composed of three links.

Stiffness Modeling

The stiffness models of the three manipulators under study are obtained by means of the refined lumped mass modeling described in [START_REF] Pashkevich | Stiffness analysis of overconstrained parallel manipulators[END_REF]. Figures 2 to 4 illustrate the flexible models of the legs of the 3-PRR, 3-RPR and 3-RRR PPMs, respectively. The actuator control loop compliance is described with a 1-dof virtual spring and the mechanical compliance of each link with a 6-dof virtual spring in each flexible model denoted θ i . Be- sides, the moving platform of the manipulators is supposed to be composed of three links of length r connected to its geometric center P.

From Fig. 2, the flexible model of the legs of the 3-PRR PPM contains sequentially: (i) a rigid link between the manipulator base and the i th actuated joint (part of the base platform) described by the constant homogeneous transformation matrix T i Base ; (ii) a 1-dof actuated joint, defined by the homo- geneous matrix function V a (q i 0 ) where q i 0 is the actuated coordinate; (iii) a 1-dof virtual spring describing the actuator mechanical stiffness, which is defined by the homogeneous ma- which is described by the homogeneous matrix function V r1 (q i 2 ); (v) a rigid leg of length L linking the foot and the movable platform, which is described by the constant homogeneous transformation matrix T i L ; (vi) a 6-dof virtual spring describing the leg stiffness, which is defined by the homogeneous matrix function

V s2 θ i 1 • • • θ i 6 , with θ i 1 , θ i 2 , θ i
3 and θ i 4 , θ i 5 , θ i 6 being the virtual spring coordinates corresponding to the spring translational and rotational deflections; (vii) a 1-dof passive R-joint between the leg and the platform, allowing one rotation angle q i 3 , which is described by the homogeneous matrix function V r2 (q i 3 ); (viii) a rigid link of length r from the manipulator leg to the geometric center of the mobile platform, which is described by the constant homogeneous transformation matrix T i r ; (ix) a 6-dof virtual spring describing the stiffness of the moving platform, which is defined by the homogeneous matrix function

V s3 θ i 7 • • • θ i 12 , θ i
7 , θ i 8 , θ i 9 and θ i 10 , θ i 11 , θ i 12 being the virtual spring coordinates corresponding to translational and rotational deflections of link C i P; (x) a homogeneous transformation matrix T i End that characterizes the rotation from the 6-dof spring associated with link C i P and the manipulator base frame.

As a result, the mathematical expression defining the endeffector location subject to variations in all above defined coordinates of a single kinematic chain i of the 3-PRR PPM takes the form:

T i = T i Base V i a q i 0 V s1 θ i 0 V r1 q i 1 T i L V s2 θ i 1 • • • θ i 6 V r2 (q i 2 )T i r V s3 θ i 7 • • • θ i 12 T i End (1)
Similarly, the mathematical expressions associated with the kinematic chains of the 3-RPR and 3-RRR PPMs are obtained.

From [START_REF] Pashkevich | Stiffness analysis of overconstrained parallel manipulators[END_REF], the kinetostatic model of the ith leg of the X-PPMs can be reduced to a system of two matrix equations, namely,

S i θ |X J i q J i q 0 2×2 f i δ q i = δ t i 0 2 (2)
where X stands for 3-PRR, 3-RPR or 3-RRR. The sub-matrix

S i θ |X = J i θ |X K i θ |X -1 J i θ |X
T describes the spring compliance relative to the geometric center of the moving platform, and the submatrix J i q takes into account the passive joint influence on the moving platform motions. J i θ is the Jacobian matrix related to the virtual springs and J i q is the one related to the passive joints. K i θ |X -1 describes the compliance of the virtual springs.

K i θ |3PRR -1 =    K i act -1 0 1×6 0 1×6 0 6×1 K i link -1 0 6×6 0 6×1 0 6×6 K i p f -1    (3a) K i θ |3RPR -1 =    K i link -1 0 6×1 0 6×6 0 1×6 K i act -1 0 1×6 0 6×6 0 6×1 K i p f -1    (3b) K i θ |3RRR -1 =       K i act -1 0 1×6 0 1×6 0 1×6 0 6×1 K i link 1 -1 0 6×6 0 6×6 0 6×1 0 6×6 K i link 2 -1 0 6×6 0 6×1 0 6×6 0 6×6 K i p f -1       (3c)
where K i act is the 1 × 1 stiffness matrix of the ith actuator, K i link is the 6 × 6 stiffness matrix of the intermediate link for the 3-PRR and 3-RPR PPMs while K i link 1 and K i link 2 are the 6 × 6 stiffness matrices of the first and second intermediate links of the ith leg of 3-RRR PPM. K i p f is the 6 × 6 stiffness matrix of the ith link of the moving platform. The compliance matrix of each link is expressed by means of the stiffness model of a cantilever beam, namely,

K i L -1 =            L EA 0 0 0 0 0 0 L 3 3EI z 0 0 0 L 2 2EI z 0 0 L 3 3EI y 0 -L 2 2EI y 0 0 0 0 L GI x 0 0 0 0 -L 2 2EI y 0 L EI y 0 0 L 2 2EI z 0 0 0 L EI z            (4)
L being the length of the corresponding link, A is its the crosssectional area, i.e., A = πr 2 j for the links of the manipulators legs and A = πr 2 p for the links of the moving platform. I y and I z are the polar moments of inertia about y and z axes, resp. I y = I z = πr 4 j /4 for the links of the manipulators legs and I y = I z = πr 4 p /4 for the links of the moving platform. I x = I z + I y is the polar moment of inertia about the longitudinal axis of the link. E and G are the Young and shear moduli of the material.

Accordingly, the Cartesian stiffness matrix K i of the ith leg defining the motion-to-force mapping is obtained from Eq. (2).

f i = K i δ t i ( 5
)
with f i being the wrench exerted on the ith leg of the manipulator and at the geometric center of the moving platform while δ t i is the small-displacement screw of the moving-platform. Finally, the Cartesian stiffness matrix K of the manipulator is found with a simple addition of the three K i matrices, namely,

K = 3 ∑ i=1 K i (6)

MULTIOBJECTIVE OPTIMIZATION PROBLEM

A multiobjective optimization problem (MOOP) is formulated in this section in order to compare 3-PRR, 3-RPR and 3-RRR PPMs. In scope of this study, the manipulators are compared with regard to their mass in motion and their regular workspace size, i.e., the two objective functions of the MOOP, defined below. Moreover, the MOOP is subject to constraints on the manipulator dexterity and stiffness. It means that for a given external wrench, the displacements of the moving platform have to be smaller than given values throughout the obtained maximum regular dexterous workspace.

Objective Functions

Mass in Motion of the Manipulators The components in motion of the manipulators are mainly their moving platform and the links of their legs. As a consequence, the mass in motion for the three PPMs under study is expressed as follows:

m PRR = 3 m link + m p f (7a) m RPR = 3 m link + m p f (7b) m RRR = 6 m link + m p f (7c)
m link is the mass of links of the legs and are supposed to be the same while m p f is the mass of the moving platform. The mass of the prismatic or revolute actuators does not appear in Eqs. (7a)-(c) as it is supposed to be fixed for the 3-PRR PPM and close to the base for the 3-RPR PPM.

m p f = π r 2 p r ν (8a) m link = π r 2 j L ν ( 8b
)
where ν is the material density. Finally, the first objective function of the MOOP is expressed as:

f 1 (x) = m X → min (9)
x being the vector of design variables, i.e., the geometric parameters of the manipulator at hand, and X stands for 3-PRR, 3-RPR or 3-RRR.

Regular workspace size

The quality of the manipulator workspace is of prime importance for the design of Parallel Kinematics Machines (PKMs). It is partly characterized by its size and shape. Moreover, the lower the amount of singularities throughout the workspace, the better the workspace for continuous trajectory planning. The workspace optimization of parallel manipulators can usually be solved by means of two different formulations. The first formulation aims to design a manipulator whose workspace contains a prescribed workspace and the second one aims to design a manipulator, of which the workspace is as large as possible. However, maximizing the manipulator workspace may result in a poor design with regard to the manipulator dexterity and manipulability [12,[START_REF] Wenger | Kinematic analysis of a new parallel machine tool: The orthoglide[END_REF]. This problem can be solved by properly defining the constraints of the optimization problem. Here, the multiobjective optimization problem of PPMs is based on the formulation of workspace maximization, i.e, the determination of the optimum geometric parameters in order to maximize a regular-shaped workspace.

In the scope of the paper, the regular-shaped workspace is supposed to be a cylinder of radius R w , for which at each point a rotation range ∆φ = 20 • of the moving-platform about the Zaxis has to be reached. Figure 5 illustrates such a regular-shaped workspace, whose x c , y c and φ c are its center coordinates and the rotation angle of the moving-platform of the manipulator in the home posture.

R w ∆φ (x c , y c , φ c ) FIGURE 5. A REGULAR-SHAPED WORKSPACE
Consequently, in order to maximize the manipulator workspace, the second objective of the optimization problem can be written as:

f 2 (x) = R w → max (10)

Constraints of the Optimization Problem

The constraints of the optimization problem deals with the geometric parameters, the dexterity and the accuracy of the manipulators. Moreover, the constraints have to be defined in order to obtain a singularity-free regular-shaped workspace.

Constraints on the Geometric Parameters

For the three PPMs under study, the kinematic constraints are handled with their inverse kinematics. It means that the inverse kinematics is solved in order for the postures of the PPM to belong to the same working mode throughout the manipulator regularshaped workspace. Besides, for the 3-PRR PPM, the lower and upper bounds of the prismatic lengths ρ i are defined such as 0 ≤ ρ i ≤ √ 3R in order to avoid collisions. To obtain feasible displacements of the prismatic joints, the range of the 3-RPR PPM is defined such that L/2 ≤ ρ i ≤ L.

Constraint on the Manipulator Dexterity

The manipulator dexterity is defined by the condition number of its kinematic Jacobian matrix. The condition number κ F (M) of a m × n matrix M, with m ≤ n, based on the Frobenius norm is defined as follows

κ F (M) = 1 m tr(M T M)tr [(M T M) -1 ] (11)
Here, the condition number is computed based on the Frobenius norm as the latter produces a condition number that is analytic in terms of the posture parameters whereas the 2-norm does not. Besides, it is much costlier to compute singular values than to compute matrix inverses. The terms of the direct Jacobian matrix of the three PPMs under study are not homogeneous as they do not have same units. Accordingly, its condition number is meaningless. Indeed, its singular values cannot be arranged in order as they are of different nature. However, from [START_REF] Li | Geometrical consideration of robot kinematics singularities[END_REF] and [START_REF] Paden | Optimal kinematic design 6r manipulator[END_REF], the Jacobian can be normalized by means of a normalizing length. Later on, the concept of characteristic length was introduced in [START_REF] Ranjbaran | The mechanical design of a seven-axes manipulator with kinematic isotropy[END_REF] in order to avoid the random choice of the normalizing length. For instance, the previous concept was used in [START_REF] Chablat | The isoconditioning loci of planar 3-dof parallel manipulator[END_REF] to analyze the kinetostatic performance of manipulators with multiple inverse kinematic solutions, and therefore to select their best working mode.

Accordingly, for the design optimization of the three PPMs, the minimum of the inverse condition number κ -1 (J) of the kinematic Jacobian matrix J is supposed to be higher than a prescribed value, say 0.1, throughout the regular-shaped workspace, for any rotation of its moving-platform, i.e., min κ -1 (J) ≥ 0.1 (12)

Constraints on the moving-platform pose errors

The position and orientation errors on the moving-platform are evaluated by means of the stiffness models of the manipulators. Let (δ x, δ y, δ z) and (δ φ x , δ φ y , δ φ z ) be the position and orien- tation errors of the moving-platform subject to external forces (F x , F y , F z ) and torques (τ z , τ y , τ z ). The constraints on the pose errors on the moving-platform are defined as follows:

δ x ≤ δ x max δ y ≤ δ y max δ z ≤ δ z max δ φ x ≤ δ φ max x δ φ y ≤ δ φ max y δ φ z ≤ δ φ max z (13)
(δ x max , δ y max , δ z max ) being the maximum allowable position errors and δ φ max x , δ φ max y , δ φ max z the maximum allowable orientation errors of the moving-platform. These accuracy constraints can be expressed in terms of the components of the mechanism stiffness matrix and the wrench applied to the movingplatform. Let us assume that the accuracy requirements are:

δ x 2 + δ y 2 ≤ 0.0001 m (14a) δ z ≤ 0.001 m (14b) δ φ z ≤ 1 deg (14c)
If the moving-platform is subject to a wrench whose components are F x,y = F z = 100 N and τ z = 100 Nm, then the accuracy con- straints can be expressed as:

k min xy ≥ F x,y / δ x 2 + δ y 2 = 10 6 N.m -1 (15a) k min z ≥ F z /δ z = 10 5 N.m -1 (15b) k min φ z ≥ τ z /δ φ z = 10 π/180 N.m.rad -1 (15c)

Design Variables of the Optimization Problem

Along with the above mentioned geometric parameters (R, r, L b ) of the PPMs, the radius r j of the circular-cross-section of the intermediate bars defined and the radius r p of the circular-crosssection of the platform bars are considered as design variables, also called decision variables. As a remainder, the movingplatform is supposed to composed of three circular bars of length r.

As there are three PPMs under study, the PPM type is another design variable that has to be taken into account. Let d denote the PPM type: d = 1 stands for the 3-PRR PPM; d = 2 stands for the 3-RPR PPM; and d = 3 stands for the 3-RRR PPM.

As a result, the optimization problem contains one discrete variable, i.e., d, and five continuous design variables, i.e., R, r, L b , r j and r p . Hence, the design variables vector x is given by:

x = d R r L b r j r p T (16)

Formulation of the Optimization Problem

The Multiobjective Design Optimization Problem of PPMs can be stated as: Find the optimum design variables x of PPMs in order to minimize the mass of the mechanism in motion and to maximize its regular shaped workspace subject to geometric, kinematic and accuracy constraints.

Mathematically, the problem can be written as:

minimize f 1 (x) = m X (17) maximize f 2 (x) = R w over x = d R r L b r j r p T subject to : g 1 : L b + r ≥ R 2 g 2 : 0 < ρ i < √ 3R g 3 : κ -1 (J) ≥ 0.1 g 4 : k min xy ≥ F x,y δ x 2 + δ y 2 = 10 6 g 5 : k min z ≥ F z δ z = 10 5 g 6 : k min φ z ≥ τ z δ φ z = 10 π/180 x lb ≤ x ≤ x ub
where x lb and x ub are the lower and upper bounds of x, respectively.

RESULTS AND DISCUSSIONS

The multiobjective optimization problem [START_REF] Chablat | Architecture optimization of a 3-dof parallel mechanism for machining applications, the orthoglide[END_REF] is solved by means of modeFRONTIER [START_REF] Esteco | modefrontier[END_REF] and by using its built-in multiobjective optimization algorithms. MATLAB code is incorporated in order to analyze the system and to get the numerical values for the objective functions and constraints that are analyzed in modeFRONTIER for their optimality and feasibility. The lower and upper bounds of the design variables are given in Tab. 1. The components of the PPMs are supposed to be made up of steel, of material density d = 7850 kg/m 3 and Young modulus E = 210 × 10 9 N/m 2 . For each iteration, The Pareto frontier, solution of MOOP [START_REF] Chablat | Architecture optimization of a 3-dof parallel mechanism for machining applications, the orthoglide[END_REF], is depicted in Fig. 6 whereas the design parameters and the corresponding objective functions for two extreme and one intermediate Pareto optimal solutions, as shown in Fig. 6, are given in Tab. 3. The CAD designs illustrating the three foregoing solutions are also shown in Fig. 8.

It appears that all Pareto-optimal solutions of MOOP ( 17) are 3-PRR PPMs. Accordingly, Fig. 7 illustrates the Pareto Frontiers associated with the three planar parallel manipulator architectures. It is noteworthy that the Pareto-optimal solutions associated with the 3-PRR PPM architectures are better than the Pareto-optimal solutions associated with the 3-RPR and 3-RRR PPM architectures. show the evolution of the design variables as a function of R w along the Pareto Frontier associated with each PPM architecture. It is noteworthy that the higher R w , the higher the design variables. It is apparent that the variations in variables R, r, L b and r j with respect to (w.r.t.) R w are almost linear whereas the variations in r p w.r.t. R w is rather quadratic. This is due to the fact that the higher the size of the mechanism the higher the bending of the moving platform links whereas the intermediate links are mainly subjected to tension and compression.

CONCLUSIONS

In this paper, the problem of dimensional synthesis of parallel kinematics machines was addressed. A multiobjective design optimization problem was formulated in order to determine optimum structural and geometric parameters of any parallel kinematics machine. The proposed approach is similar to that used in [START_REF] Altuzarra | Multiobjective optimum design of a symmetric parallel schnflies-motion generator[END_REF] but we took into account the mass and the regular workspace instead of considering the entire volume of the manipulator. The proposed approach was applied to the optimum design of three planar parallel manipulators with the aim to minimize the mass in motion of the mechanism and to maximize its regular shaped workspace. Other performance indices can be used as constraints. However, they cannot necessarily be used as objective functions as the latter are usually formulated as a sum of an index over all the manipulator workspace. As another constraint, we could use the collisions between the legs of the manipulator.

FIGURE 1 .FIGURE 2 .

 12 FIGURE 1. THE THREE PLANAR PARALLEL MANIPULATORS UNDER STUDY

FIGURE 7 .

 7 FIGURE 7. PARETO FRONTIERS ASSOCIATED WITH THE 3-PRR, 3-RPR, AND 3-RRR PLANAR PARALLEL MANIPULATOR ARCHITECTURES

TABLE 3 .FIGURE 8 .FIGURE 9 .FIGURE 10 .

 38910 FIGURE 8. CAD DESIGNS OF THREE PARETO-OPTIMAL SOLUTIONS OF MOOP[START_REF] Chablat | Architecture optimization of a 3-dof parallel mechanism for machining applications, the orthoglide[END_REF]

TABLE 1 .

 1 LOWER AND UPPER BOUNDS OF THE DESIGN VARIABLES

	Design Variable d R [m] r [m] L b [m] r j [m] r p [m]
	Lower Bound	1	0.5	0.5	0.5	0	0
	Upper Bound	3	4	4	4	0.1	0.1
	the regular-shaped workspace is evaluated for the corresponding

FIGURE 6. PARETO FRONTIER OF MOOP

[START_REF] Chablat | Architecture optimization of a 3-dof parallel mechanism for machining applications, the orthoglide[END_REF]

Copyright c 2010 by ASME


Damien Chablat
email: damien.chablat@irccyn.ec-nantes.fr

Joint space and workspace analysis of a two-DOF closed-chain manipulator

The aim of this paper is to compute of the generalized aspects, i.e. the maximal singularity-free domains in the Cartesian product of the joint space and workspace, for a planar parallel mechanism in using quadtree model and interval analysis based method. The parallel mechanisms can admit several solutions to the inverses and the direct kinematic models. These singular configurations divide the joint space and the workspace in several not connected domains. To compute this domains, the quadtree model can be made by using a discretization of the space. Unfortunately, with this method, some singular configurations cannot be detected as a single point in the joint space. The interval analysis based method allow us to assure that all the singularities are found and to reduce the computing times. This approach is tested on a simple planar parallel mechanism with two degrees of freedom.

INTRODUCTION

The kinematic design of parallel mechanism has drawn the interest of several researchers. The workspace is usually considered as a relevant design criterion [START_REF] Merlet | Workspace-0riented Methodology for Designing a Parallel Manipulator[END_REF][START_REF] Clavel | DELTA, a Fast Robot with Parallel Geometry[END_REF][START_REF] Gosselin | A Global Performance Index for the Kinematic Optimization of Robotic Manipulators[END_REF]. Parallel singularities [START_REF] Wenger Ph | Definition Sets for the Direct Kinematics of Parallel Manipulators[END_REF] occur in the workspace where the moving platform cannot resist any effort. They are very undesirable and generally eliminated by design. Serial singularities [START_REF] Chablat | Working Modes and Aspects in Fully-Parallel Manipulator[END_REF] occur if the mechanism admit several solutions to the inverse kinematic model. To cope with the existence of multiple inverse kinematic solutions in serial manipulators, the notion of aspects was introduced in [START_REF] Borrel | A study of manipulator inverse kinematic solutions with application to trajectory planning and workspace determination[END_REF]. The aspects equal the maximal singularity-free domains in the joint space. For usual industrial serial manipulators, the aspects were found to be the maximal sets in the joint space where there is only one inverse kinematic solution.

A definition of the notion of aspect was given by [START_REF] Wenger Ph | Definition Sets for the Direct Kinematics of Parallel Manipulators[END_REF] for parallel manipulators with only one inverse kinematic solution and was extended by [START_REF] Chablat | Working Modes and Aspects in Fully-Parallel Manipulator[END_REF] for parallel manipulators with several solutions to the inverse and direct kinematic problem. These aspects were defined as the maximal singularity-free domains in the Cartesian product of the joint space and the workspace. To compute the aspects, we can used discretization methods. However, we cannot find any singularity in particular if the singularity is a point. Interval based analysis method was implemented by [START_REF] Merlet | ALIAS: an interval analysis based library for solving and analyzing system of equations[END_REF][START_REF] Chablat | An Interval Analysis Based Study for the Design and the Comparison of 3-DOF Parallel Kinematic Machine[END_REF] in ALIAS to compute the workspace of parallel mechanism. However, the result is a set of boxes in which is not easy to separate the maximum singularity free regions of the workspace and the computational times is difficult to estimate.

This article introduces an algorithm based on the tree-like structure and the interval analysis based method which takes the advantages of the interval analysis based method and the simplicity of tree-like structures.

ALGORITHM

The aim of this section is to define an algorithm able to compute either the joint space or the workspace of parallel mechanism. This is done using the structure of a quadtree model and the interval based method. This algorithm will be illustrated by a planar parallel mechanism in section 3 but can easily be extended to mechanism with three degrees of freedom in using octree model. Unlike numerical computing methods, such a method allows to prove formally that there is no singular configuration in the final result.

Definition of the quadtree/octree model

The tree-like structure, called in this paper, quadtree or octree, are a hierarchical data structure based on a recursive subdivision of space [START_REF] Meagher | Geometric Modelling using Octree Encoding[END_REF]. It is particularly useful for representing complex 2 -D or 3 -D shapes, and is suitable for Boolean operations like union, difference and intersection. Since the quadtree/octree structure has an implicit adjacency graph, arcwise-connectivity analysis can be naturally achieved. The quadtree/octree model of a space S leads to a representation with cubes of various sizes. Basically, the smallest cubes lie near the boundary of the shape and their size determines the accuracy of the quadtree/octree representation. Quadtree/octrees have been used in several robotic applications [START_REF] Wenger Ph | Definition Sets for the Direct Kinematics of Parallel Manipulators[END_REF], [START_REF] Faverjon | Obstacle avoidance using an octree in the configuration space of a manipulator[END_REF], [START_REF] Garcia | Computing moveability areas of a robot among obstacles using octrees[END_REF].

The main advantages of the octree model are (i) very compact file (only B (Black), W (White) and G (Gray) letter) and (ii) accelerates display speed facilities by differentiating model into lower levels of resolution while being rotated and higher resolution while an orientation is temporarily set. Conversely, the computational times can be high due to the discretization. If we test only the center of each cube, some singularities can exist and are not detected. This feature is true even if we increase the level of resolution. The accuracy of the model is directly defined by the depth of the quadtree and the size of the initial box. For a quadtree model with a depth d and a initial box of lengths b, the accuracy is b/2 d .

Notion of aspect for fully parallel manipulators

We recall here briefly the definition of the generalized octree defined in [START_REF] Chablat | Working Modes and Aspects in Fully-Parallel Manipulator[END_REF]: Definition 1. The generalized aspects Aij are defined as the maximal sets in

W • Q so that Aij ⊂ W • Q, Aij is connected, and Aij = {(X, q) ∈ M fi \ det(A) = 0}
In other words, the generalized aspects Aij are the maximal singularity-free domains of the Cartesian product of the reachable workspace with the reachable joint space. Definition 2. The projection of the generalized aspects in the workspace yields the parallel aspects WAij so that WAij ⊂ W , and WAij is connected.

The parallel aspects are the maximal singularity-free domains in the workspace for one given working mode. Definition 3. The projection of the generalized aspects in the joint space yields the serial aspects QA ij so that QA ij ⊂ Q, and QA ij is connected.

The serial aspects are the maximal singularity-free domains in the joint space for one given working mode.

The aim of this paper is to compute separately the parallel and serial aspects thanks to the properties of the quadtree models.

Introduction to ALIAS library

An algorithm for the definition of the joint space and workspace of parallel mechanism is described in the following sections. This algorithm uses the ALIAS library [START_REF] Merlet | ALIAS: an interval analysis based library for solving and analyzing system of equations[END_REF], which is a C++ library of algorithms based on interval analysis. These algorithms deal with systems of equations and inequalities of which expressions are an arbitrary combination of the most classical mathematical functions (algebraic terms, sine, cosine, log etc..) and of which coefficients are real numbers or, in some cases, intervals. Unfortunately, this library is not connected to the octree model and generates large data file to describe by a set of boxes the solution of the problem. Thus, the operations between the set of boxes is more difficult if we compare to the boolean operations that we can made with the octree models.

A first basic tool: Box verification

Our purpose is to determine the quadtree model associated with the joint space or the workspace, that we will call only the space C. For a given box B defined by two intervals, we note valid box if it is included in C and invalid box otherwise. For that purpose we need to design first a procedure, called M(B), that takes as input a box B and returns:

• 1: if every point in B is valid, • -1: if no point in B is valid,
• 0: if neither of the other two conditions could be verified.

To check if one point is valid, we can used several approaches. For example, in the Cartesian space, we have to compute the inverse kinematic model to test if at least one solution exists, which defines the workspace. Thus, for each solution, we can define completely the mechanism for each working mode and compute the determinant of the parallel Jacobian matrix [START_REF] Chablat | Working Modes and Aspects in Fully-Parallel Manipulator[END_REF]. This procedure is able to define the non-singular domains but their are not necessary connected. However, with a quadtree model, it is easy to perform a connectivity analysis to separate the quadtree model in connected domains. This is a main advantage of the tree-like structures in comparison with the method implemented in the ALIAS library. Some additional constraints can be to define dexterous domains in using a kinetostatic index as in [START_REF] Chablat | An Interval Analysis Based Study for the Design and the Comparison of 3-DOF Parallel Kinematic Machine[END_REF].

The problem is now to implement an inverse and direct kinematic model able to take as input a box B and to return, if the box is valid, a box S which contains the solutions of the problem.

A second basic tool: Quadtree model definition

The definition of a quadtree is made recursively by calling several times the same procedure, call Q(B, d, P ), that takes as input a box B, the local depth d in the tree and a pointer P on the data structure which contains the quadtree model.

• If M(B) returns -1, it is the end of the recursive search.

• If M(B) returns 1, a black node is created in the current depth.

• If M(B) returns 0, if the local depth is smallest than the maximal depth of the quadtree, we divide the box B into four new boxes B1, B2, B3 and B4, and we call

Q(B1, d + 1, P ) Q(B2, d + 1, P ) Q(B3, d + 1, P ) Q(B4, d + 1, P )
When M(B) returns -1, we can also create a another quadtree model, called complementary space in which we save the box B where at least one constraint is not valid. With this knowledge, we can compute the quadtree model with a higher definition without retesting the valid and non valid boxes. An example of this result will be given in the following section.

MECHANISM UNDER STUDY

For more legibility, a planar manipulator is used as illustrative example in this paper. This is a five-bar, revolute (R)-closed-loop linkage, as displayed in figure 1. The actuated joint variables are θ1 and θ2, while the Output values are the (x, y) coordinates of the revolute center P . The displacement of the passive joints will always be assumed unlimited in this study. Lengths L0, L1, L2, L3, and L4 define the geometry of this manipulator entirely.

Two sets of dimensions are used to illustrate the algorithm. The first one, called M1, is defined in [START_REF] Chablat | Working Modes and Aspects in Fully-Parallel Manipulator[END_REF] and its dimensions are L0 = 9, L1 = 8, L2 = 5, L3 = 5 and L4 = 8 , in certain units of length that we need not to specify. And, the second one, called M2, is defined in [START_REF] Figielski | Towards Development of a 2-DOF Planar Parallel Robot with Optimal Workspace Use[END_REF] and its dimensions are L0 = 2.55, L1 = 2.3, L2 = 2.3, L3 = 2.3 and L4 = 2.3 .

Kinematic Relations

The velocity ṗ of point P , of position vector p, can be obtained in two different forms, depending on the direction in which the loop is traversed, namely,

ṗ = ḃ1 + θ3E(p -b1) ṗ = ḃ2 + θ4E(p -b2) (1)
with matrix E defined as E = 0 -1 1 0 and b1 and b2 denoting the position vectors, in the frame indicated in figure 1 of points B1 and B2, respectively. y A (0,0) 1

P x y ( , )

A L ( , 0)

2 0 x q 2 L 3 q 1 q 3 q 4 L 4 L 2 L 1 B 1 B 2

P x y ( , )

A L ( , 0)

2 0 x q 2 L 3 q 1 b a L 4 L 2 L 1 B 1 B 2 Figure 2:
The angle α and β used to solve the DKP Furthermore, note that ċ and ḋ are given by ḃ1 = θ1E(b1 -a2), ḃ2 = θ2E(b2 -a2)

Two Jacobian matrix, A and B, permit to study the serial and parallel singular configurations [START_REF] Wenger Ph | Definition Sets for the Direct Kinematics of Parallel Manipulators[END_REF],

A = (p -b1) T (p -b2) T , B= L1L2 sin(θ3 -θ1) 0 0 L3L4 sin(θ4 -θ2) = B11 0 0 B22 (2)
Two assembly modes can be defined with the sign of det(A). To characterize the assembly mode, we can only compute (p -b1) × (p -b2).

The parallel singular configurations are located at the boundary of the joint space. Such singularities occur whenever B1, P and B2 are aligned. In such configurations, the manipulator cannot resist an effort in the orthogonal direction of B1B2. Besides, when B1 and B2 coincide, the position of P is no longer controllable since P can rotate freely around B1 even if the actuated joints are locked. This singularity cannot be find by the discretization of the workspace but is detected by the interval analysis based method.

Direct kinematic problem

For planar mechanism, the computation of the direct kinematic problem (DKP) is very simple. However, if we want to return the good information to the function C, we have to distinguish more cases. If there is no joint limits, they are zero or two solutions for the DKP.

The procedure takes as input a box B defined by two intervals θ1 = [θ1, θ1] and θ2 = [θ2, θ2], the actuated joint variables. In this example, the values of the length are defined as a float but can be also defined by a interval to represent the tolerances of manufacturing.

The algorithm can be described by the following steps:

• Compute the position of b1 and b2 which is the location of B1 and B2 respectively.

• Compute the distance L between B1 and B2: -If L = 0 then the mechanism can be in a singular configuration.

-[L, L] = || b1 -b2||
• Compute the angle α and β of the triangle (B1, B2, P ) (Figure 2).

-

C(α) = ( L2 + L 2 3 -L 2 4 )/(2L3 L).
β = arctan

B 2y -B 1y B 2x -B 1x ) -If (C(α) ≥ -1 and C(α) ≤ 1) then α = arccos(C(α)).
• Compute the two solutions P1 and P2 of point P :

-P1x = B1x + L3 cos(α + β) -P1y = B1y + L3 sin(α + β) -P2x = B1x + L3 cos(α -β) -P2y = B1y + L3 sin(α -β).
To perform this procedure, all the trigonometric function come from the ALIAS library and accept as input an interval and return an interval. For each step, we have to check that the argument are not out of range.

For the two mechanism under study, we can plot with this function the joint space (Figure 3). The results are equivalent to the solution computed in [START_REF] Chablat | Working Modes and Aspects in Fully-Parallel Manipulator[END_REF] and [START_REF] Figielski | Towards Development of a 2-DOF Planar Parallel Robot with Optimal Workspace Use[END_REF]. However, conversely to a discretization method, we can detect the parallel singularity where B1 and B2 coincide. Normally, it is a point but with the interval analysis method, the algorithm cannot define valid boxec where det(A) is equal to zero. The set of box where at least one constraint is not valid is called the complementary joint space, figure 4.

Selection of the assembly mode

For a parallel mechanism with only two solutions to the direct kinematic problem, the assembly mode is characterize by the sign of det(A). To simplify, we can

only compute t = ( b1 -p) × ( b2 -p) (3)
and to test if tz is positive or negative.

Inverse kinematic problem

For the mechanism under study, there are four solutions for the inverse kinematic problem (IKP), two solutions for each leg. The procedure takes as input a box B defined by to two intervals x = [x, y] and ỹ = [y, y], the position of P .

The algorithm can be described by the following steps:

• Compute the distance M1 between A1 and P , and M2 between A2 and P .

• If (M1 > L1 + L3 or M2 > L2 + L4) then P is outside the workspace and the function returns -1.

• If (M1 < ||L1 -L3|| or M2 < ||L2 -L4||) then P is located in a hole of the workspace and the function returns -1.

• If (M1 > 0) and (M2 > 0) and (M1 > ||L1 -L3||) and (M2 > ||L2 -L4||) and (M1 < L1 + L3) and (M2 < L2 + L4) then compute the angles β1 = B1A1P and β2 = B2A2P noted in Figure 5: For the two mechanism under study, we can plot with this function the joint space (Figure 6). For the mechanism M∈, there is a hole in A1 and A2 which is only a point. On the picture, we can only notice that there exists a sub-division of the space because there are small boxes. The size of the hole is equal to the size of the smallest box.

-C(β1) = L 2 1 + M 2 1 -L 2 3 2 M1 L 1 C(β2) = L 2 2 + M 2 2 -L 2 4 2 M2 L 2 -If (|| C(β1)|| ≤ 1)

Selection of the working mode

For a parallel mechanism with only four solutions to the inverse kinematic problem, the working mode is characterized by the sign of B11 and B22. This can be done simply ũ = ( b1 -ã1) × (p -b1) ṽ = ( b2 -ã2) × (p -b2) [START_REF] Wenger Ph | Definition Sets for the Direct Kinematics of Parallel Manipulators[END_REF] and to test the sign of ũz or ṽz.

Computation of the generalized aspects

The number of aspects is the same for the both mechanisms. We can compute separately the serial and parallel aspects for all the working modes. For a give sign of det(A), B11 and B22, we have define a quadtree model. To obtain the generalized aspects, a connectivity analysis is made to separate the connected regions. We need to test only one point in the workspace and its projection on the joint space to associate a serial aspect to its parallel aspect counterpart. x The study of the joint space allow us to know if a trajectory between two generalized aspects exists by passing through a serial singularity. Figures 9 and 10 permit us to conclude that, for M1 and M2, no trajectory exists in which we change only one time the working modes, between the aspects 1 and 4 and between the aspects 2, 3 and 5.

q 2 L 3 q 1 b 1 a 1 L 4 L 2 L 1 B 1 B 2

Comparison between classical quadtree computation and the new algorithm

The aim of this section is to compare the number of times where the inverse or direct kinematic function is called to build the quadtree for the both mechanisms and for several depths of the tree which is equivalent to the accuracy of the model. For the joint space, the initial box B is defined by two intervals equal to [-π, π] and for the workspace, the initial box B is defined by two intervals equal to

[-(L1 + L3), (L1 + L3)].
With the discretization method, the number of times where the inverse or direct kinematic problem is used is n discretization = 2 2d with d is the depth of the tree. We call n quadtree the number of times where where the inverse or direct kinematic problem is used to build the quadtree model. To compare the computing cost between the both method, we define the following criteria:

K = n quadtree /n discretization (5)
Table 1 compares the computing times for the joint space and the workspace for the mechanisms M1 and M2. When the depth of the quadtree is small, there is no advantage to used the interval analysis based method. But, when the depth increase, the advantages can be very important. For example, to compute the workspace of M1 with d = 10, we call 36893 times the IKP while the discretization method calls 2 20 = 1048576 times the IKP.

CONCLUSIONS AND FUTURE WORKS

In this paper, we have presented an algorithm able to compute the joint space and workspace of parallel mechanism by using the octree model and the interval based method. We have the maximum singularity regions, called aspects, for two planar mechanisms and we have compared the number of times where the inverse and direct kinematic problem is called according to the accuracy used. Thanks to the use of the interval analysis based method, the result is guaranteed for all the depth used, i.e. we are sure to detect all the singular configurations. The quadtree model can be saved in text file and its size is very small. Plugin exist now to visualize the model in a 3D viewer in Web pages (as www.octree.com). Future works will be made to define as interval the lengths of the legs and to find the influence of the manufacturing error on the joint space and workspace.

Figure 1 :

 1 Figure 1: A two-dof closed-chain manipulator

Figure 3 :

 3 Figure 3: Joint space of M 1 and M 2

Figure 4 : 2 -

 42 Figure 4: The complementary joint space of M 1 and M 2

  and (|| C(β2)|| ≤ 1) then * α1 = arctan(Py/Px) α2 = arctan(Py/(C2 -Px)) * β1 = arccos( C(β1)) β2 = arccos( C(β2)) * α11 = α1 +β1 α12 = α1 -β1 α21 = π-α2 +β2 α22 = π-α2-β2 * Returns 1; -Else, returns 0;

Figure 5 :Figure 6 :

 56 Figure 5: The angle α and β used to solve the IKP

Figure 7 :

 7 Figure 7: Aspects of M 1

Figure 8 :

 8 Figure 8: Aspects of M 2

Figure 9 :Figure 10 :

 910 Figure 9: The serial aspects of M 1 for det(A) > 0 Figure 10: The serial aspects of M 2 for det(A) > 0

Table 1 :

 1 Comparison between classical quadtree computation and the new algorithm to compute the joint space and the workspace

	Joint space Depth #	5	6	7	8	9	10
	M 1	99% 73% 40% 22% 13 % 9 %
	M 2	111% 83% 40% 18% 8 % 4 %
	Workspace Depth #	5	6	7	8	9	10
	M 1	72% 45% 25% 13% 7 % 3 %
	M 2	65% 37% 19% 10% 5 % 2 %

ACKNOWLEDGMENTS

This work was supported partly by the French Research Agency A.N.R. (Agence Nationale pour la Recherche).


G Moroz

F Rouiller

D Chablat
email: damien.chablat@irccyn.ec-nantes.fr

P Wenger

On the determination of cusp points of 3-RPR parallel manipulators

Keywords: Kinematics, Singularities, Cusp, Parallel manipulator, Symbolic computation

This paper investigates the cuspidal configurations of 3-RPR parallel manipulators that may appear on their singular surfaces in the joint space. Cusp points play an important role in the kinematic behavior of parallel manipulators since they make possible a non-singular change of assembly mode. In previous works, the cusp points were calculated in sections of the joint space by solving a 24th-degree polynomial without any proof that this polynomial was the only one that gives all solutions. The purpose of this study is to propose a rigorous methodology to determine the cusp points of 3-RPR manipulators and to certify that all cusp points are found. This methodology uses the notion of discriminant varieties and resorts to Gröbner bases for the solutions of systems of equations.

Introduction

Because at a singularity a parallel manipulator loses its stiffness, it is of primary importance to be able to characterize these special configurations. This is, however, a very challenging task for a general parallel manipulator. Planar parallel manipulators have received a lot of attention [START_REF] Gosselin | The direct kinematics of planar parallel manipulators: Special architectures and number of solutions[END_REF][START_REF] Wenger | Classification of 3R positioning manipulators[END_REF][START_REF] Borrel | A study of multiple manipulator inverse kinematic solutions with applications to trajectory planning and workspace determination[END_REF][START_REF] Hunt | Assembly configurations of some in-parallel-actuated manipulators[END_REF][START_REF] Innocenti | Singularity-free evolution from one configuration to another in serial and fully-parallel manipulators[END_REF] because of their relative simplicity with respect to their spatial counterparts. Moreover, studying the former may help understand the latter. Planar manipulators with three extensible leg-rods, referred to as 3-RPR manipulators, have often been studied. Such manipulators may have up to six assembly modes and their direct kinematics can be written in a polynomial of degree six [START_REF] Gosselin | The direct kinematics of planar parallel manipulators: Special architectures and number of solutions[END_REF][START_REF] Wenger | Classification of 3R positioning manipulators[END_REF]. Moreover, they may have singularities (configurations where two direct kinematic solutions coincide). It was first pointed out that to move from one assembly mode to another, the manipulator should cross a singularity [START_REF] Borrel | A study of multiple manipulator inverse kinematic solutions with applications to trajectory planning and workspace determination[END_REF][START_REF] Hunt | Assembly configurations of some in-parallel-actuated manipulators[END_REF]. Later, Innocenti and Parenti-Castelli [START_REF] Innocenti | Singularity-free evolution from one configuration to another in serial and fully-parallel manipulators[END_REF] showed, using numerical experiments, that this statement is not true in general. In fact, this statement is only true under some special geometric conditions, such as similar base and mobile platforms [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF][START_REF] Kong | Type synthesis of 5-DOF parallel manipulators based on screw theory[END_REF]. More recently, Macho et al. [START_REF] Macho | Singularity free change of assembly mode in parallel manipulators[END_REF] proposed a method to plan non-singular assembly-mode changing trajectories. McAree [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF] pointed out that for a 3-RPR parallel manipulator, if a point with triple direct kinematic solutions exists in the joint space, then the nonsingular change of assembly mode is possible. This result holds under some assumptions on the topology of the singularities [START_REF] Husty | Non-singular assembly mode change in 3-RPR-parallel manipulators[END_REF]. For other mechanisms than 3-RPR manipulator, it is also interesting to note that encircling a cusp point is not the only way to execute a non-singular change of assembly mode [START_REF] Bamberger | Assembly mode changing in parallel mechanisms[END_REF]. A condition for three direct kinematic solutions to coincide was established in [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF]. This condition was then exploited in [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF] to derive a univariate polynomial of degree 96. A factored expression was obtained, one of the factors being a 24th-degree polynomial. The authors observed on many examples that the cusp points were each time defined by the 24th-degree polynomial, the remaining factors always defining spurious solutions only. However, they did not attempt to certify that the 24th-degree polynomial was really the only valid factor. Moreover, they never found more than 8 cusp points.

The purpose of this paper is to propose a rigorous methodology to determine the cusp points of any 3-RPR manipulator and to certify that all cusp points are found. This methodology uses the notion of discriminant varieties and resorts to Gröbner bases to solve the systems of equations. Using symbolic computation, it is verified that the cusp points are really defined by a 24th-degree polynomial. For any given 3-RPR manipulator geometry, the maximum number of cusp points in sectional sections of the joint space is determined and the results are certified. In particular, a robot with 10 cusp points in a cross section of its joint space is found for the first time.

The following section introduces the manipulators studied and recalls the main known results. Section 3 describes the algebraic tools used. Last section presents the methodology that is proposed to determine the cusp points using the algebraic tools.

2 Modeling and state of the art

Robot studied and Modeling

A general 3-RPR planar parallel manipulator is shown in Figure 1. This manipulator has three extensible leg-rods actuated with prismatic joints. This manipulator can move its moving platform B 1 B 2 B 3 in the plane. The vector of the three leg-rod lengths is L ≡ (ρ 1 , ρ 2 , ρ 3 ) (Figure 1). The geometric parameters of the manipulators are the three sides of the moving platform d 1 , d 2 , d 3 and the position of the base revolute joint centers A 1 , A 2 and A 3 . The reference frame is centered at A 1 and the x-axis passes through A 2 . Thus, Figure 1: The 3-RPR parallel manipulator under study.

A 1 = (0, 0), A 2 = (A 2x , 0) and A 3 = (A 3x , A 3y ). Parameters Position variables Equation constraints MD ρ 1 , ρ 2 , ρ 3 θ 1 , θ 2 , θ 3      ---→ B 1 B 2 = d 1 ---→ B 2 B 3 = d 2 ---→ B 3 B 1 = d 3 GRS ρ 1 , ρ 2 , ρ 3 B 1x , B 1y , α      ---→ A 1 B 1 = ρ 1 ---→ A 2 B 2 = ρ 2 ---→ A 3 B 3 = ρ 3
Table 1: Two models for the 3-RPR manipulator

The position of the moving platform can be expressed by two different sets of variables (see also Table 1):

• MD Model (McAree-Daniel): the 3 angles θ 1 , θ 2 , θ 3 . • GSR Model (Gosselin-Sefriou-Richard): the position coordinates of point B 1 (B 1x , B 1y )
and the platform orientation α, (α x = cos(α), α y = sin(α)).

Each of these sets of variables leads to a different modeling system.

MD Model

The first model was used by MacAree and Daniel in [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF] and has been extensively studied in [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF]. Let θ ≡ (θ 1 , θ 2 , θ 3 ) define the three angles between the leg-rods and the x-axis.

The six parameters (L, θ) define a configuration of the manipulator but only three of them are independent, so that the configuration space is a 3-dimensional manifold embedded in a 6-dimensional space. The dependency between (L, θ) is obtained by writing the constraint equations of the manipulator, namely, the fixed distances between the three vertices of the mobile platform B 1 , B 2 , B 3 :

Γ      Γ 1 (L, θ) = [b 2 (L, θ) -b 1 (L, θ)] T [b 2 (L, θ) -b 1 (L, θ)] -d 2 1 Γ 2 (L, θ) = [b 3 (L, θ) -b 2 (L, θ)] T [b 3 (L, θ) -b 2 (L, θ)] -d 2 2 Γ 3 (L, θ) = [b 1 (L, θ) -b 3 (L, θ)] T [b 1 (L, θ) -b 3 (L, θ)] -d 2 3 (1)
where b i is the vector defining the coordinates of B i in the reference frame as function of L and θ.

GSR Model

The GRS model was introduced in [START_REF] Cm Gosselin | Solutions polynomiales au problème de la cinématique directe des manipulateurs parallèles plans à trois degrés de liberté[END_REF]. This model, combined with appropriate algebraic methods (see Section 3), will allow us to use a full symbolic computation of all cuspidal configurations. In this modeling, point B 1 and angle α are used to specify the pose and the orientation of the platform. Let X ≡ (B 1x , B 1y , α x , α y ), where α x (resp. α y ) denotes cos(α) (resp. sin(α)). Let β x (resp. β y ) denote cos(β) (resp. sin(β)). With these variables, we can parametrize the positions of the three points B 1 , B 2 and B 3 as follows:

b 1 B 1x B 1y b 2 B 1x + d 1 α x B 1y + d 1 α y b 3 B 1x + d 3 (α x β x -α y β y ) B 1y + d 3 (α x β y + α y β x )
The lengths ρ 1 , ρ 2 , ρ 3 define the geometric constraints of the robot, and can be written as the euclidian norm of the vectors

---→ A 1 B 1 , ---→ A 2 B 2 , ---→ A 3 B 3 .
Finally, the dependency between (L, X) can be identified by writing the distances between the vertices of the moving platform and the vertices of the base platform. These distances ρ 1 , ρ 2 , ρ 3 are the norms of the vectors

---→ A 1 B 1 , ---→ A 2 B 2 , ---→ A 3 B 3 :      E 1 (L, X) = [b 1 (L, X) -a 1 ] T [b 1 (L, X) -a 1 ] -ρ 2 1 E 2 (L, X) = [b 2 (L, X) -a 2 ] T [b 2 (L, X) -a 2 ] -ρ 2 2 E 3 (L, X) = [b 3 (L, X) -a 3 ] T [b 3 (L, X) -a 3 ] -ρ 2 3 (2)
where a i is the vector defining the constant coordinates of A i in the reference frame.

The formulas in Equations 2 can be expanded as follows:

E        B 1 2 x + B 1 2 y -ρ 2 1 = 0 (B 1x + d 1 α x -A 2x ) 2 + (B 1y + d 1 α y ) 2 -ρ 2 2 = 0 (B 1x + d 3 α x β x -d 3 α y β y -A 3x ) 2 + (B 1y + d 3 α x β y + d 3 α y β x -A 3y ) 2 -ρ 2 3 = 0 α 2 x + α 2 y -1 = 0 (3)
The last polynomial in E comes from the variable α replaced by the 2 variables α x , α y and the equation constraint α 2

x + α 2 y -1 = 0. This change of variables allows us to avoid the sine and cosine functions and keep the system algebraic. Moreover, this change of variables does not introduce any spurious solutions since the function

[-π, π[ → C θ → (cos(θ), sin(θ))
is bijective on the circle C.

The following subsections recall the main properties of the 3-RPR manipulator observed using the MD Model.

Properties observed

In a special configuration (L, θ), the manipulator meets a singularity, where two assembly modes coalesce. This happens when the constraint Jacobian drops rank. A 3-RPR parallel manipulator is in a singularity whenever the three lines (A i B i ), i = 1..3, are concurrent or parallel [START_REF] Bonev | Singularity analysis of 3-DOF planar parallel mechanisms via screw theory[END_REF].

When three assembly modes coalesce, the manipulator is said to be in a cuspidal configuration. Using series expansion, McAree and Daniel show that in such configurations, the manipulator loses first and second order constraints. This gives a necessary condition for a manipulator to be in a cuspidal configuration (see Table 4).

Based on series expansion, [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF] provided an algorithm to plot the singular curves in sectional slices of the joint space and to calculate the cusp points that appear on these curves. They calculated the cusp points in various sectional slices of the joint space for the manipulator defined by the following geometric parameters:

A 1 = (0, 0) A 2 = (
The following facts were observed in [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF]:

• no more than 8 cusp points were found in a sectional slice defined for a given value of ρ 1 ; this result was also observed in many other manipulator examples;

• the number of cusp points per section stabilizes to four when ρ 1 exceeds a certain value;

• the set of all cusps points defined a set of curves in the 3-dimensional joint space (Fig. 2).

Limitations of the previous study

In [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF], the cusp points were calculated in any sectional slice of the joint space by resorting to complex algebraic calculus based on expansion and elimination procedures. A univariate polynomial of degree 96 was obtained, which was shown to factor into several polynomials, one of which is of degree 24 and was conjectured to be the one that gives all cusp points in the sectional slice at hand. The other factors were found to give always spurious solutions.

The following remarks can be drawn:

• there is no proof that the above mentioned 24-degree polynomial is indeed the only polynomial that gives all solutions;

• the sectional slices were analyzed by a discrete method, and, thus, the analysis was not exhaustive;

• a maximum number of 8 cusps points were found in many manipulator examples, but there is no proof that no more than 8 solutions can be obtained.

• previous equation modeling does not distinguish between a platform triangle and its mirror image (see Figure 3), i.e. a triangle with the same d i but with an angle β of opposite sign.

One limitation of the previous studies came from the algebraic tools used to describe the robot, which introduced spurious components that had to be removed with empirical observations. In the literature, another method exists based on the elimination of variables, reducing the problem to the computation of the triple roots of an univariate polynomial [START_REF] Omri | How to recognize simply a non-singular posture changing 3-dof manipulator[END_REF][START_REF] Corvez | Using computer algebra tools to classify serial manipulators[END_REF][START_REF] Wenger | Classification of 3R positioning manipulators[END_REF]. Unfortunately, due to the size of the univariate polynomial, this method ran out of memory when applied to 3-RPR manipulators [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF].

The following section presents the minimal Discriminant Variety and the Jacobian criterion. These algebraic tools allowed us to compute and describe exactly the cuspidal configurations of the 3-RPR manipulators, without introducing any spurious components.

Algebraic tools

This section recalls some mathematic definitions and their implementation in Maple software. The parametric systems we consider are supposed to have a finite number of complex solutions for almost all parameter values. This property is checked by computing a Gröbner basis of the system at hand (see [16, page 274] and [START_REF] Lazard | Solving parametric polynomial systems[END_REF]Theorem 2] for more details).

Discriminant Variety

A Discriminant Variety V [START_REF] Lazard | Solving parametric polynomial systems[END_REF] is associated to a parametric polynomial system S. One of its main properties is that the real roots of S can be parametrized continuously on each open connected set in the complement of V .

Notations 1

In this section, we denote by S(t 1 , ..., t s ) a polynomial system of the form: p 1 = 0, ..., p m = 0 and q 1 > 0, ..., q k > 0 depending on the s parameters t 1 , ...t s and the n variables x 1 , ..., x n . For more simplicity, (t 1 , ..., t s ) will be omitted in the subsequent sections.

For example, if we want to describe the number of solutions to the direct kinematics problem according to the articular parameters, then:

• the polynomial equations p 1 , ..., p m are equations (3) with the specifications (4)

• the polynomial inequations q 1 > 0, ..., q k > 0 are ρ 1 > 0, ρ 2 > 0, ρ 3 > 0

• the parameters t i are the articular variables ρ 1 , ρ 2 , ρ 3 and the variables x i are the pose variables B 1x , B 1y , α x , α y .

The following definition is adapted from [START_REF] Lazard | Solving parametric polynomial systems[END_REF] for our problem.

Definition 1 (Discriminant Variety)

Let S be any parametric system. With the notation defined above, we call Discriminant Variety of S a set V of parameter values such that on each connected part of R s \ V :

i. the roots of S can be parametrized as continuous functions of the parameters;

ii. the roots of S do not cross.

Moreover, the intersection of all the discriminant varieties is called the minimal discriminant variety and is denoted by DV .

Remark 1 The conditions i. and ii. imply that for every open set in the complement of DV , the number of solutions is constant.

One of the main property of the minimal discriminant variety DV is that if S has finitely solutions for almost all parameter values, then for each connected cell U of R s \ DV , the number of solutions of S restricted to U is constant.

In the problem at hand, the minimal discriminant variety may be split into two components:

-the inequation bounds in the parameters space. As far as a 3-RPR manipulator is considered, these bounds are trivial since the inequations already depend solely on the parameters;

-the projection of the parallel singularities (defined in [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF], see also section 3.3). These values are computed as follows:

1. Compute M 1 , . . . , M ( k n ) as the n × n minors of the Jacobian matrix:

         ∂p 1 ∂x 1 • • • ∂p 1 ∂x n . . . . . . . . . . . . ∂p k ∂x 1 • • • ∂p k ∂x n         
2. Eliminate the variables x 1 , . . . , x n in the system

p 1 = 0, . . . , p k = 0, det(M) 1 = 0, . . . , det(M) ( k n ) = 0
The zero iso-surface of the returned polynomials is the projection of the desired singularities.

Degree of a 0-dimensional system and multiplicity of a root

The interested reader may find more detailed definitions on the degree and multiplicity in [START_REF] Elkadi | Introduction à la résolution des systèmes d'équations algébriques[END_REF] or in [20, chapter 4].

Definition 2 (degree) Given a system S of polynomial equations with finitely many complex solutions, the degree of S is exactly the number of roots counted with multiplicities.

The following unusual definition is exactly the same as the classical one [START_REF] Cox | Using algebraic geometry[END_REF] (dimension of a local ring), the reader will find the correspondence in [START_REF] Rouillier | Solving zero-dimensional systems through the rational univariate representation[END_REF].

Definition 3 (multiplicity) Let S be a system of polynomial equations in x 1 , ..., x n with finitely many complex solutions. Let l : C n → C be a linear form and P (Z) a univariate polynomial returned by the computation of a rational univariate representation [START_REF] Rouillier | Solving zero-dimensional systems through the rational univariate representation[END_REF].

Then P can be written as:

P (Z) = α root of S (Z -l(α)) µα
We call multiplicity of α the exponent µ α .

Remark 2 When S is reduced to a univariate polynomial equation in X with k roots

k i=1 (X -c i ) µ i = 0
then the multiplicity of each root c i is exactly µ i .

By extension, we can also define the multiplicity of the roots of a parametric system.

Definition 4 (multiplicity in a parametric system) Let S(t 1 , ..., t s ) be a parametric system depending on the parameters t 1 , ..., t s and on the variables x 1 ..., x n . Assume furthermore that for all parameter values (t 0 1 , ..., t 0 s ) ∈ C s , the number of complex roots of S(t 0 1 , ..., t 0 s ) is finite. Then, the multiplicity of a root α = (t 0 1 , ..., t 0 s , x 0 1 , ..., x 0 n ) is the multiplicity of the root (x 0 1 , ..., x 0 n ) in the system S(t 0 1 , ..., t 0 s ).

Remark 3 This multiplicity definition can be naturally extended to define the multiplicity of a leaf above a connected component in the complement of the discriminant variety.

Jacobian criterion

We recall here the Jacobian criterion, used in this article to extract the points of multiplicity greater than or equal to 2. More details can be found in [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF]. The Jacobian matrix to be considered here is exactly the same as the one used in [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF] to define the singularities of type 2 of a manipulator. In this article, we will refer to these type-2 singularities as parallel singularities.

Theorem 1 Let p 1 , . . . , p m be parametric polynomials of C[t 1 , ..., t s ][x 1 , . . . , x n ] admitting a finite set of common complex roots for each value of the parameters t 1 , ..., t s . Let J be the Jacobian matrix related to the variables x 1 , ..., x n :

         ∂p 1 ∂x 1 • • • ∂p 1 ∂x n . . . . . . . . . . . . ∂p m ∂x 1 • • • ∂p m ∂x n          If M 1 , . . . , M ( m n
) denotes the n × n minors of J, then for all t 0 = (t 0 1 , ..., t 0 s ) ∈ C s , the following parametric system:

p 1 (t 0 , x 1 , ..., x n ) = 0, . . . , p m (t 0 , x 1 , ..., x n ) = 0 det(M) 1 (t 0 , x 1 , ..., x n ) = 0, . . . , det(M) ( m n ) (t 0 , x 1 , ..., x n ) = 0 has a solution in x 1 , ..., x n if and only if the system p 1 (t 0 , x 1 , ..., x n ) = 0, . . . , p m (t 0 , x 1 , ..., x n ) = 0
has at least one root of multiplicity greater than or equal to 2. This theorem can be used to define singular configurations as in [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF], but also to define the cuspidal configurations, as shown in section 4.2.

Software implementation in Maple

The algebraic tools used in this paper were adapted from the SALSA library developed at INRIA. The manipulations and computations of the algebraic objects are performed with the math software maple. The functions used are described below.

FGb Given a set of polynomials generating an ideal I, fgbrs:-fgb gbasis allows the computation of a system of generators of the ideal. These generators provide a way to reduce any polynomial to a canonical unique form modulo I. With the option ''elim''=true, it makes it possible to compute an algebraic system, the zero of which is the closure of the projection of the roots of I.

This elimination of variables is based on Gröbner basis computations, using the algorithms F4 ( [START_REF] Faugere | A new efficient algorithm for computing Gröbner bases (F4)[END_REF]). As explained in the following sections, this function is used to compute the singular and cuspidal positions, as well as the discriminant variety.

RS A system S of polynomial equations p 1 = 0, . . . , p k = 0 is said 0-dimensional if its number of complex solutions is finite (this can be straightforwardly tested on a Gröbner basis of the system).

In this case, the RootFinding:-Isolate function computes directly the real solutions of S. By default, each solution is given by a box with rational bounds, ensuring that no pairs of boxes overlaps. The algorithms implemented in Maple are based on the Rational Univariate Representation ( [START_REF] Rouillier | Solving zero-dimensional systems through the rational univariate representation[END_REF]).

This function allows us to compute the number of cuspidal positions.

Discriminant Variety Given a parametric system of equations p 1 = 0, . . . , p k = 0 and inequations g 1 = 0, . . . , g r = 0, t 1 , . . . , t s being the parameters and x 1 , . . . , x n the unknowns, its minimal discriminant variety is computed with the algorithm presented in [START_REF] Lazard | Solving parametric polynomial systems[END_REF]. As shown further in section 4.3, the discriminant variety is a key tool for the description of the cuspidal positions.

This function is part of the package RootFinding[Parametric] in maple.

Limitations These functions stand only for polynomials with rational coefficients. In particular, the trigonometric functions sin, cos, tan have to be replaced by algebraic variables.

New modelling and method

In this section and the subsequent ones, we use the equation system and the notations induced by the GSR Model presented in section 2.1.2. In this model, the position of the platform is given by 4 variables: B 1x , B 1y the coordinates of the point B 1 and α x , α y , the cosine and sine of the angle α respectively.

The configurations of a 3-RPR manipulator may be classified into three categories: the regular configurations, the singular configurations and the cuspidal configurations. The description of the special configurations (singular and cuspidal) is important for path planning. First, the regular configurations are the most common ones: these are the configurations where the position of the platform is locally uniquely determined by the values of the control parameters. Then the singular (resp. cuspidal) configurations are two (resp. three) coalesced configurations. These configurations were studied through local analysis in the past, but they can be also described with algebraic methods, as shown further in this article.

Singular configurations

From a geometrical point of view, we saw in Section 2.2 that a singular configuration represents coalesced assembly modes.

From an algebraic point of view, this condition can be retrieved in term of multiplicities. When the variables L is specialized with real numbers, the set of equations ( 3) has finitely many solutions. Moreover, a multiplicity is associated with each solution (see Section 3.2). Using this notion, it can be verified that the singular assembly modes are exactly configurations that are solutions of multiplicity greater than or equal to 2. Indeed, the Jacobian criterion [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF] states directly that these configurations are parallel singularities.

Modelling

To describe the singular points, we use the notion of multiplicity in a 0-dimensional system. The system of equations ( 3) is 0-dimensional when the lengths ρ 1 , ρ 2 , ρ 3 are given: it has a finite number of complex solutions. In this case, each solution can be associated with an integer greater than or equal to 1: its multiplicity, as defined in section 3.2. x , α 0 y ) is a solution of multiplicity greater than or equal to 2 of: E((ρ 0 1 , ρ 0 2 , ρ 0 3 ), X) = 0 0 0 0 T To find the singular configurations, we use the Jacobian criterion, reminded in section 3.

Applying the Jacobian criterion [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF] on the polynomial system Equations (3), we deduce that the singular configurations are exactly the solutions of the system:

     E(L, X) = 0 0 0 0 T det( ∂E ∂X ) = 0 (5)
Remark 4 By adding the determinant of the Jacobian matrix to Equations ( 3), we get a new system whose solutions are included in the original system. More precisely, the roots of Equations ( 5) are exactly the roots of multiplicity greater or equal to 2 of Equations [START_REF] Borrel | A study of multiple manipulator inverse kinematic solutions with applications to trajectory planning and workspace determination[END_REF]. The solutions to Equations ( 3) of multiplicity 2 are solutions of multiplicity 1 to Equations ( 5), and the solutions of multiplicity greater or equal to 3 in Equations ( 3) have a multiplicity greater or equal to 2 in Equations ( 5).

Moreover, using Gröbner basis computations to eliminate variables with Maple , a polynomial in the parametric variables L, denoted P sing , can be computed. Its solutions are exactly the sets of length values for which the manipulator admits singular configurations.

Example

In this section, the computation results are given for the manipulator example presented in [START_REF] Innocenti | Singularity-free evolution from one configuration to another in serial and fully-parallel manipulators[END_REF][START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF][START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF][START_REF] Merlet | Parallel Robots[END_REF].

Once substituting the numerical values of Equations ( 4) into Equations ( 5), a system is obtained, the solutions of which are exactly the singular configurations of the studied manipulator. After eliminating the variables X with Gröbner bases computation, a polynomial P sing in L is obtained of total degree 24. The zeros of this polynomial define a surface in the parameter space. By specifying ρ 1 = 14.98 as in [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF][START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF], the curve as in [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF][START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF] can be observed in Figure 4.

Cuspidal configurations

Cuspidal configurations are associated with second-order degeneracies that appear for triply coalesced configurations. As shown in [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF][START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF], these configurations play an important role in path planning.

To find cuspidal configurations, the idea of [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF][START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF] was to analyze the kernels of the matrices in the first and second order terms of the series expansion of Equations [START_REF] Gosselin | The direct kinematics of planar parallel manipulators: Special architectures and number of solutions[END_REF]. It allowed the authors to find the cuspidal configurations automatically when ρ 1 is specified as a numerical value. However the description they get is a list of slices of the cuspidal configurations, and they miss what could happen between 2 successive slices. Using the notion of discriminant variety and a generalization of the Jacobian criterion, we introduce a complete certified description of the cuspidal configurations. In particular, our approach allows us to find cuspidal configurations that were missed in the previous papers, and to certify that all cuspidal configuration are determined.

Modelling

Like for the singular points, we define the cuspidal configurations algebraically. .

Definition 6 The configuration

P 0 = (ρ 0 1 , ρ 0 2 , ρ 0 3 , B 1 0 x , B 1 0 y , α 0 x , α 0 y ) of the 3-RPR manipulator is said cuspidal if and only if (B 1 0 x , B 1 0 y , α 0 x , α 0 y ) is a solution of multiplicity 3 to E((ρ 0 1 , ρ 0 2 , ρ 0
In Section 4.1, the Jacobian criterion allowed us to select the configurations of multiplicity higher than or equal to 2. However, we now want to compute the configurations of multiplicity 3. Fortunately, we saw in Remark 4 that these configurations were the roots of multiplicity 2 of Equations [START_REF] Innocenti | Singularity-free evolution from one configuration to another in serial and fully-parallel manipulators[END_REF]. We can thus use the Jacobian criterion on Equations ( 5) to get a system whose roots of multiplicity 1 describe exactly the cuspidal configurations.

Let det(J) = det( ∂E ∂X ) and let M 1 , M 2 , M 3 , M 4 , M 5 be the 4 × 4 minors of the Jacobian matrix of the 5 polynomials E 1 , E 2 , E 3 , E 4 , det(J) with respect to the variables X. Then the following system of 9 equations defines exactly the cuspidal configurations of the 3-RPR manipulator:

                                               E(L, X) = [ 0 0 0 0 ] T det(J) = det(M) 1 = 0 det(M) 2 = det ∂E 1 ∂X ∂E 2 ∂X ∂E 3 ∂X ∂ det(J) ∂X = 0 det(M) 3 = det ∂E 1 ∂X ∂E 2 ∂X ∂E 4 ∂X ∂ det(J) ∂X = 0 det(M) 4 = det ∂E 1 ∂X ∂E 3 ∂X ∂E 4 ∂X ∂ det(J) ∂X = 0 det(M) 5 = det ∂E 2 ∂X ∂E 3 ∂X ∂E 4 ∂X ∂ det(J) ∂X = 0 (6)
Remark 5 These equations are algebraically dependent. In particular, even if the number of equations is 9 and the number of variables is 7, the set of solutions is a curve of dimension

1 in R 7 .
System (6) contains equations of degree smaller than 5. This will allow us to compute a certified description of the cuspidal curves in Section 4.3.

Example

For the robot example defined by Equations ( 4), triple points are exactly the solutions of Equations ( 6). Moreover, when ρ 1 is specified, Equations ( 6) has finitely many solutions. Using the methods of real solving for 0-dimensional systems of the function Isolate of Maple, one can find easily the roots of Equations ( 6) for any given ρ 1 .

The system defined by Equations ( 6) has 9 equations:

• the first four equations are the geometric model equations, each being of degree 2; • the 5th equation is the Jacobian of these equations and has degree 3;

ρ
• the last four equations are obtained through the iteration of the Jacobian computation, each one is of degree 5..

The full equations can be found at the address http://www.irccyn.ec-nantes.fr/ ~chablat/3RPR_cuspidal.html.

In particular, for ρ 1 = 14.98, we get 6 triple points (see Table 2), which confirms the results of [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF].

Moreover, in [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF], the authors have shown that for different numerical values of ρ 1 , among different spurious factors, it is possible to extract a univariate polynomial in t 1 := tan(θ 1 ) of degree24.

Using our cusp modeling, if we add the new variable t 1 = tan(θ 1 ) = B 1y /B 1x and eliminate the variables ρ 2 , ρ 3 , B 1x , B 1y α x , α y from Equations 6 with Gröbner basis computation, we can compute (in 9 seconds) a bivariate polynomial Q in ρ 1 and t 1 . The real roots defined by Q is the closure of the projection of the cuspidal configurations. We can see that Q is irreducible and has a degree 24 in t 1 . In particular, by substituting a numerical value of ρ 1 in Q, we get directly a univariate polynomial of degree 24 in t 1 . This generalizes and certifies the results in [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF].

Cusps analysis

Equations ( 6) define implicitely the cuspidal configurations of the robot. Without further computations, these equations are not sufficient to describe the geometry of the triple roots of the 3-RPR manipulator. In [START_REF] Mcaree | An explanation of never-special assembly changing motions for 3-3 parallel manipulators[END_REF][START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF], the authors observed that the set of cuspidal configurations is finite in slices of the robot joint space for given values of ρ 1 . This leads to the conjecture that the set of cuspidal configurations forms a curve in the full joint space (ρ 1 , ρ 2 , ρ 3 ). Furthermore, the authors of [START_REF] Zein | Singular curves in the joint space and cusp points of 3-rpr parallel manipulators[END_REF] described the number of cuspidal configurations for discrete values of ρ 1 in R. This allowed them to find configurations that were omitted in previous works.

In this section, we give a certified and exhaustive description of the number of cuspidal configurations as function of ρ 1 . In particular, this study allows us to find values of ρ 1 , for which the 3-RPR manipulator has 10 cuspidal configurations, while previous works never observed more than 8 cuspidal configurations. This gives new possibilities to change assembly mode without crossing singularities. More generally, our method compute the number of cuspidal configurations for all the values of ρ 1 in open intervals, and not only slices.

The dimension of the set of solutions of Equations 6 in the complex field is 1. This can be verified by computing and analyzing the Gröbner bases of Equations 6 (see [25, chapter 9] for more details).

To describe geometrically the solutions of Equations 6 as function of ρ 1 , we consider it as a parametric system where:

• the single parameter is ρ 1

• the unknowns are ρ 2 , ρ 3 , B 1x , B 1y , α x , α y First, using [16, page[341], we can check that for almost all values of ρ 1 , the roots of Equations 6 have multiplicity 1 and are thus corresponding exacty to cuspidal configurations.

Then we follow the work of [START_REF] Lazard | Solving parametric polynomial systems[END_REF][START_REF] Corvez | Using computer algebra tools to classify serial manipulators[END_REF][START_REF] Faugère | Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities[END_REF] to describe the roots of a parametric system. Our process has 2 steps:

• we first compute its minimal discriminant variety.

• we then compute the number of solutions for sample parameter's values chosen outside the discriminant variety

Discriminant variety of the cuspidal configurations

We consider Equations 6 as a system parametrized with ρ 1 . In this case, its minimal discriminant variety is a finite set of values of ρ 1 denoted by:

DV = {a 1 , . . . , a k } ⊂ R, k > 0
The main property of the discriminant variety is that for each value of ρ 1 in an interval ]a i , a i+1 [, the Equations 6 has the same number of distinct real solutions.

The points of the discriminant varieties are the real roots of univariate polynomials. The lines ρ 1 of table 3 show numerical approximations of these roots. The full univariate polynomials are not given here for lack of space. They can be found at the address http: //www.irccyn.ec-nantes.fr/ ~chablat/3RPR_cuspidal.html. They were computed in 11 seconds with a 2.9GHz Intel cpu.

The lines #Cusp gives the number of cuspidal configurations for ρ 1 in an interval ]a i , a i+1 [, where the a i are the real values of ρ 1 defining the discriminant variety DV .

Number of cuspidal configurations

Using the main property of the discriminant variety, we know that to count the number of cuspidal configurations outside the discriminant variety, it is sufficient to compute a finite set ]a i , a i+1 [, such that a i , a i+1 are consecutive reals of DV and compute the number of solutions to Equations 6 when ρ 1 = v i . Moreover, we choose a value v k+1 in ]a k , +∞[, and count the number of solutions of Equations 6 when ρ 1 = v k+1 . The results of these computations are summarized in the lines #Cusp of Table 3. To count the number of real solutions of Equations 6 when ρ 1 = v i , we use the real solver given by RootFinding:-Isolate in Maple. It took around 5 minutes to solve the systems induced by each of the 23 sample points with a 2.9GHz Intel cpu.

From Table 3 we conclude that, asymptotically, the manipulator has 4 cuspidal configurations, and that this number is stable as soon as ρ 1 is greater than 31. Moreover, we can observe that the robot may have up to 10 cuspidal configurations when ρ 1 is in the interval ]28.095, 28.107[. Figure 5 shows the singular curve of the parallel robot for ρ 1 = 28.10 and the corresponding 10 cuspidal configurations.

Conclusion

This paper shows that efficient algebraic tools can be applied to analyse in a certified way important kinematic features of parallel manipulators such as the determination of cusp points. These points are known to play an important role in planning non-singular assembly mode changing motions.

A new method was introduced, which is able to characterize all the cusp points for the 3-RPR manipulators. It allowed us to determine the number of cusp points for all the slices of the joint space. For the first time, a section for a given ρ 1 was found with 10 cusp points.

Table 4 summarizes the method used in this article and relates it to the 2 previous main methods to compute cuspidal configurations in the literature.

This results can be computed with a toolbox available now in Maple 12 and later versions [START_REF] Liang | A Package for Solving Parametric Polynomial Systems[END_REF]. Discriminant Variety of (C) Table 4: The two main methods and one original methods for singular and cuspidal configurations characterization. Only the jacobian method allowed us to describe completely the cuspidal configurations.

Original

  15.91, 0) A 3 = (0, 10) d 1 = 17.04 d 2 = 16.54 d 3 = 20.84

Figure 2 : 9 Figure 3 :

 293 Figure 2: Joint space singularity surfaces of the 3-RPR manipulator studied when ρ 1 varies from 0 to 5 [11].

Definition 5 A

 5 configuration P 0 = (ρ 0 y ) of the 3-RPR manipulator is said singular if and only if (

14 Figure 4 :

 144 Figure 4: Singular curve for ρ 1 = 14.98

p 1 ( 1 ∂x 1 • • • ∂p 1 ∂xn

 1111 L, x 1 , ..., x n ) = 0 . . . p n (L, x 1 , ..., x n ) = 0 MD Model: parameters: L unknowns: x 1 , ..., x 3 := θ 1 , θ 2 , θ 3 Model GRS: parameters: L unknowns: x 1 , ..., x 4 := B 1x , B 1y , α x , α y Method p 0 (ρ 1 , ..., ρ s , x 1 )

Figure 5 :

 5 Figure 5: Singular curve for ρ 1 = 28.10. The circles show the 10 cuspidal configurations in this configuration.

Table 2 :

 2 The 6 cuspidal configurations (roots of Equations 6) for ρ 1 = 14.98

	2	ρ 3	B 1x	B 1y	α x	α y
	1 0.845 3.777	5.336 -13.997 0.633 0.773
	2 13.851 6.260 -14.963 0.698	0.998 -0.045
	3 31.276 16.178 -6.104 13.679 -0.543 -0.839
	4 17.988 26.446 14.721 -2.769 -0.985 0.167
	5 30.449 26.619 -10.363 10.816	.537	0.843
	6 16.027 29.566 14.437	3.995	0.999 -0.010

Table 3 :

 3 Discriminant variety of the cuspidal configurations (Equations 6) w.r.t. ρ 1 ; the numerical values were truncated of sampling points in the complement of DV and to solve the corresponding zero-dimensional systems. More precisely, we choose a value v i in each interval:

	#Cusp	0	2	4	2
	ρ 1	0.000 ]--[ 0.148 ]--[ 1.655 ]--[ 1.660 ]--[
	#Cusp	4	6	8	6
	ρ 1	2.261 ]--[ 2.975 ]--[ 9.186 ]--[ 9.186 * ]--[
	#Cusp	8	6	8	6
	ρ 1 9.257 ]--[ 9.257 #Cusp 8	6	8	6
	ρ 1	14.579]--[14.579 * ]--[20.555]--[ 20.562 ]--[
	#Cusp	8	10	8	6
	ρ 1	26.786]--[ 28.094 ]--[28.107]--[ 28.257 ]--[
	#Cusp	8	6	4
	ρ 1	30.740]--[ 30.779 ]--[30.946]--------

* ]--[10.905]--[10.905 * ]--[ * these values are close but distinct, the closest values differ by at least 10 -11 .

Acknowledgement

We would like to thank the reviewers for their useful remarks, which we have all taken into account.